整數規(guī)劃學習教案

1、會計學1整數整數(zhngsh)規(guī)劃規(guī)劃 第一頁，共82頁。nInteger ProgrammingIP）和線性規(guī)劃一樣屬于運籌學中數學規(guī)劃的一個分支，其研究的問題包括整數線性規(guī)劃和整數非線性規(guī)劃n整數規(guī)劃是從1958年由R. E. Gomory提出割平面法之后形成獨立分支的。之后在該領域雖然也發(fā)展出諸如分枝定界法和割平面法等主流方法，但它仍是數學規(guī)劃中稍弱的一個分支，目前的方法僅適合解中等規(guī)模的整數線性規(guī)劃問題，而對于大規(guī)模整數線性規(guī)劃和整數非線性規(guī)劃問題，還沒有成熟的辦法n整數規(guī)劃的分類n純整數規(guī)劃：全部設計變量都取整數n混合整數規(guī)劃：部分設計變量取整數n0-1規(guī)劃：設計變量僅取0或l兩個

2、值第1頁/共82頁第二頁，共82頁。n由對每個j種貨物收費為cj，可知載貨的總收入為：n該例的目標即使得目標函數f最大化。綜合上述分析可得如下整數(zhngsh)規(guī)劃問題：1nj jja xb=1nj jjfc x=11(1,2,. . . , )m axs. t.0,nj jinj jjjjnfc xa xbx= 且取整數值第2頁/共82頁第三頁，共82頁。j=0,1,n)。那么應當如何選擇新廠廠址，鐵礦所開采出來的鐵礦石又當如何分配給兩個鋼鐵廠，才能使每年的總費用（固定運營費用和煤的運費）最低？n鋼鐵廠B0每年需要用鐵p0，而且今后該地區(qū)m座鐵礦將全部用于支持這兩個鋼鐵廠的生產，故新的鋼鐵

3、廠每年用鐵量p為該m座鐵礦的總產量減去B0的用鐵量：nn令設計變量為vi，若vi=1則表示選擇Bi作為新廠廠址，否則vi=0：01miipap=-1(1,2,. . . , )iiiBvinB=作為新廠廠址不作為新廠廠址0第3頁/共82頁第四頁，共82頁。別對其供應量的總和，即：n同樣的，對于備選廠Bj，可知其鋼鐵的用量為p，且由m座鐵礦供應，由于備選廠址只有一座，故在p前面需要乘以系數vj，即代表如果選擇Bj為備選廠址，則用鐵礦，否則，則該廠不存在，不需要使用鐵礦，此時，對應的xij將全部(qunb)取零值，故：n由Ai向Bj鋼鐵的運輸量均為非負實數n備選的鋼鐵廠只有一處0101mnnij

4、ijj jijjfc xrvv=+邋0(1,2,. . . , )nijijxaim=001miixp=1(1,2,. . . , )mijjixpvjn=0 (1,2,. . . , ;0,1,. . . , )ijximjn蕹=11njjv=第4頁/共82頁第五頁，共82頁。0101000111m i ns. t.(1,2,. . . , )(1,2,. . . , )1(01)0 (1,2,. . . , ;0,1,. . . , )mnnij ijj jijjnijijmiimijjinjjjijfc xrvvxaimxpxpvjnvvximjn=+= 邋取 或第5頁/共82頁第六頁，

5、共82頁。購買，這些可選包裝袋的容積和其對應物品在A地的價格如表所示。n試根據上述信息(xnx)給出一個合理的打包方案。n在這個問題中，我們需要確定的是，選帶哪幾個可選的包裝袋，且將必帶物品和選帶物品放到哪個旅行包中。為此我們設第i個包裝袋是否放在第j個旅行包中，并以此作為設計變量。同時，設第i個包裝袋的容積可以用wi (i=1,2,3,15)來表示，可選包裝袋對應的價格用pi (i=8,9,10,15)來表示。由于第i個包裝袋要么在第j個旅行包中，要么在要么不在，故設只取0和1，且表述如下：物品12345678容積2.545.54.83.71.67.54.5價格205010575558020

6、01001(1,2,. . . ,15;1,2,3)ijijxijij= 包裝袋 在旅行包 中0包裝袋 不在旅行包 中第6頁/共82頁第七頁，共82頁。必有一個取值為1，另外兩個取值為0，其和為1。根據上述分析，對于7件必帶的包裝袋必須滿足如下約束：n對于可選的包裝袋，則其要么在某個旅行包中，要么不在旅行包中，設包裝袋的編號為i，如果它在某個旅行包中，則設計變量xi1、xi2和xi3取值之和為1，如果它不在旅行包之中，則設計變量xi1、xi2和xi3取值之和為0，故對于可選的包裝袋必須滿足如下約束：151(1,2,3)i ijjiw xrj=311(1,2,. . . ,7)ijjxi=311

7、(8,2. . . ,15)ijjxi=第7頁/共82頁第八頁，共82頁。310ijjx=311iijjpx=驏-桫153811iijijfpx=驏=-桫邋153811513131m i n1s. t.(1,2,3)1(1,2,. . . ,7)1(8,2. . . ,15)1,0 (1,2. . . ,15,1,2,3)iijiji ijjiijjijjijfpxw xrjxixixij=驏=-桫= 邋第8頁/共82頁第九頁，共82頁。n上述形式是仿照線性規(guī)劃中的標準型給出的，其中設計變量x為n維的列向量，c為n維的行向量，A為mn的矩陣，且A行滿秩，b為m維列向量。n在模型中，(1)可以是

8、最大化也可以是最小化，對于約束(2)，可以是等式的形式也可以是不等式的形式。對于對設計變量的約束(3)，如果要求x全部分量為整數，則為純整數規(guī)劃；如果要求x的部分分量為整數，則為混合整數規(guī)劃，如果要求x分量的取值只能為0和1，則為0-1規(guī)劃。m ax(1)s. t.(2)0,(3)f= cxcxA xbA xbx x且全部或者部分取整數值第9頁/共82頁第十頁，共82頁。五入法取得其整數解？但事實證明，這樣經過四舍五入的結果甚至不是問題的可行解n可行否n枚舉法隨著變量維數增加呈指數增長，不可行！n四舍五入可能都不是可行解，不可行！12*1212*12m ax58915s. t.644 2 45

9、9451654,0,Tfxxxxxxfx x=+輊=+犏臌揶=+=x xx x且取整數值四舍五入后的解不是四舍五入后的解不是(b shi)可行解！可行解！第10頁/共82頁第十一頁，共82頁。x情況在解決實際問題的過程中一般還是比較少見的。n對于整數規(guī)劃問題的解法，一般有利用分解技術的算法和不利用分解技術的算法n利用分解技術的算法有分枝定界(dn ji)法和針對0-1規(guī)劃的隱枚舉法n不利用分解技術的算法為割平面法和群論方法n針對特定的問題還有特定的簡化方法，例如求解分派問題的匈牙利方法，等等。第11頁/共82頁第十二頁，共82頁。xj=0和xj=1分解成兩個問題之和。n松弛n凡是放棄問題P的某

10、些約束后所得到的問題Q都稱為P的松弛問題。通常的松弛方式是放棄設計變量的整數約束，若P是整數規(guī)劃，則Q就是線性規(guī)劃。n由于對于P的任何松弛問題Q，都有，故問題P與其松弛問題Q之間的關系(gun x)為：n若Q沒有可行解，則P也沒有可行解；n對于最大化的目標函數而言， P的最大值小于或者等于Q的最大值，對于最小化的目標函數而言，P的最小值大于或者等于Q的最小值；n如果Q的一個最優(yōu)解x是P的可行解，則x也是P的一個最優(yōu)解。1( )( )( )()(1,1,)miiijF PF PF PF Pimjmij=疲( )( )F PF Q第12頁/共82頁第十三頁，共82頁。或者等于f*，則說明Pi中沒有

11、比x*更好的可行解，因此可將Pi從P的分解表上刪去(shn q)；n如果Qi的最優(yōu)解是Pi的可行解，則已求得Pi的最優(yōu)解，故無須進一步考慮Pi，可從表上刪去(shn q)，若Pi的最優(yōu)解比x*好，則以Pi的最優(yōu)解代替x*n如果分解表上各個Qi的目標函數值均不大于x*，則x*便是P的一個最優(yōu)解n求解整數規(guī)劃的步驟n首先按照某種方式確定P的松弛問題Q，若Q無可行解則P也無可行解，若Q的最優(yōu)解為P的可行解，則也是P的最優(yōu)解。若Q的最優(yōu)解不是P的可行解，則要么以一種更好的方式確定松弛問題Q，繼續(xù)探測P，要么將P分解成為幾個子問題之和，然后逐個探測，當某個子問題已被探明時，就從表中刪除，否則繼續(xù)對子問題

12、進行分解第13頁/共82頁第十四頁，共82頁。界，在最大化目標函數值時為上界，在最小化目標函數值是下界n如果在求解過程中已經找到一個整數解，則最優(yōu)整數解一定不會劣于該整數解，因此，它也是最優(yōu)目標函數值的一個界，在最大化目標函數值時為下界，在最小化目標函數值是上界n如果用f表示Q的最優(yōu)值，用fi表示已經找到的最佳整數解的最優(yōu)值，f*為P的最優(yōu)值，lb表示下界，ub表示上界，則對于最大化目標函數的問題，一定存在關系，而對于最小化目標函數的問題，則為n，分枝定界法的思想就是不斷降低上界，提高下界，最后使得下界接近或者等于上界，通過這個方法來縮小搜索的范圍，進而找到問題的最優(yōu)整數解。*il bfffu

13、b=*il bfffub=第14頁/共82頁第十五頁，共82頁。若不滿足整數要求則繼續(xù)向下進行分枝，可以形成一個分枝樹。n定界與剪枝：通過不斷的分枝和求解各個子問題，分枝定界法將不斷修正上下界。上界通常由子問題的最大目標函數值確定，而下界則由已經得到的最優(yōu)的整數解來確定。n求解任何一個（子）問題都有可能出現(chxin)以下結果：n無可行解，此時無需繼續(xù)向下分枝；n得到一個整數解，則不必繼續(xù)向下分枝，如果該整數解是目前得到的最好的整數解，則被記錄下來，并用它的值作為新的下界；n得到一個非整數解，如果目標函數值大于剪枝界，則繼續(xù)向下分枝，否則該子問題被剪枝n按照上述步驟搜索迭代，在每次搜索的過程

14、中，每當下界被修改以后，都應檢查所有的還沒有求解過的子問題并剪去那些目標函數值小于新的下界的子問題，此時如果沒有找到任何整數解，則該問題沒有整數解；否則。搜索過程中已經得到的最優(yōu)的整數解就是該問題的最優(yōu)解。第15頁/共82頁第十六頁，共82頁。第16頁/共82頁第十七頁，共82頁。n廣度優(yōu)先搜索n始終選擇由最大目標函數值的子問題繼續(xù)向下分枝，在搜索的過程中，如果某子節(jié)點的上界小于當前原問題的某一可行解的值，則將該子節(jié)點刪去不再進行分枝。因為它每次都以最大上界的子問題進行處理，故用該搜索方法(fngf)找到整數解的質量較高，缺點是該方法(fngf)要在整個分枝樹上搜索，故存儲空間比深度優(yōu)先搜索大

15、，求解時間也較長。n預估法n利用一些先驗知識和相關技巧預先估計還未求解過的子問題的最好可能整數解，并選擇最好預估值的子問題向下分枝，該方法(fngf)是上述兩種方法(fngf)的折中選擇。第17頁/共82頁第十八頁，共82頁。第18頁/共82頁第十九頁，共82頁。Step1求P的松弛線性規(guī)劃問題Q，若Q無可行解，則P也無可行解，算法結束；若其最優(yōu)解符合整數條件，則找到最優(yōu)解，算法結束，若不滿足轉(2)Step2按照分枝節(jié)點和分枝變量的原則選擇不符合整數約束條件的設計變量xi=bi，令bi為bi的整數部分（向下取整），構造兩個互斥的約束條件xibi和xibi+1，形成兩個整數規(guī)劃子問題P1和P2

16、，轉Step3Step3求解P1和P2的松弛線性規(guī)劃問題Q1和Q2，則根據如下情況進一步求解：(1)Q1無可行解，Q2無可行解，則整數規(guī)劃P無可行解，算法結束；(2)Q1無可行解，Q2有整數解，則該解為P的最優(yōu)解，算法按結束；(3)Q1無可行解，Q2有非整數解，則對Q2進行分枝轉Step2(4)Q1有整數解，Q2有整數解，則較優(yōu)的一個為P的最優(yōu)解，算法結束；(5)Q1有整數解且目標函數值優(yōu)于Q2，Q2有非整數解，則Q1的整數解為P的最優(yōu)解(6)Q1有整數解，Q2有非整數解且目標函數值優(yōu)于Q1，則Q1停止分枝，其整數解為新的界，對Q2轉Step2(7)Q1無整數解，Q2也無整數解，可以按照設定的

17、規(guī)則選取一枝先進行分枝計算，其中一枝若計算得到的最優(yōu)解為整數解，且最優(yōu)值優(yōu)于另一枝，則所得的整數解就是P的最優(yōu)解，無須對另一枝進行分枝；若得到的最優(yōu)值劣于另一枝，則對另一枝進行分枝轉Step2第19頁/共82頁第二十頁，共82頁。斥的約束條件x11和x12，那么加入該組互斥條件的作用在于：排除了區(qū)間(1,2)之內的非整數解，縮小了搜索的范圍；形成了整數規(guī)劃(guhu)P的兩個子問題P1和P2121212212m ax421s. t.421121,0,fxxxxxxxx x=+- + 且取整數值3522TQx輊=犏臌()1212121211211m ax421s. t.4211211,0,351

18、22TQQfxxxxxxPxxx xxf=+-+輊=犏臌且取整數值松弛問題的最優(yōu)解，()1212122211222m ax421s. t.4211212,0,37222TQQfxxxxxxPxxx xxf=+-+輊=犏臌且取整數值松弛問題的最優(yōu)解，第20頁/共82頁第二十一頁，共82頁。()12121223211233m ax421s. t.42112112,0,913144TQQfxxxxxxxPxxx xxf=+-+ 輊=犏臌且取整數值松弛問題的最優(yōu)解，()12121242112444m ax421s. t.421122,0,fxxxxxxPxxx xQPP=+-+且取整數值松弛問題無可行

19、解，故也無可行解，停止對的分枝第21頁/共82頁第二十二頁，共82頁?，F在我們已經在P2的分枝上找到了一組整數解，現在比較fQ5和fQ1，由于現在已有整數解的目標函數值fQ5大于fQ1，而P1的最優(yōu)目標函數值不會大于fQ1，故該分枝的解不會對目標函數值有任何的改善，所以對P1進行剪枝(jin zh)，即停止對P1的向下分枝，我們已經搜索到了的最優(yōu)解。這里需要注意的，如果我們發(fā)現已經求得整數解的最優(yōu)值fQ5要小于fQ1，則P的上界還并未確定，于是問題還需要繼續(xù)分解下去。()12121225211255m ax421s. t.4211211= 2,0,213TQQfxxxxxxxPxxx xxf=

20、+-+ 輊=犏臌且取整數值松弛問題的最優(yōu)解，()12121226211266m ax421s. t.42112113,0,fxxxxxxxPxxx xPP=+-+ 且取整數值無可行解，停止對的分枝第22頁/共82頁第二十三頁，共82頁。第23頁/共82頁第二十四頁，共82頁。第24頁/共82頁第二十五頁，共82頁。nn隱枚舉法和窮舉法不同，窮舉法需要(xyo)將所有可行的變量組合逐個列舉，而隱枚舉法通過試探、分析和判斷，排除了許多變量組合作為最優(yōu)解的可能性。也就是說，它們被隱含枚舉了，這也是稱其為隱枚舉法的原因n隱枚舉法的實質n從算法描述可以看出，隱枚舉法的實質也是分枝定界法，隱枚舉法在求解過

21、程中與一般的分枝定界法不同之處只在于在分枝產生子問題時變量被固定為0或1，而不是兩個范圍之值的形式。第25頁/共82頁第二十六頁，共82頁。n數中各設計變量前面的系數變成正數，此時，取可知，于是原目標函數變?yōu)椋簄由于變量代換而產生的常數項可以從目標函數中分離出去，并不影響原問題的最優(yōu)解n當約束為“”形式時，將不等式兩端乘以(-1)變?yōu)椤啊眓當約束為“=”形式，例如Ax=b 則將其轉化為兩個不等式Axb和Axb，而后將Axb轉化成為-Ax-b。即通過加入兩個不等式約束Axb和Ax-b將其轉化成為標準型11m i n(0)s. t.(1,2,. . . , )01(1,2,. . . , )ni

22、iiinij jijjfc xca xbimxjn= 或1jjxx =-j jjj jc xcc x=-jjcc = -0jci ij jjijfc xc xc=+第26頁/共82頁第二十七頁，共82頁。第27頁/共82頁第二十八頁，共82頁。n然后對針對各個分枝進行試探，轉(4);n (4) 檢查已有的子問題，如果有某一個子問題滿足下列(xili)條件之一，就可對該子問題n進行剪枝，即該子問題停止向下分枝，可以在分枝樹中用相應的符號來表示，n例如等。此時繼續(xù)檢查其他子問題，轉(3);n試探解為自由變量均取0值、固定變量取設定值，若滿足所有約束條件，則為可行解，該解對應的目標函數值為P的目標函

23、數值的一個上界，同時該子問題停止向下分枝；n若該子問題所有試探解均不是可行解，即自由變量任取0或1時，都不能滿足某一個或者多個約束條件，則該子問題無可行解，也停止向下分枝；n設自由變量均取0值與固定變量的值一起代入目標函數，得到的目標值為f，此時對應的自由變量的系數為列向量c，若f與c中任一分量的和大于已經記錄的上界中的最小值，則說明在該子問題中固定任何自由試探解不是P的可行解，且此時所有變量均已設為固定變量，則該子問題也應該被剪枝，停止向下分枝。n變量都不可能對P的最優(yōu)值有所改善，已無更好的可行解，則該子問題被剪枝，停止向下分枝；第28頁/共82頁第二十九頁，共82頁。第29頁/共82頁第三

24、十頁，共82頁。n (2) 令所有設計變量為0，試探解x=0 0 0 0T不是P的可行解，需要分枝n (3) 按照(nzho)目標函數中各設計變量的系數從大到小的順序來選擇分枝固定變量，即以n x1、x4、x3、x2的順序設置固定變量進行問題的試探1234123412341234423m ax20689s. t.10652197224112101201(1,2,3,4)ifxxxxxxxxxxxxxxxxxxxxi=+= 或1234123412341234234m i n20689s. t.106524722442102101(1,2,3,4)ifxxxxxxxxxxxxxxxxxxxxi=+

25、- - - -+-=或第30頁/共82頁第三十一頁，共82頁。第31頁/共82頁第三十二頁，共82頁。第32頁/共82頁第三十三頁，共82頁。nn由于分派問題屬于0-1規(guī)劃，故我們可以用隱枚舉法進行求解，但是鑒于上述問題的特殊性，可以有更簡便的方法求解此類問題，由于這種方法是基于(jy)匈牙利數學家狄柯尼格（D Knig）證明的兩個定理而發(fā)展的，故稱之為匈牙利法。第33頁/共82頁第三十四頁，共82頁。n需要(xyo)注意的是，標準型中要求的是最小化目標函數的值，且對應于各設計變量的系數均不小于零。這是應用匈牙利算法的前提條件。10ijijijx=當指派第 個人去完成第 個任務時當不指派第 個

26、人去完成第 個任務時1111m i ns. t.1 (1,2,. . . , )1 (1,2,. . . , )01 (1,2,. . . , ;1,2,. . . , )nnij ijijnijjnijiijfE xxinxjnxin jn= = 邋或第34頁/共82頁第三十五頁，共82頁。n令 , 其中M是足夠大的常數，一般方法是令M為效率矩陣元素Eij中的最大值，即，由于對于任意的i,j (i=1,2,n; j=1,2,n)均可滿足max(Eij)-Eij0，故可以保證Fij0，這時，系數矩陣變?yōu)椋篎=(Fij)，且滿足Fij0，對應效率矩陣F的分派問題的目標函數滿足：n顯然可以表達成為

27、，因為nM為一常數，故當f 取得最小值時，可以取到最大值，即通過這種變換將原分派問題目標函數由最小化變成最大化，以符合匈牙利法的實施條件。1m nm nxx=-m nm nm nm nm nExEEx=-m nm nEE= -0m nE( , ) ( , )ij ijm nm nm nijm nfE xExE=+11m axnnij ijijfE x=邋ijijFME=-m ax() (1,2,. . . , ;1,2,. . . , )ijMEin jn=()111111nnnnnnij ijijijij ijijijijfF xMExnME x=-=-邋邋邋fnMf=-第35頁/共82頁第

28、三十六頁，共82頁。n來獲得分派問題的最優(yōu)解。在匈牙利法中，要求矩陣E的所有元素(yun s)均為非負，即Eij0。其基本的思想就是如果在矩陣E中存在一組（n個）位于不同行且不同列的零元素(yun s)，則最優(yōu)方案就是令對應于這些零元素(yun s)位置的xij=1，其他位置的xij=0。但是很顯然的，我們建立的分派模型的效率矩陣E中幾乎沒有零元素(yun s)，要實現上述設想就必須找到合適的方法對矩陣E進行變換，來獲得這一組位于不同行且不同列的零元素(yun s)。111212122212nnnnnnEEEEEEEEE輊犏犏犏=犏犏犏犏犏臌E ELLMMOML第36頁/共82頁第三十七頁，共

29、82頁。一列）各元素分別減去該行（或該列）的最小元素，由此得到的新的效率矩陣F，則分別對應于E和F的兩個分派問題的最優(yōu)解等價n引理2：若矩陣E的元素可以分成“0”元素和“非0”元素兩部分，則覆蓋所有“0”元素的最少直線（將直線上的元素全部劃去之后矩陣就不再有“0”元素，這樣所需直線數的最小值）等于位于不同行且不同列的“0”元素的最大個數。n根據上面的結論，用匈牙利法求解分派問題的原理即通過對原效率矩陣E各行各列元素的同加或者同減運算，構造出等價最優(yōu)解的效率矩陣F，且F的所有元素非負且具有n個不同行且不同列的“0”元素。這樣，n個“0”元素所對應的人做對應的工作就是分派問題的最優(yōu)解11nniji

30、juv=+邋第37頁/共82頁第三十八頁，共82頁。n元素，使得每一列都至少(zhsho)出現一個0元素n如果某行或者某列已經有零元素，則不必再減n對例題中的E，操作如下：44114141m i ns. t.1 (1,2,3,4)1 (1,2,3,4)01ij ijijijjijiijfE xxixjx= 邋或20123326221529232113312422163223輊犏犏犏=犏犏犏犏臌E E(I)(II)2012332680211420772215292370148100121133124801811204422163223601670020輊輊輊犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏犏

31、犏犏臌臌臌uuuuuruuuuuu r第38頁/共82頁第三十九頁，共82頁。元素，反復進行，直到所有0元素都已被標記為止。n(V)若(0)元素的數目m等于矩陣的階數n，那么這指派問題的最優(yōu)解已經找到，若mn，轉下一步(I)(II)2(0)7720772(0) 7710011011(0)1204424424400200202(0)輊輊輊犏犏犏犏犏犏哪犏犏犏犏犏犏哪犏犏犏犏犏犏犏犏犏哪犏臌臌臌uuuuuruuuuuu r第39頁/共82頁第四十頁，共82頁。n移動0元素n在未被劃去的元素中找出最小元素s，將其作為(zuwi)矩陣變換的調整量；n將標記“*”行的所有元素都減去sn將標記“*”列的所

32、有元素都加上sn結果將得到一個新的效率矩陣，轉第二步。(a)(b)(c)2(0)772(0)772(0)772(0)77*1(0)11(0)11(0)11(0)1244244*244*244*2(0)2(0)2(0)2(0)*第40頁/共82頁第四十一頁，共82頁。(b)(c)005520770255100110011001002220440222002000200020-輊輊輊犏犏犏犏犏犏犏犏犏犏犏犏-犏犏犏犏犏犏犏犏犏臌臌臌uuuuuu ruuuuur12(0)551(0)1:(0)22005510012(0)0022(0)5500201(0)1:(0)222(0)MM扉涅犏犏犏犏犏輊犏犏

33、犏犏哪犏犏臌犏檳犏犏犏犏犏犏臌犏犏 犏犏哪犏 鈹試指派第41頁/共82頁第四十二頁，共82頁。第42頁/共82頁第四十三頁，共82頁。做了簡單的修改，將其選擇分枝變量的算法由自然序改造成分枝變量選擇原則中的一種，即：選擇與整數值相差最大的非整數變量首先進行分枝n調用格式nx,fval,exitflag=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 第43頁/共82頁第四十四頁，共82頁。n列向量，A為m1n維矩陣，Aeq為m2n維矩陣。n輸入參數(cnsh)有c,A,b,Aeq,beq,lb,ub,M和TolXInteger。其中c為目標函數所對應設計變

34、量的系數，A為不等式約束條件方程組構成的系數矩陣，b為不等式約束條件方程組右邊的值構成的向量。Aeq為等式約束方程組構成的系數矩陣，beq為等式約束條件方程組右邊的值構成的向量。lb和ub為設計變量對應的上界和下界。M為具有整數約束條件限制的設計變量的序號，例如問題中設計變量為x1, x2, x6，要求x2, x3和x6為整數，則M=2;3;6；若要求全為整數，則M=1:6，或者M=1;2;3;4;5;6。TolXInteger為判定整數的誤差限，即若某數x和最鄰近整數相差小于該誤差限，則認為x即為該整數。n輸出參數(cnsh)有x, fval和exitflag。其中x為整數規(guī)劃問題的最優(yōu)解向

35、量，fval為整數規(guī)劃問題的目標函數在最優(yōu)解向量x處的函數值，exitflag為函數計算終止時的狀態(tài)指示變量。m i ns. t.0 (1,2,. . . , )()TeqeqijfxinxjM= c xc xA xbA xbAxbAxbl bxubl bxub取整數值第44頁/共82頁第四十五頁，共82頁。%整數規(guī)劃的整數規(guī)劃的MATLAB實現實現%Originally Designed By Sherif A. Tawfik,Revised By LiMing, 2009-12-29%函數調用形式函數調用形式x,fval,exitflag=intprog(f,A,b,Aeq,beq,lb,

36、ub,M,TolXInteger)%函數求解如下形式的整數規(guī)劃問題函數求解如下形式的整數規(guī)劃問題%min f*x%subject to% A*x=b% Aeq*x=beq% lb=x=ub% M存儲有整數約束的變量編號的向量存儲有整數約束的變量編號的向量% TolXInteger是判定整數的誤差限是判定整數的誤差限%函數返回變量函數返回變量%x:整數規(guī)劃的最優(yōu)解整數規(guī)劃的最優(yōu)解%fval:目標函數在最優(yōu)解處的函數值目標函數在最優(yōu)解處的函數值%exitflag =1 收斂到解收斂到解x% 0 達到線性規(guī)劃的最大迭代次數達到線性規(guī)劃的最大迭代次數% -1 無解無解%function x,fval,

37、exitflag=intprog(f,A,b,Aeq,beq,lb,ub,M,TolXInteger)%設置不顯示求解線性規(guī)劃過程中的提示信息設置不顯示求解線性規(guī)劃過程中的提示信息options = optimset(display,off);%上界的初始值上界的初始值bound=inf; %求解原問題求解原問題P0的松弛線性規(guī)劃的松弛線性規(guī)劃Q0，首先，首先(shuxin)獲得問題的初始解獲得問題的初始解x0,fval0=linprog(f,A,b,Aeq,beq,lb,ub,options); %利用遞歸法進行二叉樹的遍歷，實現分枝定界法對整數規(guī)劃的求解利用遞歸法進行二叉樹的遍歷，實現分枝

38、定界法對整數規(guī)劃的求解x,fval,exitflag,b=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);第45頁/共82頁第四十六頁，共82頁。%分枝定界法的遞歸算法分枝定界法的遞歸算法,x為問題的初始解，為問題的初始解，v是目標函數在是目標函數在x處的取值處的取值function xx,fval,exitflag,bb=rec_BranchBound(f,A,b,Aeq,beq,lb,ub,x,v,M,TolXInteger,bound)options = optimset(display,off);%求解

39、不考慮整數約束的松弛線性規(guī)劃求解不考慮整數約束的松弛線性規(guī)劃x0,fval0,exitflag0=linprog(f,A,b,Aeq,beq,lb,ub,options);%如果算法結束狀態(tài)指示變量為負值，即表示無可行解，返回初始輸入如果算法結束狀態(tài)指示變量為負值，即表示無可行解，返回初始輸入%或者所目標函數值大于已經獲得的上界或者所目標函數值大于已經獲得的上界(shngji)，返回初始輸入，返回初始輸入if exitflag0bound xx=x; fval=v; exitflag=exitflag0; bb=bound; return;end%確定所有變量是否均為整數，如是，則返回確定所有

40、變量是否均為整數，如是，則返回ind=find(abs(x0(M)-round(x0(M)TolXInteger); %該條件表示該條件表示x0(M)不是整數不是整數%如果都是整數如果都是整數if isempty(ind) exitflag=1;%如果當前的解優(yōu)于已知的最優(yōu)解，則將當前解作為最優(yōu)解如果當前的解優(yōu)于已知的最優(yōu)解，則將當前解作為最優(yōu)解 if fval0flag br_var=tempbr_var; br_value=tempbr_value; flag=temp_flag; endendif isempty(A) r c=size(Aeq);else r c=size(A);end

41、第47頁/共82頁第四十八頁，共82頁。%第第1個子問題的設置個子問題的設置,添加約束條件添加約束條件Xi=ceil(Xi) ，i即為上面找到的最接近即為上面找到的最接近(jijn)整數的非整數設計變量的序號整數的非整數設計變量的序號 A2=A;zeros(1,c);A2(end,br_var)=-1;b2=b;-ceil(br_value); %分枝后的第一個子問題的遞歸求解分枝后的第一個子問題的遞歸求解x1,fval1,exitflag1,bound1=rec_BranchBound(f,A1,b1,Aeq,beq,lb,ub,x0,fval0,M,TolXInteger,bound);e

42、xitflag=exitflag1;if exitflag10 & bound10 & bound2=20000(1,2,3,4)iixvi=1iiiisxrs-+=+第72頁/共82頁第七十三頁，共82頁。n為了增加數學模型的可讀性，我們作一個簡單(jindn)的變量代換，將s1s4用x5x8代表，將v1v4用x9x12代表。可得該問題的整數規(guī)劃數學模型為下一頁所示。()4110m i n2000050010s. t.20000(1,2,3,4)(1,2,3,4)0;0 (1,2,3,4)0(1,2,3,4)0,1 (1,2,3,4)iiiiiiiiiiiiifvxsxvisxrsissixivi=-=+=+=+= 且取整數值第73頁/共82頁第七十四頁，共82頁。()44811525636747819210311412m i n5001020000s. t.15002000400010002000002000002000002000000(1,2,. . . ,8)0,1 (9,10,11,12)iiiiijfxxxxxxxxxxxxxxxxxxxxxxxixj+=+-=+-=+-=+-=-=且取整數值第74頁/共82頁第七十五頁，共82頁。n如果某些設計變量為整數，則在intprog中我們可以通過設置M向量的值來將某些變量設置為整數值，即