1、（一）、基本思路（一）、基本思路 11max (1.2)()0,(1.2)njjjnijjijjZc xa xbimIPxjn且為整數考慮純整數問題：考慮純整數問題：11max (1.2)()0,(1.2)njjjnijjijjZc xa xbimLPxjn整數問題的松弛問題：整數問題的松弛問題：第三節第三節 分枝定界法分枝定界法且為整數且為整數)2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考慮純整數問題：考慮純整數問題：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整數問題的松弛問題：

2、整數問題的松弛問題：判斷題：整數問題的最優判斷題：整數問題的最優函數值總是小于或等于其函數值總是小于或等于其松弛問題的最優函數值。松弛問題的最優函數值。例一：用分枝定界法求解整數規劃問題（用圖解法計算）例一：用分枝定界法求解整數規劃問題（用圖解法計算）121212112max5 256 30 4,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無可無可行解行解

3、LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13例一：用分枝定界法求解整數規劃問題（用圖解法計算）例一：用分枝定界法求解整數規劃問題（用圖解法計算）121212112max5 256 30 4,0Zxxxxxxxxx 且全為整數記為（記為（IP）解：首先去掉整數約束，變成一般線性規劃問題解：首先去掉整數約束，變成一般線性規劃問題121212112max5 256 30 4,0Zxxxxxxxxx 記為（記為（LP）用圖解法求用圖解法求（LP）的最的最優解，如圖所示。優解，如圖所示。x1x23312121

4、2112max5 256 30 4,0Zxxxxxxxxx 12 2xx 14x 125630 xx125xxZx1x233(18/11,40/11) x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最大值的上限。最大值的上限。121212112max5 256 30 4,0Zxxxxxxxxx 12 2xx 14x 125630 xx125xxZLPx1=18/11, x2=40/11Z(0) 19.8x1x233(18/11,40/11)對于對于x118/111.64， 取值取值x1 1， x1 2對于對于x2 =40/11 3.64，取值

5、取值x2 3 ，x2 4 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最大值的上限。最大值的上限。先將先將（LP）劃分為（）劃分為（LP1）和）和（LP2）, ,取取x1 1, x1 212 2xx 14x 125630 xx125xxZ1212121112max5 256 30(1) 4 1,0ZxxxxxxIPxxxx 且為整數1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且為整數 現在只要求出（現在只要求出（LP1）和（）和（LP2）的最優解即可。）的最優解即可。先將先將（LP）劃分為（）劃分

6、為（LP1）和（）和（LP2）, ,取取x1 1, x1 2，有下式：有下式：LP1x1=？, x2=？Z(1) ？LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12x1x233 先求先求（LP1）, ,如圖所示。如圖所示。11A1212121112max5 256 30(1) 4 1,0ZxxxxxxIPxxxx 且為整數12 2xx 14x 125630 xx125xxZx1x233 先求先求（LP1）, ,如圖所示。如圖所示。11BA此時此時B 在點取得最優解。在點取得最優解。x11, x2 =3, Z(1)16121212111

7、2max5 256 30(1) 4 1,0ZxxxxxxIPxxxx 且為整數12 2xx 14x 125630 xx125xxZLP1x1=？, x2=？Z(1) ？LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12x1x23311BA求求（LP2） ,如圖所示。如圖所示。1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且為整數12 2xx 14x

8、125630 xx125xxZx1x23311在在C 點取得最優解。點取得最優解。即即x12, x2 =10/3, Z(2) 56/318.7BAC求求（LP2） ,如圖所示。如圖所示。1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且為整數12 2xx 14x 125630 xx125xxZLP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x

9、2=10/3Z(2) 18.7x11x12找到整數解，找到整數解，此枝停止計算此枝停止計算在在C 點取得最優解。點取得最優解。即即x12, x2 =10/3, Z(2) 56/318.7 x1x23311BAC求求（LP2） ,如圖所示。如圖所示。1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且為整數 Z2 Z116 原問題可能有比（原問題可能有比（16）更大的最優解，）更大的最優解，但但 x2 不是整數，故利用不是整數，故利用 x2 3 ， x2 4 加入條件。加入條件。12 2xx 14x 125630 xx125xxZ1212121112max5

10、 256 30(1) 4 1,0ZxxxxxxIPxxxx 且為整數1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且為整數（LP）劃分為（）劃分為（LP1）和（）和（LP2）, ,x1 1, x1 2對于對于LP2,加入條件：加入條件： x23, x24 有下式：有下式：12121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且為整數12121211212max5 256 30 4(22) 2 4,0ZxxxxxxxIPxxxx 且為整數只要求出（只要求出（LP21）和（）和（LP22）的最優解即可。）的最優解

11、即可。x11x12x24x23LP1x1=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) ？找到整數解，找到整數解，此枝停止計算此枝停止計算x1x23311BAC先求先求（LP21）, ,如圖所示。如圖所示。12121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且為整數12 2xx 14x 125630 xx125xxZx1x23311BAC先求先求（LP21）, ,如圖所示。如圖所

12、示。D此時此時D 在點取得最優解。在點取得最優解。即即 x112/5=2.4, x2 =3, Z(21)87/5=17.412121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且為整數12 2xx 14x 125630 xx125xxZx1x23311BACD求求（LP22），），如圖所示。如圖所示。無可行解，不再分枝。無可行解，不再分枝。12121211212max5 256 30 4(22) 2 4,0ZxxxxxxxIPxxxx 且為整數12 2xx 14x 125630 xx125xxZx11x12x24x23LP1x1=1, x2=3Z(1

13、) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.7LP21x1=？, x2=？Z(21) ？LP22x1=？, x2=？Z(22) ？找到整數解，找到整數解，此枝停止計算此枝停止計算x11x12x24x23LP1x1=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無可無可行解行解找到整數解，找到整數解，此枝停止計算此枝停止計算x1x23311BAC（LP21）, ,如圖所示，如圖所

14、示， 在在D點取點取得最優解。得最優解。即即 x112/5=2.4, x2 =3, Z(3)87/5=17.4Dx12.4不是整數，可繼續分枝。不是整數，可繼續分枝。即即 x12， x1 312 2xx 14x 125630 xx125xxZ12121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且為整數12121211212max5 256 30 4(22) 2 4,0ZxxxxxxxIPxxxx 且為整數在在（LP21）的基礎上繼續分枝。加入條件）的基礎上繼續分枝。加入條件x12， x1 3有下式：有下式：121212112112max5 256

15、30 4(211) 2 3 2,0ZxxxxxxxIPxxxxx 且為整數121212112112max5 256 30 4(212) 2 3 3,0ZxxxxxxxIPxxxxx 且為整數只要求出（只要求出（LP211）和（）和（LP212）的最優解即可。）的最優解即可。x12LP1x1=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

16、1x12x23x24x13找到整數解，找到整數解，此枝停止計算此枝停止計算先求先求（LP211）x13311BACD121212112112max5 256 30 4(211) 2 3 2,0ZxxxxxxxIPxxxxx 且為整數x212 2xx 14x 125630 xx125xxZ先求先求（LP211）x13311BACDE121212112112max5 256 30 4(211) 2 3 2,0ZxxxxxxxIPxxxxx 且為整數x2如圖所示，此時如圖所示，此時E 在點取得最優解在點取得最優解即即 x12, x2 =3, Z(211)1712 2xx 14x 125630 xx1

17、25xxZx1x23311BACDE求求（LP212）121212112112max5 256 30 4(212) 2 3 3,0ZxxxxxxxIPxxxxx 且為整數12 2xx 14x 125630 xx125xxZx1x23311BACDE求求（LP212）F121212112112max5 256 30 4(212) 2 3 3,0ZxxxxxxxIPxxxxx 且為整數如圖所示。此時如圖所示。此時 F在點取在點取得最優解。得最優解。x13, x2 =2.5, Z(212)31/2=15.5 12 2xx 14x 125630 xx125xxZLP1x1=1, x2=3Z(1) 16

18、LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=2.4, x2=3Z(21) 17.4LP22無可無可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13找到整數解，找到整數解，此枝停止計算此枝停止計算找到整數解，找到整數解，此枝停止計算此枝停止計算LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=2.4, x2=3

19、Z(21) 17.4LP22無可無可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13找到找到最優最優解解找到整數解，找到整數解，此枝停止計算此枝停止計算找到整數解，找到整數解，此枝停止計算此枝停止計算LP1x1=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=2, x2=3Z(211) 17LP212x1=3, x2=

20、5/2Z(212) 15.5x11x12x23x24x12x13 至此，原問至此，原問題（題（IP）的最優）的最優解為：解為： x1=2， x2 =3, Z* = Z(211) 17以上的求解過程以上的求解過程可以用一個樹形可以用一個樹形圖表示如右：圖表示如右： 且全為整數且全為整數0,13651914max21212121xxxxxxxxZ練習：用分枝定界法求解整數規劃問題練習：用分枝定界法求解整數規劃問題 （圖解法）（圖解法）LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP

21、21x1=33/14, x2=2Z(21) 61/14LP22無可無可行解行解x22x23LP211x1=2, x2=2Z(211) 4LP212x1=3, x2=1Z(212) 4x12x13且且為為整整數數0,143292)(23max21212121xxxxxxIPxxZ3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4 -1/4解解:用單純形法解對應的用單純形法解對應的(LP)問題問題,如表所示如表所示,

22、獲得最優解。獲得最優解。初始表初始表最終表最終表例二、用分枝定界法求解整數規劃問題（單純形法）例二、用分枝定界法求解整數規劃問題（單純形法） x1=13/4 x2=5/2 Z(0) =59/4=14.75 選選 x2 進行分枝，即增加兩個約束，進行分枝，即增加兩個約束， x2 2 , x2 3 有下式：有下式：且且為為整整數數0,2 14329 2) 1(23max212212121xxxxxxxIPxxZ且且為為整整數數0,3 14329 2)2(23max212212121xxxxxxxIPxxZ 分別在分別在(LP1)和和(LP2)中引入松弛變量中引入松弛變量x5和和x6 ，將新加約束條

23、件加入上表計算。，將新加約束條件加入上表計算。即即 x2+ x5= 2 , x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5繼續分枝，加入繼續分

24、枝，加入約束約束 x1 3, x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考慮分枝先不考慮分枝接接(LP1)繼續分枝，加入約束繼續分枝，加入約束 x1 3， x1 4 有下式：有下式：且且為為整整數數0,3 2 14329 2)3(23max2112212121xxxxxxxxIPxxZ且且為為整整數數0,4 2 14329 2)4(23max2112212121xxxxxxxxIPxxZ分別引入松弛變量分別引入松弛變量x7 和和 x8 ，然后進行計算。