使用MATLAB實現(xiàn)分枝定界法求解整數(shù)規(guī)劃的詳細(xì)資料說明

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

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

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

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

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

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

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

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