第五章整數(shù)規(guī)劃

1、整數(shù)規(guī)劃整數(shù)規(guī)劃v整數(shù)規(guī)劃的數(shù)學模型及解的特點v解純整數(shù)規(guī)劃的割平面法*v分支定界法v0-1型整數(shù)規(guī)劃*v指派問題例1 某廠擬用集裝箱托運甲乙兩種貨物,每箱的體積、重量、可獲利潤以及托運所受限制見下表.問每集裝箱中兩種貨物各裝多少箱,可使所獲利潤最大?1 整 數(shù) 規(guī) 劃的數(shù)學模型一、問題的提出貨物/箱體積/米3重量/百斤利潤/百元甲5220乙4510托運限制/集裝箱2413表 3.1貨物/箱體積/米3重量/百斤利潤/百元甲5220乙4510托運限制/集裝箱2413解 設 分別為甲、乙兩種貨物的托運箱數(shù).則這是一個純整數(shù)規(guī)劃問題 .其數(shù)學模型為:21,xx211020maxxxZ整數(shù), 0,13

2、522445.212121xxxxxxts 在許多線性規(guī)劃問題中,要求最優(yōu)解必須取整數(shù).例如所求的解是機器的臺數(shù)、人數(shù)車輛船只數(shù)等.如果所得的解中決策變量為分數(shù)或小數(shù)則不符合實際問題的要求. 且部分或全部為整數(shù)或 n)1.2(j 0)2 .1( .)min(max11jnjijijnjjjxmibxastxcZZ二、整數(shù)規(guī)劃問題的數(shù)學模型 對于一個規(guī)劃問題,如果要求全部決策變量都取整數(shù),稱為純(或全)整數(shù)規(guī)劃;如果僅要求部分決策變量取整數(shù),稱為混合整數(shù)規(guī)劃問題.有的問題要求決策變量僅取0或l兩個值,稱為0-l規(guī)劃問題. 整數(shù)規(guī)劃簡稱為IP問題.這里主要討論的是整數(shù)線性規(guī)劃問題,簡稱為ILP問題

3、. 形線性規(guī)劃混合整數(shù)線性規(guī)劃純整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃問題10(pure integer linear programming)(mixed integer linear programming)(zero-one integer linear programming)若不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題（slack problem）且部分或全部為整數(shù)或 n)1.2(j 0)2.1( .)min(max11jnjijijnjjjxmibxastxcZZ整數(shù)線性規(guī)劃數(shù)學模型的一般形式 n)1.2(j 0)2.1( .)min(max11jnji

4、jijnjjjxmibxastxcZZ或該整數(shù)規(guī)劃問題的松弛問題三、整數(shù)規(guī)劃問題解的特點對于整數(shù)線性規(guī)劃問題,為了得到整數(shù)解,初看起來,似乎只要先不管整數(shù)要求,而求線性規(guī)劃的解,然后將求得的非整數(shù)最優(yōu)解“舍零取整”就可以了.但實際上,這個想法卻常常行不通,有時“舍零取整”后的整數(shù)解根本就不是可行解,有的雖然為可行解,卻不是最優(yōu)解 .例1 某廠擬用集裝箱托運甲乙兩種貨物,每箱的體積、重量、可獲利潤以及托運所受限制見下表.問每集裝箱中兩種貨物各裝多少箱,可使所獲利潤最大?貨物/箱體積/米3重量/百斤利潤/百元甲5220乙4510托運限制/集裝箱2413解 設 分別為甲、乙兩種貨物的托運箱數(shù).則這是

5、一個純整數(shù)規(guī)劃問題 .其數(shù)學模型為:21,xx211020maxxxZ整數(shù), 0,13522445.212121xxxxxxts（1）若暫且不考慮 取整數(shù)這一條件.則(1)就變?yōu)橄铝芯€性規(guī)劃 : 21,xx211020maxxxZ0,13522445.212121xxxxxxts（2）我們將式(2)稱為(1)的松弛問題.解(2)得到最優(yōu)解:, 8 . 4*1x, 0*2x.96*Z（3）但它不滿足(1)的整數(shù)要求.因此它不是(1)的最優(yōu)解,若把解(3)“舍零取整”,如取X1=(5,0)T,但它不是式(1)的可行解.因為它不滿足 (1) 中的約束條件。若取X2=(4,0)T，X2是 (1) 的可

6、行解, 但它卻不是(1) 的最優(yōu)解, 因為當X2=(4,0)T 時,Z2 = 80, 但當X3 = (4,1)T 時,Z3 = 90 Z2。 即伴隨規(guī)劃的最優(yōu)解通過 “ 舍零取整 ” 得到的X1,X2 都不是 (1) 的最優(yōu)解 .因此通過松弛問題最優(yōu)解的 “ 舍零取 整 ” 的辦法 , 一般得不到原整數(shù)規(guī)劃問題的最優(yōu)解 .對上面的問題，我們從幾何的角度來觀察：若松弛問題(2)的可行域 K 是有界的,則原整數(shù)規(guī)劃(1)的可行域 K 0應是K中有限個格點(整數(shù)點）的集合.見圖1, 圖中“* 為整數(shù)點(格點).圖1 中四邊形 OABC 是松弛問題(2)的可行域.它的最優(yōu)解為 C 點(4.8, 0)。

7、而 (1) 的可行域為k0 = (0,0),(0,1), (0,2), (1,0),(1, l),(1,2), (2,0), (2,1),(3,0), (3,1),(4,0),(4, l) . 將C點“舍零取整”后得到的X1=(5.0,0)T不在 K0中,而X2=(4,0)T在K0中,但不是(1)的最優(yōu)解,最優(yōu)解在B點左側（4，1）。112348 . 421x2xACBO當然, 我們也會想到能否用“窮舉法”來求解整數(shù)規(guī)劃.如(1)問題,將 K0 中所有整數(shù)點的目標函數(shù)值都計算出來,然后逐一比較找出最優(yōu)解.這種方法對變量所能取的整數(shù)值個數(shù)較少時,勉強可以應用.如本例 可取 0,1,2,3,4共5

8、個數(shù)值。而 只能取0,1,2共三個數(shù)值,因此其組合最多為15個(其中有不可行的點).1x2x但對大型問題,這種組合數(shù)的個數(shù)可能大得驚人! 如在指派問題中,有n 項任務指派n個人去完成,不同的指派方案共有n! 種 .當 n=20 時 ,這個數(shù)超過21018. 如果用窮舉法每一個方案都計算一遍 , 就是用每秒百萬次的計算機,也要幾萬年 . 顯然 “窮舉法” 并不是一種普遍有效的方法因此研究求解整數(shù)規(guī)劃的一般方法是有實際意義的. 窮舉法舍零取整求解整數(shù)規(guī)劃整數(shù)規(guī)劃解的特點整數(shù)線性規(guī)劃及其松弛問題，從解的特點上來說，二者之間既有密切的聯(lián)系，又有本質(zhì)的區(qū)別。 松弛問題作為一個線性規(guī)劃問題，其可行解的集合

9、是一個凸集，任意兩個可行解的凸組合仍為可行解。整數(shù)規(guī)劃問題的可行解集合是它的松弛問題可行解集合的一個子集，任意兩個可行解凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。由于整數(shù)規(guī)劃問題的可行解是其松弛問題的可行解的子集，所以，其松弛問題的最優(yōu)解目標函數(shù)值是整數(shù)規(guī)劃問題目標函數(shù)值的上界。 在一般情況下，松弛問題的最優(yōu)解不會剛好滿足變量的整數(shù)約束條件，因而不是整數(shù)規(guī)劃的可行解，自然也不是整數(shù)規(guī)劃的最優(yōu)解。112348 . 421x2xACBO但松弛問題的最優(yōu)解恰好滿足變量的整數(shù)約束條件，那么它必然同時是整數(shù)規(guī)劃問題和其松弛問題的最優(yōu)解。目前，常用的求解整數(shù)規(guī)劃的方法有：目前，常用的求解整數(shù)規(guī)劃

10、的方法有： l 分支定界法和割平面法；分支定界法和割平面法；l 對于特別的對于特別的01規(guī)劃問題采用隱枚舉法和匈牙利法。規(guī)劃問題采用隱枚舉法和匈牙利法。自20世紀60年代以來, 已發(fā)展了一些常用的解整數(shù)規(guī)劃的算法,如各種類型的割平面法、分枝定界法、解 0-1 規(guī)劃的隱枚舉法、分解方法、群論方法、動態(tài)規(guī)劃方法等等。近十年來有人發(fā)展了一些近似算法及用計算機模擬法,也取得了較好的效果 .背景11max1,2.01,2.1,2,.njjjnijjijjjZc xa xbims txjnxjn取整數(shù)2 解純整數(shù)規(guī)劃的割平面法考慮純整數(shù)規(guī)劃問題純整數(shù)規(guī)劃的松弛問題是一個線性規(guī)劃問題，可用單純形法求解。在松

11、弛問題的最優(yōu)單純形表中，記Q為m個基變量的下標集合，K為n-m個非基變量的下標集合，則m個約束方程可示為：QibxaxijKjiji5.4式而對應的最優(yōu)解X*=(x1*,x2*, ,xn*)，其中KjQjbxjj0*若各 皆為整數(shù)，則X* 滿足整數(shù)約束，因而就是純整數(shù)規(guī)劃的最優(yōu)解；若 不全為整數(shù)，則 X* 不滿足整數(shù)約束，因而就不是純整數(shù)規(guī)劃的可行解，自然也不是該整數(shù)規(guī)劃的最優(yōu)解。)(Qjbj)(Qjbj割平面法的基本思想：用割平面法(cutting plane approach)解整數(shù)規(guī)劃時，若其松弛問題的最優(yōu)解不滿足整數(shù)約束，則從X*的非整分量中選取一個，用以構造一個線性約束條件，將其加入

12、原松弛問題中，形成一個新的線性規(guī)劃，然后求解之。若新的最優(yōu)解滿足整數(shù)要求，則它就是整數(shù)規(guī)劃的最優(yōu)解；否則重復上述步驟，直到獲得整數(shù)最優(yōu)解為止。為最終獲得整數(shù)最優(yōu)解，每次增加的線性約束條件應當具備兩個基本性質(zhì)： 已獲得的不符合整數(shù)要求的松弛問題最優(yōu)解不滿足該線性約束條件，從而不可能在以后的解中再出現(xiàn)。 凡整數(shù)可行解均滿足該線性約束條件，因而整數(shù)最優(yōu)解始終被保留在每次形成的松弛問題（線性規(guī)劃）可行域中。我們應該怎樣構造新的約束條件？為此，若 不是整數(shù)，在（5.4）中對應的約束方程為QibxaxijKjjii00)(00Qibi其中 按假設不是整數(shù)； 可能是整數(shù)，也可能不是整數(shù)。 0ib)(0Kja

13、ji0ibjia010,)( 10,000000000000ijiiiijijijijijijijifbNfNbKjfaNfNa其中其中5.6式5.7式5.8式分解 和 成兩部分。一部分是不超過該數(shù)的最大整數(shù)，另一部分是余下的小數(shù)即將（5.7）和（5.8）式代入（5.6）式，移項以后得：KjKjjjiiijjiixffNxNx000005.9式對5.9式分別討論當前解（非整數(shù)解）和可行域中整數(shù)解的情況：對于當前解5.9式右端有1000Kjjjiixff對于整數(shù)解5.9式左端表明 為整數(shù)，又因為 本身不能 1，故Kjjjiixff00Kjjjiixff00000Kjjjiixff由此我們以 （5

14、.10式）作為標尺來，將當前不滿足整數(shù)約束的最優(yōu)解去掉，而完全保留了原整數(shù)規(guī)劃問題的可行解。000Kjjjiixff 綜上所述，線性約束條件(5.10)式具備上述的兩個性質(zhì)。將其與原整數(shù)規(guī)劃的松弛問題合并，構成一個新的線性規(guī)劃。 記R為原松弛問題可行域，R為新的線性規(guī)劃可行域。從幾何意義上看，(5.10)式實際上對R做了一次“切割”，在留下的R 中，保留了整數(shù)規(guī)劃的所有可行解，但不符合整數(shù)要求的X*被“切割”掉了。隨著“切割”過程的不斷繼續(xù)，整數(shù)規(guī)劃最優(yōu)解最終有機會成為某個線性規(guī)劃可行域的頂點，作為該線性規(guī)劃的最優(yōu)解而被解得。 割平面法在1958年由高莫瑞（R.E.Gomory）首先提出，故又

15、稱Gomory割平面法。在割平面法中，每次增加得用于“切割”的線性約束稱為割平面約束或Gomory約束. 構造割平面約束的方法很多，但（5.10）式是最常用的一種，它可以從相應線性規(guī)劃的最終單純形表中直接產(chǎn)生。實際解題時，經(jīng)驗表明若從最終單純行表中選擇具有最大分數(shù)部分的非整分量所在行構造割平面約束，往往可以提高“切割”效果，減少“切割”次數(shù)例：用割平面法求解整數(shù)規(guī)劃問題 且且為為整整數(shù)數(shù)0,023623 max2121212xxxxxxxZ解：增加松弛變量x3和x4 ，得到(LP)的初始單純形表和最優(yōu)單純形表：Cj0100CBXBbx1x2x3x40 x3632100 x40-3201j010

16、0Cj0100CBXBbx1x2x3x40 x11101/6-1/61x23/2011/41/4j00-1/4 -1/4割平面約束：34111442xx加入割平面約束后得到的新的線性規(guī)劃問題為：0,214141023623 max543215434213212xxxxxxxxxxxxxxxZ我們可用使用單純行法從頭開始解這個線性規(guī)劃問題。但更簡便的方法是使用對偶單純形法：將生成的割平面條件加入松弛變量，然后加到表中21414143xx割平面約束：214141543xxxCj01000CBXBbx1x2x3x4x50 x11101/6-1/601x23/2011/41/400 x5-1/200-

17、1/4-1/41j00-1/4-1/40CBXBbx1x2x3x4x50 x12/3100-1/32/31x21010010 x320011-4j0000-1將 x3=6-3x1-2x2 , x4=3x1-2x2 ,帶入 中，得到等價的割平面條件： x21 見下圖。21414143 xxx1x233第一個割平面第一個割平面 此時，X1 (2/3, 1), Z=1,仍不是整數(shù)解。繼續(xù)以x1為源行生成割平面，其條件為：32323254xx將生成的割平面條件加入松弛變量，然后加到表中：323232654xxxCBXBbx1x2x3x4x5x60 x12/3100-1/32/301x210100100

18、 x320011-400 x6-2/3000-2/3-2/31j-10000-10CBXBbx1x2x3x4X5x60 x10100-1011x20010-103/20 x3600150-60 x5100011-3/2j000010-3/2CBXBbx1x2x3x4s1s20 x1110001-1/21x210100100 x310010-53/20 x4100011-3/2Z-10000-10 至此得到最優(yōu)表，其最優(yōu)解為 X= (1 , 1) , Z = 1, 這也是原問題的最優(yōu)解。 32323254xx等價的約束割平面條件為x1 x2 x1x233第一個割平面第一個割平面第二個割平面第二個

19、割平面3 分枝定界法v在20世紀60年代初 Land Doig 和 Dakin 等人提出了分枝定界法.由于該方法靈活且便于用計算機求解,所以目前已成為解整數(shù)規(guī)劃的重要方法之一。v適用范圍：分枝定界法既可用來解純整數(shù)規(guī)劃,也可用來解混合整數(shù)規(guī)劃.分枝定界法由來： 混合整數(shù)規(guī)劃問題一般有無限多個可行解。即使是純整數(shù)規(guī)劃問題，隨著問題規(guī)模的擴大，其可行解的數(shù)目也將急劇增加。因此通過枚舉全部可行解，并從中篩選出最優(yōu)解的算法無實際應用價值。分枝定界法（branch and bound）是一種隱枚舉或部分枚舉法，是在枚舉法基礎上的改進。分枝定界法的關鍵是分枝和定界。分枝定界法的基本思想：( 分枝和定界的思

20、想) 若整數(shù)規(guī)劃的松弛問題的最優(yōu)解不符合整數(shù)要求，假設 不符合整數(shù)要求， 是不超過 的最大整數(shù)，則構造兩個約束條件 。分別將其并入上述松弛問題中，從而形成兩個分枝，即兩個后續(xù)問題。 ibibib1iiiibxbx和這就是所謂分枝。 兩個后續(xù)問題的可行域中包含原整數(shù)規(guī)劃問題的所有可行解。而在原松弛問題可行域中，滿足的一部分區(qū)域在以后的求解過程中被遺棄了，讓而它不包含整數(shù)規(guī)劃的任何可行解。根據(jù)需要，各后續(xù)問題可用類似地產(chǎn)生自己的分枝，即自己的后續(xù)問題。 1iiibxb“分枝”為整數(shù)規(guī)劃最優(yōu)解的出現(xiàn)創(chuàng)造了條件*(4,4)35XZ*(5,3)20XZ什么是定界： 所謂“定界”，是在分枝過程中，若某個后

21、續(xù)問題的最優(yōu)解恰巧獲得整數(shù)規(guī)劃問題的一個可行解（即其解滿足整數(shù)約束），那么，它的目標函數(shù)值就是一個“界限”，可作為衡量處理其他分枝的一個依據(jù)。（對于最大值問題，此為“下界”） 因為整數(shù)規(guī)劃問題的可行解集是其松弛問題的可行解集的一個子集，所以其松弛問題的最優(yōu)解目標函數(shù)值是原整數(shù)規(guī)劃問題的上界。所以，對于那些相應松弛問題最優(yōu)解的目標函數(shù)值比上述“界限”值差的后續(xù)問題，就可以剔除而不再考慮?！敬硕斡袉栴}】 當然，如果在以后的分枝過程中出現(xiàn)了更好的“界限”，則以它來取代原來的界限，這樣可以提高定界的效果?！岸ń纭眲t可用提高搜索的效率*(4,4)35XZ*(5,3.17)20XZ“分枝”為整數(shù)規(guī)劃最優(yōu)解

22、的出現(xiàn)創(chuàng)造了條件，而“定界”則可用提高搜索的效率。下面，通過例子來闡明分枝定界法的基本思想和一般步驟:例 求解整數(shù)規(guī)劃問題1212121,212m ax57724843218. .0,Zxxxxxxs tx xxx為 整 數(shù)解：去掉整數(shù)要求，得其相應得線性規(guī)劃（在分枝定界法中，將此記為B，稱其為原整數(shù)規(guī)劃A的松弛問題）：1212121,2m ax5772484.32180Zxxxxs txxx x用任一種方法解問題B得最優(yōu)解和最優(yōu)值為：x1=4.55, x2=2.17, Z=37.97B的可行解集記為R0,如圖所示：A(4.55,2.17)Y 軸612943上面B的最優(yōu)解不滿足整數(shù)要求，即不是

23、整數(shù)規(guī)劃的最優(yōu)解。為尋求原整數(shù)規(guī)劃的最優(yōu)解，我們把B劃分為兩個子問題（分枝）。 任選一個不滿足整數(shù)約束的變量，這里我們?nèi)1構造兩個約束條件：在B中分別增加上述約束條件，得到B的兩個子問題：5411xx和04182384327.75max2,11212121xxxxxxxtsxxZ05182384327.75max2,11212121xxxxxxxtsxxZ問題問題x1=4, x2=2.33, Z= 36.33x1=5, x2=1.5, Z= 35.5此時，B的可行解被分成了三個部分，即問題的可行解R1, 問題的可行解R2，以及不含整數(shù)可行解的4x15的部分Y 軸6129434 5LP1x1=

24、4, x2=2.33Z(1) 36.33LPx1=4.55, x2=2.17Z(0) 37.97LP2x1=5, x2=1.5Z(2) 35.5x14x15整個求解過程問題B問題問題由于問題和問題的最優(yōu)解仍不滿足整數(shù)要求，則把和繼續(xù)進行類似的劃分。 由于的最優(yōu)值較大，則其包含原整數(shù)規(guī)劃最優(yōu)解的可能形更大些，因此先分解。在中分別增加約束條件得到的兩個子問題和。3222xx和04182384327.75max2,11212121xxxxxxxtsxxZ問題在中分別增加 兩個約束，得到的兩個子問題和3222xx和024182384327.75max2,121212121xxxxxxxxtsxxZ03

25、4182384327.75max2,121212121xxxxxxxxtsxxZ問題問題x1=4, x2=2, Z=34x1=1.71, x2=3, Z=29.57Y 軸6129434 52此時，問題1的可行域被分成三部分，即的可行集R3, 的可行解集R4，以及不含整數(shù)可行解的2x2 34，即的可行解集中還有可能含有原整數(shù)規(guī)劃的最優(yōu)解（比的最優(yōu)解目標函數(shù)值大的整數(shù)解）。 2122xx和因此需要考察問題，分別增加約束條件得到問題的兩個子問題和05182384327.75max2,11212121xxxxxxxtsxxZ問題015182384327.75max2,121212121xxxxxxxx

26、tsxxZ025182384327.75max2,121212121xxxxxxxxtsxxZ問題問題引入約束2122xx和x1=5.33, x2=1,Z=33.67無可行解問題的可行域R5問題無可行解此時，問題的可行域被分成兩部分部分，即的可行集R5,和不含整數(shù)可行解的1x2所有分枝末梢的Z值，則得最優(yōu)解。否則， 取Z值最大的非整數(shù)解，繼續(xù)分解，Go to 3iixb1iijixbxb 和LP1x1=4, x2=2.33Z(1) 36.33LPx1=4.55, x2=2.17Z(0) 37.97LP2x1=5, x2=1.5Z(2) 35.5x14x15問題問題x22x13x21x22LP3

27、x1=4, x2=2Z(3) 34LP4x1=1.71, x2=3Z(4) 29.57LP5x1=5.33, x2=1Z(5) 33.67LP6無可行解無可行解練習例：用分枝定界法求解整數(shù)規(guī)劃問題（可用圖解法求解）且且為為整整數(shù)數(shù)0,143292)(23max21212121xxxxxxIPxxZ樹形圖如下：樹形圖如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x1

28、43 0-1型整數(shù)規(guī)劃一、 0-1變量及其應用若變量只能取0或1，則稱其為0-1變量。 0-1變量作為邏輯變量(logical variable),常被用來表示系統(tǒng)是否處于某個特定狀態(tài)，或者決策時是否取某個特定方案。例如 01xP當決策取方案P時當決策不取方案P時（即取 時）01jx若Ej選擇Aj若Ej選擇jAJ=1,2,n那么，向量(x1,x2,xn)就描述了問題的特定狀態(tài)或方案即：TnnTTnnTTnnTTnnTTnAAAAAAAAAAAAAAAAxxx),.,(,)0 , 0,.0 , 0(),.,(,)0 , 0,.0 , 1 (),.,(,)0 , 1,.1 , 1 (),.,(,)

29、 1 , 1,.1 , 1 (),.,(12112112121211若選擇若選擇若選擇若選擇當問題含有多項要素，而每項要素皆有兩種選擇時，可用一組0-1變量來描述。一般地，設問題有有限項要素E1,E2,En,其中每項Ej有兩種選擇Aj和 ，則可令jA投資場所選擇問題某城市擬在其東、西、南三個區(qū)域設立郵局，各地區(qū)都由幾個具體的地點可供選擇。要求不超過總投資100萬元的條件下，建立盈利最大化0-1規(guī)劃。地區(qū)東區(qū)西區(qū)南區(qū)約束地點A1 A2A3 A4 A5A6 A7投資B1 B2B3 B4 B5B6 B7100萬元盈利C1 C2C3 C4 C5C6 C7選點數(shù)121分析：令xj(j1,2.7)為0-1

30、變量二、 0-1 整數(shù)規(guī)劃舉例其數(shù)學模型為：).2, 1(10121100.max76543217171njxxxxxxxxxBtsxCZjiiiiii或在應用中，有時會遇到變量可以取多個整數(shù)值的問題。這時，利用0-1變量是二進值變量（binary variable）的性質(zhì)，可以用一組0-1變量來取代該變量。例如，變量x可取09之間的任意整數(shù)時，可令9222233221100 xxxxx其中x0,x1,x2,x3皆為01變量0-1變量不僅廣泛應用于科學技術問題，在經(jīng)濟管理問題中也有十分重要的應用1互斥問題2 固定費用問題3 工件排序問題 含有相互排斥的約束條件的問題假設工序B的每周工時約束條件

31、為 現(xiàn)在假設工序B還有一種新的加工方式，相應的每周工時約束變成: 如果工序B只能從兩種加工方式中選擇一種，那么（1）式和（2）式就成為兩個相互排斥的約束條件。為了統(tǒng)一在一個問題中，就需要 引入01變量 ）（ 11505 . 03 . 021xx）（21205 . 02 . 021xx102y101y工序B采用原加工方式工序B不采用原加工方式工序B采用新加工方式工序B不采用新加工方式于是，通過引入0-1變量，可以將相互排斥的約束條件(1)和(2)統(tǒng)一起來：）（）（）（5141204 . 02 . 031505 . 03 . 02122211121yyyMxxyMxx其中M1和M2都是充分大的數(shù)。

32、由于（5）式?jīng)Q定了y1和y2中必定有一個是1，另一個是0（互斥條件）。若y1=1，而y2=0，即采用新的加工方式。此時由于M1是一個充分大的數(shù)，則(3)式無效。反之，若y1=0,而y2=1，即采用原加工方式。此時由于M2是一個充分大的數(shù)，則(4)式無效。一般地，若需要從p個約束條件).2, 1(1pibxainjjij中恰好選擇q個約束條件，則可用引入p個0-1向量10iy若選擇第i個約束條件若不選擇第i個約束條件那么，約束條件組pjiiiinjjijqpyyMbxa11就可用達到這個目的。因為上述約束條件組保證了在p個0-1變量中有p-q個為1，q個為0。凡取0值的yi對應的約束條件即為原約

33、束條件，而取1的yi對應的約束條件無效。固定費用問題有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件費用及售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費用見下表。要求定制一個生產(chǎn)計劃，使總收益最大。IIIIII資源量A248500B234300C123100單件費用456單件售價81012固定費用100150200建模碰到的困難主要是事先不能確切知道某種產(chǎn)品是否生產(chǎn)，因而不能確定相應的固定費用是否發(fā)生下面借助0-1變量解決這個困難設xj是第j種產(chǎn)品的產(chǎn)量, j=1,2,3;再設01iy生產(chǎn)第 j 種產(chǎn)品(即xj 0)不生產(chǎn)第 j 種產(chǎn)品(即xj 0)則問題的整數(shù)規(guī)劃數(shù)學模型是：3 , 2 , 1,

34、103 , 2 , 1,010032300432500842. .200150100)612() 510()48(max333222111321321321321321jyjxyMxyMxyMxxxxxxxxxxtsyyyxxxZjj或且為整數(shù) 如果生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj 0。此時由約束條件xj Mjyj，知yj=1。因此相應的固定費用在目標函數(shù)中將被考慮。 如果不生產(chǎn)第j種產(chǎn)品，則其產(chǎn)量xj = 0,此時由約束條件xj Mjyj可知，yj可以是0也可以是1。但yj=1不利于目標函數(shù)的最大化，因而在問題的最優(yōu)解中必然是yj=0，從而相應的固定費用將不再被考慮工件排序問題用4臺機床加工3件

35、產(chǎn)品。各產(chǎn)品的機床加工順序，以及產(chǎn)品 i 在機床 j 上的加工工時 aij 見下表產(chǎn)品產(chǎn)品1a11 a13 a14 機床機床1 機床機床3 機床機床4 產(chǎn)品產(chǎn)品2a21 a22 a24機床機床1 機床機床2 機床機床4產(chǎn)品產(chǎn)品3 a32 a33 機床機床2 機床機床3由于某種原因，產(chǎn)品2的加工總時間不得超過d，現(xiàn)要求確定各件產(chǎn)品在機床上的加工方案，使在最短的時間內(nèi)加工完全部產(chǎn)品。解：設 xij 表示產(chǎn)品 i 在機床 j 上開始加工的時間(i=1,2,3;j=1,2,3,4)下面將逐步列出問題的整數(shù)規(guī)劃模型1、同一件產(chǎn)品在不同機床上的加工順序約束對于同一件產(chǎn)品，在下一臺機床上加工的開始時間不得早

36、于在上一臺機床上加工的約束時間，故應有：產(chǎn)品產(chǎn)品1：及及xax141313xax131111產(chǎn)品產(chǎn)品2：及及xax242222xax222121產(chǎn)品產(chǎn)品3：xax3332322、每一臺機床對不同產(chǎn)品的加工順序約束一臺機床在工作中，如已開始的加工還沒有結束，則不能開始另一件產(chǎn)品的加工。對于機床1，有兩種加工順序?；蛳燃庸ぎa(chǎn)品1，后加工產(chǎn)品2；或反之。對于其它3臺機床，情況也類似。為了容納兩種相互排斥的約束條件，對于每臺機床，分別引入0-1變量)4 , 3 , 2 , 1(10jyj先加工另一件產(chǎn)品先加工某件產(chǎn)品則每臺機床上的加工產(chǎn)品的順序可用下列四組約束條件來保證：機床1：及)1 (111212

37、1yMxaxyMxax1211111機床2：及)1 (2223232yMxaxyMxax2322222機床4：及)1 (4142424yMxaxyMxax4241414機床3：及)1 (3133333yMxaxyMxax3331313各yj的意義是明顯的。如當y1=0時，表示機床1先加工產(chǎn)品1，后加工產(chǎn)品2，當y1=1時，表示機床1先加工產(chǎn)品2，后加工產(chǎn)品1。3、產(chǎn)品2的加工時間約束產(chǎn)品2的開始加工時間是x21，結束加工時間是x24+a24，故應有：dxax2124244、目標函數(shù)的建立設全部產(chǎn)品加工完畢的結束時間為W，由于三件產(chǎn)品的加工結束時間分別為x14+a14， x24+a24， x33

38、+a33，故全部產(chǎn)品的實際加工結束時間為：),max(333324241414axaxaxW轉化為線性表達式axWaxWaxWWZ333324241414min綜上所述，例題的整數(shù)規(guī)劃模型為：4, 3 ,2, 1, 100,)1 ()1 ()1 ()1 (.min333224222114131133332424141421242441424244241414313333333313132223232232222211121211211111333232242222222121141312121111jyWxxxxxxxxaxWaxWaxWdxaxyMxaxMyxaxyMxaxMyxaxyMxa

39、xMyxaxyMxaxMyxaxxaxxaxxaxxaxxaxtsWzj或 0-1型整數(shù)規(guī)劃是一種特殊的整數(shù)規(guī)劃，若含有n個變量，則可能產(chǎn)生 2n 個可能的變量組合。當n 較大時，采用完全枚舉法解題幾乎是不可能的。已有的求解0-1型整數(shù)規(guī)劃的方法一般都屬于隱枚舉法三、 0-1型整數(shù)規(guī)劃的解法 在2n個可能的變量組合中，往往只有一部分是可行解。只要發(fā)現(xiàn)某個變量組合不滿足其中一個約束條件時，就不必再去檢驗其他約束條件。 對于可行解，其目標函數(shù)值也有優(yōu)劣之分。若已發(fā)現(xiàn)一個可行解，則根據(jù)它的目標函數(shù)值可以產(chǎn)生一個過濾條件，對于目標函數(shù)值比它差的變量組合就不必再去檢驗它的可行性。在以后的求解過程中，每當

40、發(fā)現(xiàn)比原來更好的可行解，則以此替換原來的過濾條件。 上述這些做法，都可用減少運算次數(shù)，使最優(yōu)解能較快地被發(fā)現(xiàn)。例 求解0-1整數(shù)規(guī)劃1231231231223123max3252244. .346,01Zxxxxxxxxxstxxxxx x x或10,6434422.523max3213221321321321或xxxxxxxxxxxxxtsxxxZ解 求解過程可以列表表示(x1,x2,x3)Z值約束條件（a b c d）過濾條件(0,0,0)0 Z0(0,0,1)5 Z5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8 Z8abcd(x1,x2,x3)Z值約束條件（a b

41、c d）過濾條件(1,1,0)1(1,1,1)6接上表所以，最優(yōu)解（x1,x2,x3）T=(1,0,1)T,max Z = 8由于采用上述算法，實際只作了20次運算。例 求解01整數(shù)規(guī)劃104, 3, 2, 15423158443621143212. .432713min或xxxxxxxxxxxxxxxtsxxxxzZ解：采用上例那樣的算法，解此例共需作36次運算。為了進一步減少運算量，常按目標函數(shù)中各變量系數(shù)的大小順序重新排列各變量，以便最優(yōu)解有可能較早出現(xiàn)。對于最大化問題，可按由小到大的順序排列；對于最小化問題，則相反本例可寫成下列形式：10,55386412.37min341241234

42、1234123412或xxxxxxxxxxxxxxxtsxxxxZ采取這樣的形式用上法解此例，只需作30次運算。一般問題的規(guī)模越大，這樣做的好處就越明顯?；@球隊需要選擇5名隊員組成出場陣容參加比賽. 8 名隊員的身高及擅長位置見下表:隊員12345678身高1.921.901.881.861.851.831.801.78擅長位置中鋒中鋒前鋒前鋒前鋒后衛(wèi)后衛(wèi)后衛(wèi)出場陣容應滿足以下條件: 只能有一名中鋒上場 至少有一名后衛(wèi) 如1號和4號均上場, 則6號不上場 2號和8號至少有一個不出場問: 應當選擇哪5名隊員上場,才能使出場隊員平均身高最高? 試建立數(shù)學模型有五項設計任務可供選擇.各項設計任務的預

43、期完成時間分別為3, 8, 5, 4, 10 (周), 設計報酬分別為 7, 17, 11, 9, 21 (萬元). 設計任務只能一項一項地進行, 總的期限是 20 周.選擇任務時必須滿足下面要求:1 至少完成 3 項設計任務;2 若選擇任務 1, 必須同時選擇任務 2;3 任務3 和 任務4不能同時選擇應當選擇那些設計任務, 才能使總的設計報酬最大?(試建立數(shù)學模型)整數(shù)規(guī)劃v整數(shù)規(guī)劃的數(shù)學模型及解的特點v解純整數(shù)規(guī)劃的割平面法*v分支定界法v0-1型整數(shù)規(guī)劃*v指派問題5 指派問題指派問題是整數(shù)規(guī)劃的一類重要問題。也是在實際生活中經(jīng)常遇到的一種問題：由n項不同的工作或任務，需要n個人去完成

44、（每人只能完成一項工作）。由于每人的知識、能力、經(jīng)驗等不同，故各人完成不同任務所需的時間（或其它資源）不同。問應只排哪個人完成何項工作所消耗的總資源最少？一。 指派問題的數(shù)學模型引進0-1變量01ijx表示按排第i個人完成第j項工作表示不安排第i個人完成第j項工作則決策變量矩陣可表示為：nnnnnnxxxxxxxxxX212222111211用 表示第i個人完成第j項工作所需的資源數(shù)，稱之為效率系數(shù)（或價值系數(shù)）。表示為nnnnnncccccccccC212222111211ijc效率矩陣（Coefficient matrix）則指派問題的數(shù)學模型為ninjijijxcZ11minnjxnix

45、tsniijnjij, 2 , 11, 2 , 11. .110ijx或1注：指派問題是一種特殊的LP問題，是一種特殊的運輸問題。下用目前認為最簡潔的方法匈牙利法求解。例1：某商業(yè)公司計劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司 對新商店 的建造報價（萬元）為 ，見表5-9。商業(yè)公司應當對5家建筑公司怎樣分配建筑任務，才能使總的建筑費用最少？)5 , 2 , 1(iAi)5 , 2 , 1(jBj)5 , 2 , 1,(jicijC54321AAAAA54321BBBBB8106961081476106129671417971215784這是一個標準的

46、指派問題。若設0-1變量01ijx當 承建 時iAjB當 不承建 時iAjB則問題的數(shù)學模型為11125455min48108Zxxxx5, 2 , 115, 2 , 11. .5151jxixtsiijjij0ijx或1C810696108147610612967141797121578454321AAAAA54321BBBBB0010000010010001000000001*X若單說讓誰建，不讓誰建。C810696108147610612967141797121578454321AAAAA54321BBBBB-414022328023062208112359110-6-7 -6-7001

47、0000010010001000000001*X從而導出匈牙利解法的思想：匈牙利法是1955年由庫恩（W.W.Kuhn）根據(jù)匈牙利數(shù)學家狄考尼格（d.konig)關于矩陣中獨立零元素的定理發(fā)明的。匈牙利法的基本原理：定理1 將效率矩陣的某一行（或某一列）的各個元素都減去同一個常數(shù)t (t可正可負），得到新的矩陣，則以新矩陣為效率矩陣的指派問題與原指派問題的最優(yōu)解相同。但其最優(yōu)值比原最優(yōu)值減少t 。解：設效率矩陣C為二。匈牙利解法nnnnknkknnccccccccccccC21212222111211nnnnknkknnccctctctcccccccC21212222111211記新指派問題的

48、目標函數(shù)為 ，則有ZninjnkiinjnjkjkjijijijijxcxcxcZ11111njkjnkiinjnkiinjnjkjkjijijnjkjkjijijxtxcxcxtcxc1111111)(ninjijijtZtxc111 .注意到njijx11所以原式因此有tZtZZmin)min(min而新問題的約束方程同原指派問題。因此其最優(yōu)解比相同，而最優(yōu)解差一個常數(shù)。推論 若將指派問題的效率矩陣每一行及每一列分別減去各行各列的最小元素，則得到的新的指派問題與原指派問題有相同的最優(yōu)解。證明：證明：結論是顯然的。只要反復運用定理1便可得證。注：當將效率矩陣的每一行都減去各行的最小元素，將所

49、得的矩陣的每一列在減去當前列中最小元素，則最后得到新效率矩陣 中必然出現(xiàn)一些零元素。設 =0，從第i行看，它表示第 i 人去干第 j 項工作效率（相對）最好，而從第j列來看，它表示第 j 項工作讓第 i 人來干效率（相對）最高。Cijc 問題是：能否找到位于不同行、不同列的n個0元素？定義 在效率矩陣C中，有一組處于不同行、不同列的零元素，稱為獨立零元素組，此時其中每個元素稱為獨立零元素。例 已知0084765000320205C則0, 0, 0, 043312412cccc是一個獨立零元素組，0, 0, 0, 043312412cccc分別稱為獨立零元素。0084765000320205C也

50、是一個獨立零元素組。0084765000320205C不是一個獨立零元素組。根據(jù)以上對效率矩陣中零元素的分析，對效率矩陣C中出現(xiàn)的的獨立零元素組中零元素所處的位置，在決策變量矩陣中令相應的 =1，其余的 =0。就可找到指派問題的一個最優(yōu)解。ijxijx就上例中(1)0100000110000010X就是一個最優(yōu)解。同理(2)0100001010000001X也是一個最優(yōu)解。3084065070320205C 但是在有的問題中發(fā)現(xiàn)效率矩陣C中獨立零元素的個數(shù)不夠n個，這樣就無法求出最優(yōu)指派方案，需作進一步的分析。首先給出下述定理。已知效率矩陣3084065070320205C怎么辦？定理 效率矩

51、陣C中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最少直線數(shù)。本定理由匈牙利數(shù)學家狄考尼格證明的。證明的內(nèi)容已超出所需學的范圍。下面通過例子說明上述定理的內(nèi)容例 已知矩陣0084765000320205C3084065070320205C至于如何找覆蓋零元素的最少直線，通過例子來說明。例1 現(xiàn)有一個44的指派問題，其效率矩陣為：9118713161491514410413152C求解該指派問題。步驟1：變換系數(shù)矩陣，使得每行及每列至少產(chǎn)生一個零元素。9118713161491514410413152C-2-4-9-724104750111006211130-4-21001023509606071

52、30C步驟2：用圈0法確定 中的獨立0元素。若獨立零元素個素有n個，則已得最優(yōu)解。若 獨立零元素的個數(shù) n, 則轉入步驟3。1C1, 1, 1, 143312214xxxx其余全為0。在只有一個0元素的行（或列）加圈，表示此人只能做該事（或此事只能由該人來做），每圈一個“0”，同時把位于同列（或同行）的其他零元素劃去。表示此時已不能再由他人來做（或此人已不能做其它事）。如此反復，直到矩陣中所有零元素都被圈去或劃去為至。在遇到所有行和列中，零元素都不止一個時，可任選其中一個加圈，然后劃去同行、同列其他未被標記的零元素。例0080760000320205C步驟3： 若矩陣已不存在未被標記的零元素，

53、但圈零的個數(shù)m n ，作最少直線覆蓋當前零元素。已知例1(工程承包)中的系數(shù)矩陣變?yōu)?8715127917141069128767146106912106C-4-7-6-6-6046304081012630371020811340-1 -3變換系數(shù)矩陣043204050012320377108110301C 確定獨立零元素. 作最少直線覆蓋當前所有零元素。由于獨立零元素個數(shù)4 5. 對沒有圈0的行打“”。 在已打“”的行中，對零元素所在的列打“”。 在已打“”的列中，對圈0元素所在的行打“”。043204050012320377108110301C 重復和，直到再也找不到可以打“”的行或列為止

54、 對沒有打“”的行畫一橫線，對已打“”的列畫一縱線，即得覆蓋當前0元素的最少直線數(shù)目的集合。043204050012320377108110302C 繼續(xù)變換系數(shù)矩陣，以增加0元素。在未被直線覆蓋的元素中找出一個最小的元素。對未被直043204050012320377108110301C043204050012320377108110302C線覆蓋的元素所在的行（或列）中各元素都減去這一元素。這樣，在未被直線覆蓋的元素中勢必會出現(xiàn)0元素，但同時卻又使已覆蓋的元素中出現(xiàn)負元素。為了消除負元素，只要對它們所在的列（或行）中各元素都加上這一最小元素。返回。0432040500123203771081

55、10302C-1-104320405000121126601811030+1304321405010121026600811031C 中已有5個獨立0元素，故可確定指派問題的最優(yōu)方案。3C, 1, 1, 1, 1,xxxx其余全為0。304321405010121026600811031C 中已有5個獨立0元素，故可確定指派問題的最優(yōu)方案。3C, 1, 1, 1, 1,xxxx其余全為0。48715 1279 17 14 1069 128767 1461069 12 106也就是說，最優(yōu)指派方案是：讓 承建 ， 承建1A3B2A1B 承建 ，

56、 承建 。這樣安排能使總的建造費用最少，總的建造費用為7+9+6+6+6=34（萬元）。4A4B5A5B課堂練習某汽車公司擬將四種新產(chǎn)品配置到四個工廠生產(chǎn)，四個工廠的單位產(chǎn)品成本（元/件）如下表所示求最優(yōu)生產(chǎn)配置方案 表表5-1產(chǎn)品產(chǎn)品1產(chǎn)品產(chǎn)品2產(chǎn)品產(chǎn)品3產(chǎn)品產(chǎn)品4工廠工廠工廠27550150230工廠工廠36570170250工廠工廠48255200280第一步：找出效率矩陣每行的最小元素，并分別從每行中減去最小元素，有 556550582802005582250170706523015050752601806958min225145027185105501801

57、00025202122110第二步：找出矩陣每列的最小元素，再分別從每列中減去，有 4545027555000025222211022514502718510550180100025202122110第三步：用最少的直線覆蓋所有“0”，得01122222500005552704545第四步：這里直線數(shù)等于3（等于4時停止運算），要進行下一輪計算從矩陣未被直線覆蓋的數(shù)字中找出一個最小數(shù)k并且減去k，矩陣中k5直線相交處的元素加上k，被直線覆蓋而沒有相交的元素不變，得到下列矩陣4545032000000030171760第四步等價于第第四步等價于第1、3行減去行減去5，同時第，同時第1列加上列加上

58、5得到的結果得到的結果-5-5+54545032000000030171760第五步：覆蓋所有零最少需要4條直線，表明矩陣中存在4個不同行不同列的零元素容易看出4個“0”的位置 4545032000000030171760或或4545032000000030171760得到兩個最優(yōu)解 11111111)2()1(，XX有兩個最優(yōu)方案第一種方案：第一個工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品3，第三個工廠加工產(chǎn)品4，第四個工廠加工產(chǎn)品2；第二種方案：第一個工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個工廠加工產(chǎn)品3，第四個工廠加工產(chǎn)品2； 產(chǎn)品總成本Z5815025055513 三。非標準形式的指派問題在實

59、際應用中，經(jīng)常遇到非標準形式的指派問題。處理方法：化標準，再按匈牙利訪法求解。 最大化指派問題例13 有4種機械要分別安裝在4個工地，它們在4個工地工作效率（見下表）不同。問應如何指派安排，才能使4臺機械發(fā)揮總的效率最大？ 工地機器甲 乙 丙 丁30 25 40 3232 35 30 36 35 40 34 2728 43 32 38解：設最大化的指派問題系數(shù)矩陣 ，其中最大元素為m（本例種m=43），令矩陣nnijcC)(nnijnnijcmbB)()(本例中38324328273440353630353232402530C511015169387138111131813B-3-7-3-05

60、11015136050614801510-451101113601061080156圈0覆蓋打511011136010610801561B-1-1+141001012500062080166圈02B此時m=n=4,因此決策變量矩陣為0010000110000100X即指派機械安裝在工地丙，機械安裝在工地丁，機械安裝在工地甲，機械安裝在工地乙，才能使4臺機器發(fā)揮總的效率最大。其總效率為38324328273440353630353232402530 人數(shù)和事數(shù)不等的指派問題若人少事多，則添上一些虛擬的“人”。這些虛擬的“人”做各事的費用系數(shù)可取0，理解為這些費用實際上不