運籌學(xué)整數(shù)規(guī)劃

1、第7章 整數(shù)規(guī)劃1 整數(shù)規(guī)劃的基本特點 在前面的線性規(guī)劃問題中，它的解都假設(shè)為可以取連續(xù)數(shù)值。但是在許多實際問題中，決策變量僅僅取整數(shù)值時才有意義，比如變量表示的是工人的人數(shù)、機器的臺數(shù)、貨物的箱數(shù)、裝貨的車皮數(shù)等等。 為了滿足整數(shù)解的要求，比較自然的簡便方法似乎就是把用線性規(guī)劃方法所求得的非整數(shù)解進行“四舍五入”取整或“舍尾取整”處理。當(dāng)然這樣做有時確實也是有效的，可以取得與整數(shù)最優(yōu)解相近的可行整數(shù)解，因此它是實際工作中經(jīng)常采用的方法。但是實際問題中并不都是如此，有時這樣處理得到的解可能不是原問題的可行解，有的雖是原問題的可行解，但卻不是整數(shù)最優(yōu)解。（詳見后面例1）。因而有必要專門研究只取整

2、數(shù)解的線性規(guī)劃的解法問題。 在線性規(guī)劃問題中，如果最優(yōu)解必須是整數(shù)，則把這類LP問題稱為整數(shù)規(guī)劃（IP）。 在一個LP中要求所有變量取整數(shù)值的，稱為純整數(shù)（線性）規(guī)劃；只要求一部分變量值取整數(shù)的，稱為混合整數(shù)（線性）規(guī)劃。 在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，則稱這樣的IP為0-1規(guī)劃。例1 現(xiàn)有甲、乙兩種貨物擬用集裝箱托運，每件貨物的體積、重量、可獲利潤，以及集裝箱的托運限制如下表：試確定集裝箱中托運甲、乙貨物的件數(shù)，使托運利潤最大。 例2.某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤以及托運所受限制入下表所示。甲種貨物至多托運4件，問兩種貨物各托運多少件，

3、可使獲得利潤最大。貨物貨物每件體積每件體積（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利潤每件利潤（百元）（百元）甲甲乙乙19527344023托運限制托運限制1365140 分析：設(shè)x1,x2分別為甲、乙兩種貨物托運的件數(shù)，這是一個純整數(shù)規(guī)劃問題，其數(shù)學(xué)模型為為整數(shù)21211212121,0,41404041365273195. .32maxxxxxxxxxxtsxxz該問題的圖解如下所示，12312340 x2x1 2x1+3x2=62x1+3x2=14.66 2x1+3x2=14(4,2)(2.44,3.26)4x1+40 x2=140 性質(zhì): 任何求最大目標(biāo)函數(shù)值的

4、純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值； 任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。2 分枝定界法（ branch & bound method ） 分枝定界法是基于“枚舉”思想的一種求解整數(shù)規(guī)劃的常用方法。它先求與該整數(shù)規(guī)劃相對應(yīng)的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)規(guī)劃條件，則求出整數(shù)規(guī)劃的上、下界用增加約束條件的方法，并把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后求得整數(shù)規(guī)劃的最優(yōu)解。典例：且均取整數(shù)值最

5、優(yōu)解：求下述整數(shù)規(guī)劃問題的, 0,5 . 45 . 01432. .23max21212121xxxxxxtsxxz 第一步：尋找替代問題并求解，替代問題必須是原問題的松弛問題。典例的松弛問題是一個線性規(guī)劃問題，記作L0:0,5 . 45 . 01432. .23max212121210 xxxxxxtsxxzL ： L0的最優(yōu)解為（3.25，2.5）,不是原問題的可行解。 第二步：分枝定界。方法是將替代問題分成若干子問題，然后對各子問題求最優(yōu)解。 如該解滿足原問題的約束，即找到了一個原問題的可行解，否則該解為所屬分枝的邊界值（對求極大化問題該邊界值為上界，對求極小化問題，該邊界值為下界）；

6、如果所有子問題的最優(yōu)解均非原問題的可行解，則選取其邊界值最大（求極大時）或最小（求極小時）的子問題進一步再細(xì)分成子問題求解。 本例中L0的最優(yōu)解均不是整數(shù)，從中任選一個，設(shè)選x2進行分枝，分成兩個子問題L1和L2：035 . 45 . 01432. .23max:0,25 . 45 . 01432. .23max:1221212122122121211xxxxxxtsxxzLxxxxxxxtsxxzL 求得L1的最優(yōu)解為（3.5，2），z=14.5。L2的最優(yōu)解為（2.5，3），z=13.5。均非原問題的最優(yōu)解，選取邊界較大的子問題L1繼續(xù)分枝。0425 . 45 . 01432. .23ma

7、x:0,325 . 45 . 01432. .23max:21221212112211221212111xxxxxxxtsxxzLxxxxxxxxtsxxzL 求得L11的最優(yōu)解為（3，2），z=13。L12的最優(yōu)解為（4，1），z=14。這兩個最優(yōu)解均屬原問題的可行解，保留可行解中較大的一個z=14。 第三步：剪枝。將各子問題邊界值與保留的可行解的值進行比較，把邊界值劣于可行解的分枝剪去。如果除保留下來的可行解外，其余分枝均被剪去，則該可行解就是原問題最優(yōu)解。否則回到第二步，選取邊界值最優(yōu)的一個繼續(xù)分枝。如果計算中又出現(xiàn)新的可行解時，則與原可行解比較，保留最優(yōu)的，并重復(fù)上述步驟。此問題中，子

8、問題L12的最優(yōu)解（4，1），z=14即為本問題的最優(yōu)解。典例用分枝定界法計算的全過程可表示為：L0:x1=3.25 x2=2.5Z=14.75L12:x1=4 x2=1Z=14L11:x1=3 x2=2Z=13L2:x1=2.5 x2=3Z=13.5L1:x1=3.5 x2=2Z=14.5x22x14x23x133 割平面法 這是求解整數(shù)規(guī)劃問題最早提出的一種方法，1958年由Gomory提出。 他的基本思想是在整數(shù)規(guī)劃問題的松弛問題中依次引進線性約束條件，是可行域逐步縮小。但每次切割只割去問題的部分非整數(shù)解，直到使問題的目標(biāo)函數(shù)值達到最優(yōu)的整數(shù)點成為縮小后可行域的一個頂點，這樣即可用線性規(guī)

9、劃問題的方法找出這個最優(yōu)解。 具體步驟如下： 第一步：把問題中所有約束條件的系數(shù)均化為整數(shù)，若不考慮變量的整數(shù)約束，可寫出一般的線性規(guī)劃問題G0：0,921432. .23max212121210 xxxxxxtsxxzG ：用單純形法求得上述問題的最終單純形表如下：迭代迭代次數(shù)次數(shù)基變基變量量CB x1 x2 x3 x4 b比值比值bi/aij 3 2 0 0 x2x123 0 1 1/2 -1/2 1 0 -1/4 3/4 5/213/4Cj-Zj 0 0 -1/4 -5/4 234234243424341112222111(0)( 1)(2)2221112222,01110222Gomo

10、ry1122xxxxxxxxxxx xxx 第二步：找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個基變量，并寫下這一行的約束將上式中所有常數(shù)寫成整數(shù)與一個正分?jǐn)?shù)值之和得分?jǐn)?shù)項移到等式右端，整數(shù)項移到等式左端得到右端也必須取整數(shù)值，又因，因此有加上松弛變量后得約束345102xxx 第三步：將Gomory約束加到G0中得到新的線性規(guī)劃問題G1如下：)5 , 1(0212121921432. .23max543421321211jxxxxxxxxxxtsxxzGj： 第四步：重復(fù)第一至第三步直到找出最優(yōu)的整數(shù)解為止。求解G1可以采用對偶單純形法：迭代次數(shù)基變量CB x1 x2 x3 x4 x5 b比值bi/

11、aij 3 2 0 0 0 x2x1x5230 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 12（1/2）3（1/4）-1/2Cj-Zj 0 0 -1/4 -5/4 0 x2x1x3230 0 1 0 -1 1/2 1 0 0 1 -1/2 0 0 1 1 -223（1/2）1Cj-Zj 0 0 0 -1 -1/2021210212121213213212132165555415541541xxxGomoryxxxxxxxxxxx加入松弛變量后得約束為：由此得新的移項后得數(shù)部分將系數(shù)分成整數(shù)與非整。先從表中寫出非整數(shù)解，重復(fù)第二步由于表中得出的解仍為

12、將松弛變量加到G1中得到LP問題G2:)6 , 1(02121212121921432. .23max65543421321212jxxxxxxxxxxxxtsxxzGj：采用對偶單純形法求解:迭代次數(shù)基變量CB x1 x2 x3 x4 x5 x6 b 3 2 0 0 0 0 x2x1x3x62300 0 1 0 -1 1/2 0 1 0 0 1 -1/4 0 0 0 1 1 -1 0 0 0 0 0 -1/2 12（1/2）3（1/2）1-1/2Cj-Zj 0 0 -1/4 -5/4 0 x2x1x3x52300 0 1 0 -1 0 2 1 0 0 1 0 -1 0 0 1 1 0 -4

13、0 0 0 0 1 -21431Cj-Zj 0 0 0 -1 0 -1 由于從表中已經(jīng)找到變量的整數(shù)解x1=4,x2=1。求解過程到此結(jié)束。練習(xí)：4 分配問題及其解法1.問題的提出與數(shù)學(xué)模型2.匈牙利法3.兩點說明1、問題的提出與數(shù)學(xué)模型 分配問題也稱指派問題（assignment problem），是一種特殊的整數(shù)規(guī)劃問題。假定有m項任務(wù)分配給n個人去完成，并指定每人完成其中一項，每項只交給其中一個人去完成，應(yīng)如何分配使總的效率最高。 例例1 有一份說明書，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成，因個人專長不同，他們完成翻譯不同文字所需的時間（小時）如下表所示。應(yīng)如何

14、分配，使這四個人分別完成這四項任務(wù)總的時間為最小。人人工作工作甲甲乙乙丙丙丁丁譯成英文譯成英文譯成日文譯成日文譯成德文譯成德文譯成俄文譯成俄文2151341041415914161378119 設(shè)用aij表示分配問題的效率矩陣，令), 1;, 1( 1011. .min1111mjmiorxxxtsxazijmiijmjijmimjijij）（項任務(wù)個人去完成第，不分配第項任務(wù)個人去完成第，分配第mjmijijixij, 1;, 1012、匈牙利法 可以用解運輸問題的表上作業(yè)法來解分配問題，但通常用更有效的匈牙利法求解。 基本思想：如果效率矩陣的所有元素大于等于零，則只要令對應(yīng)于這些零元素位置

15、的xij=1,其余的xij=0，則 就是原問題的最優(yōu)解。如效率矩陣為：mimjijijxaz110823314309120201402390 如何尋找效率矩陣中這些位于不同行， 不同列的零元素是一個非常重要的問題。匈牙利數(shù)學(xué)家Konig證明了下面兩個基本定理，為解決這個問題奠定了基礎(chǔ)。 定理定理1 如果從分配效率矩陣aij的每一行元素中分別減去（或加上）一個常數(shù)ui(被稱為該行的位勢），從每一列分別減去（或加上）一個常數(shù)vj（稱為該列的位勢），得到一個新的效率矩陣bij，若其中bij=aij-ui-vj，則二者的最優(yōu)解相等。 定理定理2 若矩陣A的元素可分為“0”與非“0”兩部分，則覆蓋“0”

16、元素的最少直線數(shù)等于位于不同行不同列的”0”元素的最大個數(shù)。匈牙利法的計算步驟：第一步：每一行均減去該行的最小值，每一列均減去該列的最小值，使每行每列至少有一個零元素（變換效率矩陣）21097087508251541481101041105413141611235023004151390119501145第二步：試求最優(yōu)解*082511054230001145 第三步：第三步：作覆蓋所有零元素的最少直線集合作覆蓋所有零元素的最少直線集合1.1.對沒有對沒有 的行打的行打2.2.對打了對打了的行上的行上0 0元素所在的列打元素所在的列打3.3.對打了對打了的列上的列上 所在的行打所在的行打4.4

17、.對打了對打了的行上的行上0 0元素所在的列打元素所在的列打 直至打不出新的行和新的列直至打不出新的行和新的列 對沒有打?qū)]有打的行劃橫線，對打了的行劃橫線，對打了的列劃的列劃豎線，這樣就得到能夠覆蓋所有零元素的最少豎線，這樣就得到能夠覆蓋所有零元素的最少直線組合。直線組合。*0*0第四步:繼續(xù)變換效率矩陣，試求最優(yōu)解，回到第二步。從未被直線覆蓋的所有元素中找出一個最小元素，然后將效率矩陣未劃橫線的行均減去這個最小元素，劃豎線的列均加上這個最小元素。 最優(yōu)解為*0603130544300092300100100()00011000ijxmin94 11 428,min24 11 4522228

18、zz 或者2、兩點說明 分配問題中如果人數(shù)和工作任務(wù)數(shù)不相等時的處理辦法。如人數(shù)大于任務(wù)數(shù)。 如果目標(biāo)函數(shù)為最大化問題。轉(zhuǎn)化為最小化問題，按定理1處理，使效率矩陣各元素大于等于零。 例如，有四項工作分配給六個人去完成，每個人完成各項工作的時間如下表所示。規(guī)定每個人完成一項工作，每項工作只交給一個人去完成。應(yīng)從這六個人中挑選哪四個人去完成，花費的總時間為最少。工作工作人人 123456 3 6 2 6 3 6 2 6 7 1 4 4 7 1 4 4 3 6 5 8 3 6 5 8 6 4 3 7 6 4 3 7 5 2 4 3 5 2 4 3 5 7 6 2 5 7 6 2 增添兩項假想的工作，

19、每個人完成這兩項工作的時間都為零。工作工作人人 123456 3 6 2 6 3 6 2 6 0 00 0 7 1 4 4 7 1 4 4 0 00 0 3 6 5 8 3 6 5 8 0 00 0 6 4 3 7 6 4 3 7 0 00 0 5 2 4 3 5 2 4 3 0 00 0 5 7 6 2 5 7 6 2 0 00 0 如果目標(biāo)函數(shù)為最大化問題。轉(zhuǎn)化為最小化問題，按定理1處理，使效率矩陣各元素大于等于零。 例如，如果前面翻譯的例子中，不是求用時最少而是求翻譯的文字最多，則相應(yīng)的目標(biāo)函數(shù)應(yīng)該寫作：mimjijijxaz11max因為上述目標(biāo)函數(shù)等價于：11min ()mmijij

20、ijzax再根據(jù)定理1，使效率矩陣中全部元素變?yōu)?，就可以用匈牙利法進行求解。作業(yè)1.用匈牙利法解下列系數(shù)矩陣的最小化指派問題：791012131216171516141511 121516 2.分配甲、乙、丙、丁四個人去完成5項任務(wù)。每人完成各項任務(wù)時間如下表所示。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個人可兼完成兩項任務(wù)，其余三人每人完成一項。試確定總花費時間為最少的指派方案。4523364224丁3240282734丙3320263839乙3742312925甲EDCBA任務(wù)人5 整數(shù)規(guī)劃的應(yīng)用舉例 例例1 紅星日用化工廠為發(fā)運產(chǎn)品，下一年度需要6種不同容積的包裝箱。每種包裝箱的需求量及生產(chǎn)

21、一個的可變費用如下表所示： 由于生產(chǎn)不同容積包裝箱時需要進行專門準(zhǔn)備、下料等，生產(chǎn)某一容積包裝箱的固定費用均為1200元。又若某一容積包裝箱數(shù)量不夠時，可用比它容積大的代替。試問該工廠應(yīng)定做哪幾種代號的包裝箱各多少個，使費用最節(jié)??？包裝箱代號123456容積（m3）0.080.10.120.150.20.25需求量（個）500550700900450400可變費用（元/個）581012.116.318.2 解解：設(shè)xj(j=1,.6)為代號j包裝箱的定做數(shù)量，yj=1,定做第j種包裝箱；0，否則。則本例的數(shù)學(xué)模型為：)6 , 1( 10, 0)6 , 1(3000245017508504003

22、500. .2 .183 .161 .1210851200min65432654365465665432161654321jyxjMyxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxyzjjjjjj或 本題最優(yōu)決策為：生產(chǎn)包裝箱1500個，31250個，4900個，6850個，不生產(chǎn)代號為2、5的包裝箱，總計費用為46160元。Lindo求解程序：Min 1200y1+1200y2+1200y3+1200y4+1200y5+1200y6+5x1+8x2+10 x3+12.1x4+16.3x5+18.2x6Stx1+x2+x3+x4+x5+x6=3500 x6=400 x5+x6=8

23、50 x4+x5+x6=1750 x3+x4+x5+x6=2450 x2+x3+x4+x5+x6=3000 x1-100000y1=0 x2-100000y2=0 x3-100000y3=0X4-100000y4=0X5-100000y5=0X6-100000y6=0Endgin x1gin x2gin x3gin x4gin x5gin x6Int y1Int y2Int y3Int y4Int y5Int y6 例例2 春江市計劃為新建的5個居民小區(qū)中的兩個分別各設(shè)立一所小學(xué)。下表給出了各小區(qū)及各小區(qū)內(nèi)及各小區(qū)間的平均步行時間及各小區(qū)的小學(xué)生人數(shù)。要求為該市提供決策建議，兩所小學(xué)應(yīng)分別建于哪兩個居民小區(qū)，以及各居民小區(qū)學(xué)生應(yīng)分別到那所小學(xué)上學(xué)，使學(xué)生總的上學(xué)步行時間最少。小學(xué)小學(xué)位于位于該區(qū)該區(qū)小學(xué)小學(xué)生數(shù)生數(shù)至其他區(qū)步行時間至其他區(qū)步行時間 1 2 3 4 512345200180300160350 5 20 15 25 10 20 4 20 15 25 15 20 6 25 15 25 15 25 4 12 10 25 15 12 5 先將表中每行數(shù)字分別乘上該行學(xué)生數(shù)，表中數(shù)字表明該居民區(qū)小學(xué)生到可能設(shè)于各區(qū)的小學(xué)上學(xué)的總的步行時間，用kij表示。至至j由由i 1 2 3 4 512345 1000 400