第四章数学规划方法建模.ppt

第3章 数学规划方法建模 第3章 数学规划方法建模 可行解：满足约束条件的解。 最优解：使目标函数达到最优的可行解。 最优值：最优解对应的目标函数值。 数学规划问题在19世纪30年代产生，但在20世纪30年代才对线性规划提出有效的求解算法。 常用软件：Lingo（美国Lindo系统公司研发） MATLAB相关软件包 体育馆建设问题 示例3 蔗糖加工问题 在澳大利亚，甘蔗的收割已经实现了高度机械化。甘蔗在砍下之后将马上通过运行于小型铁路网上的货车运送到蔗糖厂。一辆货车的运量能够生产的蔗糖量取决于甘蔗收购的地点以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量由于发酵而迅速下降，一段时间之后，所含糖份将完全流失。现在有11辆货车到达了蔗糖厂，每辆货车运载的甘蔗量都相同。对每辆货车每小时的损失量以及剩余时间测量的数据见下表： 在蔗糖厂有三条生产线，每辆货车都可以选择在哪条生产线上进行加工。一车甘蔗的加工时间为两个小时。必须在这车甘蔗的质量寿命结束之前完成加工。蔗糖厂的经理希望找出一个生产计划，使总的蔗糖损失降到最低。 示例 选课策略 某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、所属类别和先修课要求如表1所示。那么，毕业时学生最少可以学习这些课程中的哪些中的哪些课程。 表 1 运筹学专业的课程属性表 模型与结果： 例6 饮料厂的生产与检修计划 模型与结果： 模型与结果： 3.2 整数规划方法建模 3.2.3 整数规划方法建模示例 示例1 指派问题 有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作E、J、G、R．现有甲、乙、丙、丁、戊五人，他们将中文说明书翻译成不同语种的说明书所需的时间见表3-15．请从这五人中指派四人完成这项工作，使得所需的总时间最少． 3.2 整数规划方法建模 表3-15 各人对每项任务所需时间表 4 15 13 9 7 13 14 16 11 12 15 4 14 8 6 2 10 9 7 5 甲 乙 丙 丁 戊 R G J E 语种 定义0-1变量xij(i=1,…，5；j=1,2,3,4)，xij=1表示第i个人翻译第j个语种，否则记为0；记 tij=1表示第i个人翻译第j个语种花费的时间。 3.2 整数规划方法建模 建立指派问题的数学模型如下： 问题的最优解为: ，其余变量为0，最优值为24，即甲翻译俄文，乙翻译日文，丁翻译德文，戊翻译英文所需的总时间最少，为24小时． 剩余时间 8 8 2 8 4 8 8 8 8 8 8 损失率（千克/小时）43 26 37 28 13 54 62 49 19 28 30 货车编号 1 2 3 4 5 6 7 8 9 10 11 3.2 整数规划方法建模 定义0-1变量xit(i=1,…，11；t=1,2,3,4)，xit=1表示第i辆货车的甘蔗在第t个时间段加工，否则记为0； 记li，si表示第i辆货车甘蔗的 损失率和剩余时间。 3.2 整数规划方法建模 问题的最优解为: ,其余变量 为0，各个货车蔗糖的损失量(单位：千克)分别为：172，208，74，168，52，108，124，196，152，168，180，蔗糖的最小总损失量为1602（千克）．于是得问题的最优加工方案见表3-18． 表3-18 最优加工方案表 货车3 货车1 货车4 货车2 货车6 货车5 货车10 货车9 货车7 货车8 货车11 时间段1 时间段2 时间段3 时间段4 3.2 整数规划方法建模 2.简单蕴含式 比如“如果选择项目A，则必须也选择项目B”： 再如“如果选择项目A，则不能选择项目B”： 再如“如果不选择项目A，则必须选择项目B”： 3.2 整数规划方法建模