管理运筹学课后答案.doc

1、 第一章 线性规划及单纯形法 1用 Xj（ j=1.25 ）分别代表 5 中饲料的采购数，线性规划模型： 1 2 3 4 51 2 3 41 2 3 41 2 3 4m in 0 .2 0 .7 0 .4 0 .3 0 .8. 3 2 6 7 0 00 .5 0 .2 3 00 .2 0 .8 1 0 0( 1 , 2 , 3 , 4 , 5 , 6 ) 0jz x x x x xst x x x x xx x x x xx x x x xxj 555+18 +2 0 . 5 + 2 2.解：设 1 2 3 4 5 6x x x x x x x表示在第 i 个时期初开始工作的护士人数， z表示

2、所需的总人数，则 1 2 3 4 5 6161223344556m in. 6 07060502030( 1 , 2 .3 .4 .5 .6 ) 0iz x x x x x xst x xxxxxxxxxxxxi 3解：设用 i=1， 2， 3 分别表示商品 A， B， C， j=1， 2， 3 分别代表前，中，后舱， Xij 表示装于 j 舱的 i种商品的数量， Z 表示总运费收入则： 11 12 13 21 22 23 31 32 3311 12 1321 22 2331 32 3311 21 3112 22 3213 23 3311 21 31m a x 1 0 0 0 ( ) 7 0

3、0 ( ) 6 0 0 ( ). 6 0 010008001 0 5 7 4 0 01 0 5 7 5 4 0 01 0 5 7 1 5 0 08 6 5 2 0 0 0z x x x x x x x x xst x x xx x xx x xx x xx x xx x xx x x 12 22 3213 23 3311 21 3112 22 3213 23 3312 22 3211 21 3113 23 338 6 5 3 0 0 08 6 5 1 5 0 08 6 50 .1 58 6 58 6 50 .1 58 6 58 6 50 .18 6 50 ( 1 , 2 .3 . 1 , 2

4、, 3 )ijx x xx x xx x xx x xx x xx x xx x xx x xx i j 5.（ 1） Z = 4 （ 2） 12121212m a x. 6 1 0 1 2 0705 1 038z x xst x xxxxx解：如图：由图可得： *(1 0 , 6 ) 1 6TxZ ； 即该问题具有唯一最优解 * (10,6)Tx （ 3） 无可行解 (4) 12121212m ax 5 6. 2 22 3 2,0z x xst x xxxxx 如图： 由图知，该问题具有无界 解。 6（ 1） “1 2 3 4 4 5 6“1 2 3 4 4“1 2 3 4 4 5“1 2

5、3 4 4 6 “ 1 2 3 4 4 5 6m a x 3 4 2 5 5 0 0. 2 22 2 1436z x x x x x x xst x x x x xx x x x x xx x x x x xx x x x x x x -2 + -2 - ， ， ， ， ， ， 0 （ 2） “1 2 3 3 4 “1 2 3 3 “1 2 3 3 4“1 2 3 3 4m a x 2 2 3 3 0.46z x x x x xst x x x xx x x x xx x x x x 2+ ， ， ， ， 0 7 1）系数矩阵 A：364)120C1 2 3 4 5 61 2 3 6 3 0

6、08 1 0 2 0 （ p p p p p p30000种 组 合 1 1 2 3 11 2 3 68 1 4 5 4 03 0 0B P P P B 1； 可 构 成 基 。求 B 的 基 本 解 ，（ B， b） =040 1 2 3 6 9 1 0 08 1 1 0 0 1 1 6 / 33 0 0 0 0 0 1 - 7 / 6 y1=（ 0， 16/3， -7/6， 0， 0， 0） T 同理 y2=（ 0， 10， 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，

7、 -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=（

8、0， 0， 3/2， 0， 8， 0）T 基可行解：（每个 x 值都大于 0），（ y3， y6， y8， y12， y13， y15， y16） 最优解：（ y3， y6， y15， y16） Zmax=3 p2 p3 p4， p2 p3 p5， p3 p4 p5， p2 p4 p5为奇异，只有 16 个基。 解：（ 2）该线性问题最多有 24 6C 个基本解。 基本解 Z 基本可行解 最优解 1 X1 X2 X3 X4 2 -4 11/2 0 0 3 2/5 0 11/5 0 3 -1/3 0 0 11/6 4 0 1/2 2 0 5 0 -1/2 0 2 6 0 0 1 1 8.基的定义

9、 1 0 62 1 3 5 03 1 4B X1 X2 X3所对应的列向量可以构成基 B 由 X1 X2 X3 列向量构成 = 1 0 62 1 33 1 4 N 由 非基变量对应的向量构成 = 354120 （ B， b） = 1 0 6 1 02 1 3 13 1 4 0 - 1 3 / 5 00 37/5 0 0 1 3 / 5 B 对应的基解：（ -13/5， 37/5， 0， 0， 3/5） 9解：（ 1） 由图知： *(1 , 3 / 2 ) 3 5 / 2 ;TxZ； 单纯形法：化为标准形如下： 121 2 31 2 4m a x 1 0 5. 3 4 95 2 8( 1, 2

10、, 3 , 4 ) 0iz x xst x x xx x xxi C 10 5 0 0 b CB XB X1 X2 X3 XR 0 X3 3 4 1 0 9 0 XR 5 2 0 1 8 检验数 10 5 0 0 0 0 X3 0 14/5 1 -3/5 21/5 10 X1 1 2/5 0 -1/5 8/5 检验数 0 1 0 -2 -16 5 X2 0 1 5/14 -3/14 3/2 10 X1 1 0 -1/7 3/7 0 检验数 0 0 -5/14 -25/14 -35/2 所以： *(1 , 3 / 2 ) 3 5 / 2 ;TxZ； 其中： ( 0 , 0 )( 8 / 5 ,

11、0 )(1 , 3 / 2 )ABC对 应T对 应T对 应T（ 0,0,9,8)（ 8/5,0,21/5,0)（ 1,3/2,0,0) 9.2） A 点最大 Z= 8 化为标准形：1 2 3 41 2 312m a x 2 0 0. 3 5 1 52 2 4( 1 , 2 , 3 , 4 ) 0iz x x x xst x x xx x xxi 46 0 点（ 0， 0， 15， 24） A 点（ 4， 0， 3， 0） Zmax=8 10.解 1）要使 A（ 0， 0）成为最优解则需 C 0且 d 0； 2）要使 B（ 8/5， 0）成为最优解则 C 0 且 d=0 或 C0 且 d0； 3

12、）要使 C（ 1， 3/2）成为最优解则 -5/2 -C/d -3/4 且 Cd0；即 5/2 C/d 3/4 且 Cd0； 4）要使 D（ 0， 9/4）成为最优解则 C0 或 C=0， d0 11.(1)化为标准型： 1 2 31 2 3 41 2 31 2 3m a x 2. 3 602 1020( 1 , 2 , 3 , 4 , 5 , 6) 0jz x x xst x x x xx x x xx x x xxi 56C 2 -1 1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 0 X4 3 1 1 1 0 0 60 0 X5 1 -1 2 0 1 0 10 0 X

13、6 1 1 -1 0 0 1 20 检验数 2 -1 1 0 0 0 0 0 X4 0 4 -5 1 -3 0 30 2 X1 1 -1 2 0 1 0 10 0 X6 0 2 -3 0 -1 1 10 检验数 0 1 -3 0 -2 0 -20 0 X4 0 0 1 1 -1 -2 10 2 X1 1 0 1/2 0 1/2 1/2 15 -1 X2 0 1 -3/2 0 -1/2 1/2 5 检验数 0 0 -3/2 0 -3/2 -1/2 -25 *( , ) ;TxZ15 5， 0 ； 25 C 2 -1 0 0 b CB XB X1 X2 X3 X4 0 X3 3 5 1 0 15

14、0 X4 6 2 0 1 24 检验数 2 -1 0 0 0 X3 0 4 1 -1/2 3 X1 1 1/3 0 1/6 4 检验数 0 -1 0 -1/3 -8 （ 2） 1 2 3 4 5 6 71 2 3 41 2 31323m a x 2 3 5. 2 2 3 1 22 2 86 1 64 3 1 2( 1 , 2 , 3 . 7 ) 0iz x x x x x x xst x x x xx x x xx x xx x xxi 5670 0 0 04 C 2 3 5 0 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X4 2 2 3 1 0 0 0 12

15、0 X5 1 2 2 0 1 0 0 8 0 X6 4 0 6 0 0 1 0 16 0 X7 0 4 3 0 0 0 1 12 检验数 2 3 5 0 0 0 0 0 0 X4 0 2 0 1 0 -1/2 0 4 0 X5 -1/3 2 0 0 1 -1/3 0 3/8 5 X3 2/3 0 1 0 0 1/6 0 3/8 0 X7 -2 4 0 0 0 -1/2 1 4 检验数 -4/3 3 0 0 0 -5/6 0 -40/3 0 X4 1 0 0 1 0 -1/4 -1/2 2 0 X5 2/3 0 0 0 1 -1/12 -1/2 2/3 5 X3 2/3 0 1 0 0 1/6

16、0 8/3 3 X2 -1/2 1 0 0 0 -1/8 1/4 1 检验数 1/6 0 0 0 0 -11/24 -3/4 -49/3 0 X4 0 0 0 1 -2/3 -1/8 1/4 1 2 X1 1 0 0 0 2/3 -1/8 -3/4 1 5 X3 0 0 1 0 -1 1/4 1/2 2 3 X2 0 1 0 0 3/4 -3/16 -1/8 3/2 检验数 0 0 0 0 -1/4 -7/16 -5/8 -33/2 *( 1 , 3 / 2 ) 3 3 / 2 ;TxZ， 1 ， 1 ， 0 ， 0 ； （ 3）标准型： 1 2 313212m a x 3 5.42 122

17、18( 1, 2 , 3 , 4 , 5 , ) 0iz x xst x xxxx x xxi 453 C 3 5 0 0 0 b CB XB X1 X2 X3 X4 X5 0 X3 1 0 1 0 0 4 0 X4 0 2 0 1 0 12 0 X5 3 2 0 0 1 18 检验数 3 5 0 0 0 0 X3 1 0 1 0 0 4 X2 0 1 0 1/2 0 6 X5 3 0 0 -1 1 6 检验数 3 0 0 -5/2 0 -30 X3 0 0 1 1/3 -1/3 2 X2 0 1 0 1/2 0 6 X1 1 0 0 -1/3 1/3 2 检验数 0 0 0 -3/2 -1

18、-36 *( ) ;TxZ2， 6 ； 36 （ 4）标准型 “ “ “1 2 3 4 4 5 5 6 6 7 8 9 1 0 “ “1 4 4 6 6 7“1 2 3 6 6 8 “ “1 3 5 5 6 6 92 3 1 0 “ 1 2 3 4 4 5m a x 0.93 4 2 2 22 2 2 64 3 1 2z x x x x x x x x x x M x M x xs t x x x x x xx x x x x xx x x x x x xx x xx x x x x x x ， ， ， ， ， ， “ “5 6 6 7 8 9 1 0x x x x x x ， ， ， ， ，

19、 ， 0 C -1 1 -1 -1 1 -1 1 -1 1 -M -M -M 0 b CB XB X1 X2 X3 X4 X4“ X5 X5“ X6 X6“ X7 X8 X9 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 6 0 X10 0 4 3 0 0 0 0 0 0 0 0 0 1 12 检验数 5M-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

20、-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/3 0 X10 0 4 3 0 0 0 0 0 0 0 0 0 1 12 检验数 0 4/3 -2/3M 14/5M -7/3 M-1 1-M M-1 M+1 5/3M -1/3 -5/3M +1/3 0 -5/3M +1/3 0 0 -41/3M -2/3 -M X7 0 -1/5 0 1 -1 2/5 -2/5

21、-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/5 0 X10 0 43/10 0 0 0 9/10 -9/10 -6/5 6/5 0 3/10 -9/10 1 36/5 检验数 0 -1/5M +11/10 0 M-1 1-M 2/5M -17/10 -2/5M +17/10 3/5 -1/5M 1/5M -3/5 0 -6/5M -7/5M 0 -31M/5 -22

22、/5 （ 5） 1 2 3 41 2 3 41 2 31 2 3m a x 6 2 10 8. 5 6 4 4 203 2 8 252 3 10( 1 , 2 , 3 , 4) 0jz x x x xst x x x xx x x xx x x xxj 445 4 解：标准化： 1 2 3 41 2 3 4 51 2 3 61 2 3 7m a x 6 2 10 8. 5 6 4 4 203 2 8 252 3 10( 1 , 2 , 3 , 4 , 5 , 6 , 7 ) 0jz x x x xst x x x x xx x x x xx x x x xxj 445 4 C 6 2 10 8

23、 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 X7 0 X5 5 6 -4 -4 1 0 0 20 0 X6 3 -3 2 8 0 1 0 25 0 X7 4 -2 1 3 0 0 1 10 检验数 6 2 10 8 0 0 0 0 0 X5 21 -2 0 8 1 1 4 60 0 X6 -5 1 0 2 0 0 -2 5 10 X3 4 -2 1 3 0 0 1 10 检验数 -34 22 0 -22 0 0 -10 -100 0 X5 11 0 0 12 1 2 0 70 2 X2 -5 1 0 2 0 1 -2 5 10 X3 -6 0 1 7 0 2 -3 20

24、检验数 76 0 0 -66 0 -22 34 -210 由表可得， 7 0kp 且 因此问题的解无界。 （ 6）化为 :标准形： Z =-Z 1 2 31 4 62 4 634m a x. 4 2 52 3 32 6 5( 1 , 2 , 3 , 4 , 5 , 6) 0iz x x x xst x x xx x x xx x x xxi 556- + - （ I） C -x -1 -1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 -X X1 1 0 0 -4 0 -2 5 -1 X2 0 1 0 2 -3 1 3 -1 X3 0 0 1 2 -5 6 5 检验数 0 0

25、 0 4-4x -8 7-2x 5x+8 4 4 0 17 2 0 7 / 24 4 7 2 2 / 3xxx x x 如图： 1. 1. X 7/2 时，检验数 0 ，最优解：（ 5， 3， 5， 0， 0） T 2. 2. 1 X0 由（ I）得： C -x -1 -1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 -X X1 1 0 1/3 -10/3 -5/3 0 20/3 -1 X2 0 1 -1/6 5/3 -13/6 0 13/6 0 X6 0 0 1/6 1/3 -5/6 1 5/6 检验数 0 0 X/3-7/6 -10X/3+5/3 -5X/3-13/6

26、0 20X/3+13/6 *( 2 0 / 3 1 3 / 6 0 0 0 5 / 6 ) 2 0 / 3 1 3 / 6 ;Tx Z X ， ， ， ， ， ； 3. X -2X+70 C -x -1 -1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 -X X1 1 2 0 0 -6 0 11 -1 X2 0 1/2 0 1 -3/2 1/2 3/2 -1 X3 0 -1 1 0 -2 5 2 检验数 0 2x-2 0 0 -6X-2 5 11X+2 检验数 0，列系数 0，所以解无界。 4.-3/2 X4-4X0 C -x -1 -1 0 0 0 b CB XB X1 X2 X3 X4 X5 X6 -X X1 1 0 0 -10/3 -5/3 0 20/3 -1 X2 0 1 0 5/3 -13/6 0 13/6 -1 X6 0 0 1 1/3 -5/6 1 5/6 检验数 X/3-7/6 -10X/3+5/3 -5X/3-13/6 20X/3+13/6 判断检验数的符号：