分支定界法的演算法

Ⅰ 分支定界法演算法步驟

分支定界法的演算法過程分為以下幾步:

首先，第1步是放寬或取消原問題的部分限制條件，例如針對整數解的搜索。如果由此求得的最優解仍符合原問題的可行性，那麼它即為原問題的最優解，演算法至此結束。否則，這個解的函數值將成為原問題最優解的上界。

接著，進入第2步，將放寬限制後的問題分解為多個子問題，確保這些子問題的解集合包含原問題的所有可能解。對於每個子問題，尋找其最優解。如果子問題的最優解是原問題的可行解，那麼找到了原問題的最優解，演算法結束。否則，子問題的最優解函數值成為原問題的新上界。此外，還需關注子問題中與原問題有可行解的部分，取其最大目標函數值作為下界。

第3步，對於目標函數值小於下界的問題，由於其無原問題最優解的可能性，可以舍棄。而對於目標函數值大於下界的子問題，仍然保留，進入下一輪循環。

最後，第4步是選擇所有保留子問題中目標函數值最大的一個，回到第1步，繼續執行放寬限制和子問題分解。如果找到子問題的最優可行解，將其目標函數值與所有保留子問題中最大值比較，更新下界，然後返回第3步，直到找到原問題的最優解。

Ⅱ 特徵選擇 分支定界法

分支定界 (branch and bound) 演算法是一種在問題的解空間樹上搜索問題的解的方法.但與回溯演算法不同,分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹。

分枝界限法也能夠使用在混合整數規劃問題上，其為一種系統化的解法，以一般線性規劃之單形法解得最佳解後。

將非整數值之決策變數分割成為最接近的兩個整數，分列條件，加入原問題中，形成兩個子問題(或分枝)分別求解，如此便可求得目標函數值的上限（上界）或下限（下界），從其中尋得最佳解。

分支定界法演算法分析：

1、演算法優點：可以求得最優解、平均速度快。

因為從最小下界分支，每次算完限界後，把搜索樹上當前所有的葉子結點的限界進行比較，找出限界最小的結點，此結點即為下次分支的結點。這種決策的優點是檢查子問題較少，能較快的求得最佳解。

2、缺點：要存儲很多葉子結點的限界和對應的耗費矩陣。花費很多內存空間。

存在的問題：分支定界法可應用於大量組合優化問題。其關鍵技術在於各結點權值如何估計，可以說一個分支定界求解方法的效率基本上由值界方法決定，若界估計不好，在極端情況下將與窮舉搜索沒多大區別。

Ⅲ 分支定界法的演算法步驟

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