第二节整数规划之解法--分枝界限法.ppt

分枝界限法(Branch and Bound Method) 此種方法也能夠使用在混合整數規劃問題上，其為一種系統化的解法，以一般線性規劃之單形法解得最佳解後，將非整數值之決策變數分割成為最接近的兩個整數，分列條件，加入原問題中，形成兩個子問題(或分枝)分別求解，如此便可求得目標函數值的上限或下限，從其中尋得最佳解。; 假設原整數規則問題為求極大值，所有決策變數必須為整數時，則其求解步驟如下： 考慮下列整數規劃問題 Max z ＝ CX s.t. AX＝b 所有 xj 為正整數 ;步驟一：求解時，首先不考慮整數之限制條件，以一般線性規劃單形法求解，若所有的決策變數均為整數，則獲得最佳解。若至少有一個決策變數為非整數時，令原問題為 LP－1 ，設其最佳目標函數值 z ＝ z1，z1 為原問題之最佳函數值之上限，並進入步驟二。;步驟二：於LP－1所得之最佳解中，選擇一個非整數解之變數 xi (取法見註)，對該變數分割成為最接近其解值的兩個整數，分列條件，加入原問題 LP－1 中，形成兩個子問題。分別記做 LP－2 和 LP－3，分別求解。假設 xi 為被選取作為分枝的變數， xi ＝ [ xi ] ＋ fi [ xi ]：表示整數部分，且 0 ＜ fi ＜ 1。; 因此將 xi 分割成為最接近的兩個整數為： xi ≦ [ xi ] 和 x ≧ [ xi ] ＋1 (即 xi 比小的小，比大的大) 分別加入原問題 LP－1 中，而得 LP－2： Max z ＝ CX s.t. AX ＝ b xi ≦ [ xi ] X ≧ 0 LP－3： Max z ＝ CX s.t. AX ＝ b xi ≧ [ xi ]＋1 X ≧ 0;步驟三：於步驟二中，其可能的結果有 若有一子問題之最佳解值均為整數，則其目標函數 z 值，變為原問題最佳目標函數值之下限，如 LP－2 之最佳解值均為整數，其目標函數值 z2 為原問題之目標函數值之下限。此時若 LP－3 無可行解或有可行解，但其目標函數值 z3 小 於 z2，則 LP－2 之最佳解即為原問題之最佳整數值；若 LP－3 之最佳目標函數值 z3 大於 z2 且決策變數均為整數值，則 LP－3 為原問題之最佳解；若 LP－3 有非整數解之決策變數，且z3＞ z2，則對 LP－3 再分枝，並進入步驟四。;若兩個子問題之最佳解均為非整數時，則選取一個子問題(通常取目標函數值較大者)做如步驟二之分枝情形，並進入步驟四。 步驟四：求出再分枝的兩個子問題之最佳解，當其中某一子問題之最佳解均為整數時，其目標函數值不小於原問題之目標函數值的下限，且其與對應的另一子問題無可行解或有可行解，但目標函數值較前者為小時，則已獲得原問題之最佳解，否則回到步驟三。;有下列各種情況時，子問題便可不必再分枝求解 某一子問題之最佳解均為整數時，即它是原問題的可行解。 某一子問題無可行解。 某一子問題之最佳目標函數值較原問題之下限為小時。;再以作作看 1 說明各子問題之關係，其分枝界限法樹枝圖 為 Max z ＝7x1＋x2 s.t. 5x1＋x2 ≦ 27/2 5x1－x2 ≦ 13/2 x1, x2 為正整數;將上述樹枝圖之問題型式和解彙總如下 LP－1： Max z ＝ 7x1＋x2 s.t. 5x1＋x2≦27/2 x1＝2 5x1－x2≦13/2 x2＝7/2　　　　 x1, x2 為正整數 z1＝35/2;LP－2：Max z ＝ 7x1＋x2