任務二　整數規劃的分支定界法

嚴格地說，整數規劃是非線性問題。因為整數規劃的可行解集是由一些離散的非負整數點組成的，而不是一個連續不斷的凸集。目前，求解整數規劃尚無統一有效的辦法。分支定界法是求解整數規劃的常用方法，尤其是求解相對比較復雜的整數規劃時，應用分支定界法更為有效。

分支定界法是在20世紀60年代初由Land Doig和Dakin等人提出的，由于該方法靈活，便于計算機求解，所以它是現在求解整數規劃的重要方法。它的基本思想是，先不考慮原整數規劃問題中的整數性約束，去解其相應的松弛問題。對于最大化問題，松弛問題的最優值就是原問題最優值的上界。如果松弛問題的最優解滿足整數性約束，則它就是原問題的最優解。否則，就在不滿足整數約束的變量中，任意選擇xi＝bi，設［bi］是不超過bi的最大整數，將新的約束條件xi≤［bi］和xi≥［bi］＋1分別加入原問題中，把原問題分支為兩個子問題，并分別求解子問題的松弛問題。若子問題的松弛問題的最優解滿足整數約束，則不再分支，其相應的目標函數值就是原問題目標函數值的一個下界。對不滿足整數約束的子問題，如果需要，繼續按上述方法進行新的分支，并分別求解其對應的松弛問題，直至求得原問題的最優解為止。

因此，我們總結分支定界法的求解步驟如下。

（1）先不考慮整數約束，求解整數規劃的松弛問題，可能得到以下情況之一：

①若松弛問題沒有可行解，則整數規劃也沒有可行解，停止計算；

②若松弛問題有最優解，并符合整數規劃的整數條件，則線性規劃的最優解即為整數規劃的最優解，停止計算；

③若松弛問題有最優解，但不符合整數規劃的整數條件，轉入下一步。

（2）分支：從不滿足整數條件的基變量中任選一個xi進行分支，它必須滿足xi≤［xi］或xi≥［xi］＋1中的一個，把這兩個約束條件加進原問題中，形成兩個互不相容的子問題。

（3）定界：把滿足整數條件各分支的最優目標函數值作為上（下）界，用它來判斷分支是保留還是剪支。

（4）剪支：把那些子問題的最優值與界值比較，凡不優或不能更優的分支全剪掉，直到每個分支都查清為止。

例3-2-1　用分支定界法求解。

（1）用單純形法可解得相應的松弛問題的最優解（1.2，2.1），z＝11.1，很明顯，這個最優解不符合整數條件，我們需要繼續分支，并把這個最優值定為各分支的上界。

（2）選擇x1＝1.2來進行分支，加入條件x1≤1和x1≥2，得到兩個子問題。

（3）用單純形法求得P1的最優解（1，2.25），z＝10.75，P2的最優解（2，0.5），z＝9.5。沒有得到整數解，繼續分支。對P1進行分支，加入條件x2≤2和x2≥3，生出兩個子問題。

（4）用單純形法可解得相應的P3的最優解（1，2），z＝10，P4的最優解（0，3），z＝9。P3和P4的解都是整數，比較它們對應的目標函數值，顯然P3的目標函數值大于P4，剪去P4一支，把P3中z＝10作為目標函數的下界。

（5）我們回頭看P2，在這一支中，可以繼續分支以求得整數解。但這一支現在的最優值z＝9.5，也就是說，不管再怎么分，在這一支中求得的目標函數值不可能超過9.5，因此，也不可能超過P3中求得的z＝10，因此將此支剪去。至此，我們得到了該整數規劃的最優解x1＝1，x2＝2，z＝10。

用樹形圖（見圖3-2-1）表示求解這個問題的全過程。