隱式枚舉法

隱式枚舉法( implicit enumeration method)
一種特殊的分支定界法。對0 -1規劃問題,利用變數只能取0或l的兩個值的特性,進行分支定界,以達到最優解。通過變數的變換,使目標函式中的係數全為非正,首先令全部變數取0,得到上界,若可行,這次解為最優解,計算終止;否則,有選擇地指定其中某個變數為0或1,並把它們固定下來,將問題分解為兩個子問題,然後分別對它們進行檢驗,或者停止分支,修改下界,或者把子問題再分支,直到分支到全部子問題,而以其中最大的下界值所對應的可行解為最優解。

相關詞條

熱門詞條

聯絡我們