大学精品课件：第六章 整数规划（1-2节）.ppt

1、第第1页页第第2页页第第3页页在线性规划问题中，有些最优解可能是分数或小数，在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的但对于某些具体问题，常有要求解答必须是整数的情况。情况。第第4页页要求一部分或全部决策变量必须取整数值的线性规要求一部分或全部决策变量必须取整数值的线性规划问题称为整数线性规划（划问题称为整数线性规划（Integer linear Programming，简称，简称IP）。）。第第5页页整数线性规划数学模型的一般形式为：整数线性规划数学模型的一般形式为：中中部部分分或或全全部部取取整整数数，或或或或njinjjijnjjjxxnj

2、xmibxaxcz,.,.,1,0,.,1,)(min)max(111第第6页页整数线性规划问题可以分为下列几种类型：整数线性规划问题可以分为下列几种类型：1.纯整数（全整数）线性规划（纯整数（全整数）线性规划（pure integer linear programming）：指全部决策变量都必须取整数值的）：指全部决策变量都必须取整数值的整数线性规划。整数线性规划。第第7页页2.混合整数线性规划（混合整数线性规划（mixed integer linear programming）：指决策变量中有一部分必须取整数）：指决策变量中有一部分必须取整数值，另一部份可以不取整数值的整数线性规划。值，另

3、一部份可以不取整数值的整数线性规划。3.0-1型整数线性规划（型整数线性规划（zero-one integer linear programming）：指决策变量只能取值）：指决策变量只能取值 0 或或 1 的整数的整数线性规划。线性规划。第第8页页松弛问题（松弛问题（slack problem）：不考虑整数条件，由）：不考虑整数条件，由余下的目标函数和约束条件构成的线性规划问题称余下的目标函数和约束条件构成的线性规划问题称为该整数规划问题的松弛问题（为该整数规划问题的松弛问题（slack problem）。）。第第9页页 中中部部分分或或全全部部取取整整数数，或或或或njinjjijnjjj

4、xxnjxmibxaxcz,.,.,1,0,.,1,)(min)max(111 njxmibxaxczjinjjijnjjj,.,1,0,.,1,)(min)max(11，或或或或整数线性规划整数线性规划松弛问题松弛问题第第10页页max z=2x1+3x2 且且均均为为整整数数0,12 4 16 482 .212121xxxxxxtsmax z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts整数规划整数规划松弛问题松弛问题第第11页页1.整数线性规划的可行解集合是其松弛问题可行解整数线性规划的可行解集合是其松弛问题可行解集合的一个子集，即：集合的一个子集，即：整数

5、规划可行域整数规划可行域松弛问题可行域松弛问题可行域第第12页页整数线性规划的可行解集合整数线性规划的可行解集合 其松弛问题可行解集合其松弛问题可行解集合从而可得出：从而可得出：|整数线性规划的可行解整数线性规划的可行解一定一定也是其松弛问题的可行也是其松弛问题的可行解。解。|松弛问题的可行解松弛问题的可行解不一定不一定是整数线性规划的可行解。是整数线性规划的可行解。|整数线性规划最优解的目标函数值整数线性规划最优解的目标函数值 松弛问题最优松弛问题最优解的目标函数值（极大化问题）。解的目标函数值（极大化问题）。第第13页页2.松弛问题的可行解集合：凸集（任意两个可行解松弛问题的可行解集合：凸

6、集（任意两个可行解的凸组合仍为可行解）的凸组合仍为可行解）整数线性规划的可行解集合：不是凸集（任意两个整数线性规划的可行解集合：不是凸集（任意两个可行解的凸组合不一定满足整数要求，因而不一定可行解的凸组合不一定满足整数要求，因而不一定仍为可行解）。仍为可行解）。第第14页页产生问题：利用对松弛问题的最优解中不符合整产生问题：利用对松弛问题的最优解中不符合整数要求的分量简单地取整，是否能得出整数规划数要求的分量简单地取整，是否能得出整数规划问题的最优解呢？问题的最优解呢？第第15页页3.对松弛问题的最优解中不符合整数要求的分量简对松弛问题的最优解中不符合整数要求的分量简单地取整，所得到的问题解：

7、单地取整，所得到的问题解：|不一定是整数线性规划问题的最优解。不一定是整数线性规划问题的最优解。|甚至也不一定是整数线性规划问题的可行解。甚至也不一定是整数线性规划问题的可行解。第第16页页211020maxxxz 整整数数21212121,0,13522445xxxxxxxx例：例：第第17页页解：问题的最优解为：解：问题的最优解为：x1=4.8，x2=0其中分量其中分量 x1 不满足整数要求，从而对分量不满足整数要求，从而对分量 x1 进行进行“化整化整”：0,50,42121xxxx第第18页页为可行解，但不是最优解（为可行解，但不是最优解（x1=4,x2=1更优）更优）0,421 xx

8、第第19页页0,521 xx不满足约束条件不满足约束条件 1，从而为不可行解。，从而为不可行解。第第20页页结论：利用求解整数线性规划的松弛问题的最优解，结论：利用求解整数线性规划的松弛问题的最优解，再化整的方法无法得出整数线性规划的最优解。再化整的方法无法得出整数线性规划的最优解。第第21页页|纯整数规划问题：可行解的数量是有限的。纯整数规划问题：可行解的数量是有限的。|小型纯整数规划问题：可通过全枚举法，从中筛小型纯整数规划问题：可通过全枚举法，从中筛选最优解。选最优解。|大型纯整数规划问题：可行解的数量很大，无法大型纯整数规划问题：可行解的数量很大，无法使用全枚举法。使用全枚举法。|混合

9、整数规划问题：可行解的数量是无限的，无混合整数规划问题：可行解的数量是无限的，无法使用全枚举法。法使用全枚举法。第第22页页20世纪世纪60年代由年代由 LandDoig 和和 Dakin 等人提出了一种等人提出了一种仅检查可行域内可行的整数组合的一部分，就能定出仅检查可行域内可行的整数组合的一部分，就能定出最优整数解的方法，称为分支定界法（最优整数解的方法，称为分支定界法（branch and bound method）。）。第第23页页它是在枚举法基础上的改进，是一种隐枚举法它是在枚举法基础上的改进，是一种隐枚举法（implicit enumeration）或部分枚举法，不是一种有）或部分

10、枚举法，不是一种有效算法。效算法。第第24页页特点：它比枚举法优越，因为它仅在一部分可行解特点：它比枚举法优越，因为它仅在一部分可行解的整数解中寻找最优解，计算量比枚举法要小。但的整数解中寻找最优解，计算量比枚举法要小。但若变量数目很大，则其工作量也相当可观。若变量数目很大，则其工作量也相当可观。第第25页页步骤步骤 1 求解整数线性规划问题求解整数线性规划问题 A 的松弛问题的松弛问题 B：B 没有可行解，没有可行解，A 也没有可行解，停止；也没有可行解，停止；B 有最优解，且符合整数条件，有最优解，且符合整数条件，B 的最优解就是的最优解就是 A 的最优解，停止；的最优解，停止；B 有最优

11、解，但不符合整数条件，转步骤有最优解，但不符合整数条件，转步骤 2。第第26页页步骤步骤 2 分支和定界分支和定界 分支分支在在 B 的最优解中任选一个不符合整数条件的变量的最优解中任选一个不符合整数条件的变量 xj=bj，并构造两个约束条件，并构造两个约束条件，并将这两个约束条件加入问题，并将这两个约束条件加入问题 B，得到两个分支，得到两个分支问题问题 B1 和和 B2，并求解这两个分支问题，并求解这两个分支问题 B1 和和 B2。1 jjjjbxbx和和第第27页页A 的下界的下界 =max ，max 符合整数条件的分支符合整数条件的分支的目标函数值的目标函数值 。zzz令初始令初始 =

12、0。定界定界 第第28页页步骤步骤 3 比较和剪枝：比较和剪枝：比较比较比较多个目标函数值大于比较多个目标函数值大于 且不满足整数要求的分且不满足整数要求的分支，选择目标函数值最大的分支继续分支，返回步支，选择目标函数值最大的分支继续分支，返回步骤骤 2。z第第29页页 剪枝剪枝目标函数值小于目标函数值小于 且不满足整数要求的分支：且不满足整数要求的分支：停止继续分支，即剪掉该枝。停止继续分支，即剪掉该枝。无可行解的分支：停止继续分支，即剪枝。无可行解的分支：停止继续分支，即剪枝。满足整数要求的分支：停止分支，即剪枝。满足整数要求的分支：停止分支，即剪枝。z第第30页页例：求解例：求解 ，整整

13、数数、02434408365max21212121xxxxxxxxz第第31页页解：（解：（1）利用单纯型法求解原问题的松弛问题）利用单纯型法求解原问题的松弛问题 B：cj2300iCBXBbx1x2x3x40 x3403 8 1050 x42443018c j z j5600第第32页页cj2300iCBXBbx1x2x3x46x253/811/8040/3 0 x4923/80-3/8172/23 c j z j11/40-3/40第第33页页最优解为：最优解为：23331 x231932 x231438 z（2）x1 和和 x2 均为分数，任选均为分数，任选 x1 进行分支。进行分支。c

14、j2300iCBXBbx1x2x3x46x288/23014/23-3/2340/3 5x172/2310-3/238/2372/23 c j z j00-9/23-22/23第第34页页 04 2434408365 max211212121xxxxxxxxxz、问题问题 B2：03 2434408365 max211212121xxxxxxxxxz、问题问题 B1：第第35页页问题问题 B：x1=，x2=，z=x13x14=0233323193231438z第第36页页 03 2434408365 max211212121xxxxxxxxxz、问题问题 B1：02434408365 max2

15、1212121xxxxxxxxz、问题问题 B：第第37页页解：问题解：问题 B 的最终单纯形表：的最终单纯形表：增加了约束条件增加了约束条件 x1 3 后后cj5600iCBXBbx1x2x3x46x288/23014/23-3/2340/3 5x172/2310-3/238/2372/23 c j z j00-9/23-22/23第第38页页将约束条件将约束条件 x1 +x5=3 加入到单纯形表最后一行加入到单纯形表最后一行cj56000iCBXBbx1x2x3x4x56x288/23014/23-3/2305x172/2310-3/238/2300 x5310001c j z j第第39

16、页页将将 x1 的系数列向量变为单位向量，并计算检验数的系数列向量变为单位向量，并计算检验数cj56000iCBXBbx1x2x3x4x56x288/23014/23-3/2305x172/2310-3/238/2300 x5-3/23003/23-8/231c j z j00-9/23-22/230第第40页页旋转运算旋转运算cj56000iCBXBbx1x2x3x4x56x231/8011/80-3/85x13100010 x43/800-3/81-23/8c j z j00-3/40-11/4问题问题 B1：4138 ,873 ,321 zxx第第41页页 04 2434408365 m

17、ax211212121xxxxxxxxxz、问题问题 B2：02434408365 max21212121xxxxxxxxz、问题问题 B：第第42页页解：问题解：问题 B 的最终单纯形表：的最终单纯形表：增加了约束条件增加了约束条件 x1 4 后后cj5600iCBXBbx1x2x3x46x288/23014/23-3/2340/3 5x172/2310-3/238/2372/23 c j z j00-9/23-22/23第第43页页将约束条件将约束条件 x1 -x5+x6=4 加入到单纯形表最后一行加入到单纯形表最后一行cj56000-MiCBXBbx1x2x3x4x5x66x288/23

18、014/23-3/23005x172/2310-3/238/2300-Mx641000-11c j z j第第44页页将将 x1 的系数列向量变为单位向量，并计算检验数的系数列向量变为单位向量，并计算检验数cj56000-MiCBXBbx1x2x3x4x5x66x288/23014/23-3/23005x172/2310-3/238/2300-Mx620/23003/23-8/23-11c j z j003/23M-9/23-22/23-8/23M-M0第第45页页旋转运算旋转运算cj56000-MiCBXBbx1x2x3x4x5x66x28/30101/34/3-4/35x141000-11

19、0 x320/3001-8/3-23/323/3c j z j000-2-33-M36 ,322 ,421 zxx问题问题 B2：第第46页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=02333231932314388734138322zx23x24第第47页页（3）比较问题）比较问题 B1 和和 B2 的目标函数值，选择问题的目标函数值，选择问题B1 进行分支：进行分支：0332434408365 max2121212121xxxxxxxxxxz、问题问题 B3：最优解：最优解：x1=3，x2=3，z=33 3

20、3 z，停止分支，停止分支 第第48页页 0432434408365 max2121212121xxxxxxxxxxz、问题问题 B4：最优解：最优解：zz ，继续分支，继续分支 3137,4,32221 zxx第第49页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=332333231932314388734138322z问题问题B4：x1=，x2=4，z=x23x24322问题问题B3：x1=3，x2=3，z=333137z=0 x12x13第第50页页（4）比较问题）比较问题 B2 和和 B4 的目标函数值，选

21、择问题的目标函数值，选择问题B4 进行分支：进行分支：02432434408365 max21121212121xxxxxxxxxxxz、问题问题 B5：最优解：最优解：2135,414,221 zxxzz ，继续分支，继续分支 第第51页页问题问题 B6：03432434408365 max21121212121xxxxxxxxxxxz、无可行解无可行解停止分支停止分支第第52页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=332333231932314388734138322z问题问题B4：x1=，x2=4，z

22、=x23x24322问题问题B3：x1=3，x2=3，z=333137问题问题B5：x1=2，x2=，z=4142135问题问题B6：无可行解：无可行解x13x13第第53页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=332333231932314388734138322zx23x24问题问题B3：x1=3x2=3z=33问题问题B4：x1=x2=4，z=3223137问题问题B5：x1=2x2=z=4142135问题问题B6：无可行解无可行解x13x13x23x22第第54页页（5）比较问题）比较问题 B2 和

23、和 B5 的目标函数值，选择问题的目标函数值，选择问题B2 进行分支：进行分支：问题问题 B7：最优解：最优解：2134,2,21421 zxxzz ，继续分支，继续分支 0242434408365 max2121212121xxxxxxxxxxz、第第55页页问题问题 B8：无可行解无可行解停止分支停止分支 0342434408365 max2121212121xxxxxxxxxxz、第第56页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=332333231932314388734138322zx23x24问题问

24、题B3：x1=3x2=3z=33问题问题B4：x1=x2=4，z=3223137问题问题B5：x1=2x2=z=4142135问题问题B6：无可行解无可行解x1 3x13问题问题B7：x1=x2=2z=2142134问题问题B8：无可行解无可行解x23x22x13x15第第57页页（6）比较问题）比较问题 B5 和和 B7 的目标函数值，选择问题的目标函数值，选择问题B5 进行分支：进行分支：问题问题 B9：最优解：最优解：34,4,221 zxx3334 zz 042432434408365 max212121212121xxxxxxxxxxxxz、，停止分支，停止分支 34 z，故，故 第

25、第58页页问题问题 B10：052432434408365 max212121212121xxxxxxxxxxxxz、最优解：最优解：30,5,021 zxx3330 zz，停止分支，停止分支 34 z，故，故 第第59页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=342333231932314388734138322zx23x24问题问题B3：x1=3x2=3z=33问题问题B4：x1=x2=4，z=3223137问题问题B5：x1=2x2=z=4142135问题问题B6：无可行解无可行解x13x13问题问题B

26、7：x1=x2=2z=2142134问题问题B8：无可行解无可行解x23x22问题问题B9：x1=2，x2=4，z=34问题问题B10：x1=0，x2=5，z=30 x13x15=33第第60页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=342333231932314388734138322z问题问题B7：x1=x2=2z=2142134问题问题B8：无可行解无可行解x23x22x14x15第第61页页（7）选择问题）选择问题B7 进行分支：进行分支：问题问题 B11：04242434408365 max2112

27、1212121xxxxxxxxxxxz、最优解：最优解：32,2,421 zxx3432 zz，停止分支，停止分支 34 z，故，故 第第62页页问题问题 B12：05242434408365 max21121212121xxxxxxxxxxxz、最优解：最优解：33,311,521 zxx3433 zz，停止分支，停止分支 34 z，故，故 第第63页页问题问题 B：x1=，x2=，z=问题问题B2：x1=4，x2=，z=36问题问题B1：x1=3，x2=，z=x13x14=342333231932314388734138322z问题问题B7：x1=x2=2z=2142134问题问题B8：无可行解无可行解x23x22问题问题B11：x1=4，x2=2，z=32问题问题B12：x1=5，x2=，z=33311x14x15第第64页页从而问题的最优解为：从而问题的最优解为：x1=2，x2=4，z=34