整數(shù)規(guī)劃小結(jié)

1、上頁上頁下頁下頁返回返回整數(shù)規(guī)劃v整數(shù)規(guī)劃的數(shù)學模型v設置邏輯變量建立整數(shù)規(guī)劃模型v分配問題與匈牙利法v分枝定界法、割平面法v應用舉例上頁上頁下頁下頁返回返回匈牙利法 匈牙利法的基本思想如果效率矩陣 C 中存在 n 個位于不同行不同列的零元素,則只要令對應于這些零元素位置的決策變量xij=1,其余的決策變量xij=0,則可取到最小值0,即該分配方案最優(yōu). 如： 0141208302323020939140C100000100100000144ijxX上頁上頁下頁下頁返回返回匈牙利法 匈牙利法的計算步驟 第一步:找出效率矩陣每行的最小元素,并分別從每行中減去; 第二步:找出效率矩陣每列的最小元素

2、,再分別從每列中減去; 第三步:確定能否找出n個位于不同行不同列的零元素集合來.根據(jù)定理2,該問題轉(zhuǎn)化為:要覆蓋上面矩陣中的所有零元素,至少需要多少條直線;怎么得到覆蓋零元素的最少直線數(shù)？從第一行開始,若該行只有一個零元素,就對這個零元素打上( )號,將打( )號零元素所在列畫一條直線.若該行沒有零元素或有兩個以上零元素(已劃去的不計在內(nèi)),則轉(zhuǎn)下一行,依次進行到最后一行;從第一列開始,若該列只有一個零元素就對這個零元素打上( )號(同樣不考慮已劃去的零元素),再對打( )號零元素所在行畫一條直線.若該列沒有零元素或有兩個以上零元素,則轉(zhuǎn)下一列,依次進行到最后一列;重復1和2兩個步驟,可能出現(xiàn)

3、三種情況上頁上頁下頁下頁返回返回匈牙利法第一種情況 覆蓋零元素的最少直線數(shù)(或打( )號的零元素個數(shù))等于n第二種情況 打( )號的零元素個數(shù)小于n,但未被劃去的零元素之間存在閉回路,這時可順著閉回路的走向,對每個間隔的零元素打一( )號,然后對所有打( )號的零元素,或所在行,或所在列畫一條直線.第三種情況 矩陣中所有零元素或被劃去,或打上( )號,但打( )號的零元素個數(shù)仍小于n.上頁上頁下頁下頁返回返回v 匈牙利法 第四步:為設法使每一行都有一個打( )號零元素,需繼續(xù)按定理1對矩陣進行變換： 從矩陣未被直線覆蓋的數(shù)字中找出一個最小的數(shù)k; 對矩陣的每行,當該行有直線覆蓋時,令ui=0,

4、無直線覆蓋時,令ui=k;每行元素減去ui； 對矩陣中有直線覆蓋的列,令vj=-k,對無直線覆蓋的列,令vj=0;每列元素減去vj； 得到一個新矩陣；1. 第五步:回到第三步,反復進行,一直到矩陣的每一行都有一個打( )號零元素為止,即找到了最優(yōu)分配方案.上頁上頁下頁下頁返回返回一般分配問題1、人數(shù)和工作任務不相等的分配問題(不平衡的分配問題) （1）人少任務多 （2）人多任務少 類似產(chǎn)銷不平衡問題(虛設假想的人,增添假想任務)2、某項任務一定不能由某人做的分配問題 將相應的費用系數(shù)取作足夠大的數(shù)M3、一個人可做幾項任務的分配問題4、目標函數(shù)為求最大值(最大化的分配問題)效率矩陣中元素全為負數(shù)

5、,根據(jù)定理1,讓效率矩陣中所有元素變成非負數(shù),再利用匈牙利法求解.11maxnnijijijzc x11minnnijijijwcx上頁上頁下頁下頁返回返回 第一步第一步: 先不考慮整數(shù)約束先不考慮整數(shù)約束,解解A的松弛問題的松弛問題B,可能得到以下情況之一可能得到以下情況之一: 若若B沒有可行解沒有可行解,則則A也沒有可行解也沒有可行解,停止計算停止計算. 若若B有最優(yōu)解有最優(yōu)解,并符合并符合A的整數(shù)條件的整數(shù)條件,則則B的最優(yōu)解即為的最優(yōu)解即為A的最優(yōu)解的最優(yōu)解,停止計算停止計算. 若若B有最優(yōu)解有最優(yōu)解,但不符合但不符合A的整數(shù)條件的整數(shù)條件,轉(zhuǎn)入下一步轉(zhuǎn)入下一步.為討為討論方便論方便,

6、設設B的最優(yōu)解為：的最優(yōu)解為： .z), 1(,)0 , 0 ,(0)1)0(目標函數(shù)最優(yōu)值為不全為整數(shù)mibbbXiTm分枝定界法分枝定界法上頁上頁下頁下頁返回返回第二步第二步: :定界定界 記記A的目標函數(shù)最優(yōu)值為的目標函數(shù)最優(yōu)值為z z* *, ,以以z(0)作為作為z z* * 的上界的上界, ,記為記為 = =z(0). .再用觀察法找的一個整數(shù)可再用觀察法找的一個整數(shù)可行解行解X X, ,并以其相應的目標函數(shù)值并以其相應的目標函數(shù)值z z作為作為z z* *的下的下界界, ,記為記為z zz z, ,也可以令也可以令z z, ,則有則有: :z*zzz分枝定界法分枝定界法上頁上頁下

7、頁下頁返回返回第三步第三步: :分枝分枝 在以上界在以上界 所對應的解所對應的解 中中, ,任選一個不符合整數(shù)條件的變量任選一個不符合整數(shù)條件的變量, ,例如例如 ( (不不為整數(shù)為整數(shù)),),以以 表示不超過表示不超過 的最大整數(shù)的最大整數(shù). .構(gòu)造構(gòu)造兩個約束條件兩個約束條件 將這兩個約束條件分別加入問題將這兩個約束條件分別加入問題B B中中, ,形成形成兩個子問題兩個子問題B1B1和和B2B2, ,再對這兩個子問題進行求解再對這兩個子問題進行求解. .rbrbrb1rrrrxbxb和分枝定界法分枝定界法TmrbbbX)0 , 0 ,(1z上頁上頁下頁下頁返回返回 第四步第四步: : 修改

8、上修改上、下界下界, ,按照以下兩點規(guī)則按照以下兩點規(guī)則進行進行 在各分枝問題中在各分枝問題中, ,找出目標函數(shù)值最大者找出目標函數(shù)值最大者 作為新的上界作為新的上界; ; 從已符合整數(shù)條件的分枝中從已符合整數(shù)條件的分枝中, ,找出目標函找出目標函 數(shù)值最大者作為新的下界數(shù)值最大者作為新的下界. .分枝定界法分枝定界法上頁上頁下頁下頁返回返回如此反復進行如此反復進行,直到得到直到得到 為止為止,即得即得最優(yōu)解最優(yōu)解 X* .第五步：比較與剪枝第五步：比較與剪枝 各分枝的目標函數(shù)值中各分枝的目標函數(shù)值中,若有小于若有小于 者者,則剪則剪掉此枝掉此枝,表明此子問題已經(jīng)探清表明此子問題已經(jīng)探清,不必

9、再分枝了不必再分枝了;否則繼續(xù)分枝。否則繼續(xù)分枝。 z分枝定界法分枝定界法*zzz上頁上頁下頁下頁返回返回v 1958由由Gomory提出的一種求解整數(shù)規(guī)劃問題提出的一種求解整數(shù)規(guī)劃問題的方法的方法v基本思想：基本思想：v 依次引進依次引進線性約束條件線性約束條件(稱稱Gomory約束約束或或割平面割平面)v 切割掉問題的部分非整數(shù)解切割掉問題的部分非整數(shù)解v 直到使問題的目標函數(shù)值達到最優(yōu)的整數(shù)直到使問題的目標函數(shù)值達到最優(yōu)的整數(shù)點成為縮小后可行域的一個頂點點成為縮小后可行域的一個頂點割平面法割平面法上頁上頁下頁下頁返回返回 第一步：把問題中所有約束條件的系數(shù)均第一步：把問題中所有約束條件的

10、系數(shù)均化為整數(shù)化為整數(shù), ,用單純形法求解該整數(shù)規(guī)劃對應的松用單純形法求解該整數(shù)規(guī)劃對應的松弛問題弛問題. 若松弛問題沒有可行解若松弛問題沒有可行解,則原整數(shù)問題也沒有則原整數(shù)問題也沒有可行解可行解,停止計算停止計算. 若松弛問題有最優(yōu)解若松弛問題有最優(yōu)解,并符合原整數(shù)問題的整并符合原整數(shù)問題的整數(shù)條件數(shù)條件,則該最優(yōu)解即為原整數(shù)問題的最優(yōu)解則該最優(yōu)解即為原整數(shù)問題的最優(yōu)解,停停止計算止計算. 若松弛問題有最優(yōu)解若松弛問題有最優(yōu)解,但不符合原整數(shù)問題的但不符合原整數(shù)問題的整數(shù)條件整數(shù)條件,轉(zhuǎn)入下一步轉(zhuǎn)入下一步. 割平面法割平面法上頁上頁下頁下頁返回返回第二步：第二步：從松弛問題的最優(yōu)解中從松弛

11、問題的最優(yōu)解中, ,任選一個不為整任選一個不為整數(shù)的分量數(shù)的分量x xr,r, ,將最優(yōu)單純形表中該行的系數(shù)將最優(yōu)單純形表中該行的系數(shù) 和和 分解為整數(shù)部分和小數(shù)部分之和分解為整數(shù)部分和小數(shù)部分之和, ,并以該行為源行并以該行為源行, ,按下式作割平面方程：按下式作割平面方程：rjarb nmjjrjrxff10 的小數(shù)部分的小數(shù)部分的小數(shù)部分的小數(shù)部分rjarb割平面法割平面法上頁上頁下頁下頁返回返回第三步：第三步：將所得的割平面方程作為一個新的約束將所得的割平面方程作為一個新的約束條件置于最優(yōu)單純形表中（同時增加一個單位列條件置于最優(yōu)單純形表中（同時增加一個單位列向量）向量）, ,用對偶單

12、純形法求出新的最優(yōu)解。用對偶單純形法求出新的最優(yōu)解。若表中得到的解仍為非整數(shù)解若表中得到的解仍為非整數(shù)解, ,重復第二步重復第二步, ,直至直至找到整數(shù)解找到整數(shù)解. .割平面法割平面法上頁上頁下頁下頁返回返回習題四4.2)10, 1( 102115 . .min0i1109625438171101i101ixxxxxxxxxxxxxtsxczxiiiiii或否則號井位參與鉆探表示第設上頁上頁下頁下頁返回返回習題四4.31096109532485724679278310283)(au1=2u2=2u3=2u4=2u5=64304331026350245705618061v1=1 v2=2 v3

13、=0 v4=1 v5=132022200052400346036070403202220005240034603607040k=2上頁上頁下頁下頁返回返回習題四4.3（a）u1=0u2=2u3=2u4=2u5=21020002223022212421407040v1=0 v2=-2 v3=-2 v4=-2 v5=0320222000524003460360704012020000030400126034092601202000003040012603409260 x15=1 x23=1 x32=1 x44=1 x51=1,其余變量值為0，z=21上頁上頁下頁下頁返回返回習題四4.3642691

14、44523107496651675392)(bu1=2u2=1u3=3u4=1u5=24204703341074165540553170v1=0 v2=0 v3=0 v4=2 v5=0k=140047013410541653405511704004701341054165340551170上頁上頁下頁下頁返回返回習題四4.3（a）u1=1u2=1u3=1u4=1u5=04004710230143054231440061v1=-1 v2=-1 v3=0 v4=0 v5=-1x11=1 x22=1 x35=1 x44=1 x53=1,其余變量值為0，z=1240047013410541653405

15、5117050058002410431652305500705005800241043165230550070上頁上頁下頁下頁返回返回4.5已知下列五名運動員各種姿勢的游泳成績(各為50m)如下表.試問(a)如何從中選拔一個450m混合泳的接力隊,使預期的比賽成績?yōu)樽詈茫?b)以4項成績總和計算,運動員周應列第二,但選拔結(jié)果周被淘汰,從中可得到什么啟示.需時(s)隊員項目習題四上頁上頁下頁下頁返回返回解:非標準的分配問題,先轉(zhuǎn)化成標準分配問題.習題四需時(s)隊員項目111213141521222324253132333435410-11( ,1,2,3,4,5)0min37.732.938.

16、837.035.443.433.142.234.741.833.328.538.930.433.629.226ijijxi jijzxxxxxxxxxxxxxxxx設變量表示項目由運動員 完成表示項目 不由運動員 完成建立問題的數(shù)學模型為4243444541424344555151.429.628.531.10000011,2,3,4,5. .11,2,3,4,501,1,2,3,4,5ijjijiijxxxxxxxxxxis txjxi j或上頁上頁下頁下頁返回返回37.732.938.837.035.44.805.94.12.543.433.142.234.741.810.309.11.6

17、8.733.328.538.930.433.64.8010.41.95.129.226.429.628.531.12.803.22.14.70000000000CC續(xù) ： 該 問 題 的 效 率 矩 陣 為第 三 步 ：執(zhí) 行 匈 牙12345123451.61.61.61.6001.60004.805.94.12.53.204.33.50.910.309.11.68.78.707.507.14.8010.41.95.13.208.80.33.52.803.22.14.71.201.60.00000uuuuuvvvvvCC 利 法 第 一 步 和 第 二 步 ：第 四 步 ： k=1.653.

18、100000習題四上頁上頁下頁下頁返回返回12345123450.90.90.90.9000.900.903.204.33.50.92.303.43.508.707.507.17.806.606.23.208.80.33.52.307.90.32.61.201.60.53.10.300.70.52.20000000.uuuuuvvvvvCC 續(xù) ： 第 五 步第 六 步 ： k=0.91234512345000.30.3000.3000900.902.303.43.502.30.33.43.507.806.606.27.80.36.606.22.307.90.32.62.007.6020.30

19、0.70.52.200.900.90uuuuuvvvvvCC 第 七 步 ：第 八 步 ： k=0.3.3000.40.11.900.600.90習題四上頁上頁下頁下頁返回返回2.30.33.43.50000017.80.36.606.2000102.007.602.301000000.40.11.91000000.600.9000100sCX 續(xù) ： 第 九 步最 優(yōu) 解 方 案 :周 參 加 仰 泳 ;王 參 加 蛙 泳 ;錢 參 加 蝶 泳 ;趙 參 加 自 由 泳預 期 比 賽 最 好 成 績 為 127.8 .習題四上頁上頁下頁下頁返回返回習題四4.6分配甲、乙、丙、丁四個人去完成A

20、、B、C、D、E五項任務.每個人完成各項任務的時間如表所示.由于任務數(shù)多于人數(shù)，故考慮：(1)任務E必須完成.其它4項可任選3項完成。(2)其中一人完成兩項.其他每人完成一項。(3)任務A由甲或丙完成.任務C由丙或丁完成.任務E由甲、乙或丁完成.且規(guī)定4人中乙或丁完成兩項任務.其他每人完成一項；試分別確定最優(yōu)分配方案.使完成任務的總時間最少。上頁上頁下頁下頁返回返回習題四 解：1) 這是不平衡的分配問題，首先轉(zhuǎn)換為標準型，再用匈牙利法求解。由于任務數(shù)多于人數(shù)，所以假定一名虛擬人，設為戊。因為工作E必須完成，故設戊完成E的時間為M(M是非常大的數(shù))，其余效率系數(shù)為0，則標準型效率矩陣表為：上頁上

21、頁下頁下頁返回返回習題四 解續(xù)：用匈牙利法求出最優(yōu)分配方案為：即甲-B，乙-D，丙-E，丁-A，任務C放棄，最少時間為105h。0100000010000011000000100X上頁上頁下頁下頁返回返回4.6續(xù)： （2） 考慮其中一人完成兩項，其他每人完成一項。試確定最優(yōu)分配方案，使完成任務的總時間最少。 解：虛擬戊，戊這一行數(shù)為相應列的最小數(shù)，則標準型效率矩陣表為：上頁上頁下頁下頁返回返回習題四 解續(xù)：用匈牙利法求出最優(yōu)分配方案為：即甲-B，乙-C、D，丙-E，丁-A，最少時間為131h。0100000100000011000000010X 上頁上頁下頁下頁返回返回v4.6續(xù) 分配考慮任務

22、A由甲或丙完成，任務C由丙或丁完成，任務E由甲、乙或丁完成，且規(guī)定4人中乙或丁完成兩項任務，其他每人完成一項。試確定最優(yōu)分配方案，使完成任務的總時間最少。解：虛擬戊，戊這一行數(shù)為（M，38，36，20，33），則標準型效率矩陣表為：上頁上頁下頁下頁返回返回習題四 解續(xù)：用匈牙利法求出最優(yōu)分配方案為：即甲-A，乙-D、E，丙-B，丁-C，最少時間為141h。1000000010010000010000001X 上頁上頁下頁下頁返回返回4.9 分別用分枝定界法和割平面法求解下列整數(shù)規(guī)劃問題.且為整數(shù), 0,35763-. .97max)(21212121xxxxxxtsxxza)4 , 1(035

23、763-. .97max42132121ixxxxxxxtsxxzi將它的松弛問題化為標準型：列初始單純形表最終單純形表上頁上頁下頁下頁返回返回習題四4.94.9題續(xù)：題續(xù)：( (分枝定界法分枝定界法) )因因松弛問題的解不是整數(shù)解松弛問題的解不是整數(shù)解, ,需需繼續(xù)進行分枝繼續(xù)進行分枝, ,加入約束條件加入約束條件x x2 233，當前界為：，當前界為：630z上頁上頁下頁下頁返回返回習題四（a）續(xù)：這一枝對應的解為：x1=32/7，x2=3，目標函數(shù)值z=59.上頁上頁下頁下頁返回返回習題四（a）續(xù)：另一枝加入約束條件x24這一枝無可行解,綜合起來可重新定界為：0Z59上頁上頁下頁下頁返回

24、返回（a）續(xù)：需繼續(xù)進行分枝,加入約束條件x14上頁上頁下頁下頁返回返回（a）續(xù)：加入約束條件x14這一枝對應的解為：x1=4，x2=3，目標函數(shù)值z=55.上頁上頁下頁下頁返回返回（a）續(xù)：加入約束條件x15上頁上頁下頁下頁返回返回（a）續(xù)：加入約束條件x15這一枝的目標函數(shù)值35小于左邊枝的55，應不予考慮。所有的分枝都討論完，修改上下界都應該為55，上界等于下界，即max Z Z=55，對應的最優(yōu)解為x1 = 4, x2 = 3。上頁上頁下頁下頁返回返回4.9(a)續(xù)：且為整數(shù), 0,35763-. .97max)(21212121xxxxxxtsxxza)4 , 1(035763-.

25、.97max42132121ixxxxxxxtsxxzi將它的松弛問題化為標準型：列初始單純形表最終單純形表上頁上頁下頁下頁返回返回4.9(a)續(xù)：續(xù)：(割平面法割平面法)找出非整數(shù)解變量中分數(shù)部分最大的找出非整數(shù)解變量中分數(shù)部分最大的一個基變量，寫下這一行的約束，再將生成的割平面條件一個基變量，寫下這一行的約束，再將生成的割平面條件加入松弛變量，然后加最終單純形表中：加入松弛變量，然后加最終單純形表中：21221227143sxx上頁上頁下頁下頁返回返回4.9(a)續(xù)：重新將生成割平面條件，并加入松弛變量續(xù)：重新將生成割平面條件，并加入松弛變量再加入當前單純形表中：再加入當前單純形表中：74

26、7671214ssx上頁上頁下頁下頁返回返回4.9 分別用分枝定界法和割平面法求解下列整數(shù)規(guī)劃問題.且為整數(shù), 0,30561652. .max)(21212121xxxxxxtsxxzb給出它的松弛問題B,用圖解法求解上述線性規(guī)劃問題B.12121212:max2516. . 6530,0Bzxxxxs txxx x上頁上頁下頁下頁返回返回圖解法： 、 、 、 、 、 、 、 、 、 、 、0 1 2 3 4 5 6 7 8 9 108 -7 -6 -5 -4 -3 -2 -1 -B12( 0 ):3.51.85.3Bxxz不是原問題的解但 ( 0 )zz3 . 5, 4zz定界：0,305

27、61652max:21212121xxxxxxxxzB上頁上頁下頁下頁返回返回分枝： 12(0):3.51.85.3Bxxzz3:11xB4:12xB356,0zz 0 1 2 3 4 5 6 7 43213:11xB2BB0,30561652max:21212121xxxxxxxxzB上頁上頁下頁下頁返回返回1212121121: max2+5166530. . 3,0Bzxxxxxxs txxx0,4 30 561652.max:2211212121xxxxxxxtsxxzB接下來求出（接下來求出（B1）和（）和（B2）的最優(yōu)解即可。）的最優(yōu)解即可。v 分枝后原B問題轉(zhuǎn)化成B1和B2兩個子

28、問題.上頁上頁下頁下頁返回返回圖解法： 0 1 2 3 4 5 6 7 43213:11xB00.500.200.3:)1(211zxxB20.520.100.4:)2(212zxxB2 . 553 . 54zzzz和和修改上下界：2B12(0):3.51.85.3Bxxz13x 14x 上頁上頁下頁下頁返回返回圖解法： 0 1 2 3 4 5 6 7 43213:11xB16.500.116.4:)21(2121zxxB無可行解:22B16. 552 . 55zzzz和和修改上下界：2B212(2 ):4.01.25.2Bxxz21x22x上頁上頁下頁下頁返回返回121212121221:

29、max2+5166530. . 4 1,0Bzxxxxxxs txxxx0,2 4 30 561652.max:222121212121xxxxxxxxtsxxzBv 分枝后原B2問題轉(zhuǎn)化成B21和B22兩個子問題.上頁上頁下頁下頁返回返回圖解法： 0 1 2 3 4 5 6 7 43213:11xB00.500.100.4:)211(21211zxxB00. 500. 000. 5:)211(21212zxxB00. 5516. 55zzzz和和修改上下界：2B2112(2):4.161.005.16Bxxz14x 15x 上頁上頁下頁下頁返回返回分枝定界的全過程：3.580.150.3:)0(21zxxB00.500.200.3:)1(211zxxB20.5