分支定界算法是求組合優(yōu)化問題最優(yōu)解的常用方法,它實際上是一種隱枚舉技術(shù):首先, FBMH1608HM151-T它生成一個根節(jié)點,再由根節(jié)點逐層向下產(chǎn)生新的節(jié)點,每個節(jié)點代表一個部分解并根據(jù)問題性質(zhì)賦予下界值,最終形成一個枚舉樹,問題的所有可能解只能在枚舉樹的最底層節(jié)點(稱為葉節(jié)點)獲得;然后結(jié)合各節(jié)點的下界值,采用一定的搜索策略對枚舉樹進行搜索,在搜索過程中動態(tài)更新當(dāng)前問題的最優(yōu)解,在搜索完所有節(jié)點后得到問題最優(yōu)解。

   由上可知,分支定界算法求解步驟如下。

   第一步:不考慮整數(shù)約束,用單純形法求解整數(shù)規(guī)劃問題相應(yīng)的線性規(guī)劃問題。第二步:檢查判別。

   (1)若線性規(guī)劃問題無解,則原問題也無可行解。

   (2)若線性規(guī)劃問題有最優(yōu)解,則檢查其解是否滿足整數(shù)條件,若滿足,則此最優(yōu)解也就是原問題的最優(yōu)解,否則轉(zhuǎn)入第三步。

第三步:在相應(yīng)線規(guī)劃的最優(yōu)解中,任選一個不符合整數(shù)約束的變量。將其分別取灼≤3(小于勿最大整數(shù)),≥3(大于勿最小整數(shù)),分別加入相應(yīng)的線性規(guī)劃中分解成兩個線性規(guī)劃子問題。

   第四步:再用單純形法求解第三步的子問題。

   第五步:重復(fù)步驟第二步至第四步,直到得到整數(shù)解為止。

   第六步:對子問題己得到整數(shù)最優(yōu)解后,其他子問題是否要繼續(xù)求   解,則由目標函數(shù)的大小來確定。若其他問題均劣于已取得的解,則均可舍去,不再進行分支求解。