分支定界算法由Land等劍在⒛世紀ω年代提出,是最為流行的規(guī)劃方法之一,其應(yīng)用非常廣泛。FBMH1608HM102-T它的基本思想是先求出整數(shù)規(guī)劃問題A所對應(yīng)的線性規(guī)劃問題B的最優(yōu)解,如果該解不符合A的整數(shù)條件,那么B的最優(yōu)目標函數(shù)必是A最優(yōu)目標函數(shù)的上界,而A的任意可行解的目標函數(shù)值是其最優(yōu)值的下界。然后將B的可行域分成子區(qū)域(稱為分支),逐步減少上界和增大下界,最終求得最優(yōu)解。

    分支定界算法目前己經(jīng)成功地應(yīng)用于求解整數(shù)規(guī)劃問題、旅行商問題(Travelingsalesman Problem)、制訂與優(yōu)化生產(chǎn)計劃問題、設(shè)施選址問題、背包問題(鼬apsaGkProblem)等。對于不同問題,分支與界限的步驟和內(nèi)容可能不同,但其求解問題的基本思想是相似的。