運籌學課后習題答案[共124頁]

1、第一章線性規(guī)劃及單純形法1用 Xj（ j=1.2 5）分別代表 5 中飼料的采購數(shù),線性規(guī)劃模型：min z 0.2x 0.7x 0.4x 0.3x 0.8x1 2 3 4 5st.3x 2x x 6x +18x 7001 2 3 4 5x 0.5x 0.2x +2x x 301 2 3 4 50.5 x x 0.2x +2x 0.8x 1001 2 3 4 5x ( j 1,2,3,4,5,6) 0j2.解：設(shè)x1x2x3x4x5x6 x 表示在第 i 個時期初開始工作的護士人數(shù), z 表示所需的總 人數(shù),則minz x x x x x x1 2 3 4 5 6st.x x 601 6x x

2、1 270x x2 360x x3 450x x4 520x x5 630x (i 1,2.3.4.5.6) 0i3解：設(shè)用 i=1,2,3 分別表示商品 A,B,C,j=1,2,3 分別代表前,中,后艙, Xij 表示裝于 j艙的 i 種商品的數(shù)量, Z 表示總運費收入則：max z 1000(x x x ) 700(x x x ) 600(x x x )11 12 13 21 22 23 31 32 33st x x x. 60011 12 13x x x21 22 231000x x x31 32 3380010x 5x 7x 40011 21 3110x 5x 7x 540012 22

3、 3210x 5x 7x 150013 23 338 6 5 2000x x x11 21 318x 6x 5x 300012 22 328 6 5 1500x x x13 23 338 6 5x x x11 21 318x 6x 5x12 22 320.158x 6x 5x13 23 338x 6x 5x12 22 320.158x 6x 5x11 21 318x 6x 5x13 23 330.1x 0(i 1,2.3. j 1,2,3)ij5. （1）Z = 4（2）maxz x x1 2st. 6x 10x 1201 2x x1 2705 x 1013 x 82解：如圖：由圖可得：* (

4、10,6)T * 16 x ； Z即該問題具有唯一最優(yōu)解* (10,6)xT（3）無可行解(4)max z 5x 6x1 2st. 2x x 21 22x 3x 21 2x , x 01 2如圖：由圖知,該問題具有無界解。6（1） max z 3x 4x 2x 5x 5x 0x 0x1 2 3 4 4 5 6 st.-2x x 2x x x 21 2 3 4 4 x x x 2x 2x +x 141 2 3 4 4 5 -2x 3x x x x - x 61 2 3 4 4 6 x,x,x,x ,x ,x ,x 01 2 3 4 4 5 6（2） max z 2x 2x 3x 3x 0x1 2

5、 3 3 4 st. x x x x 4 1 2 3 3 2x x x x +x 61 2 3 3 4 x,x,x ,x ,x 01 2 3 3 412 3 6 3 0 08 1 0 2 0 （p p p p p p 4 ) 1 2 3 4 5 63 0 0 0 0 171）系數(shù)矩陣 A ：3C620種組合1 2 3 6B P P P 8 1 4 5 4 0 B ； 可組成基。 1 1 2 3 13 0 0求B的基本解,112 3 6 9 1 0 0 08 1 4 10 0 1 0 16/33 0 0 0 0 0 1 -7/6（B,b）= T y1=（0,16/3,-7/6,0,0,0） T

6、T同理 y2=（0,10,0,-7,0,0） y3=（0, 3,0,0,7/2,0） T y5=（0,0,-5/2,8,0,0）Ty4=（7/4,-4,0,0,0,21/4）T Ty6=（0,0,3/2,0,8,0） y7=（1,0,-1/2,0,0, 3） T y9=（ 5/4,0,0, -2,0,15/4）Ty8=（0,0,0, 3,5,0） T y11=（0, 0,-5/2,8,0, 0）Ty10=（0, 3,-7/6,0,0,0） T y13=（4/3,0,0,0,2,3/4）Ty12=（0,0,-5/2,3,5, 0） T y15=（0, 3,0,0,7/3,0）Ty14=（0,10

7、,0,-7, 0,0）Ty16=（0,0,3/2,0, 8,0）基可行解：（每個 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）該線性問題最多有2C4 6 個基本解?；窘?Z 基本可行解 最優(yōu)解1 X1 X2 X3 X42 -4 11/2 0 0 3 2/5 0 11/5 03 -1/3 0 0 11/64 0 1/2 2 0 5 0 -1/2 0 26 0 0 1 1 1 0 6B 2 1 3 5 03 1

8、48.基的定義X1 X 2 X3 所對應(yīng)的列向量可以組成基1 0 62 1 33 1 4B 由 X 1 X2 X3 列向量組成 =3 54 12 0N 由 非基變量對應(yīng)的向量組成 =1 0 6 1 0 0 -13/52 1 3 0 1 037/53 1 4 0 0 1 3/5（B,b）=B對應(yīng)的基解： （-13/5 ,37/5 ,0,0,3/5 ）9解：（1）由圖知：* (1,3/ 2)T * 35/ 2; x ；Z單純形法：化為標準形如下：max z 10x 5x1 2st.3x 4x x 91 2 35x 2x x 81 2 4x (i 1,2,3, 4) 0iC 10 5 0 0 bCB

9、 XB X1 X2 X3 XR0 X3 3 4 1 0 90 XR 5 2 0 1 8 檢驗數(shù) 10 5 0 0 00 X3 0 14/5 1 -3/5 21/510 X1 1 2/5 0 -1/5 8/5檢驗數(shù) 0 1 0 -2 -165 X2 0 1 5/14 -3/14 3/210 X1 1 0 -1/7 3/7 0檢驗數(shù) 0 0 -5/14 -25/14 -35/2所以：* (1,3/ 2)T * 35/ 2;x ；Z其中：T對應(yīng)（0,0,9,8)A(0,0)T對應(yīng)（8/5,0,21/5,0)B(8 / 5,0)T對應(yīng)（1,3/2,0,0)C (1,3/ 2)9.2 ）A 點最大 Z=

10、 8max z 2x x 0x 0x1 2 3 4st.3x 5x x 151 2 36 x 2x x 24 1 2 4化為標準形：x (i 1,2,3, 4) 0iC 2 -1 0 0 bCB X B X1 X2 X 3 X 40 X 3 3 5 1 0 150 點（0,0,15,24） 0 X 4 6 2 0 1 24檢驗數(shù) 2 -1 0 0 0A 點（ 4,0,3,0） X 3 0 4 1 -1/2 3Zmax=8 X 1 1 1/3 0 1/6 4檢驗數(shù) 0 -1 0 -1/3 -810.解 1）要使 A（0,0）成為最優(yōu)解則需 C 0 且 d 0；2）要使 B（8/5,0）成為最優(yōu)解

11、則C 0 且d=0 或C0 且 d0；3）要使 C（1,3/2）成為最優(yōu)解則-5/2 -C/d -3/4 且 Cd0；即 5/2 C/d 3/4 且 Cd0；4）要使 D（0,9/4）成為最優(yōu)解則 C0 或 C=0,d011.(1)化為標準型：m axz x2 x x1 2 3st.3x x x x 601 2 3 4x x 2x x 1 01 2 3 5 x x x x1 2 3 620x (i 1,2,3, 4,5,6) 0jC 2 -1 1 0 0 0 bCB XB X1 X2 X3 X4 X5 X60 X4 3 1 1 1 0 0 600 X5 1 -1 2 0 1 0 100 X6

12、1 1 -1 0 0 1 20檢驗數(shù) 2 -1 1 0 0 0 00 X4 0 4 -5 1 -3 0 302 X1 1 -1 2 0 1 0 100 X6 0 2 -3 0 -1 1 10檢驗數(shù) 0 1 -3 0 -2 0 -200 X4 0 0 1 1 -1 -2 102 X1 1 0 1/2 0 1/2 1/2 15-1 X2 0 1 -3/2 0 -1/2 1/2 5檢驗數(shù) 0 0 -3/2 0 -3/2 -1/2 -25* ( , )T * ; x 15 5,0 ；Z 25（2）max z 2x 3x 5x 0x 0x 0x 0x1 2 3 4 5 6 7stx x x x . 2

13、2 3 121 2 3 4x 2x 2x x 81 2 3 54x 6x x 161 3 6 4x 3x x 122 3 7x (i 1,2,3.7) 0iC 2 3 5 0 0 0 0 bCB X B X1 X2 X 3 X 4 X 5 X6 X 70 X 4 2 2 3 1 0 0 0 120 X 5 1 2 2 0 1 0 0 80 X 6 4 0 6 0 0 1 0 160 X 7 0 4 3 0 0 0 1 12檢驗數(shù) 2 3 5 0 0 0 0 00 X 4 0 2 0 1 0 -1/2 0 40 X 5 -1/3 2 0 0 1 -1/3 0 3/85 X 3 2/3 0 1 0

14、 0 1/6 0 3/80 X 7 -2 4 0 0 0 -1/2 1 4檢驗數(shù) -4/3 3 0 0 0 -5/6 0 -40/30 X 4 1 0 0 1 0 -1/4 -1/2 20 X 5 2/3 0 0 0 1 -1/12 -1/2 2/35 X 3 2/3 0 1 0 0 1/6 0 8/33 X 2 -1/2 1 0 0 0 -1/8 1/4 1檢驗數(shù) 1/6 0 0 0 0 -11/24 -3/4 -49/30 X 4 0 0 0 1 -2/3 -1/8 1/4 12 X 1 1 0 0 0 2/3 -1/8 -3/4 15 X 3 0 0 1 0 -1 1/4 1/2 23

15、X 2 0 1 0 0 3/4 -3/16 -1/8 3/2檢驗數(shù) 0 0 0 0 -1/4 -7/16 -5/8 -33/2* (1,3/ 2 )T * 33/ 2; x ,1,1,0,0 ；Z（3）標準型：max z 3x 5x1 23st. x x 4 1 3 2x x 122 43x 2x x 181 2 5x (i 1,2,3, 4,5,) 0iC 3 5 0 0 0 bCB XB X1 X2 X3 X4 X50 X3 1 0 1 0 0 40 X4 0 2 0 1 0 120 X5 3 2 0 0 1 18檢驗數(shù) 3 5 0 0 0 0X3 1 0 1 0 0 4X2 0 1 0

16、1/2 0 6X5 3 0 0 -1 1 6檢驗數(shù) 3 0 0 -5/2 0 -30X3 0 0 1 1/3 -1/3 2X2 0 1 0 1/2 0 6X1 1 0 0 -1/3 1/3 2檢驗數(shù) 0 0 0 -3/2 -1 -36* ( )T * ; x 2,6 ；Z 36（4）標準型 max z x x x x x x x x x x Mx Mx 0x1 2 3 4 4 5 5 6 6 7 8 9 10 stx x x x x x . 91 4 4 6 6 7 3 4 2 2 2x x x x x x1 2 3 6 6 8 x 2x x x 2x 2x x 61 3 5 5 6 6 9

17、4x 3x x 122 3 10 x,x,x,x ,x ,x ,x5,x6,x 6,x7,x8,x9,x10 0 1 2 3 4 4 5C -1 1 -1 -1 1 -1 1 -1 1 -M -M -M 0 bCB XB X 1 X2 X3 X4“X4X 5“X 5X 6“X 6X7 X 8 X 9 X10-M X7 1 0 0 1 -1 0 0 1 -1 1 0 0 0 9-M X8 3 1 -4 0 0 0 0 2 -2 0 1 0 0 2-M X9 1 . 2 0 0 -1 1 2 -2 0 0 1 0 60 X10 0 4 3 0 0 0 0 0 0 0 0 0 1 12檢驗數(shù) 5M-

18、1 M+1 -1-2M M-1 1-M M+1 1+M 5M-1 1-5M 0 0 0 0 17M-M X7 0 -1/3 4/3 1 -1 0 0 1/3 -1/3 1 -1/3 0 0 28/3-1 X1 1 1/3 -4/3 0 0 0 0 2/3 -2/3 0 1/3 0 0 2/3-M X9 0 -1/3 10/3 0 0 -1 1 4/3 -4/3 0 -1/3 1 0 16/30 X10 0 4 3 0 0 0 0 0 0 0 0 0 1 12檢驗數(shù) 0 4/314/5M M-1 1-M M-1 M+1 5/3M -5/3M 0 -5/3M 0 0 -41/3M-2/3M -7/

19、3 -1/3 +1/3 +1/3 -2/3-M X7 0 -1/5 0 1 -1 2/5 -2/5 -1/5 1/5 1 -1/5 -2/5 0 31/5-1 X1 1 1/5 0 0 0 -2/5 2/5 6/5 -6/5 0 1/5 2/5 0 14/5-1 X3 0 -1/10 1 0 0 -3/10 3/10 2/5 -2/5 0 -1/10 3/10 0 8/50 X10 0 43/10 0 0 0 9/10 -9/10 -6/5 6/5 0 3/10 -9/10 1 36/5檢驗數(shù) 0 -1/5M0 M-1 1-M 2/5M -2/5M 3/5 1/5M 0 -6/5M -7/5M

20、 0 -31M/5+11/10 -17/10 +17/10 -1/5M -3/5 -22/5（5）max z 6x 2x 10x 8x1 2 3 4st. 5x 6x 4x 4x 20 1 2 3 45x 3x 2x 8x 251 2 3 44x 2x x 3x 101 2 3 4x ( j 1,2,3, 4) 0j解：標準化：max z 6x 2x 10x 8x1 2 3 4st. 5x 6x 4x 4x x 20 1 2 3 4 55x 3x 2x 8x x 251 2 3 4 64x 2x x 3x x 101 2 3 4 7x ( j 1,2,3,4,5,6,7) 0jC 6 2 10

21、 8 0 0 0 bCB XB X1 X2 X3 X4 X5 X6 X70 X5 5 6 -4 -4 1 0 0 200 X6 3 -3 2 8 0 1 0 250 X7 4 -2 1 3 0 0 1 10檢驗數(shù) 6 2 10 8 0 0 0 00 X5 21 -2 0 8 1 1 4 600 X6 -5 1 0 2 0 0 -2 510 X3 4 -2 1 3 0 0 1 10檢驗數(shù) -34 22 0 -22 0 0 -10 -1000 X5 11 0 0 12 1 2 0 702 X2 -5 1 0 2 0 1 -2 510 X3 -6 0 1 7 0 2 -3 20檢驗數(shù) 76 0 0

22、-66 0 -22 34 -2107 且pk 0 因此問題的解無界。 由表可得,（6）化為 :標準形： Z=-Zmaxz xx x x1 2 3st.x 4x - 2x 51 4 6 x 2x 3x +x 32 4 5 6 x 2x - x 6x 53 4 5 6x (i 1,2,3, 4,5,6) 0i（I）C -x -1 -1 0 0 0 bCB X B X1 X2 X3 X 4 X5 X 6-X X 1 1 0 0 -4 0 -2 5-1 X 2 0 1 0 2 -3 1 3-1 X 3 0 0 1 2 -5 6 5檢驗數(shù) 0 0 0 4-4x -8 7-2x 5x+84 4x 0 x

23、17 2x 0 x 7/ 24 4 7 2 2/3x x x 如圖：T 1. 1. X 7/2時,檢驗數(shù) 0 ,最優(yōu)解：（5,3,5,0,0）2. 2. 1 X7/2時,4-4X0由（ I ）得：C -x -1 -1 0 0 0 bCB X B X1 X2 X3 X4 X5 X 6-X X 1 1 0 1/3 -10/3 -5/3 0 20/3-1 X 2 0 1 -1/6 5/3 -13/6 0 13/60 X 6 0 0 1/6 1/3 -5/6 1 5/6檢驗數(shù) 0 0 X/3-7/6 -10X/3+5/3 -5X/3-13/6 0 20X/3+13/6* (20 / 313/ 6 0 0 0 5/ 6)T * 20 /3 13/ 6; x , , ； Z X3. X -2X+70C -x -1 -1 0 0 0 bCB X B X1 X2 X3 X4 X5 X 6-X X 1 1 2 0 0 -6 0 11-1 X 2 0 1/2 0 1 -3/2 1/2 3/2-1 X 3 0 -1 1 0 -2 5 2檢驗數(shù) 0 2x-2 0 0 -6X-2 5 11X+2檢驗數(shù) 0,列系數(shù) 0,所以解無界。4.-3/2 X4-4X0C -x -1 -1 0 0 0 bCB X B X1