运筹学(第3版) 习题答案 21
X6 1 0 -1/5 -2/5 0 0 -1 1 1 0 7/5 C(j)-Z(j) 0 1/5 2/5 因为X6>0,原问题无可行解。图解法如下：
maxZ?4x1?2x2?5x3?6x1?x2?4x3?10? (4) ?3x1?3x2?5x3?8??x1?2x2?x3?20?xj?0,j?1,2,3?
【解】大M法。X7是人工变量，数学模型为
maxZ?4x1?2x2?5x3?Mx7?6x1?x2?4x3?x4?10?3x?3x?5x?x?8 ?1235??x1?2x2?2x3?x6?x7?20?xj?0,j?1,2,,7?Cj CB 0 0 －M XB X4 X5 X7 4 X1 2 X2 5 X3 0 X4 0 X5 0 X6 －M R.H.S. X7 Ratio 10 6 3 1 4 M -1 -3 [2] 2 2M 4 -5 1 5 M 1 C(j)-Z(j) * Big M 1 －1 1 －1 10 8 20 运筹学(第3版) 习题答案
X4 13/2 X5 X2 22
0 0 2 9/2 1/2 3 C(j)-Z(j) * Big M 5 0 2 X3 13/9 X5 86/9 X2 -2/9 -25/9 C(j)-Z(j) * Big M 1 1 [9/2] -7/2 1/2 4 1 1 2/9 7/9 -1/9 -8/9 1 1 -1/2 -3/2 -1/2 1 1/2 3/2 1/2 -1 -1 1/9 4/9 -1 20 38 10 -1/9 -4/9 40/9 70/9 -17/9 17/9 482/9 13/9 -13/9 无界解。 两阶段法。第一阶段：
minZ?x7?6x1?x2?4x3?x4?10?3x?3x?5x?x?8 ?1235??x1?2x2?x3?x6?x7?20?xj?0,j?1,2,,7?Cj CB 0 0 1 XB X4 X5 X7 X1 X2 X3 0 X4 0 X5 0 X6 1 X7 R.H.S. Ratio 10 6 3 1 －1 13/2 9/2 1/2 -1 -3 [2] 4 -5 1 [9/2] -7/2 1/2 1 C(j)-Z(j) 0 0 2 X4 X5 X2 －2 －1 C(j)-Z(j) 1 1 1 1 －1 1 -1/2 -3/2 -1/2 1 1/2 3/2 1/2 1 10 8 20 20 38 10 第二阶段： Cj CB 0 0 1 XB X4 X5 X2 4 X1 2 X2 5 X3 0 X4 0 X5 0 X6 R.H.S. Ratio 13/2 9/2 1/2 C(j)-Z(j) 0 0 2 X3 X5 X2 C(j)-Z(j) 7/2 13/9 86/9 -2/9 -3 1 1 [9/2] -7/2 1/2 1 9/2 1 2/9 7/9 -1/9 -1 1 1 -1/2 -3/2 -1/2 20 38 10 1/2 -1/9 40/9 -17/9 482/9 -4/9 70/9 1 原问题无界解。
运筹学(第3版) 习题答案 23
?21?1.12 在第1.9题中，对于基B???,求所有变量的检验数?j(j?1,?,4),并判断B是不
40??是最优基．
1??0?4??1【解】B??4,B???,
1?1????2????C?CBB?1A1??0???2210?4?(5,2,0,0)?(5,0)????
14?201??1?????2??5595?(5,2,0,0)?(5,?,0,)?(0,,0,?)2424??(0,,0,?), B不是最优基，可以证明B是可行基。
1.13已知线性规划
9254maxz?5x1?8x2?7x3?4x4?2x1?3x2?3x3?2x4?20 ?3x?5x?4x?2x?30?1234?x?0,j?1,,4?j?23?的最优基为B???，试用矩阵公式求（1）最优解；(2)单纯形乘子；
25??(3)N1及N3；(4)?1和?3。
【解】
?5?4B?1????1??23???4?,CB?(c4,c2)?(4,8,),则 1?2??T?1(1)XB?(x4,x2)?Bb?(,5),最优解X?(0,5,0,),Z?50 (2)??CBB(3)
?152T52T?(1,1)
运筹学(第3版) 习题答案 24
3??5?1???44??2??4??1N1?BP??????1??11????3??1????22???2??
3??5?3???4??3??4?4?1N3?BP3??????????11??4??1????22???2??(4)
?1??4??1?c1?CBN1?5?(4,8)???5?5?0?1???2??
?3??4??3?c3?CBN3?7?(4,8)???7?7?0?1???2??注：该题有多重解：
X(1)=(0，5，0，5/2)
X(2)=(0，10/3，10/3，0)
X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解 Z＝50
1.14 已知某线性规划的单纯形表1－28, 求价值系数向量C及目标函数值Z．
表1－28 Cj CB 3 4 0 λj 【解】由?j?cj?ic1 XB x4 x1 x6 x1 0 1 0 0 c2 x2 1 0 －1 －1 c3 x3 2 －1 4 －1 c4 x4 1 0 0 0 iijc5 x5 －3 2 －4 1 c6 x6 0 0 1 0 c7 x7 2 －1 2 －2 b 4 0 3/2 ?caiij有cj??j??cai
c2＝－1＋（3×1＋4×0＋0×（－1））＝2 c3＝－1＋（3×2＋4×（－1）＋0×4）＝1 c5＝1＋（3×（－3）＋4×2＋0×（－4））＝0 c7＝-2＋（3×2＋4×(－1)＋0×2）＝0 则C＝(4,2,1,3,0,0,0,)，Z=CBXB=12
1.15 已知线性规划
maxZ?c1x1?c2x2?c3x3