運籌學(xué)課后習(xí)題答案

1、第一章 線性規(guī)劃及單純形法1用Xj（j=1.25）分別代表5中飼料的采購數(shù)，線性規(guī)劃模型：2.解：設(shè)x表示在第i個時期初開始工作的護士人數(shù)，z表示所需的總?cè)藬?shù)，則3解：設(shè)用i=1，2，3分別表示商品A，B，C，j=1，2，3分別代表前，中，后艙，Xij表示裝于j艙的i種商品的數(shù)量，Z表示總運費收入則：5. （1） Z = 4 （2）解：如圖：由圖可得：即該問題具有唯一最優(yōu)解（3） 無可行解 (4)如圖： 由圖知，該問題具有無界解。6（1） （2） 71）系數(shù)矩陣A： （B，b）= y1=（0，16/3，-7/6，0，0，0）T同理y2=（0，1

2、0，0，-7，0，0）T y3=（0， 3，0，0，7/2，0）T y4=（7/4，-4，0，0，0，21/4）T y5=（0，0，-5/2，8，0，0）T y6=（0，0，3/2，0，8，0）T y7=（1，0，-1/2，0，0，3）T y8=（0，0，0，3，5，0）T y9=（5/4，0，0，-2，0，15/4）T y10=（0， 3，-7/6，0，0，0）T y11=（0，0，-5/2，8，0，0）T y12=（0，0，-5/2，3，5，0）T y13=（4/3，0，0，0，2，3/4）T y14=（0，10，0，-7，0，0）T y15=（0， 3，0，0，7/3，0）T y16=（

3、0，0，3/2，0，8，0）T 基可行解：（每個x值都大于0），（y3，y6，y8，y12，y13，y15，y16） 最優(yōu)解：（y3，y6， y15，y16） Zmax=3p2 p3 p4，p2 p3 p5，p3 p4 p5，p2 p4 p5為奇異，只有16個基。 解：（2）該線性問題最多有個基本解。 基本解 Z基本可行解最優(yōu)解1X1X2X3X4   2-411/200  32/5011/50   3-1/30011/6   401/220 50-1/20

4、2   60011  8.基的定義 X1 X2 X3所對應(yīng)的列向量可以構(gòu)成基 B 由 X1 X2 X3 列向量構(gòu)成 = N 由 非基變量對應(yīng)的向量構(gòu)成 = （B，b）= B對應(yīng)的基解：（-13/5，37/5，0，0，3/5） 9解：（1）由圖知： 單純形法：化為標準形如下：C10500bCBXBX1X2X3XR0X3341090XR52018檢驗數(shù)1050000X3014/51-3/521/510X112/50-1/58/5檢驗數(shù)010-2-165X2015/14-3/143/210X110-1/73/70檢驗數(shù)00-5/14-25/

5、14-35/2 所以：其中： 9.2） A點最大 Z= 8 化為標準形：C2-100bCBXBX1X2X3X40X33510150X4620124檢驗數(shù)2-1000 X3041-1/23 X111/301/64檢驗數(shù)0-10-1/3-8   0點（0，0，15，24）   A點（4，0，3，0） Zmax=8 10.解1）要使A（0，0）成為最優(yōu)解則需C0且d0； 2）要使B（8/5，0）成為最優(yōu)解則 C0且d=0或C>0且d<0或C/d5/2且Cd>0； 3）要使C（1，3/2）成為最優(yōu)解則 -5/2-C/d-3/

6、4且Cd>0；即5/2C/d3/4且Cd>0；4）要使D（0，9/4）成為最優(yōu)解則C<0且d>0或C=0，d>011.(1)化為標準型： C2-11000bCBXBX1X2X3X4X5X60X4311100600X51-12010100X611-100120檢驗數(shù)2-1100000X404-51-30302X11-12010100X602-30-1110檢驗數(shù)01-30-20-200X40011-1-2102X1101/201/21/215-1X201-3/20-1/21/25檢驗數(shù)00-3/20-3/2-1/2-25 （2） C2350000

7、bCBXBX1X2X3X4X5X6X70X42231000120X5122010080X64060010160X7043000112檢驗數(shù)235000000X402010-1/2040X5-1/32001-1/303/85X32/301001/603/80X7-24000-1/214檢驗數(shù)-4/33000-5/60-40/30X410010-1/4-1/220X52/30001-1/12-1/22/35X32/301001/608/33X2-1/21000-1/81/41檢驗數(shù)1/60000-11/24-3/4-49/30X40001-2/3-1/81/412X110002/3-1/8-3/4

8、15X30010-11/41/223X201003/4-3/16-1/83/2檢驗數(shù)0000-1/4-7/16-5/8-33/2  （3）標準型：C35000bCBXBX1X2X3X4X50X31010040X402010120X53200118檢驗數(shù)350000 X3101004 X20101/206 X5300-116檢驗數(shù)300-5/20-30 X30011/3-1/32 X20101/206 X1100-1/31/32檢驗數(shù)000-3/2-1-36（4）標準型 C-11-1-11-11-11-M-

9、M-M0bCBXBX1X2X3X4X4“X5X5“X6X6“X7X8X9X10-MX71001-1001-110009-MX831-400002-201002-MX91.200-112-2001060X10043000000000112檢驗數(shù)5M-1M+1-1-2MM-11-MM+11+M5M-11-5M000017M-MX70-1/34/31-1001/3-1/31-1/30028/3-1X111/3-4/300002/3-2/301/3002/3-MX90-1/310/300-114/3-4/30-1/31016/30X10043000000000112檢驗數(shù)04/3-2/3M14/5M-

10、7/3M-11-MM-1M+15/3M-1/3-5/3M+1/30-5/3M+1/300-41/3M-2/3-MX70-1/501-12/5-2/5-1/51/51-1/5-2/5031/5-1X111/5000-2/52/56/5-6/501/52/5014/5-1X30-1/10100-3/103/102/5-2/50-1/103/1008/50X10043/100009/10-9/10-6/56/503/10-9/10136/5檢驗數(shù)0-1/5M+11/100M-11-M2/5M-17/10-2/5M+17/103/5-1/5M1/5M-3/50-6/5M-7/5M0-31M/5-22/

11、5 （5）解：標準化： C62108000bCBXBX1X2X3X4X5X6X70X556-4-4100200X63-328010250X74-21300110檢驗數(shù)6210800000X521-208114600X6-510200-2510X34-21300110檢驗數(shù)-34220-2200-10-1000X5110012120702X2-510201-2510X3-601702-320檢驗數(shù)7600-660-2234-210由表可得， 因此問題的解無界。（6）化為:標準形：Z=-Z（I）C-x-1-1000bCBXBX1X2X3X4X5X6-XX1100-40-25-1

12、X20102-313-1X30012-565檢驗數(shù)0004-4x-87-2x5x+8  如圖：1. 1.    X7/2 時，檢驗數(shù)0 ，最優(yōu)解：（5，3，5，0，0）T2. 2.    1X<7/2時，4-4X<0,-2X+7>0由（I）得：C-x-1-1000bCBXBX1X2X3X4X5X6-XX1101/3-10/3-5/3020/3-1X201-1/65/3-13/6013/60X6001/61/3-5/615/6檢驗數(shù)00X/3-7/6-10X/3+5/3-5X/3-13/6020X/3+13/

13、63. X <-3/2時 4-4X>-2X+7>0 C-x-1-1000bCBXBX1X2X3X4X5X6-XX11200-6011-1X201/201-3/21/23/2-1X30-110-252檢驗數(shù)02x-200-6X-2511X+2檢驗數(shù)>0，列系數(shù)0，所以解無界。 4.-3/2X<1； -2X+7>4-4X>0 C-x-1-1000bCBXBX1X2X3X4X5X6-XX1100-10/3-5/3020/3-1X20105/3-13/6013/6-1X60011/3-5/615/6檢驗數(shù)  X/3-7/

14、6-10X/3+5/3-5X/3-13/6 20X/3+13/6判斷檢驗數(shù)的符號： 1)1/2X< 1 ，所有檢驗數(shù) <0（1/2X<2）-1.3X<1/2時表（A）C-x-1-1000bCBXBX1X2X3X4X5X6-XX11200-600110X403/5-1/101-13/100013/100X60-1/51/50-2/5112/5檢驗數(shù)02X-1-10-6X011X對-6X討論，令-6X=0 X=01 0X<1/2時， 檢驗數(shù)<0 （0X1/2）2-1.3X<0時， -6X>0 又 X5列的系數(shù)< 0 ，所以解

15、無界3） -1.5X<-1.3時， 同表（A） -6X>0 ，又 X5的列的系數(shù)<0，所以解無界  （7）解：化為標準形： C164000000-M-M-MbCBXBX1X2X3X4X5X6X7X8X9X10X11X120X4-122100000000130X54-41010000000200X612100110000017-MX101000000001001-MX110100000-100102-MX1200100000-10013檢驗數(shù)1+M6+M4+M000-M-M-M000 0X4-1021000200-2090X5401010

16、0-40040260X61010010200-2013-MX10100000-10010016X20100000-100102-MX1200100000-10013檢驗數(shù)1+M04+M000-M6-M0-6-M0 0X4-1001000220-2-230X54000100-4104-1250X61000010210-2-110-MX10100000-10010016X20100000-1001024X300100000-10013檢驗數(shù)1+M00000-M6410-6-M-4-M 0X4000100-1221-2-240X500001004-41-44-1210X60000

17、01121-1-2-191X1100000-10010016X20100000-1001024X300100000-10013檢驗數(shù)000000164 0X80001/200-1/2111/2-1-120X5000210205-20-5290X6000-10120-1-20151X1100000-10010016X20101/200-1/2011/21/2-144X300100000-10013檢驗數(shù)000-30040-2 0X80001/401/4013/40-1-3/413/40X500031-100600-6240X7000-1/201/210-1/2-101/25/

18、21X1100-1/201/200-1/2001/27/26X20101/401/4003/400-3/421/44X300100000-10013檢驗數(shù)000-10-2000-47 即：（8）解：化為標準形：C1-11-31-1-3-M-M-M-MbCBXBX1X2X3X4X5X6X7X8X9X10X11-MX8003011010006-MX9012-1000010010-MX10-100001000100-MX11001001100016檢驗數(shù)1-MM-16M+1-M-31+M-1+3M3+M0000 1X3001 1/31/301/30002-MX9010-

19、1-2/3-2/30-2/31006-MX10-100001000100-MX110000-1/32/31-1/30014檢驗數(shù)1-MM-10-M-32/3-MM-1/3M-3000 1X300101/31/301/30002-1X2010-1-2/3-2/3001006-MX10-1000010-2/30100-MX110000-1/32/31-1/30014檢驗數(shù)1-M00-45/3M-2M-300 1X300101/20-1/21/200-1/20-1X2010-1-101-110110-MX10-10001/20-3/21/201-1/2-61X60000-1/21

20、3/2-1/2003/26檢驗數(shù)1-M00-41/2M-100 1X3111000100-110-1X2-200-100-2012-2-21X5-200010-3102-3-12-1X6-100001 00100檢驗數(shù)-100-400-3 12（1）解：標準形：1C2-12000-M-M-MbCBXBX1X2X3X4X5X6X7X8X9-MX7111-1001006-MX8-1010-100102-MX902-100-10010檢驗數(shù)2-1+3M2+M-M-M-M000 -MX7103/2-101/210-1/26-MX8-1010-100102-1X2

21、01-1/200-1/2001/20檢驗數(shù)205/2M+3/2-M-M1/2M-1/200 -MX75/200-13/21/21-3/2-1/232X3-1010-100102-1X2-1100-1/2-1/201/21/21檢驗數(shù)5/2M+7/200-M3/2M1/2M0 2X1100-2/53/51/52/5-3/5-1/56/52X3001-2/5-2/51/52/52/5-1/516/5-1X2010-1/5-1/5-2/51/51/52/58/5檢驗數(shù)0007/5-3/5-6/5 由表可知此題解無界。 2得一輔助問題： C000000

22、-1-1-1bCBXBX1X2X3X4X5X6X7X8X9-1X7111-1001006-1X8-1010-100102-1X902-100-10010檢驗數(shù)031-1-1-1000 -1X7103/2-101/210-1/26-1X8-1010-1001020X201-1/200-1/2001/20檢驗數(shù)005/2-1-11/200-3/2 -1X75/200-13/21/21-3/2-1/230X3-1010-1001020X2-1100-1/2-1/201/21/21檢驗數(shù)5/200-13/20 0X1100-2/53/51/52/5-3/5-1/56/50

23、X3001-2/5-2/51/52/52/5-1/516/50X2010-1/5-1/5-2/51/51/52/58/5檢驗數(shù)000000-1-1-10 C2-12000bCBXBX1X2X3X4X5X62X1100-2/53/51/5  -1X3001-2/5-2/51/52X2010-1/5-1/5-2/5檢驗數(shù)0-334/5由表知此題屬于解無界 （2）大M法，先化為標準形：Z=-ZC-4-100-M-MbCBXBX1X2X3X4X5X60X41201004-MX51100103-MX643-10016檢驗數(shù)5M-44M-1-M0009M0X405/

24、41/410 5/2-MX501/41/401 3/2-4X113/4-1/400 3/2檢驗數(shù)0M/4+2M/4-100 3M/2+6-1X2011/54/50 2-MX5001/5-1/51 1-4X110-2/5-3/50 0檢驗數(shù)00M/5-7/5-M/5-8/50 M+2-1X20101  10X3001-1  5-4X1100-1  2 000-3  9 原問題唯一最優(yōu)解 二階段法：引入人工變量 X5 X

25、6得原問題的一個輔助問題：C0000-1-1bCBXBX1X2X3X4X5X60X41201004-MX51100103-MX643-10016檢驗數(shù)54-100090X405/41/410 5/2-MX501/41/401 3/2-4X113/4-1/400 3/2檢驗數(shù)01/41/400 3/2-1X2011/54/50 2-MX5001/5-1/51 1-4X110-2/5-3/50 0檢驗數(shù)001/5-1/50 1-1X20101  10X3001-1  5-4X11

26、00-1  2檢驗數(shù)000-1  0 C-4-100bCBXBX1X2X3X4-1X2001-150X301011-4X1100-12檢驗數(shù)000-39  （3）標準形：  C-23-1000-M-MbCBXBX1X2X3X4X5X6X7X8-MX7142-100108-MX83200-10016檢驗數(shù)-2-4M6M+32M-1-M-M000 3X21/411/2-1/4001/402-MX85/20-11/2-10-1/212檢驗數(shù)5/2M-11/40-M-5/21/2M+3/4-M00

27、60;3X2013/5-3/101/1003/10-1/109/5-2X110-2/51/5-2/50-1/52/54/5檢驗數(shù)00-18/513/100 3X25/2100-1/2001/230X450-21-20-124檢驗數(shù)0-103/20-M-M 由表知此題解無界；（6）兩階段法：C000000-1-1bCBXBX1X2X3X4X5X6X7X8-1X7142-100108-1X83200-10016檢驗數(shù)462-1-1000 0X21/411/2-1/4001/402-1X85/20-11/2-10-1/212檢驗數(shù)5/2M-11/40-M-5/21/2M

28、+3/4-M00 0X2013/5-3/101/1003/10-1/109/50X110-2/51/5-2/50-1/52/54/5檢驗數(shù)000000-1-1 C-23-1000bCBXBX1X2X3X4X5X63X2013/5-3/101/1009/5-2X110-2/51/5-2/504/5檢驗數(shù)00-18/513/100 3X25/2100-1/2030X450-21-204檢驗數(shù)0-103/20  由表知此題為解無界；（4）化為標準形：C101512000-MbCBXBX1X2X3X4X5X6X70X4531100090X5-56150

29、10015-MX721100-115 2M+10M+1512+M00-M0 10X113/51/51/50009/50X50916110024-MX70-1/53/5-2/50-112/5 03/5M00 10X1139/80015/80-1/800015/1012X309/1611/161/16003/2-MX70-43/800-35/80-3/80-111/2 000  13（1） （2） （3）14C2-11000bCBXBX1X2X3X4X5X60X4311100600X51-12010100X601-100120&

30、#160;2-11000 0X404-51-30302X11-12010100X602-30-1110 01-30-20 0X40011-1-2102X1101/201/21/215-1X201-3/20-1/21/25 00-3/20-3/2-1/2-25 15.C2-11000bCBXBX1X2X3X4X5X60X22/3101/3008/30X5-4/3052/31014/30X65/304-5/30129/3 -1/30-4-5/300 -1X22/3101/3008/31X3-4/15012/151/5014/15

31、0X641/1500-33/15-4/5184/15 44/15003/15-1/50    16. 17.解：由表知：（1） d=1，e=0，b=-6，f=1/3，g=0，a=7； （2）由表知所有  18.證明：  20解（1） 第二章 線性規(guī)劃的對偶理論1.解：設(shè)分別表示A、B、C各產(chǎn)品的數(shù)量，Z 表示總產(chǎn)值則：  經(jīng)濟解釋：y1，y2，y3分別表示給別人代工時所得收入，對廠方而言，w越大越好，但定價不能太高，要對方容易接受，應(yīng)考慮使總收入即對方的總支出盡可能少才比較合

32、理，廠方不會吃虧，對方也容易接受。 2  3.證明： 是線性問題的可行解，即該問題存在可行解； 又其對偶問題為：4.證明：該線性問題的對偶問題為：  5.證明：對偶問題 7. 7.        1）對偶問題： 2）由題知原問題的最優(yōu)解為 由互補松弛定理得：在對偶問題中對應(yīng)第一，二個約束為緊，第三個約束條件為松，即， 對偶規(guī)劃問題的最優(yōu)解 3）影子價格為 y1 = 4 ：  8解：先寫出其對偶問題。 對偶規(guī)劃問題的最優(yōu)解 原對偶規(guī)劃問題的最優(yōu)解  

33、;  9.  10解 11解（1）設(shè)分別表示甲、乙、丙各產(chǎn)品的數(shù)量，Z 表示總產(chǎn)值則： 化為標準形：C32100bCBXBX1X2X3X4X50X4121104000X521201500檢驗數(shù)32100 0X403/201-1/21503X111/2101/2250檢驗數(shù)01/2-20-3/22502X20102/3-1/31003X1101-1/32/3200檢驗數(shù)00-2-1/3-4/3-800此時，y1，y2分別表示出租A，B設(shè)備所得利潤，由（1）中的最優(yōu)表得=1/3，即如出租A設(shè)備可獲得1000/3元，而1000/3<350所以不合算。  12.解：（1）由影子價格的定義可得： （2）由（1）可知y1只與bi的值有關(guān)當(dāng)x1的系數(shù)由3變?yōu)閤的系數(shù)1/3時，yi的值并不發(fā)生變化； x1不可能在最優(yōu)基中出現(xiàn)， x也不可能在最優(yōu)基中出現(xiàn)（3）（4）不會。 13.解：1）解：先將問題化為標準式取初始正則基 B = （p4 p5） = I則原問題已化為關(guān)于基B 的典式，C23100BCBXBX1X2X3X4X50X4-3-23