3.2 对偶单纯形法
单纯形算法从一个基本可行解出发，朝着目标函数值下降的方向迭代，直到最优．从对偶的角度来看，原问题目标函数下降的方向，就是对偶问题的对偶解可行的方向，当对偶解可行时，目标函数达到最优．
对偶单纯形法的思路是从对偶可行解出发，朝着原问题可行的方向迭代，直到原问题可行，于是得到最优解．
3.2.1 对偶可行解
考虑线性规划\begin{aligned} &\min~ \mathbf c^\top \mathbf x \\ & \text{s.t.}\begin{cases} \mathbf A\mathbf x=\mathbf b\\ \mathbf x\geq 0 \end{cases}\end{aligned}，其中\mathbf c, \mathbf x \in \mathbb{R}^n，\mathbf A\in\mathbb{R}^{m\times n}，\mathbf b\in \mathbb{R}^m \geq \mathbf{0}．我们知道，原问题的基本解\mathbf x（称为原始解）的形式为\mathbf x = \begin{pmatrix} \mathbf{x_B}\\ \mathbf {x_N} \end{pmatrix} = \begin{pmatrix} \mathbf B^{-1}\mathbf b\\ \mathbf{0} \end{pmatrix}，当\mathbf B^{-1}\mathbf b \geq 0时，\mathbf x即为基本可行解．
根据强对偶定理可知，如果原问题的解可行，对偶问题的解也可行，且对应目标函数值相等，则可得二者最优解．
因为原问题的对偶问题为
\begin{aligned} & \max~ \mathbf b^\top \mathbf y \\& \text{s.t.}~ \mathbf A^\top \mathbf y \leq \mathbf c \end{aligned}，
其中\mathbf y\in\mathbb{R}^m．
令\mathbf A=[\mathbf B,\mathbf N]，\mathbf B和\mathbf N分别代表基矩阵和非基矩阵，则对偶问题可以写成如下形式
\begin{aligned} & \max~ \mathbf b^\top \mathbf y \\ & \text{s.t.} \begin{pmatrix} \mathbf B^\top \\ \mathbf N^\top \end{pmatrix}\mathbf y \leq \begin{pmatrix} \mathbf {c_B} \\ \mathbf {c_N} \end{pmatrix}\\ \end{aligned}，
其中\mathbf B^\top仍为满秩的方阵，因此等号是可以取到的，对偶问题的基本解\mathbf y（称为对偶解）满足\mathbf B^\top\mathbf y= \mathbf {c_B}，即\mathbf y = (\mathbf B^\top)^{-1}\mathbf {c_B}．那么此时有
\begin{aligned} \mathbf {c_N} - \mathbf N^\top \mathbf y &=\mathbf {c_N} - \mathbf N^\top (\mathbf B^\top)^{-1} \mathbf {c_B}\\ & = \mathbf {c_N} - \mathbf N^\top (\mathbf B^{-1})^\top \mathbf {c_B}\\ &= \mathbf {c_N} - (\mathbf B^{-1}\mathbf N)^\top \mathbf {c_B} \\ & \geq \mathbf 0. \end{aligned}，
称式\mathbf {c_N} - (\mathbf B^{-1}\mathbf N)^\top \mathbf {c_B} \geq 0为对偶问题可行条件．
记对偶问题的非基变量的检验数向量\pmb\mu= \mathbf {c_N} - (\mathbf B^{-1}\mathbf N)^\top \mathbf {c_B}，如果\pmb\mu \geq 0，即\mathbf {c_BB}^{-1}\mathbf N\le \mathbf{c_N}，那么\mathbf y便是对偶问题的可行解．
3.2.2 对偶单纯形法的迭代过程分析
下面讨论对偶单纯形法的迭代过程．
对偶可行保证原始解的最优性，但可能损失可行性．迭代的思路就让原始解满足最优性的同时，也变得可行．
在已知基矩阵\mathbf B的情况下，首先介绍进基和离基的规则．
已知对偶可行解\mathbf y = (\mathbf B^\top)^{-1}\mathbf {c_B}．令\tilde{\mathbf b}= \mathbf B^{-1}\mathbf b，如果\tilde{\mathbf b}\geq \mathbf 0，那么原始解可行，\mathbf x和\mathbf y即为原问题和对偶问题的最优解．否则存在分量\tilde{b}_i < 0．为了使\mathbf x变得可行，自然的想法是使\mathbf B的第i行对应的变量\mathbf x_{B_i}离基，所以\mathbf x_{B_i}是离基变量．
那么进基变量如何计算？先把对偶问题改写．令\tilde{\mathbf y} = \mathbf B^\top \mathbf {y_B}，于是\mathbf y=(\mathbf B^\top)^{-1}\tilde{\mathbf y}．代入对偶问题，得到下面的等价形式
\begin{aligned} &\max~ \tilde{\mathbf b}^\top \tilde{\mathbf y} \\ &\text{s.t.}\begin{cases} \tilde{\mathbf y} \leq \mathbf {c_B}\\ (\mathbf B^{-1}\mathbf N)^\top \tilde{\mathbf y} \leq \mathbf {c_N} \end{cases}\end{aligned}．
前面假设\tilde{b}_i < 0，那么减少\tilde{\mathbf y}_i可以增加目标函数值，同时需要保证
(\mathbf B^{-1}\mathbf N)^\top \tilde{\mathbf y} \leq \mathbf {c_N}.
令J表示非基变量下标的集合．\forall j\in J，令\tilde{\mathbf a}_j = \mathbf B^{-1}\mathbf a_j，其中\mathbf a_j表示\mathbf A的第j列，那么上面的约束条件可以写成
\mathbf a_j^\top \tilde{\mathbf y}\le c_j,~~\forall j\in J.
令\tilde{\mathbf y}_i减小\delta，其中\delta > 0，有
\mathbf a_j^\top \tilde{\mathbf y}- a_{ij}\delta \le c_j,~~\forall j\in J.
如果\tilde{a}_{ij} > 0，\forall j\in J，那么\delta可以为无穷大，对偶问题的最优目标函数值为+\infty，那么原问题无可行解．
假设存在j\in J，使得\tilde{a}_{ij} < 0．为了满足约束条件，有
\delta := \min \left\{\displaystyle\frac{c_j - \tilde{\mathbf a}^\top_j \tilde{\mathbf y}}{-\tilde{a}_{ij}}\bigg| \tilde{a}_{ij} < 0, ~\forall j\in J\right\}.
注意到
\begin{aligned} \tilde{\mathbf a}^\top_j \tilde{\mathbf y} & = (\mathbf B^{-1}\mathbf a_j)^\top \mathbf B^\top\mathbf y \\ & = \mathbf a_j^\top (\mathbf B^{-1})^\top\mathbf B^\top \mathbf y\\ & = \mathbf a^\top_j \mathbf y, \end{aligned}
因此有
\delta = \min \left\{\displaystyle\frac{c_j - \mathbf a^\top_j \mathbf y}{-\tilde{a}_{ij}} \bigg| \tilde{a}_{ij} < 0, ~\forall j\in J\right\}.
上式称为最小比率（Minimum Ratio Test），取得最小值对应的下标j即为进基变量x_j的下标．
3.2.3 对偶单纯形算法步骤
根据上面的分析，可以整理出对偶单纯形法的算法步骤如下．
对偶单纯形法
Step 0 输入对偶可行的基矩阵\mathbf B．
Step 1 判断原始解是否可行．如果\tilde{\mathbf b} \geq 0，当前是最优解，算法停止．
Step 2 计算进基变量和离基变量．如果存在\tilde{b}_i < 0，那么x_i是离基变量．如果存在j \in J使得\tilde{a}_{ij} < 0，根据最小比率，找到进基变量x_j．
Step 3 判断问题是否无界．如果\forall i，\tilde{a}_{ij} \geq 0，则对偶问题无界，原问题无可行解，算法停止．
Step 4 执行进基、离基操作，更新基矩阵B，然后执行Step 1．
例3 用对偶单纯形法求解\begin{aligned}&\min =3_1+2_2\\&\text{s.t.}\begin{cases}2_1+3_2≤18\\_1 −_2≥2\\_1+3_2≥10\\_1≥0,_2≥0\end{cases}\end{aligned}.
解 先化为标准形
\begin{aligned} &\min =3_1+2_2\\ &\text{s.t.}\begin{cases} 2_1+3_2+x_2 =18\\ _1 −_2 -x_4 =2\\ _1+3_2-x_5=10\\ _i≥0,i=1,2,\cdots,5 \end{cases}\end{aligned}
对偶单纯形允许约束方程右端为负，因此可将第2,3约束方程两端同乘-1，可得含单位矩阵的标准型：
\begin{aligned} &\min =3_1+2_2\\ &\text{s.t.}\begin{cases} 2_1+3_2+x_2 =18\\ -_1 +_2 +x_4 =-2\\ -_1-3_2+x_5=-10\\ _i≥0,i=1,2,\cdots,5 \end{cases}\end{aligned}.
列出单纯形表，第一次迭代：
\begin{array}{ccc|ccccc} &&&x_1&x_2&x_3&x_4&x_5\\\mathbf{c_B}& \mathbf{x_B} &\mathbf{b} & 3 & 2 & 0 & 0 & 0 \\ \hline 0&x_3 & 18& 2 & 3 & 1 & 0 & 0 \\ 0&x_4 &-2 &-1 & 1 & 0 & 1 & 1 \\ 0&x_5 &-10&-1 & \color{red}{[-3}] & 0 & 0 & 1 \\ \hline&\sigma&& 3 & 2 & 0 & 0 & 0\end{array}
选择x_5离基．根据\min\left\{\displaystyle\frac{\sigma_j}{|a'_{ij}|}\big|a_{ij}<0\right\}，由于\displaystyle\frac{\sigma_3}{|a'_{53}|}=\frac{2}{3} < \frac{\sigma_1}{|a'_{51}|}=\frac{3}{1}，选择x_2进基，第二次迭代：
\begin{array}{ccc|ccccc} &&&x_1&x_2&x_3&x_4&x_5\\\mathbf{c_B}& \mathbf{x_B} &\mathbf{b} & 3 & 2 & 0 & 0 & 0 \\ \hline 0&x_3 & 8& 1 & 0 & 1 & 0 & 1 \\ 0&x_4 &-16/3 &\color{red}{[-4/3}] & 0 & 0 & 1 & 1/3 \\ 2&x_2 &10/3&1/3 & 1 & 0 & 0 & -1/3 \\ \hline&\sigma& & 7/3 & 0 & 0 & 0 & 2/3\end{array}
选择x_4离基．因元素-\frac{4}{3}所在行中的a'_{ij}只有的a'_{21}<0，故选择x_1进基，第三次迭代：
\begin{array}{ccc|ccccc} &&&x_1&x_2&x_3&x_4&x_5\\\mathbf{c_B}& \mathbf{x_B} &\mathbf{b} & 3 & 2 & 0 & 0 & 0 \\ \hline 0&x_3 &4 & 0 & 0 & 1 & 3/4 & 5/4 \\ 3&x_1 &4 & 1 & 0 & 0 & -3/4 &-1/4 \\ 2&x_2 &2 & 0 & 1 & 0 & 1/4 & -1/4 \\ \hline&\sigma&& 0 & 0 & 0 &7/4 & 5/4\end{array}
此时b列第二、三、四行均非负，迭代结束．原问题的最优解为x_1 = 4, x_2 = 2，目标函数值为16．
3.2.4 对偶单纯形法的特点
对偶单纯形法在实际中表现不错．不仅如此，原问题如果退化，其对偶问题可能是正常的．
对偶单纯形法的主要优点是， 不需要人工变量；当变量多于约束时，可以用对偶单纯形法减少迭代次数．其不足是，在初始单纯形表中要求对偶问题的基本可行解，即\boldsymbol\sigma≥0，这对于大多数线性规划问题来说是困难的．所以一般不单独使用对偶单纯形法．
为了直观对比，图 3-1-4列出单纯形法与对偶单纯形法流程对比．
