運(yùn)籌學(xué)作業(yè)-王程

1、運(yùn)籌學(xué)作業(yè)王程信管 1302目錄運(yùn)籌學(xué)作業(yè) 1第一章 線性規(guī)劃及單純形法 3第二章 線性規(guī)劃的對(duì)偶理論與靈敏度分析 25第三章運(yùn)輸問題 56第四章 目標(biāo)規(guī)劃 67第五章整數(shù)規(guī)劃 78第六章非線性規(guī)劃 92第七章動(dòng)態(tài)規(guī)劃 103第八章 圖與網(wǎng)絡(luò)分析 106第九章 網(wǎng)絡(luò)計(jì)劃 108第一章線性規(guī)劃及單純形法分別用圖解法和單純形法求下列線性規(guī)劃問題，指出問題具有唯一最優(yōu)解、 無窮多最優(yōu)解、無界解還是無可行解；當(dāng)具有限最優(yōu)解時(shí)，指出單純形表中 的各基可行解對(duì)應(yīng)圖解法中可行域的哪一頂點(diǎn)。(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當(dāng)X2 X1 z經(jīng)過點(diǎn)（-廠）時(shí)，z最小，且有無窮多個(gè)最優(yōu)解335 5圖解法:該問題無可行解圖解法：52單純形法:在上述問題的約束條件中分別加入松弛變量人,人,化為標(biāo)準(zhǔn)型:maxz 10X|+5x2 0x3 0x43為 4x2 X3 9s.t. 5x1 2x2 x4 8加2公3兇 0由線性規(guī)劃問題的標(biāo)準(zhǔn)型可列出單純初始形表逐步迭代，計(jì)算結(jié)果如下表所單純形表的計(jì)算結(jié)果表明:

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，表示圖中原點(diǎn)0( 0,0)X(1)(8,0, 21,0) T，表示圖中 C 點(diǎn)55X(2)(1,3,0,0) T，表示圖中 B點(diǎn)2圖解法

4、:X25 1當(dāng)x2經(jīng)過點(diǎn)(2,2)時(shí)，z取得唯一最優(yōu)解6 6將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式。(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,則該問題的標(biāo)準(zhǔn)形式為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,則該問題的標(biāo)準(zhǔn)形式為max z2x12x2x3x1x2x3x3 4s.t. 2x1 x2x3 x3x46x1,x2,x3 , x3 , x4對(duì)下述線性規(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。序號(hào)xiX2X3X4X5z可行？2620036*V4306027V4600-642X094-6045X0640630V00412180V40012612V60-212018X(2)該線性規(guī)劃問題的標(biāo)準(zhǔn)形式為:max z5x12x23x3 2xX12x23 X34x4 7s.t. 2x12x 2X32x4 3Xj0(j1，,4)其全部基解見下表中的，打V者為基可行解，注 *者為最優(yōu)解，z =5序號(hào)X1X2X3X4Z /可行？0011-5*V0-1/202-5X0-1/220-5*V-1/300

7、11/6-2X2/5011/50-43/5V-411/20031X題(3)中，若目標(biāo)函數(shù)變?yōu)?maxz ex d冷，討論c,d的值如何變化，使該問 題可行域的每個(gè)頂點(diǎn)依次使目標(biāo)函數(shù)達(dá)到最優(yōu)。解：由目標(biāo)函數(shù)maxz ex 可得：冷 彳為 彳kx彳，其中k 彳d d dd3當(dāng)3 k 0時(shí)可行域的頂點(diǎn)A使目標(biāo)函數(shù)達(dá)到最優(yōu);53當(dāng)5 k 3時(shí)，可行域的頂點(diǎn)B使目標(biāo)函數(shù)達(dá)到最優(yōu);245當(dāng) k -時(shí)，可行域的頂點(diǎn)C使目標(biāo)函數(shù)達(dá)到最優(yōu);2當(dāng)c 0,d0或c 0,d0時(shí)，最優(yōu)解為0點(diǎn)。分別用單純形法中的大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是一個(gè)任意大的正數(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由單純形表的計(jì)算結(jié)果得：最優(yōu)解 X目標(biāo)函數(shù)最優(yōu)值z(mì)*2 - 3 9755X存在非基變量檢驗(yàn)數(shù)3=0，故該線性規(guī)劃問題有無窮多最優(yōu)解。4 9匚，匚,0,0,0,0,05 5兩階段法：x4, x5,再分別加上人工變量先在上述線性規(guī)劃問題的約束條件中減去剩余變量

10、X6,x7,得第一階段的數(shù)學(xué)模型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 ，目標(biāo)函數(shù)的最優(yōu)值w 0,因人5 5T工變量X6 x? 0,所以-,9,0,0,0,0,0是原線性規(guī)劃問題的基可行解。于是可5 5以進(jìn)行第二階段計(jì)算，將第一階段的最終表中的人工變量取消， 并填入原問題的目標(biāo)函數(shù)的系數(shù)，如下表:Cj231009 iCBXbbX1X2X3X4X53X29/5013/5-3/101/102X14/510-2/51/5-2/5Cj-zj0001/21/2由表中計(jì)算可知，原線性規(guī)劃問題的最優(yōu)解X*4 ,9,0,0,0,0,0 ，目標(biāo)函數(shù)的5 5最優(yōu)值z(mì)* 2 | 3 9 7，由于存在非基變量檢驗(yàn)數(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是一個(gè)任意大的正數(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由單純性表的最終表可以看出，所有非基變量檢驗(yàn)數(shù)j 0，且存在人工變量1X7-，故原線性規(guī)劃問題無可行解。2兩階段法：x4, X5,減去剩余變量x6,再在上述線性規(guī)劃問題的約束條件中加上松弛變量加上人工變量X7,得第一階段的數(shù)學(xué)模型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，且非基變量檢驗(yàn)數(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,試確定目標(biāo)函數(shù)最優(yōu)值的下界和上界。解：（1）上界對(duì)應(yīng)的模型如下（c，b取大，a取?。﹎ax z3 x16 x21 x12 x212s.t. 2 x14 x214x1 , x20最優(yōu)值（上界）為：21;（2

16、）下界對(duì)應(yīng)的模型如下（c, b取小，a取大）maxzx14 x23 x15 x28s.t.4x16x210X1 , x20最優(yōu)值（下界）為：。已知某線性規(guī)劃問題的初始單純形表和用單純形法迭代后得到表1-21，試求括弧中未知數(shù)a : l的值。表 1-21項(xiàng)目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)解，證明在這兩點(diǎn)連線上的所有點(diǎn)也是該 問

17、題的最優(yōu)解。證明：設(shè)X和X滿足:max zC T XAXbX0對(duì)于任何0a1,兩點(diǎn)連線上的點(diǎn)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ù)，要求:組成兩個(gè)新的約束(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 ，則 為何值時(shí)， x1,x2 為問題的最優(yōu)基；解：如果=0,貝V當(dāng)34時(shí)，為必為問題的最優(yōu)基變量。 在表中，假定 =3，貝U 為何值時(shí)，K,x2為問題的最優(yōu)基。解：如果 =3,則當(dāng)-11時(shí)，X!,X2為問題的最優(yōu)基變量。試述線性規(guī)劃模型中“線性”二字的含義，并用實(shí)例說明什么情況下線性的假 設(shè)將被違背。答：線性的含義：一是嚴(yán)格的比例性，如生產(chǎn)某產(chǎn)品對(duì)資源的消耗量和可獲取 的利潤，同其生產(chǎn)數(shù)量嚴(yán)格成比例；二是可疊加性，如生產(chǎn)多種產(chǎn)品時(shí)，可獲 取的總利潤使各項(xiàng)

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

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

21、為常數(shù)時(shí)最優(yōu)解不變，否則可能發(fā)生變化；最優(yōu)解變?yōu)椋篨/入。某飼養(yǎng)場(chǎng)飼養(yǎng)動(dòng)物出售，設(shè)每頭動(dòng)物每天至少需要 700g蛋白質(zhì)、30g礦物質(zhì)、 100mg維生素?，F(xiàn)有五種飼料可供選用，各種飼料每 kg營養(yǎng)成分含量及單價(jià)如 表1-22所示。表 1-22飼料蛋白質(zhì)/g礦物質(zhì)/g維生素/mg價(jià)格/(元/kg)1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8要求確定既滿足動(dòng)物生長(zhǎng)的營養(yǎng)需要，又使費(fèi)用最省的選用飼料的方案。解：設(shè)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要求確定：該郵局至少應(yīng)配備多少職員，才能滿足值班需要； 因從周一開始上班的，雙休日都能休息；周二或周日開始上班的，雙休日 內(nèi)只能有一天得到休息；其他時(shí)間開始上

23、班的，兩個(gè)雙休日都得不到休息，很 不合理。因此郵局準(zhǔn)備對(duì)每周上班的起始日進(jìn)行輪換 （但從起始日開始連續(xù)上5 天班的規(guī)定不變），問如何安排輪換，才能做到在一個(gè)星期內(nèi)每名職工享受到同 等的雙休日的休假天數(shù)； 該郵局職員中有一名領(lǐng)班，一名副領(lǐng)班。為便于領(lǐng)導(dǎo)，規(guī)定領(lǐng)班于每周一、 三、四、五、六上班，副領(lǐng)班于一、二、三、五、日這 5天上班。據(jù)此試重新 對(duì)上述要求和建模和求解。解：(1)設(shè)x(i 1,2,K,7)表示星期一至星期天開始上班的人數(shù)，則建立如下 的數(shù)學(xué)模型。目標(biāo)函數(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則該郵局至少應(yīng)配備23名職員，才能滿足值班需要。對(duì)這23名職工分別編號(hào)，以23周為一個(gè)周期，這23名職工上班安排見下表。每周上班 時(shí)間起止周職工職工職工？職工？職工周一周五i7281622172323,16周二周六8ii9i223,1314710周三周日i2i3i3i445561112周四下周一i42i15226137141320周五下周二222323,1141515162122此時(shí)只需在每

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

26、該貨輪應(yīng)裝載A、B、C各多少件運(yùn)費(fèi)收入 為最大？試建立這個(gè)問題的線性規(guī)劃模型。表 1-24項(xiàng)目前艙中艙后艙最大允許載重量/t200030001500容積/m3400054001500表 1-25商品數(shù)量/件每件體積/（m3/件）每件重量/（t/件牛）運(yùn)價(jià)/（元/件）A6001081000B100056700C80075600解：用i=1,2,3表示A、B、C三種貨物，j=1,2,3表示前、中、后三個(gè)艙，用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長(zhǎng)城通信公司擬對(duì)新推出的一款手機(jī)收費(fèi)套餐服務(wù)進(jìn)行調(diào)查，以便進(jìn)一步設(shè)計(jì)改進(jìn)。調(diào)查對(duì)象設(shè)定為商界人士及大學(xué)生，要求：總共調(diào)查600人，其中大學(xué)生不少于250人；方式分電話調(diào)查和問卷調(diào)查，其中問卷調(diào)查人數(shù)不少于 30%對(duì)大學(xué)生電話調(diào)查 80%以上應(yīng)安排在周六或周日，對(duì)商界人士電話調(diào)查 80鳩上應(yīng)安排在周一至周五；問卷調(diào)查時(shí)間不限。已知有關(guān)調(diào)查費(fèi)用如表 1-26所示，問該公司應(yīng)如何安排調(diào)查，使總的費(fèi)用為最省。表1-26兀/人次調(diào)查對(duì)象電話調(diào)查問卷調(diào)查周一至周五周六、日大學(xué)生3.02.55.0商界人士3.53.05.0解：設(shè)x“, x2為周一至周五對(duì)大學(xué)生和

30、商界人士電話調(diào)查人數(shù),2,x22為雙休日對(duì)上述 人員電話調(diào)查人數(shù)，為3必23分別為問卷調(diào)查人數(shù)，則數(shù)學(xué)模型為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)存儲(chǔ)問題。某廠簽訂了 5種產(chǎn)品（i=1，5） 上半年的交貨合同。已知 各產(chǎn)品在第j月（j=1，6）的合同交貨量D ，該月售價(jià)Sj 、成本價(jià)co及

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

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

33、年年初購買C種債券，期限2年，到期后本息合計(jì)為投資額的130% 但限購 50萬元； 于每年年初將任意數(shù)額的資金存放于銀行，年息 4%，于每年年底取出。 求宏銀公司應(yīng)如何運(yùn)用好這筆籌集到的資金，使 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)紅豆服裝廠新推出一款時(shí)裝， 據(jù)經(jīng)驗(yàn)和市場(chǎng)調(diào)查， 預(yù)測(cè)今后 6 個(gè)月對(duì)該款時(shí)裝的需求為： 1 月 3000件， 2月 3600件， 3月 4000 件， 4月 4600 件， 5月 4800件， 6月 5000 件。生產(chǎn)每件需熟練工人工作 4h,耗用原材料150元，售價(jià)為240元/件。該廠1月初有熟 練工80人，每人每月工作160h。為適應(yīng)生產(chǎn)需要，該廠可招收新工人培訓(xùn)，但培訓(xùn)一名新 工人需占用熟練工人 50h 用于指導(dǎo)操作， 培訓(xùn)期為一個(gè)月， 結(jié)束后即可上崗。 熟練工人每月 工資 2000 元，新工人培訓(xùn)期間

35、給予生活補(bǔ)貼 800 元，轉(zhuǎn)正后工資與生產(chǎn)效率同熟練工人。 又熟練工人（含轉(zhuǎn)正一個(gè)月后的新工人）每月初有2%因各種原因離職。已知該廠年初已加工出 400件該款時(shí)裝作為庫存，要求 6月末存庫 1000件。又每月生產(chǎn)出來時(shí)裝如不在當(dāng)月 交貨，庫存費(fèi)用為每件每月 10元。試為該廠設(shè)計(jì)一個(gè)滿足各月及 6月末庫存要求，又使1 6 月總收入為最大的勞動(dòng)力安排方案。解：設(shè)該廠每月初擁有熟練工人數(shù)t（t 1L ,6）,每月招收培訓(xùn)的新工人數(shù)為t, 該廠月末庫存為t, 一月初庫存為。，R為各月對(duì)時(shí)裝的需求數(shù)，則數(shù)學(xué)模型為6maxz（每月銷售收入 熟練工人工資 培訓(xùn)工人補(bǔ)助 原材料費(fèi) 庫存費(fèi)）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元，各月有關(guān)數(shù)字如下：t123456Xt8082.47106.62130.93128.32125.75yt4.0725.8026.45000it559.3400637.38970.021000第二章線性規(guī)劃的對(duì)偶理論與靈敏度分析寫出下列線性規(guī)劃問題的對(duì)偶問題，并以對(duì)偶問題為原問題，再寫出對(duì)偶的對(duì) 偶問題。(1) min z2x12x24x3x13x24x322x1x23x33s.t.x14x23x35Xi , X20, X3無約束y12 y2y3

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

38、的對(duì)偶問題：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解：對(duì)偶問題： 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對(duì)偶的對(duì)偶問題：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)對(duì)偶問題：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對(duì)偶的對(duì)偶問題： 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ī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解； 答：錯(cuò)誤。如果原問題是無界解，則對(duì)偶問題無可行解。如果線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解； 答：錯(cuò)誤。如果對(duì)偶問題無可行解，也可能是因?yàn)樵瓎栴}是無界解。在互為對(duì)偶的一對(duì)原問題與對(duì)偶問題中，不管原問題是求極大或極小，原問 題可行解的目標(biāo)函數(shù)值一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值；答：錯(cuò)誤。如果原問題是求極小，則結(jié)論相反。任何線性規(guī)劃問題具有唯一的對(duì)偶問題。答：正確。已知某求極大線性規(guī)劃問題用單純形法求解時(shí)

41、的初始單純形表及最終單純形表如表2-30所示，求表中各括號(hào)內(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)寫出其對(duì)偶問題；用圖解法求解對(duì)偶問題；利用的結(jié)果及根據(jù)對(duì)偶問 題性質(zhì)寫出原問題最優(yōu)解。解：其對(duì)偶問題為:min w2y13y2Yi2y222yiy23s.t.3y1y25yi3 y26yi 0, y 0圖解法求解：8 1 *求得最優(yōu)解為y18,y2 5,z195(3)根據(jù)互補(bǔ)松弛型性質(zhì)可以得到最優(yōu)解X*(7 /5,0,1/ 5,0)給出線性規(guī)劃問題max z3x2x25x3X12 x2X35003x12x3460s.t.X14