九、 对偶单纯型法
关键：与传统互置（翻）
十、 利用对偶性质
广泛：如(1) 对称性 (2)弱对偶性CX≤Yb; (3) 无界性 (4)可行解相等是最优解; (5) 对偶定理 都有最优解；且目标函数值相等; (6) 兼容性，松弛变量-变量，剩余变量-原变量；(7)互补松弛性. （8）对偶变量的经济含义
1）..已知下表为求解某线性规划问题的最终单纯形表，表中x4和x5为松弛变量，
问题的约束为≤形式。 x1 x2 x3 5/2 0 1/2 X1 5/2 1 -1/2 ?4 cj?zj 0 （1）写出原线性规划问题
（2）写出原问题的对偶问题。
（3）直接由表写出对偶问题的最优解。
2、已知线性规划问题（20分）
x3 1 0 0 x4 1/2 -1/6 - 4 x5 0 1/3 -2 ???? ?minz?2x1?x2?2x3?x1?x2?x3?4?x1?x2?kx3?6x1?0,x2?0
其最优解为x1??5,x2?0,1．求k的值；
2．求出对偶问题的最优解
一、解：写出原问题的对偶问题得
x3??1
?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
TTY*?(y,y)?(?6,2)k??312 综上，，对偶问题最优解为
敏感性分析
除了单纯性表，运输问题等许多问题都可以敏感性分析
关键：找到B-1，“左乘” 出现新系数，最优解变化 最优不变的区间范围△ b变动 C，A同时变化 B, C, A同时出现变化——引入一行新约束（） C变动 A变动 十一、 B变动；
（2）若b2 变为30，求新的最优解
15 ≤ b2 ≤ 25 时，最优基不变。变化后基变量的 取值为:
两种求解方法，1）直接相乘；2）B’+△B’
XB*?1?1?1??40?0??5?10???5??????????B?1b*??01?1??20?10???5?10???15?
?001??15?0??15?0??15?????????十二、 C变动；
注：也可以直接让2+λ= K (△c1)