解：写出原问题的对偶问题得
?maxZ'?4y1?6y2?y1?y2??2??y1?y2??1?y1?ky2?2?y无约束，y2?0
?1 由互补松弛定理：x1?ys1?0得ys1?0,?y1?y2??2 ① x3?ys3?0 得ys3?0,?y1?ky2??2 ②
①②联立得
y1*?6?2k?4,y2*?1?k1?k
而Z*??12?Z'*,将y1*,y2*代入③
?4y1*?6y2*??12 ③ 则k??3,y1*??6,y2*?2 综上，k??3，对偶问题最优解为Y*?(y1,y2)?(?6,2)
TT
10. 考虑线性规划
minZ?12x1?20x2?x1?4x2?4?x?5x?2?12??2x1?3x2?7??x1,x2?0 对偶问题由最优表如下：
C(j) 4 y1 0 1 2 y2 -1/5 7/5 7 y3 1 0 0 y4 4/5 -3/5 0 y5 -1/5 CB y3 7 y1 4 C(j)-Z(j) b 28/5 2/5 0 -11/5 0 -16/5 -1/5 4/5 w=42.4
(1)通过解对偶问题由最优表中观察出原问题的最优解； (2) 利用互补松弛条件求原问题的最优解． 【解】原问题的对偶问题为
maxw?4y1?2y2?7y3?y1?y2?2y3?12??4y1?5y2?3y3?20?y?0,j?1,2,3?j
(1)对偶问题最优单纯形表为
对偶问题的最优解Y＝(4/5,0,28/5)，原问题的最优解为X=(16/5，1/5)，Z＝42.4 （2）由y1、y3不等于零知原问题第一、三个约束是紧的，解等式
11
?x1?4x2?4 ?2x?3x?7?12得到原问题的最优解为X=(16/5，1/5)。
11. 已知线性规划问题
maxz?2x1?4x2?x3?x4?x4?8?x1?3x2?2x?x?6?12?x2?x3?x4?6??x?x?x?9?123??xj?0,j?1,...,4（1）写出其对偶问题；
*TX?(2,2,4,0), 试用对偶理论，直接求对偶问题的最优解。
（2）已知原问题的最优解为
。
解: (1)设对偶变量为
y1,y2,y3,y4,, 所求对偶规划为
minw=8y1?6y2?6y3?9y4?y1?2y2?y3?2?3y?y?y?y?4234?1?y?y?1?34?y?y?14?1?y?0,j?1,2,3,4 ?j*T
(2) 运用对偶理论，将最优解X?(2,2,4,0)代入原问题的约束条件，得
y1?2y2?y3?23y1?y2?y3?y4?4y4?0,，且有：y3?y4?1, 解方程可得
y1?4/5,y2?3/5,y3?1
TY*?(45,35,1,0). 即
12. 用对偶单纯形法求解下列线性规划
（1）minZ?3x1?4x2?5x3?x1?2x2?3x3?8??2x1?2x2?x3?10?x,x,x?0?123
【解】将模型化为
12
minZ?3x1?4x2?5x3??x1?2x2?3x3?x4??8 ???2x1?2x2?x3?x5??10?x?0,j?1,2,3,4,5?j对偶单纯形表： cj CB 0 0 XB X4 X5 C(j)-Z(j) 0 3 X4 X1 C(j)-Z(j) 5 3 X2 X1 C(j)-Z(j) 3 X1 －1 [－2] 3 0 1 0 0 1 0 4 X2 －2 －2 4 [－1] 1 1 1 0 0 5 X3 －3 －1 5 －5/2 1/2 7/2 5/2 －2 1 0 X4 1 0 0 1 0 0 －1 1 1 0 X5 0 1 0 －1/2 －1/2 3/2 1/2 －1 1 b －8 －10 0 －3 5 0 3 2 b列全为非负，最优解为x＝(2，3，0)；Z＝18
（2）
minZ?3x1?4x2?x1?x2?4??2x1?x2?2?x?0,x?02?1
【解】将模型化为
minZ?3x1?4x2??x1?x2?x3??4 ?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 3 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 -4 2 4 -6 -2 6 出基行系数全部非负，最小比值失效，原问题无可行解。
13
(3)minZ?2x1?4x2?2x1?3x2?24?x?2x?10?12??x1?3x2?15??x1,x2?0
【解】将模型化为
minZ?2x1?4x2?2x1?3x2?x3?24??x?2x?x??10 ?124???x1?3x2?x5??15?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 -15 9 0 5 最优解X=(0，5)；Z＝20
（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 ???2x1?x2?x3?3x4?x6??3?x?0,j?1,,6?jCj XB X5 X6 Cj－Zj X2 X6 Cj－Zj
2 CB 0 0 3 0 X1 -1 -2 2 1/2 -5/2 1/2 3 X2 [-2] 1 3 1 0 0 5 X3 -3 -1 5 3/2 [-5/2] 1/2 14
6 X4 -4 3 6 2 1 0 0 X5 1 0 0 -1/2 1/2 3/2 0 X6 b -2 -3 1 -4 0 1 0 0 1 0 X2 X3 Cj－Zj X1 X3 Cj－Zj X1 X2 Cj－Zj 3 5 2 5 2 3 [-1] 1 0 1 0 0 1 0 0 1 0 0 -1 [1] 0 0 1 0 0 1 0 0 1 0 1 1 0 13/5 -2/5 1/5 -13/5 11/5 1/5 -2/5 11/5 1/5 -1/5 -1/5 8/5 1/5 -2/5 8/5 -1/5 -2/5 8/5 3/5 -2/5 1/5 -3/5 1/5 1/5 -2/5 1/5 1/5 -7/5 8/5 7/5 1/5 8/5 1/5 原问题有多重解：X(1)＝(7/5，0，1/5，)；最优解X(2)＝(8/5，1/5，0)；Z＝19/5 如果第一张表X6出基，则有
Cj XB X5 X6 Cj－Zj X5 X1 Cj－Zj X2 X1 Cj－Zj
3 2 0 2 CB 0 0 2 X1 -1 [-2] 2 0 1 0 0 1 0 3 X2 -2 1 3 [-5/2] -1/2 2 1 0 0 5 X3 -3 -1 5 -5/2 1/2 4 1 1 2 6 X4 -4 3 6 -11/2 -3/2 9 11/5 -7/5 23/5 0 X5 1 0 0 1 0 0 -2/5 -1/5 4/5 0 X6 b -2 -3 -1/2 3/2 1/5 8/5 0 1 0 -1/2 -1/2 1 1/5 -2/5 3/5
15