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

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

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

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

用觀察法找問題A的一個整數可行解，可取xj=0,j=1,…,n，求得其目標函數值，則它為目標的下界。目標函數值會落于上界與下界之間。12分支定界法求解步驟(最大化)進行迭代分支，在B的最優解中任選一個不符合整數條件的變量xj，其值為bj，以［bj］表示小于bj的最大整數。構造兩個約束條件xj≤［bj］和xj≥［bj］+1將這兩個約束條件，分別加入問題B，求兩個后繼規劃問題B1和B2。不考慮整數條件求解這兩個后繼問題。定界，以每個后繼問題為一分支標明求解的結果，比較所有分支問題的解，找出最優目標函數值最大者作為新的上界。從已符合整數條件的各分支中，找出目標函數值為最大者作為新的下界。比較與剪支各分支的最優目標函數中若有小于下界者，則剪掉這支(用打×表示)，即以后不再考慮了。若大于下界，且不符合整數條件，則再進行分支(步驟3.1)。一直到最后得到得最優整數解為止。13Ex.分支定界法請用分支定界法求解下列整數規劃問題。14不考慮整數條件的最優解是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×××所以，最優整數解為x1=4,x2=2,z=340。隨堂練習不考慮整數條件時，下列問題的最優解為x1=3.667,x2=0,z=36.667，請用分支定界法求解下列整數規劃問題。15課后練習不考慮整數條件時，下列問題的最優解為x1=1.429,x2=4.286,z=41.429，請用分支定界法求解下列整數規劃問題。16課后練習不考慮整數條件時，下列問題的最優解為x1=1.5,x2=3.333,z=4.833，請用分支定界法求解下列整數規劃問題。170-1型整數線性規劃0-1型整數線性規劃是整數線性規劃中的特殊情形，它的變量xi僅取值0或1。這時xi稱為0-1變量，或稱二進制變量。xi僅取值0或1這個條件可由下述約束條件所代替:

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

(i=1,2，…，7)

于是問題可列成：

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

數規劃問題。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×所以，最優整數解為

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

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

28指派問題的線性規劃模式當問題要求極小化時數學模型是：

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

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

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

)。對已打勾(

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

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

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

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

)的行畫橫線，對有勾(

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

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

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

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

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

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