运筹学(第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
运筹学(第3版) 习题答案 25
?a11x1?a12x2?a13x3?b1??a21x1?a22x2?a23x3?b2 ?x,x,x?0?123的最优单纯形表如表1－29所示，求原线性规划矩阵C、A、及b，最优基B及B．
Cj CB c1 c2 λj XB x1 x2 c1 x1 1 0 0 c2 x2 0 1 0 表1－29 c3 x3 4 －3 －1 c4 x4 1/6 0 －2 c5 x5 1/15 1/5 －3 b 6 2 ?1?11??615??6?2??1?1?1，得到B?(B)?,c4＝c5＝0， 【解】由B??????05??01??5???由公式?j?cj??ciaij得
i?16?c4??2?(c1,c2)????2?c1/6?0?c1?12
?0??115?c5??3?(12,c2)??0?c2?11 ??15??4?c3???1?(12,11)???14
??3??1由 A?BA
4??6?2??10?得 A?BA??????01??305??????1由 b?Bb
32??6?2??6??得 b?Bb?? ??????10??05??2??6?2?30
05??1?51.16思考与简答
（1）在例1.2中，如果设xj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化。
（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路。
（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化。
（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化。
(5)在单纯形法中，为什么说当?k?0并且aik?0(i?1,2,,m)时线性规划具有无界解。 (6)选择出基变量为什么要遵循最小比值规则，如果不遵循最小比值规则会是什么结果。 （7）简述大M法计算的基本思路，说明在什么情形下线性规划无可行解。 （8）设X(1)、X(2)、X(3)是线性规划的3个最优解，试说明
X??1X(1)??2X(2)??3X(3)(其中?1,?2,?3?0并且?1??2??3?1)
也是线性规划的最优解。