分支定界演算法流程圖

A. 分支定界法的演算法步驟

(1)求整數規劃的鬆弛問題最優解。
(2)若鬆弛問題的最優解滿足整數要求，得到整數規劃的最優解，否則轉下一步。
(3)任意選一個非整數解的變數 ，在鬆弛問題中加上約束 及 +1組成兩個新的鬆弛問題，稱為分支。新的鬆弛問題具有如下特徵：當原問題是求最大值時，目標值是分支問題的上界；當原問題足求最小值時，目標值是分支問題的下界。
(4)檢查所有分支的解及目標函數值，若某分支的解是整數並且目標函數值大於(max)等於其他分支的目標值，則將其他分支剪去不再計算，若還存在非整數解並且目標值大於( max)整數解的目標值，需要繼續分支，再檢查，直到得到最優解。