运筹学(第3版) 习题答案 29
maxw?4y1?2y2?7y3?y1?y2?2y3?12??4y1?5y2?3y3?20?y?0,j?1,2,3?j
容易看出原问题和对偶问题都有可行解，如X＝(2，1)、Y＝(1，0，1)，由定理2.4知都有最优解。
(2)对偶问题最优单纯形表为 C(j) Basis y3 y1 C(j)-Z(j) C(i) 7 4 4 y1 0 1 2 y2 -1/5 7/5 7 y3 1 0 0 y4 4/5 -3/5 0 y5 -1/5 R. H. S. 28/5 2/5 0 -11/5 0 -16/5 -1/5 4/5 w=42.4 对偶问题的最优解Y＝(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z＝42.4
1?1??4?4???5?55?5??1（3）CB=(7,4),B???, X?(7,4)???(16/5,1/5)
??32???32????55???55??(4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式
?x1?4x2?4 ?2x?3x?7?12得到原问题的最优解为X=(16/5，1/5)。
2.4证明下列线性规划问题无最优解
minZ?x1?2x2?2x3?2x1?x2?2x3?3 ?x?2x?3x?2?123?x,x?0,x无约束3?12证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为
maxw?3y1?2y2?2y1?y2?1?y?2y??2 ?12???2y1?3y2??2??y2?0,y1无约束由约束条件①②知y1≤0，由约束条件③当y2≥0知y1≥1，对偶问题无可行解，因此原问题
也无最优解(无界解)。
2.5已知线性规划
运筹学(第3版) 习题答案 30
maxZ?15x1?20x2?5x3?x1?5x2?x3?5?5x?6x?x?6 ?123??3x1?10x2?x3?7??x1?0,x2?0,x3无约束的最优解X?(,0,1419T)，求对偶问题的最优解． 4【解】其对偶问题是：
minw?5y1?6y2?7y3?y1?5y2?3y3?15?5y?6y?10y?20 ?123??y1?y2?y3?5??y1,y2,y3?0由原问题的最优解知，原问题约束③的松弛变量不等于零(xs3?0)，x1、x3不等于零，则对偶问题的约束①、约束③为等式，又由于xs3?0知y3＝0；解方程
?y1?5y2?15 ?y?y?5?12得到对偶问题的最优解Y=(5/2,5/2,0)；w＝55/2＝27.5
2.6用对偶单纯形法求解下列线性规划
（）1minZ?3x1?4x2?6x3?x1?2x2?3x3?10??2x1?2x2?x3?12?x,x,x?0?123
【解】将模型化为
minZ?3x1?4x2?6x3??x1?2x2?3x3?x4??10 ???2x1?2x2?x3?x5??12?x?0,j?1,2,3,4,5?j对偶单纯形表：
cj CB 0 0 XB X4 X5 C(j)-Z(j) 3 X1 －1 [－2] 3 4 X2 －2 －2 4 6 X3 －3 －1 6 0 X4 1 0 0 0 X5 0 1 0 b －10 －12 0 运筹学(第3版) 习题答案 31
0 3 X4 X1 C(j)-Z(j) 0 1 0 0 1 0 [－1] 1 1 1 0 0 －5/2 1/2 9/2 5/2 －2 2 1 0 0 －1 1 1 －1/2 －1/2 3/2 1/2 －1 1 －4 6 －18 4 2 －22 5 3 X2 X1 C(j)-Z(j) b列全为非负，最优解为x＝(2，4，0)；Z＝22
（2）
minZ?5x1?4x2?x1?x2?6??2x1?x2?2?x?0,x?02?1
【解】将模型化为
minZ?5x1?4x2??x1?x2?x3??6 ?2x?x?x?2?124?x?0,j?1,2,3,4?j XB X3 X4 Cj－Zj X1 X4 Cj－Zj X1 X2 Cj－Zj 3 4 3 0 CB 0 0 5 X1 [-1] 2 3 1 0 0 1 0 0 4 X2 -1 1 4 1 [-1] 1 0 1 0 0 X3 1 0 0 -1 2 3 1 -2 5 0 X4 0 1 0 0 1 0 1 -1 1 b -6 2 6 -10 -4 10 出基行系数全部非负，最小比值失效，原问题无可行解。
(3)minZ?2x1?4x2?2x1?3x2?24?x?2x?10?12??x1?3x2?18??x1,x2?0
【解】将模型化为
运筹学(第3版) 习题答案 32
minZ?2x1?4x2?2x1?3x2?x3?24??x?2x?x??10 ?124???x1?3x2?x5??18?xj?0,j?1,2,3,4,5? cj XB X3 X4 X5 Cj－Zj X3 X4 X2 Cj－Zj 0 0 4 CB 0 0 0 2 X1 2 -1 -1 2 1 -1/3 1/3 2/3 4 X2 3 -2 [-3] 4 0 0 1 0 0 X3 1 0 0 0 1 0 0 0 0 X4 0 1 0 0 0 1 0 0 0 X5 0 0 1 0 1 －2/3 －1/3 4/3 b 24 -10 -18 6 2 6 最优解X=(0，6)；Z＝24
（4）minZ?2x1?3x2?5x3?6x4?x1?2x2?3x3?x4?2???2x1?x2?x3?3x4??3?x?0,j?1,,4?j
【解】将模型化为
minZ?2x1?3x2?5x3?6x4??x1?2x2?3x3?x4?x5??2 ??2x?x?x?3x?x??3?12346?x?0,j?1,,6?jCj XB X5 X6 Cj－Zj X2 X6 Cj－Zj X2 X3 Cj－Zj X1 X3 2 5 3 5 3 0 CB 0 0 2 X1 -1 -2 2 1/2 -5/2 1/2 [-1] 1 0 1 0 3 X2 [-2] 1 3 1 0 0 1 0 0 -1 [1] 5 X3 -3 -1 5 3/2 [-5/2] 1/2 0 1 0 0 1 6 X4 -4 3 6 2 1 0 13/5 -2/5 1/5 -13/5 11/5 0 X5 1 0 0 -1/2 1/2 3/2 -1/5 -1/5 8/5 1/5 -2/5 0 X6 b -2 -3 1 -4 -7/5 8/5 0 1 0 0 1 0 3/5 -2/5 1/5 -3/5 1/5 7/5 1/5