1、第五章 整數規劃5.1 5.1 整數規劃數學模型和解的特點整數規劃數學模型和解的特點5.2 5.2 割平面法和分支定界法割平面法和分支定界法5.3 0-15.3 0-1整數規劃整數規劃5.4 5.4 隱枚舉法隱枚舉法5.5 5.5 匈牙利法匈牙利法本章學習要求p熟悉分支定界法和割平面法的原理及其應用p掌握求解0-1規劃問題的隱枚舉法p掌握求解指派問題的匈牙利法5.1整數規劃數學模型和解的特點整數規劃數學模型和解的特點n整數規劃的類型整數規劃的類型n整數規劃的數學模型實例整數規劃的數學模型實例n整數規劃解的特點整數規劃解的特點 某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量和可獲得的利潤及托運

2、所受限制如表，問兩種貨物各托運多少箱，使得利潤最大？ 設甲乙兩種貨物各托運X1,X2箱貨物體積重量利潤甲5220乙4510托運限制2413Max z=20 x1+10 x2 5x1+4x224 2x1+5x213 x1,x20且為整數貨物體積重量利潤甲5220乙4510托運限制2413 現有資金總額B，可供選擇的投資項目有m個，項目j所需要的投資額和預期的收益分別為aj和cj，由于各種原因有3個附加條件：若選項目1，則必選項目2，反之則不一定；項目3和項目4必須選一個；項目5，6，7中恰好選2個。應當如何選擇投資項目才能使總預期收益為最大？解：每一個投資項目都有被選擇和不被選擇兩種可能，設xj

3、=1 對j項目投資 0 對j項目不投資Max z=cjxj ajxjB x2x1 x3+x41 x5+x6+x7=2 xj=0或1 1.整數線性規劃（整數線性規劃（ILP）的類型）的類型整數線性規劃的一般形式：Max (min) z=CX AX(,=)b X 0 X中部分或全部為整數 X為0或1線性規劃模型max z=x1+4x2s.t. 14x1+42x2196 -x1+ 2x2 5 x1, x20整數規劃模型max z=x1+4x2s.t. 14x1+42x2196 -x1+ 2x2 5 x1, x20 x1,x2 為整數0 1 2 3 4 5 6 7 84321A(2.6, 3.8)B(

4、5, 3)2.整數線性規劃（整數線性規劃（ILP）實例）實例線性規劃的最優解A(x1, x2)=(2.6, 3.8)不是整數解，目標函數值為z=17.8。整數規劃的最優解B(x1, x2)=(5,3)目標函數值為z=17。線性規劃最優解A(2.6, 3.8)四舍五入得到的解為(3,4)，不是可行解；舍去尾數取整的解為(2,3)，目標函數值z=14。因此整數規劃的最優解一般不能由線性規劃的最優解通過簡單的取整得到。0 1 2 3 4 5 6 7 84321A(2.6, 3.8)B(5, 3)3.整數線性規劃（整數線性規劃（ILP）解的特點）解的特點5.2 割平面法和分支定界法割平面法和分支定界法

5、n割平面法（割平面法（Gomory法）法）n分支定界法分支定界法1.割平面法割平面法1.割平面法割平面法1.割平面法割平面法ikikibxaxbibikikikifNxfNx)(bikikfxf1.割平面法割平面法且為整數, 4 , 1, 020546242132121jxxxxxxxxxMaxZjCj1100CBXBbx1x2x3x40 x3621100 x4204501j1100 35x1入 x3出1x1311/21/200 x4803-21j01/2 -1/20 68/3x2入 x4出1x28/301-2/3 1/31x15/3105/6 -1/6j00-1/6 -1/635616543

6、1xxx32)1 (3265654143xxxx5456543xxx534544(2)55xxxxcj11000CBXBbx1x2x3x4x51X15/3105/6 -1/601X28/301-2/3 1/300 x500-5/6 -5/61j00-1/6 -1/60-1/51/5-1X11100-111X216/50101-4/50 x34/50011-6/5j0000-1/5cj110000CBXBbx1x2x3x4x5x61X11100-1101X2 16/50101-4/500 x3 4/50011-6/500 x6 -4/50000-4/51j0000-1/501X10100-105

7、/41X2401010-10X3200110-3/20 x5100001-5/4j00000-1/44)0 , 1 , 0 , 2 , 4 , 0(*ZXT2. 分支定界法分支定界法松弛問題沒有可行解，松弛問題沒有可行解，ILP也沒有可行解，停止計算。也沒有可行解，停止計算。松弛問題有最優解，并符合松弛問題有最優解，并符合ILP的整數條件，則此最優解即為的整數條件，則此最優解即為ILP的最優解，停止計算。的最優解，停止計算。松弛問題有最優解，但不符合松弛問題有最優解，但不符合ILP的整數條件，記它的目標函數值的整數條件，記它的目標函數值為為 ；ZZZZZ*(11/4,9/4),Z=31/4(3

8、,3/2),Z=15/2(2,2),Z=6無解無解例：且為整數0,21260522121212121xxxxxxxxxxMaxZ(11/4,9/4)x12x13(2,2)(3,3/2)x21x22(19/6,1),Z=21/3(3,1),Z=7(19/6,1)x13x145.3 0-1整數規劃整數規劃n背包問題背包問題n廠址選擇問題廠址選擇問題n多決策問題多決策問題n固定費用問題固定費用問題n相互排斥的約束條件相互排斥的約束條件1.背包問題背包問題一只背包最大裝載重量為50公斤。現有三種物品，每種物品數量無限。每種物品每件的重量、價格如下表：物品1物品2物品3重量（公斤/件）104120價值（

9、元/件）177235求背包中裝入每種物品各多少件，使背包中物品總價值最高。設三種物品的件數各為x1，x2，x3件，總價值為z。max z=17x1+72x2+35x3s.t. 10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3為整數這是一個整數規劃問題（Integer Programming）。這個問題的最優解為： x1=1件，x2=0件，x3=2件，最高價值z=87元物品1物品2物品3重量（公斤/件）104120價值（元/件）1772352.廠址選擇模型廠址選擇模型在5個備選地點中選擇3處建設生產同一產品的工廠，每個地點建廠所需投資，占用農田，建成以后的生產能力如下。

10、總投資不超過800萬元，占有農田不超過60畝。如何選擇廠址，使總生產能力最大。建廠備選地點12345所需投資（萬元）320280240210180占有農田（畝）201815118生產能力（萬噸）7055422811設5個01變量x1，x2，x3，x4，x5，）（地建廠在地不建廠在54321ii1i0 xi,max z=70 x1+55x2+42x3+28x4+11x5s.t. 320 x1+280 x2+240 x3+210 x4+180 x5800 20 x1+ 18x2+ 15x3+ 11x4+ 8x5 60 x1+ x2+ x3+ x4+ x5= 3 x1, x2, x3, x4, x5

11、0 x1，x2，x3，x4，x5 為 01變量這個01規劃問題的最優解為：x1=1，x2=0，x3=1，x4=1，x5=0，z*=140即在地點1、3和4建3個廠，總生產能力最大，可以達到140萬噸。 3.多決策問題多決策問題一個工廠用3種設備生產5種產品，三種設備的能力（小時），生產每種產品需要占有的各種設備的能力（小時/件）以及5種產品的利潤（元/件）如下：產品12345設備能力設備A5.01.03.02.04.01800設備B3.04.01.05.02500設備C3.02.01.03.02.02200利潤2418211722求使總利潤最大的生產計劃。max z=24x1+18x2+21x

12、3+17x4+22x5s.t. 5.0 x1+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x1，x2，x3，x4，x50 x1，x2，x3，x4，x5為整數設五種產品產量之間有以下邏輯關系：p五種產品中，安排生產的產品不能超過3種p每一種產品如果安排生產，最小批量為50件p如果產品1安排生產，產品2就不能生產p如果產品4生產，產品5必須生產，而且至少生產50件設5個01變量y1，y2，y3，y4，y5）（生產產品不生產產品5 , 4

13、, 3 , 2 , 110iiiyimax z=24x1+18x2+21x3+17x4+22x5s.t. 5.0 x1+1.0 x2+3.0 x3+2.0 x4+4.0 x5 180 3.0 x2+4.0 x3+1.0 x4+5.0 x52500 3.0 x1+2.0 x2+1.0 x3+3.0 x4+2.0 x52200 x110000y1 x210000y2 x310000y3 x410000y4 x510000y5 y1+y2+y3+y4+y5 3 50y1x110000y1 50y2x210000y2 50y3x310000y3 50y4x410000y4 50y5x510000y5

14、y1+y21 y4y5 x1，x2，x3，x4，x50 x1，x2，x3，x4，x5為整數 y1，y2，y3，y4，y5為01變量用10000表示M4.固定費用問題固定費用問題即生產成本和產量成線性關系。如果產品不生產，不發生任何成本，如果產品生產，則產量增加一倍，成本也增加一倍。這樣的成本稱為變動成本。在實際問題中，除了變動成本以外，還有固定成本。如果產品不生產，固定成本為0，如果產品生產，就發生固定成本，而且固定成本是一個常數，與產品產量無關。有固定成本的最小化目標函數的表達式為n1jjjxcmin一般的成本最小化目標函數表達式為0 xdxc0 x0jjjjjj種產品的成本第產量成本固定成

15、本變動成本產量成本變動成本設n種設備，第j種設備的產量為xj，設備運行的變動成本為cj，設備開工的固定成本為dj。引進0-1變量y1，y2，yn，yj=0表示設備j不生產，yj=1表示設備j生產。考慮變動成本和固定成本，使總成本最小化的目標函數為n1jjjn1jjjydxcmin設備開工與否與產量的邏輯關系，用以下約束條件表示xjMyj其中M為一個足夠大的正數。具有固定成本的最小生產費用問題煉焦廠以原煤為原料生產焦炭，同時得到焦爐煤氣和煤焦油。有4臺不同生產能力的煉焦爐，有關的數據為煉焦爐ABCD產品焦炭（噸/噸原煤）0.640.680.710.73煤氣（m3/噸原煤）23252728煤焦油（

16、噸/噸原煤）0.120.150.170.19成本固定成本（元）400120026003100變動成本（元/噸原煤）85817876生產能力（噸原煤）100150200250要求焦炭產量不低于280噸，煤氣產量不低于10000m3，煤焦油產量不低于60噸，編制使總成本最低的生產計劃。不考慮固定成本，使變動成本最小化min z=85x1+81x2+78x3+76x4s.t.0.64x1+0.68x2+0.71x3+0.73x4280 23x1+ 25x2+ 27x3+ 28x4100000.12x1+0.15x2+0.17x3+0.19x460 x1 85 x2 81 x3 78 x4 76x1，

17、x2，x3，x40最優解為：x1=x2=0，x3=137.32，x4=250，max z=29711.27考慮變動成本和固定成本，使總成本最小化。Min z=85x1+81x2+78x3+76x4 +400y1+1200y1+2600y3+3100y4s.t. 0.64x1+0.68x2+0.71x3+0.73x4280 23x1+ 25x2+ 27x3+ 28x4100000.12x1+0.15x2+0.17x3+0.19x460 x110000y1x210000y2x310000y3x410000y4 x1 85 x2 81 x3 78 x4 76x1，x2，x3，x40，y1，y2，y3

18、，y4：0-1變量最優解為： y1=0，y2=1，y3=0，y4=1 x1=0，x2=143.38，x3=0，x4=250，max z=34913.975.相互排斥的約束條件貨物體積/公路體積/船重量利潤甲57220乙43510托運限制244513采用公路運輸的體積限制 5x1+4x224采用船運的體積限制 7x1+3x245 引入01變量另y= 0 采用車運 1 采用船運則約束條件為：5x1+4x224+yM7x1+3x245+(1-y)M思考如果有m種相互排斥的約束條件呢？5.4 隱枚舉法隱枚舉法n基本原理基本原理n舉例說明舉例說明1.基本原理基本原理檢查變量取值為0或1的每一個組合，比較

19、目標函數值的大小以求得最有解。只檢查變量取值組合的一部分，就能求得問題的最有解的方法。步驟：步驟：如求極大化問題，根據目標函數中變量系數Cj的遞增順序，對目標函數和約束不等式中的變量重新排序，找一個可行解，其目標函數值定為過濾值。考察各變量的組合，若產生Z劣于此時的過濾值，則不考慮，繼續下一個組合，若由于此時的過濾值，則逐個考察是否滿足約束條件，只要有一個不滿足，則該組合為不可行解，繼續下一個組合；如果滿足所有約束，則產生新的過濾值，繼續下一個組合。例：例：123123123122332522443460或1，1,2,3jMaxZxxxxxxxxxxxxxxj(x2,x1,x3)Z值約束條件Z

20、過濾值（0,0,0)（0,0,1)（0,1,0)（0,1,1)（1,0,0)（1,0,1)（1,1,0)（1,1,1)3,2,110643434225323212312312312jxxxxxxxxxxxxxxMaxZj，或0055388-2316588885.5 匈牙利法匈牙利法n標準指派問題標準指派問題n匈牙利法步驟匈牙利法步驟n實例實例n非標準指派問題非標準指派問題1.標準指派問題標準指派問題 njixnixnjxxCMinZijnjijniijnjniijij,1,10,1,1,1,11111，或2.匈牙利法步驟匈牙利法步驟3.實例 有一份英文說明書，需譯成英文、日文、俄文和德文，分別

21、記為E，J，R，G。有甲乙丙丁四人，他們將說明書翻譯成不同語種所需時間如表，問應如何派人使工作所需總時間為最少？EJGR甲215134乙1041415丙9141613丁98119例:ABCDE甲 12 7979乙 89666丙 717 12 14 9丁 15 14 6610戊 410 710 9 對沒有 的行打 對已打的行中含有0元素的列打 再對打的列中含有 的行打 重復2,3,直到得不到打的行和列 劃去沒有打的行和已經打 的列就得到覆蓋所有0元素的最少的直線數.4.非標準指派問題非標準指派問題例:有3個建筑公司A1,A2,A3，承建5個工程，所需時間見表，根據實際情況可以允許每家建筑公司承建

22、一個或兩個工程，求總時間最少的方案。B1B2 B3 B4 B5A1 4871512A2 79171410A3 6912187習題:1.用分支定界法求Max z=2x1+3x2 5x1+7x235 4x1+9x236 x1,x20且為整數2.用割平面法求Max z=7x1+9x2 -x1+3x26 7x1+x235 x1,x20且為整數3.已知某運輸問題的產銷平衡表,單位運價表及給出的一個最優調運方案分別見表,試確定k的取值范圍使最優解不變.B1B2B3B4產量A151015A20101525A355銷量5151510B1B2B3B4A11012011A212k920A321416184.某玩具公司分別生產三種新型玩具,每月可供量分別為1000件,2000件和2000件,它們分別被送到甲乙丙