运筹学基础及应用第五版胡运权第四章解决方案.ppt

图示割平面 最优解为（4 , 1）这时 z*= 14。 (1) (2) 步骤： ① 化标准形(隐枚举法)：1) 目标函数极小化 2) 约束条件化成? 3) 使目标函数系数皆为非负, 若xj系数为负值, 则令xj=1-xj? 4) 使目标函数按变量系数由小→大顺序排列，约束条件变 量排列的顺序要与之对应。 ② 令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。 ③ 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。 ④ 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) zmin分枝，剪掉； (c) 能判断出为无可行解的分枝，剪掉； (d) 非上述情况，继续分枝。 §5．解0-1规划问题的隐枚举法 例：求解下述 0-1规划问题： Max z=8x1+2x2-4x3-7x4-5x5 st. 3x1+3x2+x3+2x4+3x5 ?4 5x1+3x2- 2x3 - x4+ x5 ?4 xj=0或1 (j=1,2,3,4,5) 1) 目标函数极小化: min z?=-8x1-2x2+4x3+7x4+5x5 ① 化标准形： 2) 约束条件?： -3x1-3x2-x3-2x4-3x5 ?-4 -5x1-3x2+ 2x3 + x4- x5 ?-4 xj=0或1 (j=1,2,3,4,5) 3) 使目标函数系数皆为正： 令 x1=1-x1? ，x2=1-x2? min z?=-8+8 x1? -2+2 x2? +4x3+7x4+5x5 st. -3+3 x1? -3+3 x2? -x3-2x4-3x5 ?-4 -5+5 x1? -3+3 x2? + 2x3 + x4- x5 ?-4 x1? , x2? ,xj=0或1 (j=3,4,5) 4) 变量按顺序排列： min z?= 2 x2? +4x3 +5x5 +7x4+8 x1? -10 st. 3 x2? -x3 -3x5 -2x4 +3 x1? ?2 3 x2? + 2x3 - x5 + x4+5 x1? ?4 x1? , x2? ,xj=0或1 (j=3,4,5) 求解图示： 1 2 3 4 5 6 7 8 9 10 11 z?=-10 z? =-8 z?=-4 z?=-6 z?=-5 z?=-1 z?=1 z?=-5 z?=-3 z?=-6 x2?=1 x2?=0 x3=1 x3=0 x3=1 x3=0 x5=1 x5=0 x5=1 x5=0 z?=-3 √ × × × × × min z?= 2 x2? +4x3 +5x5 +7x4+8 x1? -10 st. 3 x2? -x3 -3x5 -2x4 +3 x1? ?2 3 x2? + 2x3 - x5 + x4+5 x1? ?4 x1? , x2? ,xj=0或1 (j=3,4,5) 第四章 整数规划与分配问题 §1．整数规划的特点及作用 § 2．分配问题与匈牙利法 § 3．分枝定界法 § 4．割平面法 § 5．解0-1规划问题的隐枚举法 §1．整数规划的特点及应用 在实际问题中，全部或部分变量的取值必须是整数。比如人或机器是不可分割的，选择建厂地点可以设置逻辑变量等。 在一个线性规划问题中要求全部变量取整数值的，称纯整数线性规划或简称纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。 对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解，我们从下面的例子说明这样的方法是不合适的。 例1. 求下述整数规划问题的最优解 解：如果不考虑整数约束（称为整数规划问题的松弛问题）用图解法得最优解为（3.25 , 2.5） 考虑到整数约束，用凑整法求解时，比较四个点（4 , 3）,（4 , 2）,（3 , 3）（3 , 2），前三个都不是可行解，第四个虽然是可行解，但 z=13 不是最优。实际问题的最优解为（4 , 1）这时 z*= 14。 逻辑（0-1）变量在建立数学模型中的作用 1. m 个约束条件中只有 k 个起作用 设 m 个约束条件可以表示为： 定义逻辑变量 又设 M 为任意大的正数，则约束条件可以改写为：