第四章整數規(guī)劃與分配問題

1、第四章整數規(guī)劃與分配問題§ 4.1整數規(guī)劃的特點及作用用單純形法求解線性規(guī)劃的結果往往得到分數或小數解。但在很多實際問題中，全 部或部分變量的取值必須是整數，如人或者機器設備不可分割。此外還有一些問題，如 要不要在某地建設工廠，可選用一個邏輯變量x,令x 1表示在該地建廠，x 0表示不在該地建廠，邏輯變量也只允許取整數值的一類變量。在一個整數規(guī)劃中要求全部變 量取整數值的，稱純整數線性規(guī)劃或純整數規(guī)劃；只要求一部分變量取整數值的，稱為 混合整數(線性)規(guī)劃；在純整數規(guī)劃問題中，若所有變量只允許取0, 1兩個值，則稱其為0-1規(guī)劃。有人認為，對整數規(guī)劃問題的求解可以先不考慮對變量的整數

2、約束，作為一般線性 規(guī)劃問題來求解，當解為非整數時可用四舍五入或湊整數尋找最優(yōu)解，其實這種方法是 不可行的，原因有以下兩點：一、用湊整的方法計算量很大，而況還不一定能找到最優(yōu)解。如某線性規(guī)劃問題的最優(yōu)解為X1 X24.6 5.5 ,用湊整數的方法時需比較與士2的上述數值最接近的四種組合：(4,5),(5,5),(4,6),(5,6)如果問題中有10個變量，就 要比較210 1024個整數解組合，而且最優(yōu)解還不一定在這些組合中。二、放松約束也無法求出其最優(yōu)解maxz 3x1 2x2f2x1 3x2 14s.t K 0.5x2 4.5如果不考慮整數約束，稱為上述線性規(guī)劃問題的松弛問題，松弛問題的最

3、優(yōu)解為:x1取整以后Xi3,X22是可行解，但Xi解，而x13,x2 2 對應的目標函數值z3.25, x22.53,x2 3;x1 4, x2 2; x1 4, x2 3都不是可行3x1 2x2 13卻不是最優(yōu)解，然而最優(yōu)解是Xi 4,X2 i,maX z 3Xi 2X2 i4 。直接對松弛問題進行求解都無法求得整數規(guī)劃問題的最優(yōu)解， 這就需要對整數線性規(guī)劃問題有特殊的求解方法。此外，整數線性規(guī)劃問題的數學模型的研究有著重要的意義，很多管理問題無法歸納為線性規(guī)劃問題的數學模型，但卻可以設置邏輯變量建立起整數規(guī)劃問題的數學模型。下面舉例說明邏輯變量在解決問題中的重要作用。1.m個約束條件中只有

4、k個起作用設m個約束條件可以表示為naijXjbi,(ii, 2,L , m)ji定義 yi假設第i個約束條件不起作用.假設第i個約束條件起作用'i 1,2,L ,m)又 M 為任意大的正數，則naijXj bi Myi(i i,2,L ,m)jiyi y2 Lym m kyi,y2,L ,ym ?；騣n因為若 yi 0 ，則 aij Xjjin若yi 1,則 對為bijibi 條件起作用nM , aijxj R條件不起作用ji2.約束條件的右端項可能是r個值(%b2,L ,br)中的某一個，即定義iyi 0najXj 匕或2或L或br ji假定約束條件右端項為 bi 否則由此，上述約

5、束條件可以表示成:aijxjb1y1b2y2Lbryrj1y1y2Lyr1 y1, y2,L , yr 0或13. 兩組條件中滿足其中一組若 x14 ，則 x2 1 ；否則（即 x1 4 時） ，x23最小，即：定義yi第i組條件不起作用 第i組條件起作用1,2)又 M 為任意大的正數，則問題可表達為：x1 4 My1x21 My1x14 My2x23 My2y1 y21y1, y20,14. 用以表示含固定費用的函數例如用Xj代表產品j的生產數量，其生產費用函數通?？杀硎緸?Cj(xj)KjcjXj0( Xj0)( Xj0)式中 K j 是同產量無關的生產準備費用。問題的目標是使所有產品的總

6、生產費用為nmin zCj(Xj)j11Xj 0yj，那么XjMyjj 0Xj 0使問題化為：nminzcjXjKjyjj10 s.tyjXjMyj0 或 1)j1,2,L ,n)（M 為充分大的正數）股整數規(guī)劃問題建模:例 1 某飯店24小時中需要服務員數量如下：如果每個服務員連續(xù)工作8小時，試問在2點、 6點、 10點、 14點、 18點、 22點鐘開始上班的服務員為多少時，一天所需服務員人數最少？時間2-66-1010-1414-1818-2222-2最少服務員48107124設在2點、6點、10點、14點、18點、22點鐘開始上班的服務員分別為 Xi,X2,X3,X4,X5,4,X64

7、810X47X4X512X5X64X4,X5X60整數min ZX1x2x3XiXiX2X2X3S.tX3X4X5X6則可建立整數規(guī)劃數學模型Xi, X2,X3 ,利用LINGO求解整數線性規(guī)劃問題，得Min=x1+x2+x3+x4+x5+x6;x1+x6>=4;x1+x2>=8;x2+x3>=10;x3+x4>=7 ;x4+x5>=12;x5+x6>=4;gin(x1); gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);Global optimal solution found.Objective value:26.0000

8、0Extended solver steps:0Total solver iterations:6VariableValueReduced CostX14.0000001.000000X24.0000001.000000X36.0000001.000000X41.0000001.000000X511.000001.000000X60.0000001.000000RowSlack or SurplusDual Price126.00000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.

9、0000000.00000077.0000000.0000002.在高?；@球聯賽中，某學院男子籃球隊要從 8名隊員中選擇平均身高最高的出場陣容，隊員的號碼、身高及擅長的位置如表所示:隊員號碼12345678身高（cm）1.921.901.881.861.851.831.801.78a®中鋒中鋒前鋒前鋒前鋒后衛(wèi)后衛(wèi)后衛(wèi)同時要求出場陣容滿足以下條件:(1)中鋒只能有一個上場；(2)至少有一名后衛(wèi)；(3)如果1號隊員和4號隊員都上場，則6號隊員不能上場；(4) 2號隊員和6號隊員必須保留一個不出場。寫出該問題的數學模型解：設Xj第j號隊員出場第j號隊員不出場(j 123,4,5,6,7,8

10、)則可建立整數規(guī)劃模型:maxZ1.92x1 1.90x21.88x31.86x4 1.85x5 1.83x6 1.80x7 1.78x8xx2x3x4xx2s.txx4x2x5x8乂6X7乂6乂6x8 121x1,x2,x3,x4,x5,x6,x7,x8利用LINGO進行求解0 1規(guī)劃問題，得Max=1.92*x1+1.9*x2+1.88*x3+1.86*x4+1.85*x5+1.83*x6+1.8*x7+1.78*x8 x1+x2+x3+x4+x5+x6+x7+x8=5;產數量，該廠才能有最大利潤?x1+x2=1;x6+x7+x8>=1;x1+x4+x6<=2;x2+x6<

11、;=1;bin(x1); bin(x2); bin(x3); bin(x4); bin(x5); bin(x6); bin(x7); bin(x8);Global optimal solution found.Objective value:9.310000Extended solver steps:0Total solver iterations:0VariableValueReduced CostX11.000000-1.920000X20.000000-1.900000X31.000000-1.880000X41.000000-1.860000X51.000000-1.850000X60

12、.000000-1.830000X71.000000-1.800000X80.000000-1.7800003.某工廠生產A1、4兩種產品，產品分別由Bi、B2兩種部件組裝而成，每件產品所用部件數和有關部件的產量限額以及產品利潤由下表所示。問怎樣安排Ai、A2的生7''部件 產品-BiB2利潤(元)Ai6115A24320部件的最大產量2510解：設生產A、A2分別為xv x2件，則maxZ 15x1 20x26x1 4x2 25s.t x1 3x2 10x1 ,x2 0, 整數很容易用 LINGO10.0 求出它的最優(yōu)解。Max=15*x1+20*x2;6*x1+4*x2&l

13、t;=20;x1+3*x2<=10;gin(x1);gin(x2);下料問題也是典型的整數規(guī)劃問題下面講指派問題§ 4.2 分配問題(指派問題)與匈牙利法2-1問題的提出與數學模型分配問題也稱指派問題(Assignment Problem)，是一種特殊的整數規(guī)劃問題，假定 有m項任務分配給m個人去完成，并指定每人完成其中一項，每項只交給其中一個人去例：有m個人，去完成m項任務，不同的人完成不同的任務效率如下表:B1B2LBmAa11a12La1mA2a21a22L92mLLLLLAmam1am2La mm如何分配任務，使花費的總時間最少?&1&2LWma21a2

14、2 L92m稱為分配問題的效率矩陣。LLLLamiam2Lamm(i,j 1,2,L ,m)K1分配第i個人去完成第j項任務Xj0不分配第i個人去完成第j項任務則分配問題的數學模型一般可以寫為:m m min zaij xji 1 j 1 mXij1 (i 1,2,L ,m)j 1 ms.tXij1 (j 1,2,L ,m)i 1xijOS； 1 (i, j 1,2,L , m)2-2匈牙利法理論上，這也是運輸問題，但是它比運輸問題更特殊，可以用更特殊的方法加以解 決?？梢杂们蠼膺\輸問題的表上作業(yè)法求解分配問題，但通常更有效的是用匈牙利方法 求解。解分配問題的匈牙利方法是從這樣一個明顯的事實出

15、發(fā)的：如果效率矩陣的所有元素A 0,而其中存在一組位于不同行不同列的零元素，則只要令對應于這些元素位置m m的Xij 1其余的Xij 0 ,則zajXj就是問題的最優(yōu)解。如效率矩陣為：1 1 j 1014939200232303801214010000010010000就是指派問題的最優(yōu)解。01但問題是如何產生并尋找這些位于不同行不同列的零元素。匈牙利數學家克尼格 （Konig）證明了下面兩個基本定理，為解決以上問題奠定了基礎。因此，基于這兩個 定理基礎上所建立的求解分配問題的計算方法被稱為匈牙利法。Ui定理1如果從分配問題的效率矩陣（aj）中的某一行分別減去（或加上）一個常數 （被稱為該行的

16、位勢），從某一列分別減去（或加上）一個常數 vj （稱為該列的位勢） 得到一個新的效率矩陣（bj）,若其中bj aj Ui vj,則以（bj）為效率矩陣分配問題的最 優(yōu)解等價于以（aj）為效率矩陣分配問題的最優(yōu)解。證明：mbj%j 1m(aj Ui vj)xj j 1所以ajXj i 1majXji 1m Ui i 1 jmUi i 1xij1vj1minmvj1mxij i 1（后兩項是常數）mb. xij ij j 1m mminaj xji 1 j 1例：現有四人每人都能完成四項工作中的一項，但由于各自對不同工作的熟練程度或 技術專長的不同，完成每項工作花費的時間也不同。如下表BB2B3

17、B4Ai314105A21041210A39141513A4781190”元素匈牙利方法的步驟：1 .變換效率矩陣，使變換后的效率矩陣每行、每列至少有一個310(aij)9714414810121511510139349706001105178644264220600110513420042(bj)02.試求最優(yōu)解（通過標注零的方法）所以可以求得0 0 0 10 10 0(Xj),min z 5 4 9 11 2910 0 00 0 10A B4,A2 B2A Bi,A4 B3例：有一份說明書，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個 人去完成。因各人專長不同，他們完成翻譯不同文

18、字所需的時間如下表，應如何分配， 使這四個人分別完成這四項任務的總時間為最短。甲乙丙丁譯成英文21097譯成日文154148譯成彳思義13141611譯成俄文415139列均減去該列的最小值，使每行每列至少有一1 .每一行均減去該行的最小值, 個零元素（變換效率矩陣）215134104141591416137811924114011208031171059554050112080311250454052 .試求最優(yōu)解*011208*031125*0454053 .作覆蓋所有零元素的最少直線集合(D(2)(3)(4)對沒有0*的行打，對打了，的行上0元素所在的列打， 對打了，的列上0所在的行打V

19、 對打了，的行上0元素所在的列打，直至打不出新的行和新的列這樣就得到能夠覆蓋所有零元素的對沒有打，的行劃橫線，對打了，的列劃豎線, 最少直線組合。定理2若矩陣A可分為“ 0”與非“ 0”兩部分，則覆蓋“ 0”元素的最少直線數等 于位于不同行不同列的“ 0”元素的最大個數。恰好等于我們標出 0*的個數。證明：已知矩陣中有若干個0元素，設覆蓋全部0元素最少需要m條直線，又設位 于不同行不同列的0有M個，因覆蓋每個0至少用一條直線，故有m M卜面要證明Mm,假定覆蓋所有0元素的m條直線有行（用ii,i2,L ,ir表示）c列（用ji, j2,L , jc表示），m r c;顯然在每一行上至少存在一個

20、不在ji, j2,L , jc列上的0元素；設某一行上這些不在j1, j2,L , jc列上的0元素下標的集合為§ laii 0,l ji，j2，L,jJ對ii,i2,L ,ir行分別有集合Si1,Si2,L ,Sr ,從這些集合中任取k個（k r）,其集合中 的不同元素個數必不少于k,否則這k行的直線可用少于k條列線代替，與m是覆蓋0 元素的最少直線的假定矛盾。由此可知，在r條行線上存在不少于r個位于不同的列，且這些0不位于ji,j2,L , jcccJ|7J477jc列上。同理可以證明在c條列線上存在不少于c個位于不同行的 0,且這些0不位于ii,i2,L ,ir行上。若上述兩部

21、分0的個數總和為S ,則S m,又顯然S M ,故有M m從而有M m ,定理得證4.繼續(xù)變換效率矩陣，試求最優(yōu)解，回到第二步。從未被直線覆蓋的所有元素中找出一個最小元素 k,然后將效率矩陣未劃橫線的行均減去這個最小元素，劃豎線的列均加上這個最小元素 再試求最優(yōu)解，繼續(xù)。最優(yōu)解為（面）0 0 100 10 00 0 0 110 0 0*0 6 0313 05 4*43 0 0*0923min z 9 4 11 4 28,或者 min z 2411 45222 28例：求下列指派問題的最優(yōu)解人（工件）B1B2B3B4B5A1127979A289666A3717121412A415146610A5

22、4107106* *12797950202702028966623*00043*000717121412*010575*0835315146610980*041180*044107106063620414*0最優(yōu)解（Xj）min z兩點說明0010010000601000000106000016 32或 min z 76764222 321.分配問題中如果人數和工作任務數不相等時的處理方法。舉例來說，如果人員數 大于任務數，可以增加虛的任務，使總的任務數與總的人員數相等，不過每個人完成虛任務的時間為0, 數等于任務總數。如：效益當然也為0;當人員數小于任務數，可增加虛的人員，使人員總37365

23、5min z61642722453466487320000008000000InmIVVVI136260027144003365800464370055243006576200*04*03225*0531602312442651*0000*0000000*002.如果把效率矩陣改為效益矩陣, 即可。把求指派問題的最小值化為求指派問題的最大值m如 max zi 1ma xij人jj 1等價于min zm(aij )xij,由于（aj）為負，不容易比較，現在將每一個數都加上M ,等價于min wm(Mj 1aij ）xj, Mmax aj化為一般的最小化指派問題。虛人員完成各任務的效率與效益均為

24、0,這時可能有的任務無法落實。例：一個公司要分派5個推銷員去5個地區(qū)推銷某種產品，5個推銷員在各個地區(qū)推銷這種產品的預期利潤如下表所示。若每個推銷員只能去一個地區(qū)，應如何分派這5個推銷員才能使公司的利潤最大？ABCDE甲1 15110121 1012乙1112999丙1020151712丁1 18 11791 913戊713101312maxaj 20510810898111111(20 a。)1005382311117053531033310053801995050*5210032*100237*0169 4*600 00*05 030*10 010*10 0 215*01672*822 0

25、013 7 10 780 0 10 0(Xj)0 0 0 0 10 0 0 ,maxz 12 9 20 18 13 72例：某車隊有5輛汽車，將駛往3個目的地運貨。一地的貨物只需一輛車送，其運 費(元)如下表：(1)試求最優(yōu)指派的調運方案(2)若表中數字表示所得利潤，則應如何指派？(3)若車2載不下A地所需貨物，車5爬不上通往B地必經之路上的坡，對(1) (2)的最優(yōu)解有什么影響？汽車1叱2叱3汽車4叱5A10121411P 13B1320231521C861075相應的作業(yè)P125, 4.3 (a) (b)P125 4.5提示以后讓學生自己完成要真正弄懂(a)將最后一列先減去一個數如30,使

26、E列占優(yōu)勢，這就保證了任務E必須能完成,252931427然后再增加一個虛的人393826203,再增加一行0也無妨3427284022442362315(b)取每列的最小值，放至最后一行，作為第 5個人，然后在任務分派時將第 5 個人的任務再還原。ABCDE甲2529314237乙3938262033丙3427284032丁244236：2345戊2427262032(c)將不能完成任務的人、任務對應時間放至 M 100,然后再從丙、丁行的最小值放 至下一行，分配完任務以后，與(b) 一樣進行還原。ABCDE甲2529 11004237 I乙100381002033丙34272840100丁

27、10042 I362345 I戊3427282345這樣即可達到目的§4.3分枝定界法在線性規(guī)劃問題中，變量x是在一個連續(xù)的范圍內取值，因此可行解個數無限多。 但在整數規(guī)劃問題中變量只能取離散的整數值，可行解的總數是有限的。從有限多的可 行解中尋找最優(yōu)解的最直觀、最簡單的方法是枚舉法，但方法不可行。分枝定界法 （branch and bound method）就是為求解同整數規(guī)劃具有類似性質的一大類問題而設計 的一種較好的方法。第一步：尋找替代問題并求解。方法是放寬約束條件，去掉整數約束。如果非整數線性規(guī)劃問題的最優(yōu)解就是整數, 則已求得整數問題的最優(yōu)解；否則，這個最優(yōu)解是原整數線性

28、規(guī)劃問題最優(yōu)解的一個上 界（求最大值）或者下界（求最小值）。max z 3x1 2x22x1 3x2 14 st x1 0.5x2 4.5放松約束條件，求解如下問題maxz 3x1 2x22x1 3x2 14s.t 2x1 x2 9(LP1)x1,x2 0,整數,x2 0基解x1x2x3x4x3142310x492101z032001x35021-1x19/211/201/2z-27/201/20-3/2x25/2011/2-1/2x113/410-1/43/4z-59/400-1/4-5/4基解x1x2x3x4xsx25/2011/2-1/20x113/410-1/43/40x-1/200-

29、"21/21z-59/400-1/4-5/402x1 3x2 142x1 x2 9(LP13)st12x2 3x1,x2 0x1,x2 0一.135(LP1)取優(yōu)斛 x1, x2 ,max z42max z3x12x22x1 3x2 142x1x29(LP12)st12x22594maxz 3x1 2x2X2X1x327/210100110 01/2-1/200 1-1-2z-29/20 0 0 -3/2-1/2(LP12)最優(yōu)解 x1 7,x2 2,maxz 2max z 3x1 2x22xi 3x2 142x1 x2 9 (LP121)s.t x2 2xi 3x1, x2 029

30、2max z 3x1 2x22xi 3x2 142x1 x2 9(LP122)s.t x2 2x14x1, x2 0基解XiX2X3X4X5X6X2 xi x3 x627/21-1/2010010010001/2-1/2001-1-2000-1/21/21z-29/2000-3/2 -1/2 0X2 xi x3 x4232101001001000001010-3-2001-1-2z-130000-2-3(LP121)最優(yōu)解為 x1 3,x22,max z 13, z 13基解X1X2X3X4X5X6X2 xi x3 %27/21-4010-110010001/2-1/2001-1-200000

31、1z-29/2000 -3/2 -1/20X2 xi x3 x627/21-1/2010010010001/2-1/2001-1-20001/2-1/21z-29/2000 -3/2 -1/20X2 xiX3 X614310100101020000-101-30-400-11-2一 z 一-14000-20-1(LP122)最優(yōu)解為 x14,x2 1,maxz 14, z 14基解Xx2x3x4x5x25/2011/2-1/20x113/410-1/43/40*5-30-1001z-59/400-1/4-5/40x25/2011/2-1/20x113/410-1/43/40x5-1/2001/

32、2-"21z-59/400-1/4-5/40x230100-1x15/2101/203/2x4100-11-2z-54/400-3/20-5/2527(LP13)最優(yōu)解xi ,X2 3,maxz 13.5 14 ,盡管不是整數解，但它的目標函數的最大 22值小于14,不必分枝，因此該整數線性規(guī)劃問題的最優(yōu)解為：x1 4,x2 1,maxz 14故，最優(yōu)解求得：x1 4,x2 1,maxz 14這一個比較簡單的整數線性規(guī)劃問題，分解為求解四個非整數線性規(guī)劃問題，有些 求解更為復雜。希望同學們要注意到這一點，理解這種原理，求解這樣方法。作業(yè)：P127, 4.8 (b)§ 4.4

33、 割平面法這是求解整數規(guī)劃問題最早提出的一種方法，1958年由高莫瑞（Gomory）提出。它的基本思想是在整數規(guī)劃問題的松弛問題中依次引進線性約束事件（Gomory約束或割平面），使問題的可行域逐步縮小。但每次切割只割去問題的部分非整數解，直到使問 題的目標函數值達到最優(yōu)的整數點成為縮小后可行域的一個頂點，這樣就可以用求解線性規(guī)劃問題的方法找出這個最優(yōu)解。第一步：把問題中所有約束條件的系數均化為整數，若不考慮變量的整數性約束， 可得到該問題的松弛問題并求解得最后一個單純形表maxz 3x1 2x22x1 3x2 14st 2x1 x2 9 X1,X2 0基解X1X2X3X4X5X2X15/21

34、3/4011/2-1/2010-1/43/40z-59/400 -1/4-5/40X5-1/200 -1/2-1/21 111（增加割平聞X3 x4 ） 222若第一步得到整數解，求解到此結束，否則轉第二步。第二步；找出非整數解變量中非整數部分最大的一個基變量，它們對應的方程為bilXl bi2X2 LbinXnbi0設 fjbbj, j 0,1,2,L ,n ,那么，有bilXi fi1X1 兒風fi2X2 LbinXnfB甌1從而有fi1X1fi2X2 LfinXnfi0稱為割平面引入松弛變量Xn i ,儲Xifi2X2 LfXn Xni解加入到單純形表中去，利用對偶單純形方法進行換基迭代

35、，得到基解XiX2X3X4X5X6X22010-110X17/21001-1/20X310011-20z-29/2000-1-1/20X6-1/20000-"21盡管得到最優(yōu)解，仍不是整數解，增加割平面 繼續(xù)使用對偶單純形方法進行換基迭代，得到:基bX1X2X3X4X5X6X21010-102Xi410010-1X3300110-4X5100001-2z-14000-10-1最優(yōu)解，并且為整數最優(yōu)解。因此得到原整數線性規(guī)劃問題的最優(yōu)解為:x1 4, x2 1,maxz 14這就是割平面法?？梢?，割平面方法比分枝定界方法來得快。§ 5應用舉例例3東方大學計算機實驗室聘用 4名

36、大學生（代號1, 2, 3, 4）和2名研究生（代號5, 6） 值班答疑，已知每人從周一至周五每天最多可安排的值班時間及每人每小時值班的報酬如下表:星期一星期二星期三星期四星期五110.0606072 110.0 10r 606039.94830549.855604510.830480611.306063該實驗室開放時間為上午8: 00至晚上10: 00,開放時間內須有且僅須有一名學生值班，規(guī)定3人，且其中必須有一名研究生。試為該實驗室安排大學生每周值班不少于 8小時，研究生每周不少于 7小時，每名學生每周值班不超過3次，每次值一張人員安排的值班表，使總的支付報酬為最少!1,學生i在周j值班解

37、：設xj為學生i在時間星期j的值班時間,yjij 0,否則min z 10x11 10x219.9x31 9.8x4110.8x51 11.3x6110X2 10x229.9x32 9.8x4210.8x52 11.3x6210X3 10x239.9x33 9.8x4310.8x53 11.3x6310X4 10x249.9x34 9.8x4410.8x54 11.3x6410。10x259.9x35 9.8x4510.8%5 11.3x65班不少于2小時，每天安排值班的學生不超過%2yj0,(i 1,2,3,4,5,6; j 1,2,3,4,5)%aj yj0,(i 1,2,3,4,5,6;

38、j 1,2,3,4,5)xi1xi2xi1xi2xi 3Xi4xi 3xi4x5 8,(ix5 7,(i1,2,3,4)5,6)st x1jx2 jx3jx4j x5j x6j 14,(j 1,2,3,4,5)yi1%2yi3y yi5 3,(i1,234,5,6)y1jy2j y3j y4j y5j y6j3,(j 1,2,3,4,5)y5jy6j1,(j 1,2,3,4,5)xj0,yj0或 1 ,(i1,2,3,4,5,6; j 1,2,3,4,5)min=10*x11+9.9*x31+9.8*x41+10.8*x51+10*x22+9.9*x32+9.8*x42+11.3*x62+10

39、*x13+9. 9*x33+9.8*x43+10.8*x53+10*x24+10.8*x54+11.3*x64+10*x15+9.9*x35+9.8*x45+11.3*x 65;x11-2*y11>0;x13-2*y13>0;x15-2*y15>0;x22-2*y22>0;x24-2*y24>0;x31-2*y31>0;x32-2*y32>0;x33-2*y33>0;x35-2*y35>0;x41-2*y41>0;x42-2*y42>0;x43-2*y43>0;x45-2*y45>0;x51-2*y51>0;x

40、53-2*y53>0;x54-2*y54>0;x62-2*y62>0;x64-2*y64>0;x65-2*y65>0;x11-6*y11<0;x13-6*y13<0;x15-7*y15<0;x22-6*y22<0;x24-6*y24<0;x31-4*y31<0;x32-8*y32<0;x33-3*y33<0;x35-5*y35<0;x41-5*y41<0;x42-5*y42<0;x43-6*y43<0;x45-4*y45<0;x51-3*y51<0;x53-4*y53<0;x

41、54-8*y54<0;x62-6*y62<0;x64-6*y64<0;x65-3*y65<0;x11+x13+x15>8;x22+x24>8;x31+x32+x33+x35>8;x41+x42+x43+x45>8;x51+x53+x54>7;x62+x64+x65>7;x11+x31+x41+x51=14;x22+x32+x42+x62=14;x13+x33+x43+x53=14;x24+x54+x64=14;x15+x35+x45+x65=14;y11+y13+y15<3;y22+y24<3;y31+y32+y33+y3

42、5<3;y41+y42+y43+y45<3;y51+y53+y54<3;y62+y64+x65<3;y11+y31+y41+y51<3;y22+y32+y42+y62<3;y13+y33+y43+y53<3;y24+y54+y64<3;y15+y35+y45+y65<3;y51>1;y62>1;y53>1;y54+y64>1;y65>1;gin(x11);gin(x13); gin(x15);gin(x22); gin(x24);gin(x31) gin(x41) gin(x51) gin(x62) bin(y

43、11) bin(y22) bin(y33) bin(y41)bin(y51) bin(y62)gin(x32); gin(x33);gin(x35);gin(x42); gin(x43); gin(x45);gin(x53); gin(x54);gin(x64); gin(x65);bin(y13); bin(y15);bin(y24); bin(y31); bin(y32);bin(y35);bin(y42); bin(y43); bin(y45);bin(y53); bin(y54);最優(yōu)結果為支付報酬為每周bin(y64); bin(y65);例4 紅星日用化工廠為發(fā)運產品，下一年需 6

44、種不同容積的包裝箱，每種包裝箱的需 求量及生產一個包裝箱的可變費用如下表包裝箱代號123456容積（m3）0.080.10.120.150.200.25需求量（個）500550700900450400口艾費用（兀/個）5.08.010.012.116.318.2由于生產不同規(guī)格的包裝箱需要專門設備、材料等，生產每一種容積的包裝箱的固定費 用為1200元，又若某一種容積的包裝箱數量不夠時可用比它容積大的代替。試問該化 工廠應訂做哪幾種代號的包裝箱各多少個，使費用最節(jié)省？解：設為,（j 1,2,3, 4,5,6）為代號j的包裝箱的數量訂做第j種包裝箱 否則j123,4,5,6min z 1200(

45、 yi y 坐 y y y6)5xi 8x210x3 12.1x4 16.3x5 18.2x6X1 x2 x3 x4 x5 x63500x6400xx6850x4x5x61750stx3x4x5x62450x2x3x4xsx63000xj 9999yj 0,( j 1,2,3,4,5,6)xj 0, yj 0或 1,(j 123,4,5,6)x1 500, x2 0,x3 1250, x4 900, x5 0,x6 850min z 46160元Min =1200*y1+1200*y2+1200*y3+1200*y4+1200*y5+1200*y6+5*x1+8*x2+ 10*x3+12.1*

46、x4+16.3*x5+18.2*x6;x6>=400;x5+x6>=850;x4+x5+x6>=1750;x3+x4+x5+x6>=2450;x2+x3+x4+x5+x6>=3000;x1+x2+x3+x4+x5+x6>=3500;x1-10000*y1<=0;x2-10000*y2<=0;x3-10000*y3<=0;x4-10000*y4<=0;x5-10000*y5<=0;x6-10000*y6<=0;gin (x1);gin (x2);gin (x3);gin (x4);gin (x5);gin (x6);bin (y1);bin (y2);bin (y3);bin (y4);bin (y5);bin (y6);例5春江市計劃為新建的 5個居民區(qū)中的兩個分別各設立一所小學，下表給出