分支定界法是一種求解離散最優(yōu)化問題的計(jì)算分析方法。它是由Land Doig和Dakin等人在20世紀(jì)60年代初提出的。分支定界法可求純整數(shù)或混合整數(shù)線性規(guī)劃問題，求解方法由分支和定界組成?！胺种А睘檎麛?shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件，而“定界”則可以提高搜索的效率。用MATLAB編寫程序，通過計(jì)算機(jī)來完成這一復(fù)雜的過程。

　　這種方法通常僅需計(jì)算和分析部分允許解，即可求得最優(yōu)解，而且這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。

　　整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃的重要分支之一，是離散最優(yōu)化的基礎(chǔ)和重要組成部分．整數(shù)規(guī)劃模型和算法在管理科學(xué)，經(jīng)濟(jì)，金融工程， 工業(yè)管理和其它領(lǐng)域有廣泛的應(yīng)用， 是近年來國際運(yùn)籌學(xué)和最優(yōu)化研究的熱點(diǎn)之一．整數(shù)規(guī)劃的應(yīng)用范圍也是極其廣泛的．它不僅在工業(yè)和工程設(shè)計(jì)和科學(xué)研究方面有許多應(yīng)用，而且在計(jì)算機(jī)設(shè)計(jì)、系統(tǒng)可靠性、編碼和經(jīng)濟(jì)分析等方面也有新的應(yīng)用．

　　分支界法是目前求解整數(shù)規(guī)劃的成功方法之一，是一種系統(tǒng)化的解法．目前已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等．分枝界限法的思想能夠使用在混合整數(shù)規(guī)劃問題上，也適用于幾乎任何組合最優(yōu)化問題．

　　在許多實(shí)際問題中我們所研究的量具有不可分割的性質(zhì)，如人數(shù)、機(jī)器數(shù)、項(xiàng)目數(shù)等；而開與關(guān)、取與舍、真與假等邏輯現(xiàn)象都需要用取值僅為0和1的變量來數(shù)量化的描述．涉及這些量的線形規(guī)劃問題，非整數(shù)的解答顯然不合乎要求．

　　分支定界法以一般線性規(guī)劃之單形法解得最佳解后，將非整數(shù)值之決策變量分割成為最接近的兩個(gè)整數(shù)，分列條件，加入原問題中，形成兩個(gè)子問題（或分枝）分別求解，如此便可求得目標(biāo)函數(shù)值的上限（上界）或下限（下界），從其中尋得最佳解．

　　分支定界法是一個(gè)用途十分廣泛的算法，運(yùn)用這種算法的技巧性很強(qiáng)，不同類型的問題解法也各不相同．分支定界法的基本思想是對(duì)有約束條件的最優(yōu)化問題的所有可行解（數(shù)目有限）空間進(jìn)行搜索．該算法在具體執(zhí)行時(shí)，把全部可行的解空間不斷分割為越來越小的子集（稱為分支），并為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界（稱為定界）．在每次分支后，對(duì)凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支．這樣，解的許多子集（即搜索樹上的許多結(jié)點(diǎn)）就可以不予考慮了，從而縮小了搜索范圍．這一過程一直進(jìn)行到找出可行解為止，該可行解的值不大于任何子集的界限．因此這種算法一般可以求得最優(yōu)解．

　　將問題分枝為子問題并對(duì)這些子問題定界的步驟稱為分支定界法．