运筹学_分支定界法

（一）、基本思路11max(1.2)()0,(1.2)njjjnijjijjZcxaxbimIPxjn且为整数考虑纯整数问题：11max(1.2)()0,(1.2)njjjnijjijjZcxaxbimLPxjn整数问题的松弛问题：第三节分枝定界法且为整数)2.1(,0)2.1()(max11mjxmibxaIPxcZjnjijijnjjj考虑纯整数问题：)2.1(,0)2.1()(max11mjxmibxaLPxcZjnjijijnjjj整数问题的松弛问题：判断题：整数问题的最优函数值总是小于或等于其松弛问题的最优函数值。例一：用分枝定界法求解整数规划问题（用图解法计算）121212112max5256304,0Zxxxxxxxxx且全为整数记为（IP）（二）、例题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＃＃＃＃例一：用分枝定界法求解整数规划问题（用图解法计算）121212112max5256304,0Zxxxxxxxxx且全为整数记为（IP）解：首先去掉整数约束，变成一般线性规划问题121212112max5256304,0Zxxxxxxxxx记为（LP）用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33⑶121212112max5256304,0Zxxxxxxxxx122xx14x125630xx125xxZx1x2⑴⑵33(18/11,40/11)⑶x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限。121212112max5256304,0Zxxxxxxxxx122xx14x125630xx125xxZLPx1=18/11,x2=40/11Z(0)＝19.8x1x2⑴⑵33(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≥2122xx14x125630xx125xxZ1212121112max525630(1)41,0ZxxxxxxIPxxxx且为整数1212121112max525630(2)42,0ZxxxxxxIPxxxx且为整数现在只要求出（LP1）和（LP2）的最优解即可。先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2，有下式：LP1x1=？,x2=？Z(1)＝？LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=？,x2=？Z(2)＝？x1≤1x1≥2x1x2⑴⑵33⑶先求（LP1）,如图所示。11A1212121112max525630(1)41,0ZxxxxxxIPxxxx且为整数122xx14x125630xx125xxZx1x2⑴⑵33⑶先求（LP1）,如图所示。11BA此时B在点取得最优解。x1＝1,x2=3,Z(1)＝161212121112max525630(1)41,0ZxxxxxxIPxxxx且为整数122xx14x125630xx125xxZLP1x1=？,x2=？Z(1)＝？LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=？,x2=？Z(2)＝？x1≤1x1≥2LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=？,x2=？Z(2)＝？x1≤1x1≥2x1x2⑴⑵33⑶11BA求（LP2）,如图所示。1212121112max525630(2)42,0ZxxxxxxIPxxxx且为整数122xx14x125630xx125xxZx1x2⑴⑵33⑶11在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝56/3≈18.7BAC求（LP2）,如图所示。1212121112max525630(2)42,0ZxxxxxxIPxxxx且为整数122xx14x125630xx125xxZLP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=？,x2=？Z(2)＝？x1≤1x1≥2LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=2,x2=10/3Z(2)＝18.7x1≤1x1≥2找到整数解，此枝停止计算在C点取得最优解。即x1＝2,x2=10/3,Z(2)＝56/3≈18.7x1x2⑴⑵33⑶11BAC求（LP2）,如图所示。1212121112max525630(2)42,0ZxxxxxxIPxxxx且为整数∵Z2Z1＝16∴原问题可能有比（16）更大的最优解，但x2不是整数，故利用x2≤3，x2≥4加入条件。122xx14x125630xx125xxZ1212121112max525630(1)41,0ZxxxxxxIPxxxx且为整数1212121112max525630(2)42,0ZxxxxxxIPxxxx且为整数（LP）划分为（LP1）和（LP2）,x1≤1,x1≥2对于LP2,加入条件：x2≤3,x2≥4有下式：12121211212max5256304(21)23,0ZxxxxxxxIPxxxx且为整数12121211212max5256304(22)24,0ZxxxxxxxIPxxxx且为整数只要求出（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)＝？找到整数解，此枝停止计算x1x2⑴⑵33⑶11BAC先求（LP21）,如图所示。12121211212max5256304(21)23,0ZxxxxxxxIPxxxx且为整数122xx14x125630xx125xxZx1x2⑴⑵33⑶11BAC先求（LP21）,如图所示。D此时D在点取得最优解。即x1＝12/5=2.4,x2=3,Z(21)＝87/5=17.412121211212max5256304(21)23,0ZxxxxxxxIPxxxx且为整数122xx14x125630xx125xxZx1x2⑴⑵33⑶11BACD求（LP22），如图所示。无可行解，不再分枝。12121211212max5256304(22)24,0ZxxxxxxxIPxxxx且为整数122xx14x125630xx125xxZ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)＝？找到整数解，此枝停止计算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=2.4,x2=3Z(21)＝17.4LP22无可行解找到整数解，此枝停止计算x1x2⑴⑵33⑶11BAC（LP21）,如图所示，在D点取得最优解。即x1＝12/5=2.4,x2=3,Z(3)＝87/5=17.4Dx1＝2.4不是整数，可继续分枝。即x1≤2，x1≥3122xx14x125630xx125xxZ12121211212max5256304(21)23,0ZxxxxxxxIPxxxx且为整数12121211212max5256304(22)24,0ZxxxxxxxIPxxxx且为整数在（LP21）的基础上继续分枝。加入条件x1≤2，x1≥3有下式：121212112112max5256304(211)232,0ZxxxxxxxIPxxxxx且为整数121212112112max5256304(212)233,0ZxxxxxxxIPxxxxx且为整数只要求出（LP211）和（LP212）的最优解即可。x1≤2LP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/11Z(0)＝19.8LP2x1=2,x2=10/3Z(2)＝18.5LP21x1=2.4,x2=3Z(21)＝17.4LP22无可行解LP211x1=？,x2=？Z(211)＝？LP212x1=？,x2=？Z(212)＝？x1≤1x1≥2x2≤3x2≥4x1≥3＃找到整数解，此枝停止计算先求（LP211）x1⑴⑵33⑶11BACD121212112112max5256304(211)232,0ZxxxxxxxIPxxxxx且为整数x2122xx14x125630xx125xxZ先求（LP211）x1⑴⑵33⑶11BACDE121212112112max5256304(211)232,0ZxxxxxxxIPxxxxx且为整数x2如图所示，此时E在点取得最优解即x1＝2,x2=3,Z(211)＝17122xx14x125630xx125xxZx1x2⑴⑵33⑶11BACDE求（LP212）121212112112max5256304(212)233,0ZxxxxxxxIPxxxxx且为整数122xx14x125630xx125xxZx1x2⑴⑵33⑶11BACDE求（LP212）F121212112112max5256304(212)233,0ZxxxxxxxIPxxxxx且为整数如图所示。此时F在点取得最优解。x1＝3,x2=2.5,Z(212)＝31/2=15.5122xx14x125630xx125xxZLP1x1=1,x2=3Z(1)＝16LPx1=18/11,x2=40/1