運籌學作業(yè)-王程

1、運籌學作業(yè)王程信管 1302目錄運籌學作業(yè) 1第一章 線性規(guī)劃及單純形法 3第二章 線性規(guī)劃的對偶理論與靈敏度分析 25第三章運輸問題 56第四章 目標規(guī)劃 67第五章整數(shù)規(guī)劃 78第六章非線性規(guī)劃 92第七章動態(tài)規(guī)劃 103第八章 圖與網(wǎng)絡分析 106第九章 網(wǎng)絡計劃 108第一章線性規(guī)劃及單純形法分別用圖解法和單純形法求下列線性規(guī)劃問題，指出問題具有唯一最優(yōu)解、 無窮多最優(yōu)解、無界解還是無可行解；當具有限最優(yōu)解時，指出單純形表中 的各基可行解對應圖解法中可行域的哪一頂點。(1) minz 2x13X2（2）maxz3x12x24x16x262x1X22s.t.3x1 2x24s.t.3x1

2、4x212X1,X20X1, X20(3)maxz 10 X15x2（4）maxz5x16x23x14 x292x1X22s.t.5x12 x28s.t.2x1 3x22x1, x20X1, X2 0解：圖解法:X2216 1當X2 X1 z經(jīng)過點（-廠）時，z最小，且有無窮多個最優(yōu)解335 5圖解法:該問題無可行解圖解法：52單純形法:在上述問題的約束條件中分別加入松弛變量人,人,化為標準型:maxz 10X|+5x2 0x3 0x43為 4x2 X3 9s.t. 5x1 2x2 x4 8加2公3兇 0由線性規(guī)劃問題的標準型可列出單純初始形表逐步迭代，計算結果如下表所單純形表的計算結果表明:

3、 單純形表迭代的第一步得 單純形表迭代的第二步得 單純形表迭代的第三步得示：Cj10500aCBXBbX1X2X3X40X39341030X4852018/5Cj-Zj105000X321/5014/51-3/53/210X18/512/501/54Cj-Zj010-25X23/2015/14-3/1410X1110-1/72/7Cj-Zj00-5/14-25/14*3t *3X ( ,1,0,0) T,Z 105 1202 2X(0)(0,0,9,8) T，表示圖中原點0( 0,0)X(1)(8,0, 21,0) T，表示圖中 C 點55X(2)(1,3,0,0) T，表示圖中 B點2圖解法

4、:X25 1當x2經(jīng)過點(2,2)時，z取得唯一最優(yōu)解6 6將下述線性規(guī)劃問題化成標準形式。(1) min z3片 4x2 2x3 5x44xx2 2x3 X4s.t.xix2 x3 2x4142x1 3x2 x3 x4x1, x2, x3 0,x4 無約束解：上述問題中令z乙x4 x4 x4,其中x4 0,x4 0,則該問題的標準形式為maxz 3x1 4x2 2x3 5x4 5x4 4x1 x2 2x3 x4 x4 2x1 x2 x3 2x4 2x4 x5 14 s.t.2x1 3x2 x3 x4 x4 x6 2 x1,x2,x3,x4 ,x4 , x5 , x6 02)min z 2x1

5、 2x2 3x3x1 x2x3 4s.t. 2x1 x2 x3 6x10, x20, x3無約束解：上述問題中令z乙x,x,X3 X3 X3,其中x/ 0,X3” 0,則該問題的標準形式為max z2x12x2x3x1x2x3x3 4s.t. 2x1 x2x3 x3x46x1,x2,x3 , x3 , x4對下述線性規(guī)劃問題找出所有基解，指出哪些是基可行解，并確定最優(yōu)解1)max z3x15x2(2)min z5x12x23x3 2x4x1x34x12x23x34x4 72 s.t.x2x412s.t. 2x12x2x32x4 33x12x2x518xj 0(j1,L ,4)xj0 j1,L,

6、5解：（1）該線性規(guī)劃問題的全部基解見下表中的，打V者為基可行解, 注 * 者為最優(yōu)解， z* =36。序號xiX2X3X4X5z可行？2620036*V4306027V4600-642X094-6045X0640630V00412180V40012612V60-212018X(2)該線性規(guī)劃問題的標準形式為:max z5x12x23x3 2xX12x23 X34x4 7s.t. 2x12x 2X32x4 3Xj0(j1，,4)其全部基解見下表中的，打V者為基可行解，注 *者為最優(yōu)解，z =5序號X1X2X3X4Z /可行？0011-5*V0-1/202-5X0-1/220-5*V-1/300

7、11/6-2X2/5011/50-43/5V-411/20031X題(3)中，若目標函數(shù)變?yōu)?maxz ex d冷，討論c,d的值如何變化，使該問 題可行域的每個頂點依次使目標函數(shù)達到最優(yōu)。解：由目標函數(shù)maxz ex 可得：冷 彳為 彳kx彳，其中k 彳d d dd3當3 k 0時可行域的頂點A使目標函數(shù)達到最優(yōu);53當5 k 3時，可行域的頂點B使目標函數(shù)達到最優(yōu);245當 k -時，可行域的頂點C使目標函數(shù)達到最優(yōu);2當c 0,d0或c 0,d0時，最優(yōu)解為0點。分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問題，并指出屬哪一類解。(1 mins.t.z 2為 3x2 x1 4x2

8、2x3 3片 2x2Xi，X2，X30X38(2)max z 10x,15x2 12x35x, 3x2 x395x1 6x215x315s.t.2 x1 x2 x35冷必壓 0(1)解：大怯：在上述線性規(guī)劃問題的約束條件中減去剩余變量、Xs,再分別加上人工變量 xc、x?，得minz 2x1 3冷x, 4x? 2x3s.Bx1 2x2 xsX3X4X70x4 Oxg M怡 MXc 86為X，溝,x4,x5,xj,X70其中M是一個任意大的正數(shù)，據(jù)此可列出初始單純形表如下:Cj23100MM9 iCbbX1X2X3X4X5X6X7MX68142-10102MX763200-1013Cj-Zj2-

9、4M3-6M1-2MMM003X221/411/2-1/401/408MX725/20-11/2-1-1/214/5Cj-Zj545M20M丄234Im2MCO I寸WCO I CXI03X29/5013/5-3/101/103/10-1/102Xi4/510-2/51/5-2/5-1/52/5Cj-Zj0001/21/2M-1/2M-1/2由單純形表的計算結果得：最優(yōu)解 X目標函數(shù)最優(yōu)值z*2 - 3 9755X存在非基變量檢驗數(shù)3=0，故該線性規(guī)劃問題有無窮多最優(yōu)解。4 9匚，匚,0,0,0,0,05 5兩階段法：x4, x5,再分別加上人工變量先在上述線性規(guī)劃問題的約束條件中減去剩余變量

10、X6,x7,得第一階段的數(shù)學模型min w=x6 x7為 4x2 2x3 x4 x68s.t. 3x1 2x2 x5 x76Xi，X2，X3，X4, X5, X6，X70據(jù)此可列出單純初始形表如下:Cj00000119 iCbXbbX1X2X3X4X5X6X71X68142-101021X763200-1013Cj -Zj-4-6-211000X221/411/2-1/401/4081X725/20-11/2-1-1/214/5Cj -Zj520112132000X2xi9/54/501103/5-2/5-3/101/51/10-2/53/10-1/5-1/102/5Cj-Zj0000011T

11、第一階段求得的最優(yōu)解X*上,9,0,0,0,0,0 ，目標函數(shù)的最優(yōu)值w 0,因人5 5T工變量X6 x? 0,所以-,9,0,0,0,0,0是原線性規(guī)劃問題的基可行解。于是可5 5以進行第二階段計算，將第一階段的最終表中的人工變量取消， 并填入原問題的目標函數(shù)的系數(shù)，如下表:Cj231009 iCBXbbX1X2X3X4X53X29/5013/5-3/101/102X14/510-2/51/5-2/5Cj-zj0001/21/2由表中計算可知，原線性規(guī)劃問題的最優(yōu)解X*4 ,9,0,0,0,0,0 ，目標函數(shù)的5 5最優(yōu)值z* 2 | 3 9 7，由于存在非基變量檢驗數(shù)3=0，故該線性規(guī)劃問

12、題有無窮多最優(yōu)解解：大M法：在上述線性規(guī)劃問題的約束條件中加上松弛變量5,減去剩余變量g,再加上 人工變量得maxz 1CX1+15C, 12x30X4 0Xs 0x. M 治6x2 15x3 xx3 滄 X7155x1,x2,x3,x4, x5,xg,x?其中M是一個任意大的正數(shù)，據(jù)此可列出單純形表如下:Cj101512000-M9 iCBXbbX1X2X3X4X5X6X70X4953110009/50X515-56150100-MX7521100-115/2Cj-Zj10+2M15+M12+M00-M010X19/513/51/51/500090X524091611003/2-MX77/5

13、0-1/53/5-2/50-117/3Cj-Zj0c M9 510+3M522 -M50M010X13/2139/8003/16-1/800012X33/209/1611/161/1600-MX71/20-43/800-7/16-3/80-11Cj-Zj02743“M8 800217 “M8 1653 “M8 80M0由單純性表的最終表可以看出，所有非基變量檢驗數(shù)j 0，且存在人工變量1X7-，故原線性規(guī)劃問題無可行解。2兩階段法：x4, X5,減去剩余變量x6,再在上述線性規(guī)劃問題的約束條件中加上松弛變量加上人工變量X7,得第一階段的數(shù)學模型min w=x75x1 3x2 Xq x49s.t

14、.5為 6x2 15x32x1X2X3x6X5X7155X-,X2,X3,X4,X5, X6,X7據(jù)此可列出單純初始形表如下:Cj00000019 iCBbX1X2X3X4X5X6X70X4953110009/50X515-56150100-1X7521100-115/2Cj-Zj-2-1-1001010X19/513/51/51/500090X524091611003/21X77/50-1/53/5-2/50-117/3Cj-Zj0-1/53/5-2/50100X13/2139/8003/16-1/80000X33/209/1611/161/16001X71/20-43/800-7/16-3

15、/80-11Cj-Zj0438007/163/8010第一階段求得最優(yōu)解xj ,|0,因人工變量x7 20，且非基變量檢驗數(shù)j 0，所以原線性規(guī)劃問題無可行解?？紤]下述線性規(guī)劃問題：zc1 x1c2 x2a1 xa2 x?b|a?1 xa 22 x?b?x1, x20maxs.t.式中，c 3,4 C2 6, 13,2 目2 5,8 b 12,2 a21 4,4 a22 6,10 b2 14,試確定目標函數(shù)最優(yōu)值的下界和上界。解：（1）上界對應的模型如下（c，b取大，a取小）max z3 x16 x21 x12 x212s.t. 2 x14 x214x1 , x20最優(yōu)值（上界）為：21;（2

16、）下界對應的模型如下（c, b取小，a取大）maxzx14 x23 x15 x28s.t.4x16x210X1 , x20最優(yōu)值（下界）為：。已知某線性規(guī)劃問題的初始單純形表和用單純形法迭代后得到表1-21，試求括弧中未知數(shù)a : l的值。表 1-21項目x 1x 2x 3x 4x 5X46(b)(c)(d)10x 51-13(e)01Cj -Zj(a)-1200X1(f)g)2-11/20X54:h)(i)11/21Cj -Zj0-7(j)(k)(l)解：abcdefgh ijkl324-223105-5-3/20若X,X（2）均為某線性規(guī)劃問題的最優(yōu)解，證明在這兩點連線上的所有點也是該 問

17、題的最優(yōu)解。證明：設X和X滿足:max zC T XAXbX0對于任何0a1,兩點連線上的點X滿足：XaX(1 a ) X也是可行解，且C TXC T aX (1)C T (1 a )X C T aX aC TX (2) C TX c T X所以 X也是最優(yōu)解?？紤]線性規(guī)劃問題maxz x 2x2 x3 4x4(i)(ii)人 Xx4 4 2s.t. 2x! x? 3x3 2x 5 7x1,x2,x3,x4模型中，為參數(shù)，要求:組成兩個新的約束(i)=(i)+(ii),(ii)=(ii)-2(i),根據(jù)式(i)和式(ii)，以xi,為基變量，列出初始單純形表；(i)人備3 2 解：(ii)冷為

18、1Cj fa21-4CB基bX1X2X3X4aX13+2 B101-12X21-B01-10Cj-Zj003- aa-4 在表中，假定 =0 ，則 為何值時， x1,x2 為問題的最優(yōu)基；解：如果=0,貝V當34時，為必為問題的最優(yōu)基變量。 在表中，假定 =3，貝U 為何值時，K,x2為問題的最優(yōu)基。解：如果 =3,則當-11時，X!,X2為問題的最優(yōu)基變量。試述線性規(guī)劃模型中“線性”二字的含義，并用實例說明什么情況下線性的假 設將被違背。答：線性的含義：一是嚴格的比例性，如生產(chǎn)某產(chǎn)品對資源的消耗量和可獲取 的利潤，同其生產(chǎn)數(shù)量嚴格成比例；二是可疊加性，如生產(chǎn)多種產(chǎn)品時，可獲 取的總利潤使各項

19、產(chǎn)品的利潤之和，對某項資源的消耗量應等于各產(chǎn)品對該資 源的消耗量之和；三是可分性，即模型中的變量可以取值為小數(shù)、分數(shù)或某一 實數(shù)；四是確定性，指模型中的參數(shù) cj,aij,bi 均為確定的常數(shù)。很多實際問題往往不符合上述條件，例如每件產(chǎn)品售價 3 元，但成批購買 就可以得到折扣優(yōu)惠。判斷下列說法是否正確，為什么？ 含n個變量m個約束的標準型的線性規(guī)劃問題，基解數(shù)恰好為 Cnm個；答：錯誤?；窘獾膫€數(shù) =基的個數(shù) Cnm 線性規(guī)劃問題的可行解如為最優(yōu)解，貝該可行解一定為基可行解；答：錯誤。當有唯一最優(yōu)解時，最優(yōu)解是可行域頂點，對應基本可行解；當 有無窮多最優(yōu)解時，除了其中的可行域頂點對應基本可

20、行解外，其余最優(yōu)解不 是基本可行解。 如線性規(guī)劃問題存在可行域，貝可行域一定包含坐標的原點；答：錯誤。如果約束條件中有一個約束所對應的區(qū)域不包含坐標的原點，貝 即使有可行域，也不包含坐標的原點。 單純形法迭代計算中，必須選取同最大檢驗數(shù) j 0對應的變量作為換入 基的變量。答：錯誤。若此時最大檢驗數(shù)j 0，可是Pj 0，則問題是無界解，計算結束線性規(guī)劃問題maxz CX,AX b,X 0,如X是該問題的最優(yōu)解，又 0為某 一常數(shù)，分別討論下列情況時最優(yōu)解的變化。目標函數(shù)變?yōu)閙axz CX ；目標函數(shù)變?yōu)閙axz (C )X ；C目標函數(shù)變?yōu)閙axz X，約束條件變?yōu)锳X b。解：最優(yōu)解不變；C

21、為常數(shù)時最優(yōu)解不變，否則可能發(fā)生變化；最優(yōu)解變?yōu)椋篨/入。某飼養(yǎng)場飼養(yǎng)動物出售，設每頭動物每天至少需要 700g蛋白質(zhì)、30g礦物質(zhì)、 100mg維生素。現(xiàn)有五種飼料可供選用，各種飼料每 kg營養(yǎng)成分含量及單價如 表1-22所示。表 1-22飼料蛋白質(zhì)/g礦物質(zhì)/g維生素/mg價格/(元/kg)1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8要求確定既滿足動物生長的營養(yǎng)需要，又使費用最省的選用飼料的方案。解：設Xj表示第i種飼料數(shù)量，i 1,2,3, 4,5min z0.2 x10.7 x20.4 X30.3 x40.8 X53x12x2x3

22、6 x418 x5700丄Xi0.5 x20.2 X32x40.5 x530s.t.0.5x1x20.2 X32x40.8 X5100Xi0, i 1,2,3, 4,5最優(yōu)解為 Xi X2 X30, X439.74, x 25.64, z 32.44（元）遼源街郵局從周一到周日每天所需的職員人數(shù)如下表1-23所示。職員分別安排在周內(nèi)某一天開始上班，并連續(xù)工作5天，休息2天。表 1-23人周一二三四五六日所需人數(shù)17131519141611要求確定：該郵局至少應配備多少職員，才能滿足值班需要； 因從周一開始上班的，雙休日都能休息；周二或周日開始上班的，雙休日 內(nèi)只能有一天得到休息；其他時間開始上

23、班的，兩個雙休日都得不到休息，很 不合理。因此郵局準備對每周上班的起始日進行輪換 （但從起始日開始連續(xù)上5 天班的規(guī)定不變），問如何安排輪換，才能做到在一個星期內(nèi)每名職工享受到同 等的雙休日的休假天數(shù)； 該郵局職員中有一名領班，一名副領班。為便于領導，規(guī)定領班于每周一、 三、四、五、六上班，副領班于一、二、三、五、日這 5天上班。據(jù)此試重新 對上述要求和建模和求解。解：(1)設x(i 1,2,K,7)表示星期一至星期天開始上班的人數(shù)，則建立如下 的數(shù)學模型。目標函數(shù)：min z % x2 x3 x4 x5 x? x7XiX4X5XX7i3xXX6X7Xii5X3XX7XiX2i9約束條件：s.

24、t. x4X7XiX2X3i4X5XiX2X3X4i6x6X2X3X4X5iiX7X3X4X5X6i7Xi,X2,X3,x4,X5,6,X70解得最優(yōu)解為 X* (7,4,2,8,0,2,0), z* 23則該郵局至少應配備23名職員，才能滿足值班需要。對這23名職工分別編號，以23周為一個周期，這23名職工上班安排見下表。每周上班 時間起止周職工職工職工？職工？職工周一周五i7281622172323,16周二周六8ii9i223,1314710周三周日i2i3i3i445561112周四下周一i42i15226137141320周五下周二222323,1141515162122此時只需在每

25、天人數(shù)中減去領班和副領班兩人即可，重現(xiàn)建模如下:min z=x1 x2 x3 x4 x5 x6 x7X1X4X5X6X715X1X2X5X6X712X1X2X3X6X713X1X2X3X4X718X1X2X3X4X512X2X3X4X5X616X3X4X5XX710X1,X2, X3, X4,X5, X6,X70一艘貨輪分前、中、后三個艙位，它們的容積與最大允許載重量如表1-24所示?，F(xiàn)有三種貨物待運，已知有關數(shù)據(jù)列于表1-25。又為了艙運安全，前、中、后艙的實際載重量大體積保持各艙最大允許載重量的比例關系。具體要求：前、后艙分別與中艙之間載重量比例的偏差不超過15%前、后艙之間不超過10%問

26、該貨輪應裝載A、B、C各多少件運費收入 為最大？試建立這個問題的線性規(guī)劃模型。表 1-24項目前艙中艙后艙最大允許載重量/t200030001500容積/m3400054001500表 1-25商品數(shù)量/件每件體積/（m3/件）每件重量/（t/件牛）運價/（元/件）A6001081000B100056700C80075600解：用i=1,2,3表示A、B、C三種貨物，j=1,2,3表示前、中、后三個艙，用x(i , j)表示貨物i在艙j的裝載量。max z 1000( x(1,1)x(1,2)+ x(1,3)+700( x(2,1)+ x(2,2)+ x(2,3)+600( x(3,1)+ x

27、(3,2)+ x(3,3)商品數(shù)量約束：1)x(1,1)x(1,2)x(1,3)6002)x(2,1)x(2, 2)x(2,3)10003)x(3,1)x(3, 2)x(3,3)800商品容積約束：4)10x(1,1)5x(2,1)7x(3,1)40005)10 x(1,2)5x(2, 2)7x(3, 2)54006)10x(1,3)5x(2,3)7x(3,3)1500最大載重量約束：7)8x(1,1)6x(2,1)5x(3,1)20008)8 x(1,2)6x(2, 2)5x(3, 2)30009)8 x(1,3)6x(2,3)5x(3,3)1500重量比例偏差約束：10)8 x(1,1)6

28、x(2,1)5x(3,1)Id0.15)(8 x(1,2)6x(2,1)5x(3, 2)11)8 x(1,1)6x(2,1)5x(3,1)3(10.15)(8 x(1,2)6x(2,1)5x(3, 2)12)8 x(1,3)6x(2,3)5x(3,3)i(10.15)(8 x(1,2)6x(2,1)5x(3, 2)13)8 x(1,3)6x(2,3)5x(3,3)2(10.15)(8 x(1,2)6x(2,1)5x(3, 2)14)8 x(1,3)6x(2,3)5x(3,3)0.1)(8 x(1,1)6x(2,1)5x(3,1)15)8 x(1,3)6x(2,3)5x(3,3)3(10.1)(

29、8 x(1,1)6x(2,1)5x(3,1)4長城通信公司擬對新推出的一款手機收費套餐服務進行調(diào)查，以便進一步設計改進。調(diào)查對象設定為商界人士及大學生，要求：總共調(diào)查600人，其中大學生不少于250人；方式分電話調(diào)查和問卷調(diào)查，其中問卷調(diào)查人數(shù)不少于 30%對大學生電話調(diào)查 80%以上應安排在周六或周日，對商界人士電話調(diào)查 80鳩上應安排在周一至周五；問卷調(diào)查時間不限。已知有關調(diào)查費用如表 1-26所示，問該公司應如何安排調(diào)查，使總的費用為最省。表1-26兀/人次調(diào)查對象電話調(diào)查問卷調(diào)查周一至周五周六、日大學生3.02.55.0商界人士3.53.05.0解：設x“, x2為周一至周五對大學生和

30、商界人士電話調(diào)查人數(shù),2,x22為雙休日對上述 人員電話調(diào)查人數(shù)，為3必23分別為問卷調(diào)查人數(shù)，則數(shù)學模型為minz 3.CX11 2.5Xi2 5.CX13 3.5x?i 3.CX22 5.CX23X|1 X12 X13 x?1 X22 X23600x11 X12x13 250X|3x?3S.t.X121800.8X11 X12X210.8X21 X2最優(yōu)解X|1 0,Xi2 350Xl3 0,X2158,x?2 11,x23 180 z2014生產(chǎn)存儲問題。某廠簽訂了 5種產(chǎn)品（i=1，5） 上半年的交貨合同。已知 各產(chǎn)品在第j月（j=1，6）的合同交貨量D ，該月售價Sj 、成本價co及

31、 生產(chǎn)1件時所需工時aij。該廠第j月的正常生產(chǎn)工時為tj，但必要時可加班生產(chǎn)，第j月允許的最多加 班工時不超過tj/,并且加班時間內(nèi)生產(chǎn)出來的產(chǎn)品每件成本增加額外費用 Cij / 元。若生產(chǎn)出來的產(chǎn)品當月不交貨，每件庫存 1個月交存儲費p元。試為該廠 設計一個保證完成合同交貨，又使上半年預期盈利總額為最大的生產(chǎn)計劃安排。解：設Xjj為i種產(chǎn)品j月正常時間生產(chǎn)數(shù),56maXzi1j5aij Xijc15aij Xijs.t. i 1j(Xikk1Xij0(sij1cij )xij(sijX；j為加班時間生產(chǎn)數(shù)，模型為j,(Xik Xik Dik ) k1cijcij )xij c1pij1tj

32、tjxik)Dikk1(j(j(j宏銀公司承諾為某建設項目從 2003 年起的1,L ,6)1,L ,6)1,L ,6)4 年中每年年初分別提供以下數(shù)額貸款： 2003年 100萬元， 2004年 150萬元， 2005 年 120萬元， 2006年110 萬元。以上貸款資金均需于 2002 年年底前籌集齊。但為了充分發(fā)揮這筆資 金的作用，在滿足每年貸款額情況下，可將多余資金分別用于下列投資項目： 于2003年年初購買A種債券，期限3年，到期后本息合計為投資額的140% 但限購 60萬元； 于2003年年初購買B種債券，期限2年，到期后本息合計為投資額的125%且限購 90 萬元； 于2004

33、年年初購買C種債券，期限2年，到期后本息合計為投資額的130% 但限購 50萬元； 于每年年初將任意數(shù)額的資金存放于銀行，年息 4%，于每年年底取出。 求宏銀公司應如何運用好這筆籌集到的資金，使 2002年年底需籌集到的資金數(shù) 額為最少。解：用Xj（i為第1,2,3年年初，j 1,2,3,4分別為A, B,C, D四類投資數(shù)）min z 480(x11x12 x13x14 )(x21 x22x11(1140%)110x1160x12(1125%)120x1290s.t. x23(1130%)110x2350(x11x12x13x14)(14%)100(x21x22x23x24)(14%)150

34、(x31x32x33x34)(14%)120x23x24)(x31x32x33x34)紅豆服裝廠新推出一款時裝， 據(jù)經(jīng)驗和市場調(diào)查， 預測今后 6 個月對該款時裝的需求為： 1 月 3000件， 2月 3600件， 3月 4000 件， 4月 4600 件， 5月 4800件， 6月 5000 件。生產(chǎn)每件需熟練工人工作 4h,耗用原材料150元，售價為240元/件。該廠1月初有熟 練工80人，每人每月工作160h。為適應生產(chǎn)需要，該廠可招收新工人培訓，但培訓一名新 工人需占用熟練工人 50h 用于指導操作， 培訓期為一個月， 結束后即可上崗。 熟練工人每月 工資 2000 元，新工人培訓期間

35、給予生活補貼 800 元，轉(zhuǎn)正后工資與生產(chǎn)效率同熟練工人。 又熟練工人（含轉(zhuǎn)正一個月后的新工人）每月初有2%因各種原因離職。已知該廠年初已加工出 400件該款時裝作為庫存，要求 6月末存庫 1000件。又每月生產(chǎn)出來時裝如不在當月 交貨，庫存費用為每件每月 10元。試為該廠設計一個滿足各月及 6月末庫存要求，又使1 6 月總收入為最大的勞動力安排方案。解：設該廠每月初擁有熟練工人數(shù)t（t 1L ,6）,每月招收培訓的新工人數(shù)為t, 該廠月末庫存為t, 一月初庫存為。，R為各月對時裝的需求數(shù)，則數(shù)學模型為6maxz（每月銷售收入 熟練工人工資 培訓工人補助 原材料費 庫存費）i1It 1 40x

36、t 12.5yt RtIt It 1 40xt 40yt 1 12.5yt Rts.t.xt 1 0.98xt ytxt,yt 0解得z*=87512元，各月有關數(shù)字如下：t123456Xt8082.47106.62130.93128.32125.75yt4.0725.8026.45000it559.3400637.38970.021000第二章線性規(guī)劃的對偶理論與靈敏度分析寫出下列線性規(guī)劃問題的對偶問題，并以對偶問題為原問題，再寫出對偶的對 偶問題。(1) min z2x12x24x3x13x24x322x1x23x33s.t.x14x23x35Xi , X20, X3無約束y12 y2y3

37、2s.t.3y1 y24 y324 y1 3y2 3y34y10, y20, y3無約束對偶的對偶問題：minv 2m1 2m 24mm1 3m 24m322m1 m23m33s.t.m1 4m23m35m1 ,m20,m3無約束(2) max z 5x1 6x23x3x1 2x22x35x1 5x2x33s.t.4x1 7x23x38捲無約束，x20,x30解：對偶問題： min w5y13y2 8y3y1y24y3 5w33y25y32 y1解：對偶問題： maxs.t.2y1 5y27y362y1 3y23y33丫無約束，y20, y30max v5m16m23m3m12m22m30對偶

38、的對偶問題：m1 5m2 3m30s.t.4m1 7m2 3m30無約束，m20, m30n1(3) minzcij xiji1j1nxij ai (i 1,L ,m)j1ms.t. xij bj(j 1,L ,n)i1xij 0 (i 1,L ,m, j 1,L ,n)mn解：對偶問題： maxwai yibj yj mi 1 j 1s.t.yi yj m cij (i 1,L ,m, j 1,L ,n)yi 無限制，i 1,L ,n m對偶的對偶問題：mnminvcij xiji 1 j 1nxijai(i 1,L ,m)j1ms.t.xijbj(j 1,L ,n)i1Xj 0 (i 1,

39、L ,m, j 1L ,n)(4) max zaij1j X jbi(i 1,L,m1 m)ns.t.aij1j X jbi(i m11,m12,L ,m)xj0( j 1,L ,n1n)Xj無:約束( j n11,L ,n)對偶問題：minw b1 y1b2 y2 Lbmymmaijyii1c j ( j1,2,L ,n1)s.t.maijyii1cj (jn1 1,n1 2,Lyi 0( i1,L ,m1)y無約束(jm1 1,L ,m)cjxjn解：ncjxj對偶的對偶問題： max,n)naij Xj b j1i (i1,L,m1m)ns.t.aij Xj bj1i (im11,m12

40、,L ,m)Xj 0( j1,L,n1n)xj無約束(jn11,L,n)j1判斷下列說法是否正確，并說明為什么。如果線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解； 答：錯誤。如果原問題是無界解，則對偶問題無可行解。如果線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解； 答：錯誤。如果對偶問題無可行解，也可能是因為原問題是無界解。在互為對偶的一對原問題與對偶問題中，不管原問題是求極大或極小，原問 題可行解的目標函數(shù)值一定不超過其對偶問題可行解的目標函數(shù)值；答：錯誤。如果原問題是求極小，則結論相反。任何線性規(guī)劃問題具有唯一的對偶問題。答：正確。已知某求極大線性規(guī)劃問題用單純形法求解時

41、的初始單純形表及最終單純形表如表2-30所示，求表中各括號內(nèi)未知數(shù)(a)(I)的值。Cj T322000Cb基bX1X2X3X4X5X60X4(b)1111000X515(a)120100X6202(c)1001Cj-Zj3220000X45/400(d)(l)-1/4-1/43Xi25/410(e)03/4(i)2X25/201(f)0(h)1/2Cj-Zj0(k)(g)0-5/4(j)解:l=1 , k=0, a=2, c=3,h=-1/2 ,b=10,e=5/4 ,f=-1/2 ,d=1/4 ,g=-3/4 , i=-1/4 , j=-1/4.給出線性規(guī)劃問題min z 2x1 3x25x3 6x4x1 2x2 3x3x42s.t. 2x1x2 x33x43Xj0( j1,L ,4)寫出其對偶問題；用圖解法求解對偶問題；利用的結果及根據(jù)對偶問 題性質(zhì)寫出原問題最優(yōu)解。解：其對偶問題為:min w2y13y2Yi2y222yiy23s.t.3y1y25yi3 y26yi 0, y 0圖解法求解：8 1 *求得最優(yōu)解為y18,y2 5,z195(3)根據(jù)互補松弛型性質(zhì)可以得到最優(yōu)解X*(7 /5,0,1/ 5,0)給出線性規(guī)劃問題max z3x2x25x3X12 x2X35003x12x3460s.t.X14