§2.4 对偶单纯形法
1． 问题的提出
在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验行得到的是对偶问题的基本解，通过逐步迭代，当在检验数行得到对偶问题的基本解也是基可行解时，则得到原问题和对偶问题的最优解。
根据对偶问题的对称性，若保持对偶问题的解是基可行解，而原问题是非可行解，则通过逐步迭代使之成为基可行解，这样也可以得到最优解。
优点：原问题的最初解不一定是基可行解。
缺点：要求所有检验数?j?0。 2． 对偶单纯形法的计算步骤
maxZ?cxAx?bx?0
设B是线性规划的一个基，所有的检验数?j?0。 （I）根据线性规划，列出初始单纯形表，使?j?0； （II）若B?1b?0，则已得最优解，停止。否则，转入下一步； （III）由min?(B?1b)i|(B?1b)i?0??(B?1b)l对应的基变量xl为换出变量； （IV）若(B?1b)l?0，但alj?0，j?1,...,n，则原问题无可行解，停止。否则，转入下一步。
????j??（V）若(Bb)l?0且存在alj?0，则由??min?|alj?0??k，确定非基
j?alj???alk?1变量xk为换入变量（目的保持迭代后?j?0，即对偶问题的解是基可行解）； （VI）以alk为主元进行迭代，并将xB列中xl用xk代替。 重复（II）～（VI）。
例1. 用对偶单纯形法求解
minw?2x1?3x2?4x3x1?2x2?x3?32x1?x2?3x3?4x1,x2,x3?0
29
解：将原问题化为
maxz??2x1?3x2?4x3?x1?2x2?x3?x4??3?2x1?x2?3x3?x5??4x1,x2,x3,x4,x5?0 建立初始单纯形表
xB x4 x5 b x1 -1 x2 -2 1 -3 x3 -1 -3 -4 x4 1 0 0 x5 0 1 0 -3 -4 0 ?2 -2 xB x4 x1 b x1 0 1 0 x2 ??x3 1 23 2x4 1 0 0 x5 ??1 21 2-1 2 4 b 5 21 2-4 -1 -1 xB x2 x1 x1 0 1 0 x2 1 0 0 x3 1? 57 59? 5x4 ?2 51? 58? 5x5 1 52? 51? 52 511 528 5112故原问题的最优解为 x*?(,,0,0,0)T
5581对偶问题的最优解为 y*?(,)
55
３．对偶单纯形法的优点
30
（1）初始解可以是非可行解，但检验数?j?0。
（２）变量多于约束条件（变量少，约束多，可化为对偶问题）。 （３）用于灵敏度分析。
§2.5 灵敏度分析
1. 问题的提出
考虑线性规划的标准形
maxz?cxAx?b x?0 设B是基，则单纯形表为 xB 基 变 量 b x B?1A B?1b ?CBB?1b C?CBB?1A ?B?1b? 基本解x???是最优解的充要条件是：
0??B?1b?0,C?CBB?1A?0
前面讨论的A,b,c都是常数，但实际上往往是估计值或预测值。例如 市场条件变化?C变化
工艺条件变化?A变化 问题：
当这些系数有一个或几个发生变化时，为了保持最优基（或最优解），这些数据变化的范围；
当这些数据的变化超出了范围，如何作微小的调整，在原有的最优基（或最优解）的基础上求出新的最优基（或最优解）。
系数发生变化后原问题与对偶问题的变化情况 原问题 可行解 可行解 对偶问题 可行解 非可行解 结论或计算步骤 最优解不变 单纯形法求解 31
非可行解 非可行解
2. 资源变量变化的分析
可行解 非可行解 对偶单纯形法 引入人工变量 b的变化，在单纯形表中只有B?1b与CBB?1b变化，而检验数C?CBB?1A不变。当b变成b??b时，只要B?1(b??b)?0就能使最优基不变，但最优解，最优值变化。
例１．
maxz?2x1?3x2?x1?2x2?8?4x?16?1?4x2?12???x1,x2?0最终单纯形表
xB x1 x5 x2 b 4 4 2 14 x1 1 0 0 0 x2 0 0 1 0 x3 0 -2 1 23? 2x4 1 41 21? 81? 8x5 0 1 0 0 例２．（I）为了使最优基不变，求b2的变化范围？
（II）若该厂从别处抽出４台时用于生产产品Ⅰ，Ⅱ，求最优生产方案？ 解：（I）
32
B?1(b??b)?B?1b?B?1?b1??00??4?4????0?1??????4????21???b2???2?2????0?????11???0??28??1??4??b2??4??1?4??b??0
2??2??1??2??b2??8??? 故?b2的变化范围是??8,16?，因此b2的变化范围是?8,32?。
（II）
1??00??412?????12?1????B?1(b??b)?B?1?16????21??16???2?12?12????????11???0??28???4??????4? ?4???
将上述结果反映到单纯形表中
xB x1 x5 x2 b 4 －4 4 x1 1 0 0 0 x2 0 0 1 0 x3 0 x4 1 41 21? 81? 8x5 0 1 0 0 ?2 1 23? 2
应用对偶单纯形法
33