AOR1 线性规划、单纯形法、对偶单纯形法

本部分为应用运筹学基础笔记整理Part 1。由于有部分内容课上没来得及记下，用学长的博客补充了部分定理证明的内容。

latex被我修好了，可喜可贺。

参考博客

1. 优化问题的基本概念

基本模型

• 基本模型：变量，变量限制和一个需要优化的目标函数。

• 数学表示：$min(max)\ f(x)$, $s.t.$ $x\in\Omega$. 这里 $\Omega$ 为变量限制（Feasible Set），通常是一些等式或不等式。

• 例子：LP，TSP

邻域、局部最优与全局最优

• 邻域（Neighborhood）：给定一个优化问题 $(\Omega, f)$ ，邻域是 $\Omega$ 到其幂集 $2^\Omega$ 的映射，即 $N: \Omega \rightarrow 2^\Omega$ 。
  • TSP：对一个可行解，去掉两条不相邻的边，交叉相连，即可得到一个邻域解（2-change，$N_2$）。
  • MST：改变一条边。
• 对某一个邻域，如果其局部最优就是全局最优，我们称这个邻域是精确（exact）的。
  • 对TSP，$N_2$ 不精确，$N_n$精确。
  • 对MST，邻域精确。

凸集、凸函数与凸规划

• 凸组合：对于 $x, y\in R^n$，有 $z=\lambda x+(1-\lambda)y,\ 0<\lambda<1$，则称 $z$ 是 $x, y$ 的一个凸组合。
• 凸集（Convex Set）：如果对任意 $x, y \in S$，其凸组合都属于 $S$，则称 $S$ 是一个凸集。
  • 凸集的交仍是凸集。
• 凸函数：对于定义在凸集 $S$ 上的函数 $f: S\rightarrow R$，如果对任意 $x, y \in S, 0<\lambda<1$，有 $f(\lambda x+(1-\lambda)y)\le\lambda f(x) + (1-\lambda)f(y)$，则 $f$ 是凸函数。
  • 若 $f$ 是凸函数，则 $-f$ 是凹函数（Concave）。
  • 仿射函数既是凸函数也是凹函数。
• 凸规划：在凸集上求凸函数的最小值。
  • 性质：凸规划的局部最优就是全局最优，其邻域是精确的。
  • LP是特殊的凸规划。

2. 线性规划的基本原理

线性规划定义

线性规划问题有如下形式：$\begin{aligned} \max \quad z=c^Tx \\ \text{s.t.} \quad Ax = b \\ x \ge 0 \end{aligned}$

• 仿射函数既是凸函数也是凹函数，因此优化目标是$max$还是$min$差别不大。
• 对于 $Ax \le b$ 的约束，可以添加松弛变量，让它变成等式。

极点与基可行解

• 极点：对于 $\gamma\in S$，$\gamma$ 不能表示成 $S$ 中任意两点的严格凸组合。

  • 严格指 $\lambda \ne 0, \lambda \ne 1$。

  • 极点是一个几何学的概念，LP问题的可行域实际上是很多超平面的交，组成一个超多面体，极点就是超多面体的顶点。

  • 如果目标函数值是有限的，则LP问题的最优解一定能在极点处取得。

    • 证明如下：假设存在一个非极点 $x$ 是最优解，则可以找到 $x_1, x_2 \in S$, 使得 $x = \lambda x_1 + (1-\lambda)x_2$。因为 $z=c^Tx$，所以 $z = \lambda c^Tx_1 + (1-\lambda)c^Tx_2$。又因为 $x$ 是最优解，则 $x_1,x_2$ 也一定是最优解，同理 $x_1, x_2$ 这条直线上的所有点都能取到最优解，就能够把最优点一步一步约束到极点上。

• 基可行解：考虑 $Ax=b$，假定 $r(A)=m$ 且行满秩（如果不满足行满秩，说明有约束条件冗余，可以去掉变成行满秩）。设 $A$ 是一个 $m*n$ 的矩阵，我们可以从 $A$ 中选出最多 $m$ 列线性无关的列向量，其它列向量都和它们线性相关。把这 $m$ 个列向量调整到前面去，把 $A$ 分成两部分：$A = \begin{bmatrix} A_B & A_N \end{bmatrix}$， $A_B$ 就是 $m$ 个线性无关的列向量，并称 $A_B$ 是基矩阵。我们容易构造出 $Ax = b$ 的一个解：$x = \begin{bmatrix} A_B^{-1}b \\ 0 \end{bmatrix}$ 。称这种解为基可行解。显然，基可行解至多有 $C_n^m$ 种。

• 基本定理：**线性规划的基可行解是极点，反之亦然。**证明如下：

• 极点 $\rightarrow$ 基可行解，证明过程：

  • 引理：如果存在 $x$ 不是基可行解，设 $x = (x_1, x_2, ... x_k, 0, ...0)$，即 $x$ 有 $k$ 个非零元素，则这些非零分量对应在 $A$ 中的 $k$ 列是线性相关的。
    • 引理证明：如果 $k > m$，显然这 $k$ 列线性相关；如果 $k \le m$ 但这 $k$ 列线性无关，再选几个线性无关的列，凑成 $m$ 个，就可以把 $x$ 扩充成基可行解。所以这 $k$ 列线性相关。
    • 反证法：假设 $x$ 不是基可行解，则 $x = (x_1, x_2, ... x_k, 0, ...0)$ 的非零分量在 $A$ 中对应的 $k$ 列向量$(p_1,...p_k)$ 线性相关。则存在不全为0的 $\lambda_1, ...\lambda_k$，使得 $\lambda_1p_1+...+\lambda_kp_k=0$。取 $x'=x+\epsilon(\lambda_1, ...\lambda_k,0,...0)$，$x''=x-\epsilon(\lambda_1, ...\lambda_k,0,...0)$，可知 $x$ 是 $x',x''$ 的中点，又有$Ax'=Ax''=Ax=b$，所以 $x', x''$ 在该LP问题的可行域上，所以 $x$ 不是极点。
  • 基可行解 $\rightarrow$ 极点，证明过程：
    • 反证法：假设 $x$ 不是极点，则可行域内存在 $x'=(x'_1,...x'_n), x''=(x''_1,...x''_n)$ ，使得 $x=\lambda x'+(1-\lambda)x'', 0<\lambda<1$，而且 $x' \ne x''$，$x' \ge 0$ ，$x'' \ge 0$。设 $x = (x_1, x_2, ... x_k, 0, ...0)$ ，容易知道 $x',x''$ 在 $x$ 为0的分量上也为0。设 $x$ 的非零分量在 $A$ 中对应的 $k$ 列向量为 $(p_1,...p_k)$ ，则有 $\Sigma_{i=1}^k x'_i p_i =b$，$\Sigma_{i=1}^k x''_i p_i =b$。所以$\Sigma_{i=1}^k (x'_i-x''_i) p_i =0$。所以 $(p_1,...p_k)$ 线性相关，$x$ 不是基可行解。
  • 基可行解和极点不一定一样多，两者可能不是一对一的关系。

• **一定存在一个基可行解是最优解。**证明如下：

  • 假设没有基可行解是最优解，设最优解为 $x = (x_1, x_2, ... x_k, 0, ...0)$ 不是基可行解，由引理，$x_1$ 到 $x_k$ 对应的 $A$ 中 $k$ 列 $(p_1,...p_k)$ 是线性相关的。那么有不全为 0 的 $\lambda$，使得 $\sum_{i=1}^k \lambda_i p_i = 0$。
  • 记辅助向量 $v = (\lambda_1,\lambda_2,\dots,\lambda_k,0,\dots 0 )^T$，我们仍然构造 $x' = x + \epsilon v$ 和 $x'' = x - \epsilon v$。显然有 $x = \frac{x'+x''}{2}$，由于 $x$ 是最优解，当然 $x'$ 和 $x''$ 也是最优解。如果存在 $\lambda_i < 0$，那么我们取 $\epsilon = \min\limits_{\lambda_i < 0} -\frac{x_i}{\lambda_i}$，就能把 $x'$ 中 $x_1$ 到 $x_k$ 的某一个变成 0；如果不存在 $\lambda_i < 0$，那么我们取 $\epsilon = \min \frac{x_i}{\lambda_i}$，就能把 $x''$ 中 $x_1$ 到 $x_k$ 的某一个变成 0。也就是说，非 0 元素少了一个。这样一直构造下去，我们就能不断减少非 0 元素，直到 $x_1$ 到 $x_k$ 在 $A$ 中对应的 $k$ 列线性无关，$x$ 就变成了一个基可行解。而且在构造过程中，最优性没有改变，$x$ 还是最优解。
  • 所以综上所述，已知基可行解是有限多个，一定存在基可行解是最优解，我们可以通过找基可行解的方式求得LP问题的解。接下来介绍找基可行解的方法。

3. 线性规划的单纯形法

单纯形法

单纯形法的每一步都在引入一个非基变量取代某一基变量，找出目标函数值更优的另一基本可行解，这样一步一步调整到最优解。

给定一个例子：$\begin{aligned} \max \quad z=x_1+2x_2 \\ \text{s.t.} \quad x_1+x_2 \le 3\\ x_2 \le 1 \\ x_1,x_2 \ge 0 \end{aligned}$，添加松弛变量化成标准形式：$\begin{aligned} \max \quad z=x_1+2x_2 \\ \text{s.t.} \quad x_1+x_2+x_3 = 3\\ x_2+x_4 = 1 \\ x_1,x_2,x_3,x_4 \ge 0 \end{aligned}$

选取$x_3,x_4$为基变量，则可以构造初始基本可行解为 $x=(0, 0, 3, 1)^T$，此时 $z=0$。

将原问题化成典则形式，即用非基变量表示基变量与目标函数：$\begin{aligned} x_3 &= 3-x_1-x_2 \\ x_4 &= 1-x_2 \\ z &= x_1+2x_2 \end{aligned}$

此时在目标函数中，$x_1$和 $x_2$ 的系数称为检验数。$x_2$的检验数更大，我们增大$x_2$，增大到1时$x_4$变成0， $x_4$ 出基，$x_2$ 成为基变量。此时 $x=(0, 1, 2, 0)^T$，$z=2$，典则形式为：$\begin{aligned} x_2 &= 1-x_4 \\ x_3 &= 2-x_1+x_4 \\ z &= 2+x_1-2x_4 \end{aligned}$

从检验数可以看出，接下来只能增大 $x_1$。$x_1$ 增大到2时，$x_3$ 变成0，出基。此时 $x=(2,1,0,0)^T$，$z=4$，典则形式为：$\begin{aligned} x_1&=2-x_3+x_4 \\x_2 &= 1-x_4 \\ z &= 4-x_3-x_4 \end{aligned}$ 。这时目标函数中所有的检验数都小于0，因为 $x_1,x_2,x_3,x_4 \ge 0$，无法继续优化，我们就得到了该LP问题的最优解。

归纳起来，单纯形法的基本步骤如下：

1. 把线性规划问题的约束方程组表达成典则形式，找出基本可行解作为初始基可行解。
2. 若基本可行解不存在，即约束条件有矛盾，则问题无解。
3. 若基本可行解存在，从初始基可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。
4. 按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。
5. 若迭代过程中发现问题的目标函数值无限，则终止迭代。

单纯形表

设$A = \begin{bmatrix} A_B & A_N \end{bmatrix}$， $x = \begin{bmatrix} x_B^T & x_N^T \end{bmatrix}^T$。

则有 $\begin{aligned} A_Bx_B + A_Nx_N = b \\ z = c_B^Tx_B + c_N^Tx_N \end{aligned}$ 。移项转化为典则形式，$\begin{aligned} x_B &= A_B^{-1}b - A_B^{-1}A_Nx_N \\ z &= c_B^TA_B^{-1}b + (c_N^T - c_B^TA_B^{-1}A_N)x_N \end{aligned}$。

可以看出，$c_N^T - c_B^TA_B^{-1}A_N$ 是检验数。如果检验数都小于等于0，$x$ 就成为最优解。如果存在检验数大于0且在矩阵中对应的系数都小于等于0（该分量可以取到无限大），就没有有限最优解了。

单纯形表的原理如下：

初始表：$\begin{array}{c|cc|c} & c_B^T & c_N^T & 0 \\ \hline x_B & A_B & A_N & b\end{array}$

对于第二行，利用行变换将 $A_B$ 变为 $I$，相当于左乘 $A_B^{-1}$：$\begin{array}{c|cc|c} & c_B^T & c_N^T & 0 \\ \hline x_B & I & A_B^{-1}A_N & A_B^{-1}b\end{array}$

再把第二行乘上 $c_B^T$，用第一行相减，得到 $\begin{array}{c|cc|c} & 0 & c_N^T-c_B^TA_B^{-1}A_N & -c_B^TA_B^{-1}b \\ \hline x_B & I & A_B^{-1}A_N & A_B^{-1}b\end{array}$

这个线性变换的过程就是化成典则形式的过程，第一行第三列就是检验数，第一行第四列就是 $-z$，而基变量和非基变量之间的系数也可以通过第二行的第三、四两列求出。表格每这样计算一次，就是单纯形法里的一次迭代。

简单的说，对于取 $max$ 的情况，我们首先选择检验数大于0且绝对值最大的 $x_j$ 分量入基；之后在$\overline{a}_{ij}$ 大于0的基变量中选择 $\overline{b}_i/\overline{a}_{ij}$ 最小的分量 $x_i$ 出基。之所以选择最小的分量，是因为它对应的基变量会最先变成0（约束最紧）。通过线性变换，入基变量对应行的系数调整为1，其他基变量行和目标函数行（检验数）调整为0，完成一次迭代。所有的检验数都小于等于0时，得到最优解。

就前面介绍单纯形法的例子 $\begin{aligned} \max \quad z=x_1+2x_2 \\ \text{s.t.} \quad x_1+x_2+x_3 = 3\\ x_2+x_4 = 1 \\ x_1,x_2,x_3,x_4 \ge 0 \end{aligned}$来说，单纯形表的过程如下：

• 选取基变量为 $x_3, x_4$，有初始单纯形表：$\begin{array}{c|cccc|c} & 1 & 2 & 0 & 0 & 0 \\ \hline x_3 & 1 & 1 & 1 & 0 & 3 \\ x_4 & 0 & 1 & 0 & 1 & 1 \end{array}$
• 最大的正检验数对应 $x_2$，$x_2$ 入基；$ 3/1 > 1/1$，$x_4$ 出基。线性变换得到 $\begin{array}{c|cccc|c} & 1 & 0 & 0 & -2 & -2 \\ \hline x_3 & 1 & 0 & 1 & -1 & 2 \\ x_2 & 0 & 1 & 0 & 1 & 1 \end{array}$
• 最大的正检验数对应 $x_1$, $x_1$ 入基；只剩 $x_3$ 可以出基。线性变换得到 $\begin{array}{c|cccc|c} & 0 & 0 & -1 & -1 & -4 \\ \hline x_1 & 1 & 0 & 1 & -1 & 2 \\ x_2 & 0 & 1 & 0 & 1 & 1 \end{array}$
• 所有的检验数都小于等于0，得到最优 $z=4$，$x = (2, 1, 0, 0)^T$。

单纯形表的过程实际上是在选取不同的非基变量组合表达目标函数，每变换一次都是重新转换一次典则形式。当检验数都小于0时，结果没办法再改善，目标函数就取得了最大值。

初始解的选取：两阶段法

在上面的例子中，我们要解决的是约束为 $Ax \le b$ 的问题，此时通过添加松弛变量变成等号之后，取初始可行解为 $x = 0$，松弛变量对应取 $b$ 即可。

但如果我们要解决的问题形如 $\begin{aligned} \max \quad z=c^Tx \\ \text{s.t.} \quad Ax = b \\ x \ge 0 \end{aligned}$，即约束为 $Ax = b$。同样加入 $\overline{x}$，变成 $Ax + \overline{x} = b$，$\overline{x},x\ge 0$。再取 $x=0$，$\overline{x}=b$，显然它是一个初始可行解。但因为 $\overline{x}$ 是我们添加的变量，我们要求它能够全部出基（取0），才与原问题等价。解决办法如下：

• 考虑一个新的线性规划：$\begin{aligned} \min \quad \Sigma_{i=1}^m\overline{x}_i \\ \text{s.t.} \quad Ax + \overline{x} = b \\ x,\overline{x} \ge 0 \end{aligned}$，对这个问题来说， $x=0$，$\overline{x}=b$ 显然是一个初始可行解。如果优化目标的最优解不是0，那么原问题中的 $\overline{x}$ 不能全部出基，原问题无可行解；否则我们就得到了原问题的初始可行解，也就能够以此为起点求原问题的最优解。

所以线性规划的可行解和最优解求解难度相同。

4. 线性规划对偶理论

引入对偶问题

最小上界角度

• 考虑LP问题 $\begin{aligned} \max \quad z=4x_1+x_2+3x_3 \\ \text{s.t.} \quad x_1+4x_2 \le 1\\ 3x_1-x_2+x_3 \le 3 \\ x_1,x_2,x_3 \ge 0 \end{aligned}$。显然，每个可行解都能给出最优目标函数值的一个下界。比如带入 $x=(1,0,0)^T$ 得到 $z^*=4$，带入 $(0,0,3)^T$ 则得到 $z^*=9$，所以最优目标一定大于等于 $9$。所以我们考虑一个问题：怎么判断一个可行解是不是最优解？如果能得到一个上界，我的可行解恰好等于或非常接近这个上界，我们就可以判断这个可行解是不是最优的，或者与最优解有多接近。因此，我们希望能够找到一个最小的上界。
• 对于本问题来说，显然，第二行乘以3加上第一行，可以得到一个很简单的上界：$10x_1+x_2+3x_3 \le 10$，所以10是一个上界。
• 我们希望取得一个最小的上界，可以这么考虑：首先，假设第一行系数是 $y_1$，第二行 $y_2$，为了让结果是上界，我们有 $y_1+3y_2 \ge 4$，$4y_1-y_2 \ge 1$，$y_2 \ge 3$。又要使得结果最小，所以取 $min\ y_1+3y_2$。系数只能是大于等于0的（否则不等号都变了），所以 $y_1, y_2 \ge 0$。至此，我们得到了一个新的问题：$\begin{aligned} \min \quad z=y_1+3y_2 \\ \text{s.t.} \quad y_1+3y_2 \ge 4\\ 4y_1-y_2 \ge 1 \\ y_2 \ge 3 \\ y_1,y_2 \ge 0 \end{aligned}$。我们称这个问题是原LP问题的对偶问题。

材料定价角度

• 考虑LP问题 $\begin{aligned} \max \quad z=4x_1+3x_2 \\ \text{s.t.} \quad 2x_1+3x_2 \le 24\\ 5x_1+2x_2 \le 26 \\ x_1,x_2 \ge 0 \end{aligned}$。我们可以理解为单件产品1的利润为 $4$ ，生产时需要2件材料A，5件材料B；单件产品2的利润为 $3$ ，生产时需要3件材料A，2件材料B；同时，我们一共有24个材料A，26个材料B，思考分别生产多少件产品1、产品2能使得利润最大化。
• 此时有一名客户，不需要我们的产品，只买我们的原材料。那么材料A、B怎么定价？设分别定价为 $y_1, y_2$。首先要保证我们的利润不会减少，即原本那么多材料要卖出更高的价格，有 $2y_1+5y_2 \ge 4$，$3y_1+2y_2 \ge 3$。在此基础上也不能漫天要价，所以考虑总价最小 $min \ 24y_1+26y_2$。综上所述得到问题 $\begin{aligned} \min \quad z=24y_1+26y_2 \\ \text{s.t.} \quad 2y_1+5y_2 \ge 4\\ 3y_1+2y_2 \ge 3 \\ y_1,y_2 \ge 0 \end{aligned}$。这是第二种得到对偶问题的角度。

对偶问题

综上所述，一般情况下，一个LP问题（P）和其对偶问题（Q）有如下对应形式：

（P） $\begin{aligned} \max \quad c^Tx \\ \text{s.t.} \quad Ax \le b \\ x \ge 0 \end{aligned}$ （Q）$\begin{aligned} \min \quad b^Ty \\ \text{s.t.} \quad A^Ty \ge c \\ y \ge 0 \end{aligned}$

所以原问题有几个变量，对偶问题就有几个约束；同理原问题有几个约束，对偶问题就有几个变量。

约束的不等号和对偶问题的 $\ge 0$要求是一一对应的。如果原问题是一个最大化问题，我们有以下结论：

• 原问题 $a_i^Tx \le b_i$，对偶问题 $y_i \ge 0$
• 原问题 $a_i^Tx \ge b_i$，对偶问题 $y_i \le 0$
  • 原问题转换为 $-a_i^Tx \le -b_i$，对应一个 $\overline{y}_i \ge 0$，由对偶问题定义得原问题的 $y_i = -\overline{y}_i \ge 0$。
• 原问题 $a_i^Tx = b_i$，对偶问题 $y_i$ 无限制
  • 等号不会存在变号的情况，所以 $y_i$ 无限制。
• 原问题 $x_j \ge 0$，对偶问题 $A_j^Ty \ge c_j$
• 原问题 $x_j \le 0$，对偶问题 $A_j^Ty \le c_j$
• 原问题 $x_j$ 无限制，对偶问题 $A_j^Ty = c_j$

D是P的对偶问题，则P也是D的对偶。

弱对偶，强队偶和互补松弛

考虑 （P） $\begin{aligned} \max \quad c^Tx \\ \text{s.t.} \quad Ax \le b \\ x \ge 0 \end{aligned}$ （Q）$\begin{aligned} \min \quad y^Tb \\ \text{s.t.} \quad y^TA \ge c^T \\ y \ge 0 \end{aligned}$

弱对偶定理

设 $x$ 和 $y$ 分别是P和D的可行解，有 $c^Tx \le y^Tb$。

证明：因为 $Ax \le b$，所以 $y^TAx \le y^Tb$，所以 $c^Tx \le y^TAx \le y^Tb$.

我们有如下结论：

• 若P和D都有有限可行解，P问题的任一可行解目标函数值都小于等于D问题任一可行解的目标函数值。
• 设x和y分别是P和D问题的可行解，若两者目标函数值相等，则它们分别是各自问题的最优解。
• 若P有无限最优解，则D不可行；若D有无限最优解，则P不可行。

注意也有可能两个问题都不可行。

强对偶定理

**若P（D）有有限最优解，则D（P）也有有限最优解，且目标函数值相等。**证明如下：

• 给P引入松弛变量有：$\begin{aligned} \max \quad c^Tx \\ \text{s.t.} \quad Ax + I \overline{x} =b \\ x,\overline{x} \ge 0 \end{aligned}$ 不妨设 $\overline{A}=(A,I)$，设P有有限最优解： $x^*=(x_B^T, x_N^T)^T$，在 $\overline{A}$ 中对应列 $(\overline{A}_B, \overline{A}_N)$.

  如果我们能找到对应D的优先最优解，则定理得证。

• 考虑初始单纯形表：$\begin{array}{c|cc|c} & c^T & 0 & 0 \\ \hline x^*_B & A & I & b\end{array}$；则最后的单纯形表为：$\begin{array}{c|cc|c} & c^T-c_B^T\overline{A}_B^{-1}A & -c_B^T\overline{A}_B^{-1} & -c_B^T\overline{A}_B^{-1}b \\ \hline x^*_B & \overline{A}^{-1}_BA & \overline{A}^{-1}_B & \overline{A}^{-1}_Bb\end{array}$。

• 因为 $x^*$ 是最优解，所以检验数小于等于0。所以 $\begin{aligned} c^T-c_B^T\overline{A}_B^{-1}A \le 0\\ -c_B^T\overline{A}_B^{-1} \le 0\\ c_B^T\overline{A}_B^{-1}b = c^Tx^* \end{aligned}$。所以 $\begin{aligned} c_B^T\overline{A}_B^{-1}A \ge c^T\\ c_B^T\overline{A}_B^{-1} \ge 0\\ c_B^T\overline{A}_B^{-1}b = c^Tx^* \end{aligned}$.

• 令 $y^{*^T} = c_B^T\overline{A}_B^{-1}$，易知 $y^*$ 就是原问题对偶问题的最优解，并且 $y^{*^T}b=c^Tx^*$。

互补松弛定理

若 $x^*$，$y^*$ 分别是P、D的可行解，则：$x^*,y^*$ 最优 $\Leftrightarrow$ $\begin{aligned} (y^{*^T}A-c^T)x^*=0 \\ y^{*^T}(Ax^*-b)=0 \end{aligned}$ 。证明如下：

在前面的弱对偶定理部分我们有：$c^Tx \le y^TAx \le y^Tb$ 。因为对最优解有 $y^{*^T}b=c^Tx^*$ ，所以 $c^Tx^* =y^{*^T}Ax^* = y^{*^T}b$ 。得证。

可以看出，如果某个约束没有满足，对偶问题的对应分量只能为0。

对偶单纯形法

最优解有两个条件：首先最优解是可行解；其次，检验数 $\le 0$ 保证它是最优解。为讨论方便，我们接下来的引入部分都是考虑最大化问题，最小化问题反号即可。

我们原先用单纯形表 $\begin{array}{c|cc|c} & 0 & c_N^T-c_B^TA_B^{-1}A_N & -c_B^TA_B^{-1}b \\ \hline x_B & I & A_B^{-1}A_N & A_B^{-1}b\end{array}$ ，实际上是在保证可行（$A_B^{-1}b \ge 0$）的基础上做Local Search（更换一个基变量），使得检验数 $ \le 0$ 逐步被满足。当检验数 $\le 0$时，对偶问题可行，所以原来的单纯形法是在保证原问题可行的基础上，找对偶问题的可行解，如果构造成功，那么两个都是最优解。

那么相应的，我们可以想象对偶单纯形法：在保证对偶问题可行（检验数 $\le 0$）的基础上，逐步迭代找原问题的可行解（$A_B^{-1}b \ge 0$），使得目标函数值相同。如果构造成功，那么两个都是最优解。

例如，对于如下LP问题P，有对偶问题D：

（P） $\begin{aligned} \max \quad -5x_1-5x_2+9x_3 \\ \text{s.t.} \quad -x_1-2x_2+4x_3 \le 1 \\ -x_1-x_2+6x_3 \le 2 \\ x \ge 0 \end{aligned}$ （D）$\begin{aligned} \min \quad y_1+2y_2 \\ \text{s.t.} \quad -y_1-y_2 \ge -5 \\ -2y_1-y_2 \ge -5 \\ 4y_1 + 6y_2 \ge 9 \\ y \ge 0 \end{aligned}$

把问题D转化为最大化形式，并加入松弛变量，转化为：$\begin{aligned} \max \quad -y_1-2y_2 \\ \text{s.t.} \quad y_1+y_2+y_3 \le 5 \\ 2y_1+y_2+y_4 \le 5 \\ -4y_1 - 6y_2 + y_5 \le -9 \\ y \ge 0 \end{aligned}$

选取基变量为 $y_3,y_4,y_5$，有初始单纯形表：$\begin{array}{c|ccccc|c} & -1 & -2 & 0 & 0 & 0 & 0\\ \hline y_3 & 1 & 1 & 1 & 0 & 0 & 5 \\ y_4 & 2 & 1 & 0 & 1 & 0 & 5 \\ y_5 & -4 & -6 & 0 & 0 & 1 & -9 \end{array}$。

只有 $-9 <0$，所以 $y_5$ 出基。考虑让 $y_1$ 还是 $y_2$ 入基：如果让 $y_2$ 入基，$y_1$ 的检验数就会大于0，所以应该让 $y_1$ 入基（判断方法：$\frac{-1}{-4}<\frac{-2}{-6}$，选前者）。得到：$\begin{array}{c|ccccc|c} & 0 & -1/2 & 0 & 0 & -1/4 & 9/4\\ \hline y_3 & 0 & -1/2 & 1 & 0 & 1/4 & 11/4 \\ y_4 & 0 & -2 & 0 & 1 & 1/2 & 1/2 \\ y_1 & 1 & 3/2 & 0 & 0 & -1/4 & 9/4 \end{array}$。

因为所有的$A_B^{-1}b \ge 0$，此时已经得到目标函数最优值 $-9/4$，$y=(9/4, 0, 11/4, 1/2, 0)^T$。所以最小化时最优值为 $9/4$，也就是原问题的最优值。

综上所述，对偶单纯形法的步骤总结如下：

• 首先通过变换，得到初始对偶单纯形表，保证对偶可行（检验数 $\sigma \le0$）；
• 检查可行性$A_B^{-1}b \ge 0$。如果全部符合，已经得到最优解；否则在$A_B^{-1}b<0$中找到$A_B^{-1}b$绝对值最大一行的对应分量，出基；之后在$\overline{a}_{ij}$ 小于0的变量中选择 $\sigma_j/\overline{a}_{ij}$ 最小的分量 $x_i$ 入基。通过线性变换，入基变量对应行的系数调整为1，其他基变量行和目标函数行（检验数）调整为0，完成一次迭代。
• 重复第二步。