5、对偶单纯形法
在标准形式的线性规划问题中，如果σj =c j -C B P j ≤0，但b i 的值不一定为正，这时可用对偶单纯形法继续求解，直到所有b i ≥0。

对偶单纯形法的步骤：
1、 确定出基变量
存在小于零的b i 时，令b r =min{b i }，其对应变量x r 为出基变量。

（先定出基变量）
2、 确定入基变量
在非基变量中找出a rj <0（j=m+1,….,n ）,令
θ=mjn ⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧<0rj rj j a a σ=rs
s a σ 称a rs 为主元素，x s 为入基变量 3、 用入基变量替换出基变量，得到一个新的基。

用新的基再检查是否所有b i ≥0，如果是，找到了问题的最优解，否则，回到第一步再重复计算。

【例】求解线性规划问题
min ω=12y 1+16y 2+15y 3
s.t. ⎪⎩⎪⎨⎧≥≥+≥+0,,3522423
213121y y y y y y y 【解】 转化为目标函数最大化，并化为标准形
min （-ω）=-12y 1-16y 2-15y 3+0y 4+0y 5
s.t. ⎪⎩⎪⎨⎧≥=-+=-+)5,4,3,2,1(0352242531421j
y y y y y y y
但这时没有单位矩阵，需要用大M 法或两阶段法求解，较麻烦。

但这时可用对偶单纯形法求解。

在约束条件的两边乘-1，得
min （-ω）=-12y 1-16y 2-15y 3+0y 4+0y 5
s.t. ⎪⎩⎪⎨⎧≥-=---=--)5,4,3,2,1(0352242531421j
y y y y y y y 有单位矩阵，
列出单纯形表，用对偶单纯形法求解，此时3)3,2min(-=--，y 5为出基变量，3515,212min =⎭
⎬⎫⎩⎨⎧----，y 3为入基变量
3416,26min =⎭
⎬⎫⎩⎨⎧----，y 1为入基变量
此时所有的σj =c j -C B P j ≤0，b i ≥0，有最有解
得最优解 Y * = (1,0,1/5,0,0)
最优值 ω =15
注意最终单纯形表中剩余变量（y 4,y 5）的检验数所对应的值（符号相反），正好为原问题（常山机器厂）的最优解。