1、12第八章第八章 整數規劃整數規劃 1 整數規劃的圖解法整數規劃的圖解法 2 整數規劃的計算機求解整數規劃的計算機求解 3 整數規劃的應用整數規劃的應用 4 整數規劃的分枝定界法整數規劃的分枝定界法3整數規劃整數規劃是一類要求變量取整數值的數學規劃，是一類要求變量取整數值的數學規劃，可分成可分成線性線性和和非線性非線性兩類。兩類。求整數解的線性規劃問題，求整數解的線性規劃問題，應注意：應注意：不是不是用四舍五入法用四舍五入法和和去尾法對線性規劃的非去尾法對線性規劃的非整數解加以處理就能解決的。整數解加以處理就能解決的。整數線性規劃整數線性規劃一些基本算法的設計是一些基本算法的設計是以相應以相應

2、線性規劃的最優解為出發點線性規劃的最優解為出發點而發展出來的。而發展出來的。根據變量的取值情況，整數線性規劃又可以分根據變量的取值情況，整數線性規劃又可以分為為純整數規劃純整數規劃（所有變量取（所有變量取非負非負整數），整數），混合混合整數規劃整數規劃（部分變量取（部分變量取非負非負整數），整數），0-1整數規整數規劃劃（變量只取（變量只取0或或1）等。）等。第八章第八章 整數規劃整數規劃4整數規劃是數學規劃中一個較弱的分支，目前整數規劃是數學規劃中一個較弱的分支，目前有成熟的方法解有成熟的方法解線性整數規劃問題線性整數規劃問題，而非線性，而非線性整數規劃問題，還沒有好的辦法。整數規劃問題，還

3、沒有好的辦法。整整數線性規劃數線性規劃(Integer Linear Programming，簡記為簡記為ILP)問題研究的是要求變量取整數值時，問題研究的是要求變量取整數值時，在一組線性約束條件下一個線性函數最優問題，在一組線性約束條件下一個線性函數最優問題，是應用非常廣泛的運籌學的一個重要分支。是應用非常廣泛的運籌學的一個重要分支。 第八章第八章 整數規劃整數規劃51 1 整數規劃的圖解法整數規劃的圖解法例例1. 某公司擬用集裝箱托運甲、乙兩種貨物，某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。托運

4、所受限制如表所示。甲種貨物至多托運甲種貨物至多托運4件件，問兩種貨物各托運多，問兩種貨物各托運多少件，可使獲得的利潤最大。少件，可使獲得的利潤最大。貨物貨物每件體積每件體積(立方米立方米)每件重量每件重量(百千克百千克)每件利潤每件利潤（百元）（百元）甲甲乙乙19527344023托運限制托運限制1365140 6貨物貨物每件體積每件體積(立方米立方米)每件重量每件重量(百千克百千克)每件利潤每件利潤（百元）（百元）甲甲乙乙19527344023托運限制托運限制1365140 解：設解：設x1 、 x2分別為甲、乙兩種貨物托運的件數，建分別為甲、乙兩種貨物托運的件數，建立模型。立模型。 目標函

5、數：目標函數： Max z = 2x1 +3x2 約束條件：約束條件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0, 為整數為整數。如果去掉最后一個約束，就是一個線性規劃問題如果去掉最后一個約束，就是一個線性規劃問題.1 1 整數規劃的圖解法整數規劃的圖解法7利用圖解法，得到線性規劃的最優解為利用圖解法，得到線性規劃的最優解為x1=2.44, x2=3.26,目標函數值為目標函數值為14.66。由圖表可看出由圖表可看出, 整數規劃的最優解（黃色叉號）為整數規劃的最優解（黃色叉號）為x1=4, x2=2,目標函數值為目標函數值為1

6、4。Max z = 2x1 +3x2195x1+273x2=13654 x1+40 x2 =1404231123x2x11 1 整數規劃的圖解法整數規劃的圖解法Max z = 2x1 +3x2 約束條件：約束條件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 48由于相應的由于相應的線性規劃的可行域包含線性規劃的可行域包含了其了其整整數規劃的可行點數規劃的可行點，則對于整數規劃，易知，則對于整數規劃，易知有以下性質：有以下性質：性質性質1：任何求最大目標函數值的純整數規：任何求最大目標函數值的純整數規劃或混合整數規劃的最大目標函數值劃或混合整數規劃

7、的最大目標函數值小于小于或等于或等于相應的線性規劃的最大目標函數值；相應的線性規劃的最大目標函數值；任何求最小目標函數值的純整數規劃或混任何求最小目標函數值的純整數規劃或混合整數規劃的最小目標函數值合整數規劃的最小目標函數值大于或等于大于或等于相應的線性規劃的最小目標函數值。相應的線性規劃的最小目標函數值。1 1 整數規劃的圖解法整數規劃的圖解法9例例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1, x2, x3 0 , 均為整數均為整數用管理運籌學軟件用管理運籌學軟件求解得：求解得：

8、x1 = 5 x2 = 2 x3 = 2 2 2 整數規劃的計算機求解整數規劃的計算機求解純整數規劃問題純整數規劃問題1011例例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 - 3x2 + 2x3 3 x3 1 x1, x2, x3 0 x1，x3 為整數，為整數，x3 為為0-1變量變量用用管理運籌學管理運籌學軟件求軟件求解得解得: z = 16.25x1 = 4 x2 = 1.25 x3 = 1 123 3 整數規劃的應用整數規劃的應用應用實例：應用實例： 投資投資場所的選擇問題場所的選擇問題 背包問題背包問題

9、 固定成本固定成本問題問題 指派指派問題問題 分布系統設計分布系統設計 投資投資問題問題13143 3 整數規劃的應用整數規劃的應用 一、投資場所的選擇一、投資場所的選擇 例例4、京成畜產品公司計劃在市區的東、西、南、北四區、京成畜產品公司計劃在市區的東、西、南、北四區建立銷售門市部，擬議中有建立銷售門市部，擬議中有10個位置個位置 Aj (j=1,2,3,10)可供選可供選擇，考慮到各地區居民的消費水平及居民居住密集度，規定擇，考慮到各地區居民的消費水平及居民居住密集度，規定: 在東區由在東區由A1 ， A2 ，A3 三個點三個點至多至多選擇選擇兩個兩個； 在西區由在西區由A4 ， A5 兩

10、個點中兩個點中至少至少選選一個一個； 在南區由在南區由A6 ， A7 兩個點中兩個點中至少至少選選一個一個； 在北區由在北區由A8 ， A9 ， A10 三個點中三個點中至少至少選選兩個兩個。 Aj 各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測情況見表所示預測情況見表所示 (單位：萬元單位：萬元)。但投資總額。但投資總額不能超過不能超過720萬萬元，問應選擇哪幾個銷售點，可使年利潤為最大元，問應選擇哪幾個銷售點，可使年利潤為最大?解：設：解：設：0-1變量變量 xi = 1 (Ai 點被點被選用選用)或或 0 (Ai 點點沒被

11、選用沒被選用)。 這樣我們可建立如下的數學模型：這樣我們可建立如下的數學模型：Max z=36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0 且且xi 為為0-1變量變量，i = 1, 2, 3, ,10在東區由在東區由A1 ， A2 ，A3 三個點三個點至多至多選擇選擇兩個兩個

12、；在西區由在西區由A4 ， A5 兩個點中兩個點中至少至少選選一個一個；在南區由在南區由A6 ， A7 兩個點中兩個點中至少至少選選一個一個；在北區由在北區由A8 ， A9 ， A10 三個點中三個點中至少至少選選兩個兩個補充例、解決某市消防站的布點問題，該城市有補充例、解決某市消防站的布點問題，該城市有6個個區，每個區都可以建消防站。市政府希望設置的消區，每個區都可以建消防站。市政府希望設置的消防站最少，但必須滿足在城市的任何地區發生火警防站最少，但必須滿足在城市的任何地區發生火警時，消防車時，消防車要在要在15分鐘內分鐘內趕到現場。據實地測定，趕到現場。據實地測定，各區之間消防車行駛的時間

13、如下表所示，請幫助該各區之間消防車行駛的時間如下表所示，請幫助該市制定一個最省的計劃。市制定一個最省的計劃。 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0 設設 xi =1,0; 1i 區建消防站，區建消防站，0i 區不建消區不建消防站，防站，i=1,6min z = x1 + x2 + x3 + x4 + x5 + x6約束方程保證每個地區都有一個消防站在約束方程保證每個地區都有一個消防站在15分鐘行

14、程內。分鐘行程內。將將6個地區的條件分別列出：個地區的條件分別列出：s.t. x1 + x2 1, x1 + x2 + x6 1 x3 + x4 1, x3 + x4 + x5 1 x4 + x5 + x6 1, x2 + x5 + x6 1 xi = 0, 1; i=1,6 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24 32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 018 1 2 3 4 5 61 0 10 16 28 27 202 10 0 24

15、32 17 103 16 24 0 12 27 214 28 32 12 0 15 255 27 17 27 15 0 146 20 10 21 25 14 0第第2個地區建一個（地區個地區建一個（地區1、2、6都解決了）都解決了）第第4個地區建一個（地區個地區建一個（地區3、4、5都解決了）都解決了）二、二、背包問題背包問題（補充）（補充）背包可裝入背包可裝入8單位重量，單位重量，10單位體積物品。若單位體積物品。若背包中背包中每件物品至多只能裝一個每件物品至多只能裝一個，怎樣才能使背包，怎樣才能使背包裝的物品價值最高。裝的物品價值最高。物品物品 名稱名稱 重量重量 體積體積 價值價值 1

16、書書 5 2 20 2 攝像機攝像機 3 1 30 3 枕頭枕頭 1 4 10 4 休閑食品休閑食品 2 3 18 5 衣服衣服 4 5 15 解：解：xi為是否帶第為是否帶第 i 種物品種物品Max Z=20 x1 + 30 x2 +10 x3+18x4 +15x55x1+3x2 +x3 +2x4 +4x5 82x1+x2 +4x3 +3x4 +5x5 10 xi為為0, 1物品物品 名稱名稱 重量重量 體積體積 價值價值 1 書書 5 2 20 2 攝像機攝像機 3 1 30 3 枕頭枕頭 1 4 10 4 休閑食品休閑食品 2 3 18 5 衣服衣服 4 5 15 一般形式：一般形式：0

17、max11iniiiniiixbxaxCZ, 整數整數 xi為是否攜帶第為是否攜帶第i 種物品種物品ai為為i 物品單位重量，物品單位重量，b為最大負重為最大負重ci為為i 物品重要性估價物品重要性估價223 3 整數規劃的應用整數規劃的應用三、固定成本問題三、固定成本問題 例例5高壓容器公司制造小、中、大三種尺寸的金屬高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設備，制造一容器，所用資源為金屬板、勞動力和機器設備，制造一個容器所需的各種資源的數量如表所示。不考慮固定費個容器所需的各種資源的數量如表所示。不考慮固定費用，每種容器售出一只所得的用，每種容器售出一只

18、所得的利潤分別為利潤分別為 4萬元、萬元、5萬元、萬元、6萬元萬元，可使用的金屬板有，可使用的金屬板有500噸，勞動力有噸，勞動力有300人人/月，機月，機器有器有100臺臺/月，此外不管每種容器制造的數量是多少，都月，此外不管每種容器制造的數量是多少，都要支付一筆要支付一筆固定的費用：小號是固定的費用：小號是l00萬元，中號為萬元，中號為 150 萬萬元，大號為元，大號為200萬元。萬元。現在要制定一個生產計劃，使獲得現在要制定一個生產計劃，使獲得的利潤為最大。的利潤為最大。23解：這是一個整數規劃的問題。解：這是一個整數規劃的問題。 設設x1，x2， x3 分別為小號容器、中號容器和大分別

19、為小號容器、中號容器和大號容器的生產數量。號容器的生產數量。各種容器的固定費用只有在各種容器的固定費用只有在生產該種容器時才投入，若不生產則沒有這部分生產該種容器時才投入，若不生產則沒有這部分費用，費用，為了說明固定費用的這種性質，為了說明固定費用的這種性質，設設 yi = 1(當當生產第生產第 i種容器種容器, 即即 xi 0 時時) 或或0（當不生產第（當不生產第 i種種容器即容器即 xi = 0 時）。時）。 引入約束引入約束 xi M yi ，i =1，2，3，M充分大，充分大，以保證當以保證當 yi = 0 時，時，xi = 0 。 3 3 整數規劃的應用整數規劃的應用即：不投入固即

20、：不投入固定費用，是不定費用，是不能投入生產的能投入生產的24這樣我們可建立如下的數學模型：這樣我們可建立如下的數學模型：Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大充分大 xj 0 yj 為為0-1變量變量，i = 1,2,33 3 整數規劃的應用整數規劃的應用沒有固定投入，就不生產沒有固定投入，就不生產.yi =0，則，則xi=0. xi是數量，是數量，M為一個充分大的數

21、。為一個充分大的數。一個容器至少需要一個容器至少需要2個勞動個勞動力，共有力，共有300個勞動力，因個勞動力，因此容器數量不會超過此容器數量不會超過150.因因此當此當yi =1時，時，M可取可取150投入固定費用，投入固定費用，生產小號容器生產小號容器y1y2y325三、指派問題三、指派問題 有有 n n 項不同的任務，恰好項不同的任務，恰好 n n 個人可分個人可分別承擔這些任務，但由于每人特長不同，完別承擔這些任務，但由于每人特長不同，完成各項任務的效率等情況也不同。現假設必成各項任務的效率等情況也不同。現假設必須指派須指派每個人去完成一項任務每個人去完成一項任務，怎樣把，怎樣把 n n

22、 項任務指派給項任務指派給n n個人，使得完成個人，使得完成 n n 項任務的項任務的總的效率最高總的效率最高，這就是，這就是指派問題。指派問題。 3 3 整數規劃的應用整數規劃的應用26例例6 6有四個工人，要分別指派他們完成四項有四個工人，要分別指派他們完成四項不同的工作，不同的工作，每人做各項工作所消耗的時間每人做各項工作所消耗的時間如下表所示如下表所示，問應如何指派工作，才能使，問應如何指派工作，才能使總總的消耗時間為最少的消耗時間為最少。3 3 整數規劃的應用整數規劃的應用27解：引入解：引入01變量變量 xij，并令并令 xij =1(當指派第當指派第 i人去完成第人去完成第j項工

23、作時項工作時)或或0(當不指當不指派第派第i人去完成第人去完成第j項工作時項工作時)這可以表示為一個這可以表示為一個0-1整數規劃問題：整數規劃問題：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x443 3 整數規劃的應用整數規劃的應用28整數規劃模型為：整數規劃模型為：Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21

24、x42+23x43+17x44s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作

25、只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干) xij 為為0-1變量變量，i,j = 1,2,3,43 3 整數規劃的應用整數規劃的應用每人只每人只能干一能干一項工作項工作一項工一項工作只能作只能由一個由一個人干人干 對于有對于有m個人完成個人完成n項任務的一般指派問題，項任務的一般指派問題，設：設：29變量為1-0,.,2, 1, 1,.,2, 1, 1min1111ijmiijnjijminjijijxnjxmixxCZm不一定等于不一定等于n，當當mn時，有的時，有的人沒有任務。人沒有任務。第第i個人完成的任務個人完成的任務且最多承擔一項

26、且最多承擔一項第第j項工作正好有一項工作正好有一人承擔人承擔注意：當注意：當m0 yi=0時，當不利用第時，當不利用第i種設備生產時，此時相應種設備生產時，此時相應的的Xi=0 目標函數為：目標函數為： Min Z=7x1+2x2+5x3+100y1+300y2+200y358 (1) 約束條件約束條件 X1 800，X2 1200，X3 1400， X1+X2+X3=2000(改大于等于結果相同改大于等于結果相同) 0.5X1+1.8X2+1.0X3 2000 還得保證還得保證Yi=0時，時，Xi=0.(沒有準備費就不啟沒有準備費就不啟用該設備用該設備)，引入一個很大的，引入一個很大的M X

27、i M Yi（i=1,2,3） Xi 0,（i=1,2,3） Yi（i=1,2,3）是）是0-1變量變量59 （2）約束條件改為 0.5X1+1.8X2+1.0X3 250060 （3）約束條件改為 0.5X1+1.8X2+1.0X3 280061 （4）去掉電量的約束條件62第第5題題635：二二50080070064yi是是0-1變量，變量， yi=0，相當于該，相當于該庫房不存在庫房不存在需求量需求量上海上海y2，武漢，武漢y40,10,01,1最多最多2個庫房個庫房武漢和廣州不能同時建武漢和廣州不能同時建i=1,2,3,4北京北京上海上海廣州廣州武漢武漢華北華北華中華中華南華南2第第6

28、題：指派問題題：指派問題（1）引入引入01變量變量 xij，并令并令 xij =1(當指派第當指派第i人去完成第人去完成第j項工作時項工作時) 0(當不指派第當不指派第i人去完成第人去完成第j項工作時項工作時)目標函數 Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x4465 x11+ x12+ x13+ x14= 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能

29、干一項工作乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作丁只能干一項工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干工作只能一人干)66 （2）把目標函數改為求最大值即可，即：）把目標函數改為求最大值即可，即：M

30、ax Z= 20 x11+ 19x12+ 20 x13+ 28x14+18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x44約束條件不變約束條件不變67 （3）增加了一項工作增加了一項工作E，問應指派，問應指派四個人干四個人干哪四項工作哪四項工作，共有五項工作，則結果中肯定，共有五項工作，則結果中肯定有一項工作無人做。有一項工作無人做。 mn，人數少于任務數。此時，添加虛擬，人數少于任務數。此時，添加虛擬人數人數n-m=1個，該人是虛擬的，因此完成各個，該人是虛擬的，因此完成各項工

31、作所需的時間都設為項工作所需的時間都設為0.此時變為此時變為5個人個人完成完成5項工作的問題了。項工作的問題了。Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20 x24+ 20 x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20 x42+ 24x43+ 19x44 +16x45 + 0 x51+ 0 x52+ 0 x53+ 0 x54 +0 x5568甲乙丙甲乙丙丁每個丁每個人做第人做第5項工作項工作的時間的時間 約束條件 x11+ x12+ x13+ x14 + x1

32、5 = 1 x21+ x22+ x23+ x24 + x25 = 1 x31+ x32+ x33+ x34 + x35 = 1 x41+ x42+ x43+ x44 + x45 = 1 x51+ x52+ x53+ x54 + x55 = 1 x11+ x21+ x31+ x41 + x51 =1 x12+ x22+ x32+ x42 + x52 =1 x13+ x23+ x33+ x43 + x53 = 1 x14+ x24+ x34+ x44 + x54 = 1 x15+ x25+ x35+ x45 + x55 = 169結果中安排第結果中安排第5個虛擬人去個虛擬人去做哪項工作，做哪項工作

33、，表明實際中該表明實際中該項工作無人做項工作無人做70方法二：方法二：x11+ x12+ x13+ x14 + x15 = 1 (甲只能干一項工作甲只能干一項工作) x21+ x22+ x23+ x24 + x25 = 1 (乙只能干一項工作乙只能干一項工作)x31+ x32+ x33+ x34 + x35 = 1 (丙只能干一項工作丙只能干一項工作)x41+ x42+ x43+ x44 + x45 = 1 (丁只能干一項工作丁只能干一項工作)x11+ x21+ x31+ x41 1 ( A工作工作)x12+ x22+ x32+ x42 1 ( B工作工作)x13+ x23+ x33+ x43

34、 1 ( C工作工作)x14+ x24+ x34+ x44 1 ( D工作工作)x15+ x25+ x35+ x45 1 ( E工作工作)Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20 x24+ 20 x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20 x42+ 24x43+ 19x44 +16x45 用用普通線性規普通線性規劃模塊劃模塊求解求解 （4）增加了一個人，問應指派哪四個人去）增加了一個人，問應指派哪四個人去干這四項工作，肯定有一個人沒有工作做。干這四項工作

35、，肯定有一個人沒有工作做。目標函數目標函數 Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20 x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20 x42+ 24x43+ 19x44 + 16x51+ 17x52+ 20 x53+ 21x5471 方法一：虛設一個工作，每個人完成此項工方法一：虛設一個工作，每個人完成此項工作的時間設為作的時間設為0.72x11+ x12+ x13+ x14 + x15 = 1 x21+ x22+ x23+ x24 + x25 = 1x31+ x32+ x33

36、+ x34 + x35 = 1x41+ x42+ x43+ x44 + x45 = 1x51+ x52+ x53+ x54 + x55 = 1x11+ x21+ x31+ x41 + x51 =1x12+ x22+ x32+ x42 + x52 =1x13+ x23+ x33+ x43 + x53 = 1x14+ x24+ x34+ x44 + x54 = 1x15+ x25+ x35+ x45 + x55 = 1Min Z= 20 x11+ 19x12+ 20 x13+ 28x14+0 x15 + 18x21+24x22+27x23+ 20 x24+ 0 x25+ 26x31+16x32+15x33+ 18x34+ 0 x35+ 17x41+ 20 x42+ 24x43+ 19x44 +0 x45 + 16x51+ 17x52+20 x53+ 21x54 +0 x5