運籌學(xué) 整數(shù)線性規(guī)劃學(xué)習(xí)課件

整數(shù)線性規(guī)劃OperationsResearch,Autumn2017,C.-J.Chang整數(shù)線性規(guī)劃問題的提出在前面討論的線性規(guī)劃問題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對于某些問題，常要求解必須是整數(shù)(稱為整數(shù)解)。Ex.機器臺數(shù)、工作人數(shù)或裝貨車數(shù)。為滿足整數(shù)解的要求，初看起來，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過“舍入化整”就可以了。但這常常是不行的，因為化整后不見得是可行解；或雖是可行解，但不一定是最優(yōu)解。這種求最優(yōu)整數(shù)解的問題，須要另行研究，這樣的問題則稱為整數(shù)線性規(guī)劃(integerlinearprogramming,ILP)。2整數(shù)線性規(guī)劃的分類如果所有的變量都限制為(非負(fù))整數(shù)，就稱為純整數(shù)線性規(guī)劃(pureintegerlinearprogramming)或稱為全整數(shù)線性規(guī)劃(allintegerlinearprogramming)。如果僅一部分變量限制為整數(shù)，則稱為混合整數(shù)規(guī)劃(mixedintegerlinearprogramming)。整數(shù)線性規(guī)劃的一種特殊情形是0-1規(guī)劃，即變量的取值僅限于0或1。指派問題就是一個0-1規(guī)劃問題。3Ex.整數(shù)線性規(guī)劃某廠擬用集裝箱托運甲乙兩種貨物，相關(guān)數(shù)據(jù)如下表。問兩種貨物各托運多少箱，可使獲得利潤為最大?

用x1,x2分別為甲、乙兩種貨物的托運箱數(shù)(當(dāng)然都是非負(fù)整數(shù))，這就是一個(純)整數(shù)線性規(guī)劃問題，用數(shù)學(xué)模型可表示為：

4貨物體積(m3/箱)Ⅰ重量(100kg/箱)利潤(百元/箱)甲5220乙4510托運限制24m31300kgEx.整數(shù)線性規(guī)劃5在不考慮整數(shù)條件，所得到的最優(yōu)解是x1=4.8,x2=0,z=96用化整的方式，很容易找到最接近的整數(shù)解是x1=5,x2=0，但它不是可行解。用舍去尾數(shù)的化整，可得到整數(shù)可行解是x1=4,x2=0，z=80,但它不是最優(yōu)解。將線性規(guī)劃的最優(yōu)解經(jīng)過“化整”來解整數(shù)線性規(guī)劃，雖是最容易想到的，但常常得不到整數(shù)線性規(guī)劃的最優(yōu)解，甚至根本不是可行解。這個整數(shù)規(guī)劃問題的最優(yōu)解應(yīng)為x1=4,x2=1,z=90，目標(biāo)函數(shù)的差額是因變量不可分所造成的。分支定界解法在求解整數(shù)線性規(guī)劃時，如果可行域是有界的，首先容易想到的方法就是窮舉所有可行的整數(shù)解，然后比較它們的目標(biāo)函數(shù)值，從而確定最優(yōu)解。對于規(guī)模較小的問題，變量個數(shù)很少，可行解的組合數(shù)也較小時，這個方法是可行的，也是有效的。對于大型問題，可行的整數(shù)組合數(shù)會很大。適合的解法應(yīng)是僅檢查可行的整數(shù)組合的一部分，來找出最優(yōu)的整數(shù)解。分支定界解法就是其中之一。分支定界法可用于解純整數(shù)或混合整數(shù)線性規(guī)劃問題。20世紀(jì)60年代初由LandDoig和Dakin等提出，是解整數(shù)線性規(guī)劃的重要方法之一。6分支定界解法的基本思想考慮最大化整數(shù)線性規(guī)劃問題A，與它相應(yīng)的線性規(guī)劃記為問題B。我們從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)值z*的上界。而A的任意可行解的目標(biāo)函數(shù)值將是z*的一個下界。分支定界法就是將B的可行域分成子區(qū)域(稱為分支)的方法，逐步減小上界和增大下界，最終求到z*。7上界下界不考慮整數(shù)條件的最優(yōu)解是初始上界原點是初始下界每次分支定界后，若沒出現(xiàn)整數(shù)解，就向下調(diào)整上界每次分支定界后，若出現(xiàn)整數(shù)解，就向上調(diào)整下界反復(fù)數(shù)次分支定界后，當(dāng)上界與下界重合，此時就找到了最優(yōu)整數(shù)解分支定界解法8在不考慮整數(shù)條件，所得到的最優(yōu)解是x1=4.81,x2=1.82,z=356。在增加整數(shù)條件后，最優(yōu)解不可能比它更好，它是我們的上界。分支定界解法9我們以x1來分析，找出接近的整數(shù)，并把不含整數(shù)的部份去掉，將可行域分成兩部份，這個動作就是分支。原先最優(yōu)解的部份已被我們刪去，新問題的最優(yōu)值會改變，須要重新確認(rèn)，這叫作定界。最優(yōu)解是x1=4,x2=2.1,z=349最優(yōu)解是x1=5,x2=1.57,z=341繼續(xù)分解問題，因為B1問題目前的最優(yōu)解較好，故先分解B1問題。分支定界解法10我們在B1問題以x2來分析，找出接近的整數(shù)，并把不含整數(shù)的部份去掉。新問題的最優(yōu)值再要重新確認(rèn)。最優(yōu)解是x1=1.42,x2=3,z=327最優(yōu)解是x1=5,x2=1.57,z=341因為B3問題已為整數(shù)解，它會是我們整數(shù)規(guī)劃問題的下界。最優(yōu)解是x1=4,x2=2,z=340B4問題的最優(yōu)解比我們的下界差，故不須再進(jìn)行討論。而B2問題的最優(yōu)解比下界好，有可能會存在較佳的整數(shù)解，因此需要繼續(xù)討論。分支定界解法11我們在B2問題以x2來分析，找出接近的整數(shù)，并把不含整數(shù)的部份去掉。新問題的最優(yōu)值再要重新確認(rèn)。最優(yōu)解是x1=5.44,x2=1,z=308最優(yōu)解是x1=4,x2=2,z=340B5問題的最優(yōu)解比我們的下界差，故不須再進(jìn)行討論。

B6問題無可行解。所以，可以斷定問題B3的解x1=4,x2=2,z=340會是最優(yōu)整數(shù)解。分支定界法求解步驟(最大化)將要求解的整數(shù)線性規(guī)劃問題稱為問題A，將與它相應(yīng)的線性規(guī)劃問題稱為問題B：解問題B，可能得到以下情況之一：B沒有可行解，這時A也沒有可行解，則停止。B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止。B有最優(yōu)解，但不符合問題A的整數(shù)條件，則它為目標(biāo)的上界。

用觀察法找問題A的一個整數(shù)可行解，可取xj=0,j=1,…,n，求得其目標(biāo)函數(shù)值，則它為目標(biāo)的下界。目標(biāo)函數(shù)值會落于上界與下界之間。12分支定界法求解步驟(最大化)進(jìn)行迭代分支，在B的最優(yōu)解中任選一個不符合整數(shù)條件的變量xj，其值為bj，以［bj］表示小于bj的最大整數(shù)。構(gòu)造兩個約束條件xj≤［bj］和xj≥［bj］+1將這兩個約束條件，分別加入問題B，求兩個后繼規(guī)劃問題B1和B2。不考慮整數(shù)條件求解這兩個后繼問題。定界，以每個后繼問題為一分支標(biāo)明求解的結(jié)果，比較所有分支問題的解，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界。比較與剪支各分支的最優(yōu)目標(biāo)函數(shù)中若有小于下界者，則剪掉這支(用打×表示)，即以后不再考慮了。若大于下界，且不符合整數(shù)條件，則再進(jìn)行分支(步驟3.1)。一直到最后得到得最優(yōu)整數(shù)解為止。13Ex.分支定界法請用分支定界法求解下列整數(shù)規(guī)劃問題。14不考慮整數(shù)條件的最優(yōu)解是x1=4.81,x2=1.82,z=356。問題Bx1=4.81x2=1.82z=356問題B4x1=1.43x2=3z=327問題B3x1=4x2=2z=340問題B5x1=5.44x2=1z=308問題B6無可行解問題B1x1=4x2=2.1z=349問題B2x1=5x2=1.57z=341×××所以，最優(yōu)整數(shù)解為x1=4,x2=2,z=340。隨堂練習(xí)不考慮整數(shù)條件時，下列問題的最優(yōu)解為x1=3.667,x2=0,z=36.667，請用分支定界法求解下列整數(shù)規(guī)劃問題。15課后練習(xí)不考慮整數(shù)條件時，下列問題的最優(yōu)解為x1=1.429,x2=4.286,z=41.429，請用分支定界法求解下列整數(shù)規(guī)劃問題。16課后練習(xí)不考慮整數(shù)條件時，下列問題的最優(yōu)解為x1=1.5,x2=3.333,z=4.833，請用分支定界法求解下列整數(shù)規(guī)劃問題。170-1型整數(shù)線性規(guī)劃0-1型整數(shù)線性規(guī)劃是整數(shù)線性規(guī)劃中的特殊情形，它的變量xi僅取值0或1。這時xi稱為0-1變量，或稱二進(jìn)制變量。xi僅取值0或1這個條件可由下述約束條件所代替:

xi≤1,xi≥0,整數(shù)它和一般整數(shù)線性規(guī)劃的約束條件形式是一致的。在實際問題中，如果引入0-1變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個問題中討論了。在本節(jié)我們先介紹引入0-1變量的實際問題，再研究解法。18投資場所的選定—相互排斥的計劃某公司擬在市東、西、南三區(qū)建立門市部，擬議中有7個位置(點)Ai(i=1，2，…，7)可供選擇。規(guī)定：在東區(qū)，由A1,A2,A3三個點中至多選兩個；在西區(qū)，由A4,A5兩個點中至少選一個；在南區(qū)，由A6,A7兩個點中至少選一個。如選用Ai點，設(shè)備投資估計為bi元，每年可獲利潤估計為ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個點可使年利潤為最大?19投資場所的選定—相互排斥的計劃先引入0-1變量xi

(i=1,2，…，7)

于是問題可列成：

200-1型整數(shù)線性規(guī)劃的解法求解0-1型整數(shù)線性規(guī)劃最容易想到的方法(和一般整數(shù)線性規(guī)劃的情形一樣)，就是窮舉法，即檢查變量取值為0或1的每一種組合，并比較目標(biāo)函數(shù)值以求得最優(yōu)解。這就需要檢查變量取值的2n個組合。當(dāng)變量個數(shù)n較大(例如n＞10)時，這幾乎是不可能的。因此，需要設(shè)計一些特殊的方法，只需要檢查變量取值組合中的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法(implicitenumeration)。分枝定界法也是一種隱枚舉法。21隱枚舉法的步驟對于有n個變量的0-1規(guī)劃，可用以下步驟求解：列出2n個可能解。計算所有解的目標(biāo)值。依目標(biāo)值的大小，依序檢驗其可行性(每個解依次代入約束條件左側(cè)，求出數(shù)值，看是否符合不等式條件)。如某一條件不符合，同行以下各條件就不必檢查。第一個可行解就是最優(yōu)解。22Ex.隱枚舉法請用隱枚舉求解下列0-1整數(shù)規(guī)劃問題。23點z值條件可行性？(1)(2)(3)(4)(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)05-2338160215√所以，最優(yōu)整數(shù)解為(x1,x2,x3)=(1,0,1),z=8。(1)(2)(3)(4)隨堂練習(xí)請用隱枚舉求解下列0-1整

數(shù)規(guī)劃問題。24點z值條件可行性？(1)(2)(3)(0,0,0,0)0(0,0,0,1)4(0,0,1,0)3(0,0,1,1)7(0,1,0,0)5(0,1,0,1)9(0,1,1,0)8(0,1,1,1)12382√(1,0,0,0)2(1,0,0,1)6(1,0,1,0)5(1,0,1,1)9(1,1,0,0)7(1,1,0,1)11(1,1,1,0)10(1,1,1,1)14-1×所以，最優(yōu)整數(shù)解為

(x1,x2,x3,x4)=(0,1,1,1),z=12。(1)(2)(3)隨堂練習(xí)請用隱枚舉求解下列0-1整數(shù)規(guī)劃問題。25點z值條件可行性？(1)(2)(3)(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)02354679081√所以，最優(yōu)整數(shù)解為(x1,x2,x3)=(1,1,1),z=9。(1)(2)(3)指派問題在生活中經(jīng)常遇到這樣的問題，某單位需完成n項任務(wù)，恰好有n個人可承擔(dān)這些任務(wù)。由于每人的專長不同，各人完成任務(wù)不同(或所費時間)，效率也不同。于是產(chǎn)生應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高(或所需總時間最小)。這類問題稱為指派問題或分派問題(assignmentproblem)。26Ex.指派問題有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人。他們將中文說明書翻譯成不同語種的說明書所需時間如下表所示。問應(yīng)指派何人去完成何工作，使所需總時間最少?

27人員任務(wù)EJGR甲215134乙1041415丙9141613丁78119指派問題類似有：有n項加工任務(wù)，怎樣指派到n臺機床上分別完成的問題；有n條航線，怎樣指定n艘船去航行問題…。對應(yīng)每個指派問題，需有類似上題那樣的數(shù)表，稱為效率矩陣或系數(shù)矩陣，其元素cij>0(i,j=1,2,…,n)表示指派第i人去完成第j項任務(wù)時的效率(或時間、成本等)。解題時需引入變量xij；其取值只能是1或0。并令

28指派問題的線性規(guī)劃模式當(dāng)問題要求極小化時數(shù)學(xué)模型是：

滿足約束條件的可行解xij可以寫成表格或矩陣形式，稱為解矩陣。29每項任務(wù)只能由一人完成。每個人只能完成一項任務(wù)。解矩陣(xij)中各行各列的元素之和都是1。Ex.指派問題的線性規(guī)劃模式30指派問題指派問題是0-1規(guī)劃的特例，也是運輸問題的特例；即n=m,

aj=bi=1。當(dāng)然可用整數(shù)線性規(guī)劃，0-1規(guī)劃或運輸問題的解法去求解，這就如同用單純形法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法。指派問題的最優(yōu)解有這樣性質(zhì)，若從系數(shù)矩陣(cij)的一行(列)各元素分別減(加)去一個常數(shù)，得到新矩陣(bij)，那么以(bij)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同。31指派問題利用這個性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變。在系數(shù)矩陣(bij)中，我們關(guān)心位于不同行不同列的0元素，以下簡稱為獨立的0元素。若能在系數(shù)矩陣(bij)中找出n個獨立的0元素；則令解矩陣(xij)中對應(yīng)這n個獨立的0元素的元素取值為1，其他元素取值為0。將其代入目標(biāo)函數(shù)中得到zb=0，它一定是最小。這就是以(bij)為系數(shù)矩陣的指派問題的最優(yōu)解。也就得到了原問題的最優(yōu)解。32匈牙利法的步驟(1)系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。每行減去該行最小元素每列減去該列最小元素進(jìn)行指派，以尋求最優(yōu)解。從只有一個0元素的行開始，給這個0元素加圈，記作。。然后劃去所在列的其它零元素，記作。給只有一個0元素列的0元素加圈，記作；然后劃去所在行的其它零元素，記作。反復(fù)進(jìn)行2.1與2.2，直到所有0元素都被圈出和劃掉為止。若仍有未畫圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，這行(列)各0元素所在列(行)中0元素的數(shù)目，選擇0元素少的那列的0元素加圈，然后劃掉同行同列的其它0元素。若

元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m＜n，則轉(zhuǎn)入下一步。33這表示對這行所代表的人，只有一種任務(wù)指派。這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。Ex.匈牙利法有甲、乙、丙、丁四個人，要指派E、J、G、R四個工作，每人一個工作，若每個人所需的工作時間(小時)如下表。應(yīng)該如何指派，才能使所需總時間最少？34人員任務(wù)EJGR甲215134乙1041415丙9141613丁78119所以，最優(yōu)解為甲R、乙J、丙E、丁G，所需時間為4+4+9+11=28(小時)。隨堂練習(xí)某家小型航空公司有6位空服員，該公司將指派這些空服員服勤未來六個月的飛行航線，指派的方式希望這些空服員在外過夜的次數(shù)可以達(dá)到最少，每位空服員服勤各預(yù)定航線必須在外過夜的次數(shù)如下表，試決定最佳的指派方式？空服員航線A航線B航線C航線D航線E航線F1746105824551276399117108411685910558610766101211991035最優(yōu)解為：1B、2A、3F、4D、5C、6E，所需次數(shù)為4+4+8+5+6+9=36。匈牙利法的步驟(2)作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣能找到最多的獨立元素。步驟：對沒有的行打勾(

)。對已打勾(

)的行中，所有含元素的列打勾。再對已打勾(

)的列中，含有的行打勾(

)重復(fù)3.2與3.3，直到得不到新的打勾(

)的行、列為止。對沒有勾(

)的行畫橫線，對有勾(

)的列畫縱線，這就得到覆蓋所有0元素的最少直線。36匈牙利法的步驟(3)對矩陣進(jìn)行變換。為此在沒有被直線覆蓋的部分中找出最小元素。然后在打勾(

)行各元素中都減去這最小元素，而在打勾(

)列的各元素都加上這最小元素。沒有被線蓋住的成本減去最小元素被一條線蓋住的成本不變被兩條線蓋住的成本加上最小元素新系數(shù)矩陣的最優(yōu)解和原問題相同?；氐?進(jìn)行指派。37Ex.匈牙利法求下表所示效率矩陣的指派問題的最小解。38人員任務(wù)ABCDE甲127979乙89666丙71712149丁15146610戊4107109

所以，最優(yōu)解為：甲B、乙D、丙E、丁C、戊A，所需時間為7+6+9+6+4=32；

或，甲B、乙C、丙E、丁D、戊A，所需時間為7+6+9+6+4=32。

隨堂練習(xí)某出版公司目前有五本書要完成，有5位主編可以執(zhí)行編審計劃，但是因為領(lǐng)域與專長的不同，每位主編針對每本書稿的編審所需時間也不相同，又因趕稿因素，一本書稿只能指定一位主編編審，下表為預(yù)估所需之編審時間(以小時計)，請問最佳的指派方式為何？39書稿主編A主編B主編C主編D主編E1128101613291014139317149181241571191851218221127最優(yōu)解為：1B、2E、3C、4D、5A，所需時間為8+9+9+9+12=47。隨堂練習(xí)有4個工人