运筹学-分支定界法.pptxVIP

010203基本思路考虑纯整数问题：整数问题的松弛问题：第三节分枝定界法

考虑纯整数问题：整数问题的松弛问题：判断题：整数问题的最优函数值总是小于或等于其松弛问题的最优函数值。

例一：用分枝定界法求解整数规划问题（用图解法计算）1记为（IP）2（二）、例题

LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=2,x2=10/3Z(2)＝18.5LP21x1=12/5,x2=3Z(21)＝17.4LP22无可行解LP211x1=2,x2=3Z(211)＝17LP212x1=3,x2=5/2Z(212)＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃

例一：用分枝定界法求解整数规划问题（用图解法计算）记为（IP）01解：首先去掉整数约束，变成一般线性规划问题02记为（LP）03

用图解法求（LP）的最优解，如图所示。x1x2⑴⑵3⑶

x1x2⑴⑵3(18/11,40/11)⑶x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限。

010204x1=18/11,x2=40/11Z(0)＝19.8LP

x1x2⑴⑵3(18/11,40/11)⑶对于x1＝18/11≈1.64，取值x1≤1，x1≥2对于x2=40/11≈3.64，

取值x2≤3，x2≥4x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限。先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2

现在只要求出（LP1）和（LP2）的最优解即可。先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2，有下式：0102

LP101x1=？,x2=？02Z(1)＝？03LP04x1=18/11,x2=40/1105Z(0)＝19.806LP207x1=？,x2=？08Z(2)＝？09x1≤110x1≥211

先求（LP1）,如图所示。x1x2⑴⑵3⑶11A

先求（LP1）,如图所示。x1x2⑴⑵3⑶11BA此时B在点取得最优解。x1＝1,x2=3,Z(1)＝16

LP101x1=？,x2=？02Z(1)＝？03LP04x1=18/11,x2=40/1105Z(0)＝19.806LP207x1=？,x2=？08Z(2)＝？09x1≤110x1≥211

LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=？,x2=？Z(2)＝？x1≤1x1≥2

求（LP2）,如图所示。x1x2⑴⑵3⑶11BA

求（LP2）,如图所示。x1x2⑴⑵3⑶11在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝56/3≈18.7BAC

LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=？,x2=？Z(2)＝？x1≤1x1≥2

LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=2,x2=10/3Z(2)＝18.7x1≤1x1≥2找到整数解，

此枝停止计算

求（LP2）,如图所示。在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝56/3≈18.7x1x2⑴⑵33⑶11BAC∵Z2Z1＝16∴原问题可能有比（16）更大的最优解，

但x2不是整数，故利用x2≤3，x2≥4加入条件。

（LP）划分为（LP1）和（LP2）,x1≤1,x1≥2

对于LP2,加入条件：x2≤3,x2≥4有下式：只要求出（LP21）和（LP22）的最优解即可。

x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=2,x2=10/3Z(2)＝18.7LP21x1=？,x2=？Z(21)＝？LP22x1=？,x2=？Z(22)＝？找到整数解，

此枝停止计算

先求（LP21）,如图所示。x1x2⑴⑵3⑶11BAC

先求（LP21）,如图所示。x1x2⑴⑵3⑶11BACD此时D在点取得最优解。即x1＝12/5=2.4,x2=3,Z(21)＝87/5=17.4

x1x2⑴⑵3⑶11BACD求（LP22），如图所示。无可行解，不再分枝。

x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)＝16LPx1