管理运筹学-第8章-整数规划.pptVIP

8.2.1 分支定界法 在IP2中分别再加入条件： x2≤3, x2≥4 得下式两支： 分别求出LP21和LP22的最优解 8.2.1 分支定界法 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D 先求LP21,如图所示。此时D 在点取得最优解。 即 x1＝12/5≈2.4, x2 =3, Z(21)＝-87/5≈-17.4 Z(1)=-16 但x1＝12/5不是整数，可继续分枝。即 3≤x1≤2。 求LP22，如图所示。无可行解，故不再分枝。 8.2.1 分支定界法 在（LP21）的基础上继续分枝。加入条件3≤x1≤2有下式： 分别求出（LP211）和（LP212）的最优解 8.2.1 分支定界法 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D E F 先求（LP211）,如图所示。此时 在E点取得最优解。即 x1＝2, x2 =3, Z(211)＝－17 找到整数解，问题已探明，此枝停止计算。 求（LP212），如图所示。此时 F在点取得最优解。即x1＝3, x2 =2.5, Z(212)＝－31/2≈－15.5 Z(211) 如对LP212继续分解，其最小值也不会低于－15.5 ，问题探明,剪枝。 8.2.1 分支定界法 原整数规划问题的最优解为: x1=2, x2 =3, Z* =－17 以上的求解过程可以用一个树形图表示如右： LP1 x1=1, x2=3 Z(1) ＝－16 LP x1=18/11, x2=40/11 Z(0) ＝－19.8 LP2 x1=2, x2=10/3 Z(2) ＝－18.5 LP21 x1=12/5, x2=3 Z(21) ＝－17.4 LP22 无可 行解 LP211 x1=2, x2=3 Z(211) ＝－17 LP212 x1=3, x2=5/2 Z(212) ＝－15.5 x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 ＃ ＃ ＃ ＃ 8.2.1 分支定界法 例9. 用分枝定界法求解 解: 先求对应的松弛问题（记为LP0） 用图解法得到最优解X＝(3.57,7.14),Z0=35.7,如下图所示。 8.2.1 分支定界法 10 10 松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7 x1 x2 o A B C 8.2.1 分支定界法 10 x2 o A B C LP1 LP2 3 4 LP1:X=(3,7.6),Z1=34.8 ① ② LP2:X=(4,6.5),Z2=35.5 8.2.1 分支定界法 10 x1 x2 o A B C LP1 LP21 3 4 LP21:X=(4.33,6),Z21=35.33 6 8.2.1 分支定界法 10 x1 x2 o A C LP1 3 4 6 LP211:X=(4,6), Z211=34 LP212:X=(5,5),Z212=35 5 LP212 8.2.1 分支定界法 上述分枝过程可用下图表示： LP0:X=(3.57,7.14),Z0=35.7 LP1:X=(3,7.6) Z1=34.8 LP2:X=(4,6.5) Z2=35.5 x1≤3 x1≥4 LP21:X=(4.33,6) Z21=35.33 x2≤6 LP211:X=(4,6) Z211=34 LP212:X=(5,5) Z212=35 x1≤4 x1≥5 LP22 无可行解 x2≥7 小结 学习要点： 掌握一般整数规划问题概念及模型结构 掌握分支定界法原理 能够用分支定界法求解一般整数规划问题 * 作业： 教材P180-181 ： 1; 3; 4; 5 * 整数规划 8.1 整数规划的特点与应用 8.2　整数规划的求解方法 分支定界法 分配问题与匈牙利法 8.1 整数规划的特点及应用 整数规划（简称：IP） 一部分或全部决策变量取整数值的规划问题称为整数规划。 不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。 若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。Integer Linear Programming 8.1 整数规划的特点及应用 整数线性规划问题的种类： 纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。 * 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、