运筹学__五章(整数规划).ppt

1、浙江科技大学经济与管理学院管理科学与工程系运筹学，2020年8月4日，浙江科技大学经济与管理学院管理工程系，2，第5章整数规划，5.1整数规划数学模型，5.2截平面法和分枝定界法5.3 0-1整数规划5.4隐式枚举法5.5匈牙利法，2020年8月4日，浙江科技大学经济与管理学院， 管理工程系学习本章要求，熟悉分枝定界法和截平面法的原理和应用，掌握求解0-1规划问题的隐式枚举法，掌握求解指派问题的匈牙利法，2020年8月4日，浙江科技大学经济管理学院管理系，4，5.1整数规划的数学模型和解法特点，整数规划的数学模型实例，整数规划解法的特点，2020年8月4日，浙江科技大学经济管理学院管理系，5，

2、 整数线性规划(ILP)类型，纯ILP: Xj为整数混合ILP: XJ部分为整数0-1 ILP: XJ为0或1，2020/8/4，浙江科技大学经济管理学院管理系，6，线性规划模型maxz=x14x 2s . t . 14x 1 42x 2196-x12x 25x 1，x20，整数规划模型maxz=x14x 2s . t . 14x 1 42x 2196-x12x 25x 1整数线性规划的一个例子，浙江科技大学经济管理学院管理工程系，2020/8/4，7。线性规划A(x1，x2)=(2.6，3.8)的最优解不是整数解，目标函数值为z=17.8。整数规划的最优解是B(x1，x2)=(5，3)，目标

3、函数值是z=17。线性规划的最优解A(2.6，3.8)被舍入到解(3，4)，这不是可行解；尾数舍入的解是(2，3)，目标函数值是z=14。因此，整数规划的最优解不能简单地通过取整线性规划的最优解来获得。2020年8月4日，浙江科技大学经济管理学院管理系，8，3。线性规划解的特征，线性规划是线性规划的一个子问题，所有解都是线性规划的可行解，所以如果线性规划的最优解满足线性规划的整数条件，那么就得到最优解。2020年8月4日，浙江科技大学经济管理学院管道工程系，9月5.2，切平面法和分枝定界法，2020年8月4日，浙江科技大学经济管理学院管道工程系，10，1。切割平面法，基本原理：根据单纯形法得到

4、其松弛问题的最优解，然后从最优解中选择真实分数最大的一行构造切割平面约束，并将其加入到原松弛问题中形成新的线性规划解，逐步缩小解的范围而不去除整数解，直到找到整数解为止。2020年8月4日，浙江科技大学经济管理学院管道工程系，11，1。切割平面法，切割平面束构造：让真分数最大的非整数部分的行为为：并将约束方程的系数和常数分解为整数N和正真分数F的和，即，约束方程等价于：2020年8月4日，浙江科技大学。1，0，0，3，5，x1进x3出，6，8/3，x2进x4出，从右边的结果构造切割平面束，2020年8月4日，浙江科技大学经济管理学院管道工程系，13(续):从上面的结果构造切割平面束，2020年

5、8月8日，如果线性规划的最优解碰巧是整数解，那么这个解就是整数规划的最优解。如果线性规划的最优解中至少有一个变量不是整数，则线性规划的可行域被分成两部分，分别求解两个线性规划的最优解。如果这两个线性规划的最优解不是整数解，则划分每个可行域如果松弛问题有一个最优解并且满足迭代学习过程的整数条件，那么这个最优解就是迭代学习过程的最优解，所以停止计算。松弛问题有一个最优解，但它不满足迭代学习过程的整数条件，所以它的目标函数值为；用观察的方法找到迭代学习过程的整数可行解，并得到其目标函数值，将其写成，如果Z*是迭代学习过程的最优目标函数值，那么它将分支。如果松弛问题有一个非整数值bj的最优解xj，那么

6、可以构造两个分支。Xjbj xjbj 1被定界，并且每个后续问题被作为一个分支来显示解决结果。2020/8/4，浙江科技大学经济与管理学院管理系，16、(11/4，9/4)，Z=31/4，(3，3/2)，Z=15/2，(2，2 X22，(19/6，1)，z=22/3，(3，1)，z=7、(19/6，1)，x13，x14，2020/8/4，浙江大学经济与管理学院管理系每件物品的重量和价格如下：每件物品有多少件装在背包里，这样背包里物品的总价值最高。2020年8月4日，浙江科技大学经济管理学院管理系，19。三个项目的个数分别为x1、x2和x3，其总值为z。最大z=17 x1 72 x2 35 x3

7、 s . t . 10x 141 x2 20 x350 x1x 2、x2、x30 x1、x2和x3为整数，这是一个整数规划问题。该问题的最优解如下：x1=1块，x2=0块，x3=2块，最高值z=87元，2020年8月4日，浙江科技大学经济管理学院管理系，20，2。选址模型，从5个备选场地中选择3个生产相同产品的工厂，每个场地建一个工厂和占用耕地所需的投资，建成后的生产能力如下：总投资不超过800万元，占用耕地不超过60亩。如何选择工厂地点以最大化总生产能力。包含五个01变量x1，x2，x3，x4，x5，2020年8月4日，浙江科技大学经济与管理学院管理系，21，最大z=70 x1 55 x2

8、42 x3 28 x4 11 X5 s . t . 320 x1 280 x2 240 x3 210 x4 180 x5800 20 x1 18 x2 15 x3 11 x4 8x 5 60 x1 x2 x3 x4 X5=3 x1，x2，x3，x4，X5 is 最大z=140，也就是说，将在位置1、3和4建造三个工厂，最大总生产能力为140万吨。2020年8月4日，浙江科技大学经济管理学院管理系，22，3。多重决策问题，一个工厂用三种设备生产五种产品，三种设备的能力(小时)，生产每种产品所需的各种设备的能力(小时/件)和五种产品的利润(元/件)如下：生产总利润最大化，2020年8月4日，浙江科

9、技大学经济管理学院管理系，23， 最大z=24x 1 18 x2 21 x3 17 x4 22 x5 s . t . 5.0 x1 1.0 x2 3.0 x3 2.0 x4 4.0 X5 180 3.0 x2 4.0 x3 1.0 x4 5.0 x 52500 3.0 x1 2.0 x2 1.0 x3 3.0 x4 2.0 x 52200 x1，x2，x3，x4，x50 x1，x2，x3，x4，X5为整数。 让我们假设五种产品的输出具有以下逻辑关系：在五种产品中，最多只能生产三种产品。如果安排生产，最小批量为50件。如果产品1被安排用于生产，则产品2不能被生产。如果生产产品4，则必须生产产品5

10、，并且必须生产具有五个变量y1和y2的至少50件产品。Y3，y4，Y5，2020年8月4日，浙江科技大学经济与管理学院管理系，24，最大z=24 x1 18 x2 21 x3 17 x4 22 X5 s . t . 5.0 x1 1.0 x2 3.0 x3 2.0 x4 4.0 X5 180 3.0 x2 4.0 x3 1.0 x4 5.0 x52500 3.0 x1 2.0 x2 1.0 x3 3.0 x4 2.0 x52200Y3、y4和y5是01的变量，只生产五种产品中的三种，最小批量为50。如果安排生产产品1，则不能生产产品2，必须生产产品4，并且必须生产产品5。2020/8/4，浙江

11、科技大学经济管理学院管理系，25，4。固定成本问题，即如果不生产产品，就不会产生成本。如果生产这种产品，产量将翻一番，成本将翻一番。这种成本被称为可变成本。在实际问题中，除了可变成本，还有固定成本。如果产品不生产，固定成本为0；如果生产产品，固定成本是一个常数，与产品产量无关。固定成本最小化目标函数的表达式为，最小化目标函数的一般表达式为，2020/8/4，浙江科技大学经济管理学院管理系，26，N种设备，J种设备产量为xj，设备运行可变成本为cj，设备启动固定成本为dj。引入0-1变量y1、y2、yn、yj=0表示不生产设备j，yj=1表示生产设备j。考虑到可变成本和固定成本，总成本最小化的目

12、标函数是设备启动和输出之间的逻辑关系。xjMyj由以下约束表示，其中m是一个足够大的正数。2020/8/4，浙江科技大学经济与管理学院管道工程系，27，针对固定成本下的最小生产成本问题，焦化厂使用原煤作为原料生产焦炭，同时获得焦炉煤气和煤焦油。有四个不同生产能力的焦炉，相关数据如下：焦炭产量要求不低于280吨，煤气产量不低于10000m3，煤焦油产量不低于60吨，因此应制定总成本最低的生产计划。2020年8月4日，浙江科技大学经济管理学院管理系，28，不计固定成本。最小化可变成本z=85 x1 81 x2 78 x3 76 x4 s . t . 0.64 x1 0.68 x2 0.71 x3

13、0.73 x4 280 23 x1 25 x2 27 x3 28 x4 10000 0 0.12 x1 0.15 x2 0.17 x3 0.19 x4 60 x1，x2，x3，x40的最佳解决方案是：x1=x2=0，x3=137.32，x4=250，最大z=29711考虑可变成本和固定成本，总成本最小化。最小z=85 x1 81 x2 78 x3 76 x4 400 y1 1200 y1 2600 y3 3100 y4 s . t . 0.64 x1 0.68 x2 0.71 x3 0.73 x4 280 23 x1 25 x2 27 x3 28 x4 10000 0 0.12 x1 0.15

14、 x2 0.17 x3 0.19 x460 x1 100 y1 x2150 y2 x3200 y3 x4 2250 y4 x1变量的最优解如下：y1=0，y2=1，y3=0，y4=1 x1=0，x2=143.38，浙江科技大学经济管理学院管理工程系，30，5.4隐式枚举法，以基本原理为例，2020年8月4日，浙江科技大学经济管理学院管理工程系，31，1。基本原理，枚举法3360检查变量值为0或1的每个组合，并比较目标函数值以获得最佳解。隐式枚举法：通过只检查变量值组合的一部分来寻找问题最优解的方法。步骤：如果最大化问题得到解决，根据目标函数中值系数Cj的递增顺序，重新排序目标函数中的变量和约束

15、不等式，找到可行解，并将目标函数值确定为滤波值。检查变量的组合。如果此时Z低于过滤器值，不要考虑它，继续下一个组合。如果此时它优于过滤器值，请逐个检查是否满足约束条件。如果一个不满意，该组合是不可行的解决方案，并进行下一个组合；如果满足所有约束条件，将生成一个新的过滤器值，并继续下一个组合。2020/8/4，浙江科技大学经济管理学院管理系，32，示例：5，3，8，标准分配问题，有n个任务要由n个人来完成，并且已知第一个人做第j件事的成本是Cij，从而找到最佳的任务分配方案并使总成本最小。2020/8/4，浙江科技大学经济管理学院管理系，35，2。匈牙利方法步骤，将分配问题转化为最小化问题找到最优解，即在n个不同的