1.对偶理论 (Duality)

1.1 拉格朗日对偶 (Lagrangian Duality)

为了理解对偶理论，我们先引入拉格朗日函数 (Lagrangian)，它是解决带约束优化问题的一个强大工具。

我们的出发点是一个标准形式的线性规划（LP）问题 。

• 目标: 最小化成本函数 $c^Tx$ 。
• 约束: 解决方案 $x$ 必须满足等式约束 $Ax=b$ 和不等式约束 $x≥0$ 。

为了处理这些约束，我们定义了一个新的函数，即拉格朗日函数 $L(x,y,z)$ ，表达式是 $$L(x,y,z)=c^\top x-y^\top(Ax-b)-z^\top x$$ 这个函数是通过将约束条件融入到原始的目标函数中来构造的 。

在构造过程中，我们引入了两个新的变量 $y$ 和 $z$，它们被称为对偶变量(Dual Variables)或拉格朗日乘子 (Lagrange Multipliers) 。

• 变量 y 对应等式约束 $Ax=b$ ，变量 $z$ 对应不等式约束 $x\geq0$

这是拉格朗日方法最核心的思想：将一个复杂的“带约束优化问题”转化为一个相对简单的“无约束优化问题”。

“惩罚”思想: 我们可以把对偶变量 y 和 z 理解为对“违反约束”的惩罚项或价格。

• 对于约束 $Ax−b=0$: 如果我们找到了一个满足约束的解 $x$，那么 $Ax−b$ 就等于0，$−y^T(Ax−b)$ 这一项也就等于0，对原始目标函数 $c^Tx$ 没有任何影响。但如果一个解 $x$ 不满足约束， $Ax-b\neq0$，那么 $−y^T(Ax−b)$ 就不为0。通过后续的优化（在对偶问题中是最大化），这个惩罚项会迫使我们去寻找那些使 $Ax−b$ 尽可能等于 0 的解。
• 对于约束 $x≥0$: 这一项的理解稍微复杂一些。在后续的推导中，我们会要求 $z≥0$。在这种情况下，如果某个 $x_i​<0$（违反了约束），那么 $−z_i​x_i​$ 就会是一个正数。后续的优化过程会试图让这个惩罚项变大，从而“惩罚”这种违反约束的行为，推动解朝着 $x≥0$ 的方向移动。

1.1.1 等价性证明

通过对拉格朗日函数 $L(x,y,z)$ 先进行最大化（max）再进行最小化（min），可以完全等价地恢复出我们最初的那个带约束的线性规划问题。

1. 分析内部的最大化：$max_y max_{z≥0} L(x,y,z)$

这里，我们先把 $x$ 看作是固定的，然后分析当 $y$ 和 $z$ (其中 $z ≥ 0$) 可以自由取值时， $L(x,y,z)$ 的最大值会是多少。这会产生三种情况 ：

情况一：如果 x 是一个可行解 (即 $Ax=b$ 且 $x≥0$)

• 因为 $Ax=b$，所以 $Ax−b=0$，那么 $−y^T(Ax−b)$ 这一项就等于0，无论 y 取什么值 。
• 因为 $x ≥ 0$ 且我们是在 $z ≥ 0$ 的范围内取最大值，$−z^Tx$ 的最大值只能是0（当 $z = 0$ 时取得） 。
• 因此，当 $x$ 可行时，$L(x,y,z)$ 的最大值就是原始的目标函数 $c^Tx$ 。

情况二：如果 x 违反了等式约束 (即 $Ax \neq b$)

• $Ax−b$ 是一个非零向量。我们可以通过选择一个合适的 $y$ (例如，让 $y$ 的方向与 $−(Ax−b)$ 的方向一致且模长极大)，使得 $−y^T(Ax−b)$ 趋向于正无穷大 ($∞$) 。
• 所以，只要违反这个约束，$L(x,y,z)$ 的最大值就是无穷大。

情况三：如果 x 違反了非负约束 (即存在某个 xi​<0)

• 我们可以选择对应的zi​ 为一个极大的正数，而其他的 $z_j​=0$。这样，$−z^Tx$ 这一项因为有了 $−z_i​x_i​$ （一个正数乘以一个负数的相反数）而趋向于正无穷大 ($∞$) 。
• 所以，只要违反这个约束，$L(x,y,z)$ 的最大值也是无穷大。

综合以上三点，我们可以得出一个结论： $$\max_{z\geq0,y}L(x,y,z)=\begin{cases}c^\top x,&\mathrm{if~}Ax=b\mathrm{~and~}x\geq0\\infty,&\mathrm{otherwise}&&\end{cases}$$ 这个函数是一个“惩罚函数”。它对所有不可行的解 x 都给出了无穷大的代价值。

因此，当我们再去求解 $min_x$  时，即 $min_x max_{z≥0,y} L(x,y,z)$，我们自然会忽略那些值为无穷大的不可行解，而只在所有可行解中寻找使 $c^Tx$ 最小的那个解 。这和我们原始的LP问题是完全等价的。

那么，既然原始问题可以写成 $min_x max_{y,z} L(x,y,z)$，那么我们可以“翻转”min和max的顺序，得到一个新的问题 ：$\max_{z\geq0,y}\min_xL(x,y,z)$。

这个新问题就被定义为原始问题的对偶问题 (Dual Problem)。

在数学上，$min max$ 和 $max min$ 的顺序交换并非总是等价的。它们之间存在一个非常重要的关系，称为最小最大不等式 (Minimax Inequality)： $$\max_y\min_xf(x,y)\leq\min_x\max_yf(x,y)$$

直观理解: 想象一个两人游戏。x 是你，y 是对手。

• $min_x max_y f(x,y)$: 你（x）先出招，目标是让你在对手（y）做出最好的回应后，你的损失（$f(x,y)$）最小。这代表了你的最差情况下的最优策略。
• $max_y min_x f(x,y)$: 对手（y）先出招，目标是在你（x）做出最好的回应后，你的损失（$f(x,y)$）最大。
• 你的最差情况下的最优策略，肯定比对手让你陷入的最糟情况要好（或相等）。

为什么要构造对偶问题？

构造并求解对偶问题，而不是直接解原始问题，通常有以下好处：

• 简化问题: 有时对偶问题比原始问题有更少的变量或更简单的约束结构，从而更容易求解。
• 提供下界: 即使我们找不到原始问题的最优解，对偶问题的任何一个可行解都能为原始问题的最优值提供一个下界（根据弱对偶性）。这在设计近似算法时非常有用。
• 经济学解释: 在很多资源分配问题中，对偶变量（即 y 和 z）有非常明确的经济学含义，被称为影子价格 (Shadow Prices)，代表当某个约束（如资源上限）放宽一个单位时，目标函数（如总利润）会增加多少。

1.2 对偶定理

1.2.1 弱对偶性 (Weak Duality)

原始问题最优值 $p^∗$ 和对偶问题最优值 $d^∗$ 的定义如下：

• $p^∗=min_x​max_{z≥0,y}​L(x,y,z)$ (原始问题)
• $d^∗=max_{z≥0,y}​min_x​L(x,y,z$) (对偶问题)

弱对偶定理 (Theorem: Weak Duality):

• 定理内容: 如果原始问题和对偶问题都有解，那么对偶问题的最优值 $d^∗$ 永远不会超过原始问题的最优值 $p^∗$，即 $d^∗$≤$p^∗$ 。
• 核心含义: 对偶问题的最优解，是原始问题最优解的一个下界 (lower bound)。

证明：

第一步 (等于): $$d^*=L(x_d,y_d,z_d)=\min_xL(x,y_d,z_d)$$ 这是根据对偶最优解的定义得来的。$(y_d​,z_d​)$ 是使得 $min_x​L(x,y,z)$ 最大的那一组对偶变量，而 $x_d$​ 是在给定 $(y_d​,z_d​)$ 的情况下，使 $L$ 最小的那个 $x$。所以 $L$ 在这个点上的值就是 $d^∗$。

第二步 (小于等于): $$\min_xL(x,y_d,z_d)\leq L(x_p,y_d,z_d)$$ 一个函数在所有 $x$ 上的最小值，必然小于或等于这个函数在任何一个特定点 ($x_p$​) 上的取值。这是“最小值”的基本定义。

第三步 (小于等于): $$L(x_p,y_d,z_d)\leq\max_{y,z\geq0}L(x_p,y,z)$$ 同样地，一个函数在某个特定点 $(y_d​,z_d​)$ 上的取值，必然小于或等于这个函数在所有可行点上的最大值。这是“最大值”的基本定义。

第四步 (等于): $$\max_{y,z\geq0}L(x_p,y,z)=L(x_p,y_p,z_p)=p^*$$ 这是根据原始最优解的定义得来的。$x_p$​ 是使得 $max_{y,z≥0}​L(x,y,z)$ 最小的那个 $x$，而 $(y_p​,z_p​)$ 是在给定 $x_p$​ 的情况下，使 $L$ 最大的那组对偶变量。所以 $L$ 在这个点上的值就是 $p^∗$。

原始问题目标值和对偶问题目标值之间的差值 (p∗−d∗) 被称为对偶间隙(Duality Gap)。

• 根据弱对偶性，这个间隙永远 ≥0。
• 强对偶性 (Strong Duality): 在线性规划和很多凸优化问题中，一个更强的结论成立：对偶间隙为0，即 $d^∗=p^∗$ 。这意味着我们通过求解对偶问题得到的下界，实际上就是我们想求的真实最优值。这是单纯形法能够保证找到最优解的理论基石。

“最优性证书” (Optimality Certificate)

弱对偶性提供了一种非常强大的验证最优解的方法。

• 假设你找到了一个原始可行解 $\hat{x}$ 和一个对偶可行解 $(\hat{y},\hat{z})$。
• 你计算出它们的的目标值 $c^T\hat{x}$ 和 $b^T\hat{y}​$，发现它们相等。
• 根据弱对偶性，我们知道 $d^∗≤p^∗$。因为你找到了两个值相等的可行解，所以我们知道 $b^T\hat{y}​≤d^∗≤p^∗≤c^T\hat{x}$。既然 $b^T\hat{y}​=c^T\hat{x}$，那么中间所有的不等号都必须是等号。
• 结论: 无需再进行任何计算，就可以100%确定 $\hat{x}$ 就是原始问题的最优解，$(\hat{y},\hat{z})$ 就是对偶问题的最优解。

1.2.2 强对偶性 (Strong Duality)

强对偶定理 (Theorem: Strong Duality)

• 核心内容: 对于线性规划问题，强对偶性成立 。这意味着原始问题与对偶问题的最优值完全相等 $(p^∗=d^∗)$ 。这与弱对偶性 $(d^∗≤p^∗)$ 相比，是一个更强大、更精确的结论。与单纯形法的关系: 定理还指出，单纯形法在结束时，会同时给出原始问题的最优解 $x^∗$ 和对偶问题的最优解 $y^∗$。

证明如下：

第一步：单纯形法的终止条件

• 当单纯形法找到最优解并终止时，同时满足两个条件：
  1. 原始可行性 (Primal Feasibility): 当前的基解是非负的，$x_B^*=A_B^{-1}b\geq0$ 。
  2. 最优性条件 (Optimality Condition): 检验数（或称判别数）行中的所有系数都非负，即 $\overline{c}=c^T-c_B^TA_B^{-1}A\geq0$ 。
• 第二步：构造一个对偶解
  • 这是证明中最关键的一步。我们利用单纯形法最终解中的信息，定义一个候选的对偶解 $y$ :$$y=(A_B^{-1})^Tc_B$$
  • 这个 $y$ 完全由原始问题的最优基 $A_B$​ 和对应的成本 $c_B$​ 决定。

第三步：验证这个 $y$ 是对偶最优解

1. 证明 y 是对偶可行的:
   • 我们将单纯形法的最优性条件 $c^T≥c_B^T​A_B^{−1}​A$ 两边同时转置，得到 $c\geq A^T(A_B^{-1})^Tc_B$​ 。
   • 把我们构造的 $y$ 代入上式，就得到 $A^Ty≤c$ 。这正好是对偶问题的可行性约束条件 。所以，我们构造的 $y$ 是一个对偶可行解 。
2. 证明 y 的目标值等于原始问题的最优值:
   • 我们来计算原始问题的最优值 $p^∗$，它等于 $c^Tx^=c_B^Tx_B^=c_B^TA_B^{-1}b$ 。
   • 接着，我们计算我们构造的对偶解 $y$ 的目标值，即 $b^Ty$ 。将 $y$ 的定义代入，得到 $b^Ty=b^T(A_B^{−1}​)^Tc_B​$。
   • 利用向量运算法则 $(u^Tv=v^Tu)$，我们发现 $$b^T(A_B^{-1})^Tc_B=(c_B^TA_B^{-1}b)^T=c_B^TA_B^{-1}b$$
   • 结论: 我们证明了 $p^∗=b^Ty$ 。

最终的逻辑闭环:

• 我们知道$y$ 是一个对偶可行解，所以它的目标值 $b^Ty$ 必然小于等于对偶问题的最优值 $d^∗$ (即 $b^Ty≤d^∗$) 。结合上一步，我们得到 $p^=b^Ty\leq d^$但是，根据弱对偶定理，我们早已知道 $d^\leq p^$，同时成立的唯一可能性就是 $p^=d^$ 强对偶性得证。

推论 (Corollary)

• 内容: 一个可行的原始解 $x$ 是最优解的充要条件是，存在一个可行的对偶解 $y$，使得它们的目标函数值相等，即 $c^Tx=b^Ty$ 。
• 解释: 这个推论提供了一个极其强大的最优性检验标准。如果你找到了这样一对 primal-dual 解，它们的 "gap" 为0，你就可以立刻停止搜索，因为你已经同时找到了两个问题的最优解。

这个证明告诉我们，单纯形法不仅仅是在闷头寻找原始问题的最优解。它的每一步迭代，实际上都可以看作是在同时调整原始解和对偶解：

• 它始终保持着原始可行性。
• 它的目标（寻找所有 $\overline{c}_j\geq0$）正是在努力达成对偶可行性。
• 当算法终止时，两个可行性都达到了，也就同时找到了两个问题的最优解。

1.3 标准LP的对偶问题推导

1.3.1 推导

第一步：定义内部的最小化问题 $g(y,z)$

对偶问题是 $max_{z\geq0,y}\min_xL(x,y,z)$ 为了方便，我们先把内部的 $\min_xL(x,y,z)$ 这个子问题拿出来，把它定义为一个新函数 $g(y,z)$

我们的目标就变成了先解出 $g(y,z)$，然后再把它代回去求 $max_{z\geq0,y}g(y,z)$

第二步：求解 $g(y,z)$

1. 展开与重组:
   • 我们把拉格朗日函数 $L(x,y,z)$ 得到 $g(y,z)=\min_x{c^\top x-y^\top(Ax-b)-z^\top x}$
   • 通过分配律和矩阵转置的性质 $(y^T A x = (A^T y)^T x)$ ，我们将所有与决策变量 $x$ 相关的项合并在一起，与 $x$ 无关的项移到后面。
   • 整理后得到：$g(y,z)=\min_x(c-A^\top y-z)^\top x+y^\top b$
2. 分析最小化:
   • 现在我们需要求解 $\min_x(\text{一个向量})^\top x+(\text{一个常数})$
   • 注意到 $y^Tb$ 部分与 $x$ 无关，可以看作常数。核心是最小化 $(c-A^\top y-z)^\top x$
   • 这是一个关于 $x$ 的线性函数。对于一个无约束的线性函数，它的最小值是多少？
     • 情况A: 如果括号里的向量 $(c-A^\top y-z)$ 不为零，那么我们总能找到一个 x 的方向（例如，与这个向量完全相反的方向），让这个线性函数的值趋向于负无穷 ($−∞$)。
     • 情况B: 只有当括号里的向量 $(c−A^Ty−z)$ 恰好为零向量时，$(c−A^Ty−z)^Tx$ 这一项才恒等于0。此时，函数的最小值就是剩下的常数项 $y^Tb$。
• 因此，$g(y,z)$ 的解是一个分段函数 ：$$g(y,z)=\begin{cases}y^\top b,&\mathrm{if~}A^\top y+z=c\-\infty,&\mathrm{otherwise}&\end{cases}$$ 第三步：代回原问题，得到最终的对偶形式

• 现在我们来求解 $max_{z≥0,y​}g(y,z)$。
• 因为我们是在求最大值，所以我们自然会忽略掉所有让 $g(y,z)$ 等于 $−∞$ 的情况。
• 这意味着我们只关心满足条件 $A^Ty+z=c$ 的 $y$ 和 $z$。
• 因此，问题就变成了：在满足$A^Ty+z=c$ 和 $z≥0$ 的前提下，最大化 $y^Tb$ 。

最后一步：简化

• 约束条件 $A^Ty+z=c$ 可以改写为 $z=c−A^Ty$。
• 将这个代入到另一个约束 $z ≥ 0$ 中，我们就得到了 $c−A^Ty≥0$，即 $A^Ty≤c$。
• 通过这个代换，我们成功地消去了变量 $z$，得到了一个只包含变量 $y$ 的、更简洁的对偶问题形式 ：$$max_yy^\top b$$$$s.t.A^\top y\leq c$$ 这次推导为我们揭示了一个对应关系，常被称为“原始-对偶字典”：

原始问题中的目标函数系数 $c$ 变成了对偶问题中的约束右端项，而原始的约束右端项 $b$ 变成了对偶的目标函数系数。这个“交叉”关系是LP对偶理论的一个核心特征。

为什么对 $x$ 的最小化是无约束的？

这是一个常见的困惑点。在原始问题中，x 明确有约束 $x ≥ 0$。但在推导 $g(y,z)=min_x​L(x,y,z)$ 这一步时，我们把 $x$ 当作了无约束变量。

• 原因: $x ≥ 0$ 这个约束已经被拉格朗日乘子 $z$ 以及 $−z^Tx$ 这一项吸收进了拉格朗日函数内部。
• 从数学上讲，$L(x,y,z)$ 是一个定义在所有 $x∈R_n$ 上的函数。当我们从理论上推导它的性质时，我们是在它的整个定义域上进行最小化。
• $x ≥ 0$ 这个约束的影响，最终会体现在对偶问题的约束 $A^Ty≤c$ 之中，而不是在求解 $g(y,z)$ 的中间步骤里体现。

1.3.2 例子

原始问题： $$\begin{cases}&\mathrm{min}\quad7x_{1}+2x_{2}+5x_{3}+4x_{4}\&\mathrm{s.t.}\quad2x_{1}+4x_{2}+7x_{3}+x_{4}=5\&\quad\quad\quad8x_{1}+4x_{2}+6x_{3}+4x_{4}=8\&\quad\quad\quad x_{1},x_{2},x_{3},x_{4}\geq0\end{cases}$$ 对偶问题：$$\begin{cases}\max_{\mathbf{y}\in\mathbb{R}^2}&5y_1+8y_2\\mathrm{s.t.}&2y_1+8y_2\leq7\&4y_1+4y_2\leq2\&7y_1+6y_2\leq5\&y_1+4y_2\leq4\end{cases}$$

• 目标函数 (Objective Function)
  • 原始: min 7x₁ + 2x₂ + 5x₃ + 4x₄
  • 对偶: max 5y₁ + 8y₂
  • 转换规则: 原始问题约束条件右侧的向量 b = [5, 8]ᵀ，直接变成了对偶问题目标函数的系数 。同时，min 问题变成了 max 问题。
• 约束条件 (Constraints)
  • 原始:
    • 2x₁ + 4x₂ + 7x₃ + 1x₄ = 5
    • 8x₁ + 4x₂ + 6x₃ + 4x₄ = 8
  • 对偶:
    • 2y₁ + 8y₂ ≤ 7
    • 4y₁ + 4y₂ ≤ 2
    • 7y₁ + 6y₂ ≤ 5
    • 1y₁ + 4y₂ ≤ 4
  • 转换规则:
    • 原始问题的系数矩阵 A 的每一列，都变成了对偶问题系数矩阵 Aᵀ 的每一行。
      • A的第一列[2, 8]ᵀ 变成了对偶问题第一条约束的系数 2y₁ + 8y₂ 。
      • A的第二列[4, 4]ᵀ 变成了对偶问题第二条约束的系数 4y₁ + 4y₂ 。
      • ...以此类推。
    • 原始问题目标函数的系数 c = [7, 2, 5, 4]ᵀ，则变成了对偶问题约束条件的右侧数值 。
• 变量与约束的数量
  • 原始: 有 4 个变量 $(x_1​,x_2​,x_3​,x_4​)$ 和 2 条等式约束 。
  • 对偶: 有 2 个变量 $(y_1​,y_2​)$ 和 4 条不等式约束 。
  • 转换规则: 原始问题的约束数量决定了对偶问题的变量数量。原始问题的变量数量决定了对偶问题的约束数量。

规则：

• 目标转换: min ↔ max。
• 系数交换: 原始的 b 向量（约束右侧）与 c 向量（目标系数）在对偶问题中交换角色。
• 矩阵转置: 原始的约束矩阵 A 变为对偶问题中的 Aᵀ。
• 数量交换: 原始的约束数量 ↔ 对偶的变量数量；原始的变量数量 ↔ 对偶的约束数量。
• 类型对应: 原始问题中 >= 0 的变量对应对偶问题中 ≤ 的约束；原始问题中 = 的约束对应对偶问题中无符号限制的变量（这里的 y ∈ ℝ² 就是指y₁, y₂没有非负限制） 。

维度视角下的理解

• 原始问题是在一个四维空间($\mathbb{R}^4$)中寻找一个点 $x$ ，这个点需要满足两个超平面的交集（2个等式约束）。
• 对偶问题则是在一个二维空间($\mathbb{R}^2$)中寻找一个点 $y$ ，这个点需要满足四个半空间（4个不等式约束）的交集。
• 从这个角度看，对偶问题将一个高维（4D）的问题转化成了一个低维（2D）的问题。在某些情况下，低维问题可能更容易求解或进行可视化分析。

应用一个具体的经济学故事

我们可以为这个例子赋予一个经济学上的直观解释：

• 原始问题 (工厂视角):
  • 一个工厂生产4种产品 $(x_1​,x_2​,x_3​,x_4​)$ 。
  • 目标是最小化总生产成本 7x₁ + 2x₂ + ... 。
  • 生产需要两种关键资源，比如“电力”和“水源”。工厂必须不多不少地消耗掉 5 单位电力和 8 单位水源 。
• 对偶问题 (市场视角):
  • 现在市场上有一个投机商，想直接从你这里购买“电力”和“水源”这两种资源。他为电力出价 $y_1​$ 元/单位，为水源出价 $y_2​$ 元/单位。
  • 投机商的目标是最大化他付给你的总金额 5y₁ + 8y₂ 。
  • 但你需要一个不亏本的理由才肯卖给他。这就引出了对偶问题的约束：
    • 约束1: 2y₁ + 8y₂ ≤ 7 。生产1单位的第1种产品，需要2单位电力和8单位水源。投机商为这些资源出的总价是2y₁ + 8y₂。这个价格不能超过你自己生产第1种产品的成本 7，否则你宁愿自己生产产品1，而不是把资源卖给他。
    • 其他三条约束同理，保证了投机商的出价对于任何一种产品来说都是“有竞争力的”，即不会高到让你觉得卖资源是亏本的。

通过这个故事，对偶问题就从一个纯数学构造，变成了一个有实际意义的“影子价格”问题：在满足不让工厂亏本的前提下，市场愿意为这些生产资源付出的最高价格是多少。

2.对偶单纯形法 (Dual Simplex Algorithm)

2.1 核心思想与动机

检验数的公式是 $\overline{c}=c-A^TA_B^{-T}c_B$ ，标准单纯形法包含这两步：

• 第一步 (保持可行): 在算法的每一步，我们都保证当前的基解 $x_B=A_B^{-1}b$ 是大于等于0的 。这被称为保持原始可行性 (primal feasible)。
• 第二步 (寻找最优): 我们的目标是不断迭代，直到所有的检验数 $\overline{c}$ 都大于等于0 。因为一旦满足这个条件，我们就找到了最优解。

如前文所述，如果我们定义 $y=A_B^{-T}c_B$ ，那么单纯形法的最优性条件 $\overline{c} ≥ 0$ 就完全等价于对偶问题的可行性条件 $A^Ty\leq c$

标准单纯形法，本质上是一个在始终保持“原始可行性”的前提下，努力去达成“对偶可行性”的过程。

现在我们有了两个维度的“可行性”：

• 原始可行性 (Primal Feasibility): 解向量 x 的所有分量都大于等于0 $(x_B=A_B^{-1}b\geq0)$。
• 对偶可行性 (Dual Feasibility): 所有的检验数都大于等于0 $(\overline{c}\geq0)$。

当一个解同时满足这两种可行性时，它就是最优解。

标准单纯形法的策略可以总结为：

• 起点: 找到一个原始可行的解（通过引入人工变量等方法）。
• 过程: 保持原始可行，通过迭代逐步满足对偶可行。
• 终点: 同时达到原始可行和对偶可行。

这就很自然地引出了一个镜像问题：我们能不能设计一个完全相反的算法？

• 起点: 找到一个对偶可行的解（即 $\overline{c}≥0$）。
• 过程: 保持对偶可行，通过迭代逐步满足原始可行。
• 终点: 同时达到原始可行和对偶可行。

2.2 算法步骤与更新规则

与标准单纯形法正好相反：

• 第一步 (保持): 在算法的每一步，我们都保证解是对偶可行 (dual feasible) 的 。这等价于保证单纯形表中所有的检验数（reduced costs）都大于等于0 $(\overline{c}\geq0)$。
• 第二步 (目标): 我们的目标是，通过迭代，使解最终成为原始可行 (primal feasible) 的 。这意味着我们要消除解向量 xB​ 中的所有负数，使其最终满足 $x_B=A_B^{-1}b\geq0$ 。

现在的关键问题是我们需要找到另一种更新基 $B$ 的方法” 。

• 解释: 在标准单纯形法中，我们先根据负的检验数 $c_j​$ 来决定哪个变量入基，再通过最小比率测试来决定哪个变量出基（以保持原始可行性）。
• 现在我们的前提和目标都反过来了，所以选择入基和出基变量的规则也必须改变。旧的规则不再适用，我们需要一套全新的规则来保持对偶可行性。

2.2.1 主元变换规则

出基变量：

如果检查发现 b 中存在负值（例如 $\overline{b}_i<0$），说明当前解还不是原始可行的，我们需要继续迭代 。

我们的目标是消除这些负值。因此，我们选择一个下标 $i$ 对应的负值基变量，作为出基变量 。这个变量所在的行，就是我们接下来要进行主元变换的“主元行”。

第一步：改写原始问题

• 首先将原始问题的约束，从标准的 $Ax=b$ 形式，改写成单纯形表中的“字典”形式：$$x_B+A_B^{-1}A_Nx_N=A_B^{-1}b$$
• 为了简化表达，我们引入两个新符号：
  • $V:=A_B^{-1}A_N$ (代表单纯形表中非基变量对应的矩阵部分)
  • $\overline{b}:=A_B^{-1}b$ (代表单纯形表中解向量那一列)
• 这样，原始问题就等价于求解 $min c^Tx$ ，约束于 $x_B+Vx_N=\overline{b}$ 以及非负条件。

第二步：对改写后的问题求对偶

我们现在不把 $Ax=b$ 看作约束，而是把 $x_B+Vx_N=\overline{b}$ 看作约束。这个约束可以写成矩阵形式：$$(I,V)\begin{pmatrix}x_B\x_N\end{pmatrix}=\overline{b}$$ 我们对这个新的问题形式应用标准的“原始-对偶转换字典”：

• 原始目标: $min c^Tx$ --> 对偶约束右侧:  $c$
• 原始约束右侧: $\overline{b}$ --> 对偶目标: $max \overline{b}^Ty$
• 原始约束矩阵: $(I, V)$ --> 对偶约束矩阵: $(I,V)^T$

这样我们就得到了一个新的对偶问题： $$\max_{y\in\mathbb{R}^m}\overline{b}^Ty$$ $$s.t.(I,V)^Ty\leq c$$

第三步：展开新的对偶约束

• 最后，我们将这个新的对偶约束 $(I,V)^Ty≤c$ 展开成更具体的形式： $$(I,V)^T=\begin{pmatrix}I\V^T\end{pmatrix}$$ $$c=\begin{pmatrix}c_B\c_N\end{pmatrix}$$
• 所以，这个约束等价于两个子约束：

1. $y\leq c_B$
2. $V^Ty\leq c_N$

这个新的对偶形式，为我们揭示了如何在对偶单纯形法的迭代中改进目标函数。因为我们现在的目标是 $\max_{y\in\mathbb{R}^m}\overline{b}^Ty$ ，既然我们知道有一个分量 $b_i​$ 是负数，那么在目标函数 $\overline{b}^Ty=\sum_j\overline{b}_jy_j$​ 中，如果我们能设法减小对应的 $y_i​$ 的值，就能让整个目标函数的值增大

所以，我们有一个与当前基 $B$ 相关的、等价的对偶问题 $max \overline{b}^Ty^{\prime}$ 。

为了简化推导，我们假设我们当前的对偶可行解恰好是 $y=c_{B}$ ，这里这个假设的前提是当初始基 $B$ 是一个单位矩阵时（例如，当所有约束都是 <= 并加入松弛变量时），初始的对偶解 $y=(A_B^{-1})^Tc_B$ 就会简化为 $y=c_B$ 。这里是为了让后续的代数推导更清晰。

我们想要最大化对偶目标 $\overline{b}^Ty^{\prime}$ ，我们发现，这个目标函数中，有一个系数 $b_i​$ 是负数 。

那么，如果我们保持其他 $y_j$​ 不变，只将对应的 $y_i$​ 减小一个正量 $δ$，会发生什么？

$$\underbrace{(y_{1},\ldots,y_{i-1},y_{i}-\delta,y_{i+1},\ldots,y_{m})}{:=(\mathbf{y}^{\mathrm{new}})^{\top}}\bar{\mathbf{b}}=\mathbf{y}^{\top}\bar{\mathbf{b}}-\delta\bar{b}{i}>\mathbf{y}^{\top}\bar{\mathbf{b}}$$ 新的目标函数值 $(y^{new})^T\overline{b}$ 等于旧的目标函数值 $y^T\overline{b}$ 加上了一个正数 $(-\delta\overline{b}_i)$ 。因此，新的目标函数严格地变大了。

我们的新解 $y^{new}$ 不仅要取得更好的目标值，它还必须仍然是对偶可行的。也就是说，它必须继续满足之前推导出的那两个约束：

1. $y^{new} \leq c_B$
2. $V^Ty^{new}\leq c_N$

我们可以把 $y_i​$ 不断减小，但不能减小得太过分，一旦越界导致上述任一约束被打破，我们的解就不再是对偶可行解了。

检查条件(A)

• $y^{new} ≤ c_B$ 是自动成立的。
• 原因: 我们原来的解是 $y=c_B​$。新解 $y^{new}$ 的构造是 $y_i​ \rightarrow y_i​−δ$（其中$\delta>0$），其他分量不变。所以新解的第 $i$ 个分量 $y_i^{new}​ = c_{B_i​​}−δ$ ，这显然小于 $c_{B_i}$​​。其他分量则仍然等于对应的$c_{B_j}$​​。因此，这个约束是满足的。

检查条件(B) 这个条件 $V^Ty' ≤ c_N$ 是一组不等式，需要对每个非基变量 $j$ 进行检查。我们将其分为两种情况：

• 情况一 (安全的列): 对于任何一个 $j$，如果在主元行中的对应元素 $v_{ij}​≥0$，那么约束仍然成立。
  • 原因: 新的约束左侧值 $v_j^Ty^{new}=v_j^Ty-\delta v_{ij}$。因为 $δ>0$ 且 $v_{ij​}≥0$，所以 $−δv_{ij​}≤0$。这意味着新的值比原来的值更小（或相等），而原来的值是满足约束 $v_j^Ty\leq c_j$ 的，所以新的值必然也满足约束。
• 情况二 (危险的列): 对于任何一个 $j$，如果在主元行中的对应元素 $v_{ij​}<0$，那么这个约束就有被打破的风险。
  • 原因: 此时，新的约束左侧值 $\mathrm{}v_j^Ty^{new}=v_j^Ty-\delta v_{ij}$。因为 $δ>0$ 且 $v_{ij}​<0$，所以 $−δv_{ij}​>0$。这意味着新的值比原来的值变大了，有可能就会超过右侧的 $c_j​$。
  • 推导边界: 为了维持对偶可行性，我们必须保证 $v_j^Ty-\delta v_{ij}\leq c_j$。通过简单的代数移项，就可以解出 $δ$ 必须满足的上限：$$\delta=\min_{j\in N:v_{ij}<0}\frac{\overline{c}j}{-v{ij}}$$
• 入基规则: 那个提供了这个最小比率的下标 $j^$，就是入基变量 。我们用 $j^$ 替换掉 $i$，完成基 $B$ 的更新 。

如果我们按照上述规则更新基 $B$，我们得到的新解不仅仍然是对偶可行的，而且其目标函数值也变得更优 。

2.2.2 算法步骤

• 第一步：前提条件
  • 每次迭代开始时，我们都必须处于一个对偶可行的状态 。这意味着，由当前基 $B$ 所决定的检验数行（c）必须全部大于等于0 。
• 第二步：选择出基变量（确定主元行）
  • 计算当前基对应的解 $x_B=A_B^{-1}b$ 。
  • 检查这个解是否原始可行。如果其中存在负值（$x_i​<0$），说明还未达到最优解，我们需要继续迭代 。
  • 我们选择任意一个值为负的基变量 $x_i$​ 作为出基变量 。它所在的行就是主元行。
  • (隐含的终止条件): 如果 $x_B$​ 中没有负值，说明解已经同时满足原始可行和对偶可行，算法终止，当前解即为最优解。
• 第三步：选择入基变量（确定主元列）
  • 这是算法的核心计算步骤。我们需要在主元行中，通过对偶比率测试来确定谁入基 。
  • 规则: $j^*=\arg\min_{j\in N:v_{ij}<0}\frac{\overline{c}j}{-v{ij}}$。
  • 无解条件: 如果在主元行中，所有非基变量的系数 $v_{ij}$​ 都大于等于0，那么问题无解（infeasible），算法终止 。
• 第四步：更新基 (Pivot)
  • 用上一步选出的入基变量 $j^*$ 替换掉出基变量 $i$，完成基 $B$的更新 。然后进行主元变换，回到第一步开始下一次迭代。

在很多对偶单纯形法的实际应用中，我们初始选择的基 $B$ 通常是一个单位矩阵 $I$ 。在这种情况下，对偶解的计算公式 $y=(A_B^{-1})^Tc_B$ 会简化为 $y=c_B$ 。这与之前理论推导中为了简化而做的假设是完全一致的 。

为什么 $B=I$ 的情况很常见？

这通常发生在我们处理带有“大于等于（≥）”约束的最小化问题时。

• 例如，一个约束为：$2x_1​+3x_2​≥5$。
• 为了化为标准型，我们减去一个剩余变量（surplus variable）$s_1​：2x_1​+3x_2​−s_1​=5$。
• 为了在初始单纯形表中凑出单位矩阵，我们通常将整个等式乘以 $-1：−2x_1​−3x_2​+s_1​=−5$。
• 这样，变量 $s_1$​ 就可以作为初始基变量，它在系数矩阵中对应的那一列是 [..., 1, ...] ，可以构成单位矩阵 $I$。
• 此时，它的初始解是 $s_1​=−5$，是原始不可行的。
• 而它的检验数 $c_{s_1}​$ 通常为0，其他原始变量的检验数 $c_j​$ 也常常是非负的，这就构成了一个对偶可行的初始状态。
• 这完美地符合了对偶单纯形法的启动条件，所以我们可以直接开始迭代，而无需像标准单纯形法那样引入人工变量来求解第一阶段。

最终的算法流程对比

2.3 对偶单纯形法的应用场景

算法的选择，取决于我们更容易获得哪种类型的初始解

• 首要原则 (The Main Principle)
  • 对偶单纯形法的优势在于，我们可以很容易地找到一个初始的对偶可行解（即检验数行 $\overline{c} \ge 0$），但不容易找到一个初始的原始可行解（即解向量 $x_B​$ 中没有负值）。
  • 在这种“对偶可行，原始不可行”的起点，对偶单纯形法可以直接开始迭代。而标准单纯形法，则需要先通过引入人工变量进行“第一阶段”计算，来找到一个原始可行解，这会花费额外的计算成本。

1. 常见场景 (Common Scenario)
   • 有一个非常普遍且重要的应用场景：为一个已经求解过的线性规划问题，增加一条新的不等式约束 。
   • 步骤1: 假设我们已经成功求解了一个标准的LP问题，并得到了原始最优解 $x^∗$ 和对偶最优解 $y^∗$ 。此时的解，既是原始可行的，也是对偶可行的。
   • 步骤2: 现在，因为业务需求变化或其他原因，我们需要给问题增加一个新的限制条件 $g^Tx\leq h$ 。

• 我们原来的最优解 $x^∗$ 是在没有新约束的“旧世界”里找到的。当新约束 $g^Tx\leq h$ 加入后，$x^∗$ 不一定会满足这个新规定。
• 很有可能出现 $g^Tx\leq h$ 的情况。如果是这样，那么 $x^∗$ 对于这个“新世界”来说，就是一个不可行的解。
• 我们就失去了原始可行性，无法直接从 $x^∗$ 开始进行标准的单纯形法迭代。

为什么“增加约束”后，对偶可行性还在？

证明如下：

第一步：将新约束标准化

• 我们要增加的新约束是 $g^Tx\leq h$ 为了将其并入标准形式 $Ax=b$ ，我们引入一个松弛变量 $x_{n+1}$​（其成本 $c_{n+1}$​ 设为0）。
• 这样，原始的约束系统 $Ax=b$ 就扩展成了一个更大的分块矩阵系统：$$\begin{pmatrix}A&0\\mathbf{g}^{\top}&1\end{pmatrix}\begin{pmatrix}\mathbf{x}\x_{n+1}\end{pmatrix}=\begin{pmatrix}b\h\end{pmatrix}$$ 第二步：分析可行性
• 原始可行性: 要将原来的最优解 $x^∗$ 修改成满足这个新系统的解，是“不平凡的”（Not trivial）。这通常意味着原来的解$x^∗$ 对于新系统是不可行的，我们失去了一直保持的原始可行性。
• 对偶可行性: 有一个断言，我们可以非常容易地构造一个新问题的对偶可行解。
  • 这个新的对偶解就是 $\binom{y^}{0}$ ，即保持旧的对偶最优解 y∗ 不变，并为新增的约束添加一个值为0的对偶变量 。$$\begin{pmatrix}A^\top&\mathbf{g}\0&1\end{pmatrix}\begin{pmatrix}\mathbf{y}^\0\end{pmatrix}\leq\begin{pmatrix}\mathbf{c}\0\end{pmatrix}$$
  • 新问题的对偶约束是 $A_{new}^Ty_{new}\leq c_{new}$ ，代入后我们检查：
  • 上半部分: $:A^Ty^+g\cdot0=A^Ty^$。因为 $y^∗$ 是原问题的最优解，所以它必然满足 $A^Ty^∗≤c$。此部分约束满足。
  • 下半部分: $0^Ty^*+1\cdot0=0$。而新松弛变量的成本是 $c_{n+1}​=0$，所以约束是 $0≤0$。此部分约束也满足。
  • 所以，构造的这个新对偶解是可行的。

既然我们有了一个对偶可行但（很可能）原始不可行的初始状态，我们就可以直接使用对偶单纯形法来求解，这通常比从头开始要快得多 。

这个过程在单纯形表中的操作非常直观：

• 我们拿出原来问题最优的、最后那张单纯形表。
• 为了表示新约束 $g^Tx+x_{n+1}=h$，我们在表的中间增加新的一行，并为了新变量 $x_{n+1}$​ 在右侧增加新的一列。
• 此时，表的检验数行（最底行）仍然是全部非负的，即对偶可行性得到了保持。
• 但是，新增加的那一行可能不满足基的形式（比如，原来基变量所在的列在新行中不是0）。我们需要进行一些行变换，将这些非零元消掉。
• 消元后，新行的解（在SOL列的值）很可能会变成一个负数。这就造成了原始不可行性。
• 现在我们得到的这个新单纯形表，完美地符合了对偶单纯形法的启动条件，可以直接开始迭代求解。

整数规划中的“割平面法”

这张幻灯片提到的整数规划，其核心算法之一就是割平面法 (Cutting-Plane Method)，该方法完美地诠释了对偶单纯形法的威力：

• 第一步 (LP松弛): 先忽略所有变量必须是整数的要求，求解一个普通的线性规划问题。
• 第二步 (检查解): 如果解恰好是整数，那么我们找到了最优解。但更常见的情况是，解是小数，例如 $x_1​=3.5$。
• 第三步 (增加约束/“切割”): 我们增加一条新的约束，这条约束被称为“割平面”。它的作用是“切掉”当前这个小数解（使 $x_1​=3.5$ 变得不可行），但不会切掉任何可能的整数解。例如，我们可以增加一条约束 $x_1​≤3$。
• 第四步 (重新求解): 我们现在有了一个增加了新约束的LP问题。此时，正是对偶单纯形法大显身手的时刻。我们用它从上一步的最优解快速迭代，得到新的最优解。
• 循环: 不断重复第2到第4步，像“剥洋葱”一样，一层一层地切割，直到找到一个整数解。

2.4 单纯形表 (Tableaux) 实现

对于一个标准的、已经通过若干步迭代得到的单纯形表，有如下结构：

• 基变量: $x_{i_1},...,x_{i_m}$​​ 所在的列构成了单位矩阵。
• 解 (SOL): 右侧的 $SOL$ 列给出了当前基变量的值。
• 检验数: 最下面一行给出了非基变量的检验数 $\overline{c}_j$。
• 目标函数值: 右下角的值是当前目标函数的相反数 $(-c_B^TA_B^{-1}b)$。

对偶单纯形法的每一次迭代都遵循以下四个步骤：

1. 第一步：检查最优性
   • 操作: 查看 $SOL$ 列的所有数值。
   • 判断: 如果所有的值都大于等于0，说明当前解既是原始可行的（本步检查结果），又是对偶可行的（算法前提，即最底行非负），因此这就是最优解，算法结束 。
2. 第二步：检查原始问题是否无解
   • 操作: 如果 $SOL$ 列中存在负值，选择任意一个负值 $x_i​<0$ 所在的行作为主元行 。然后，查看这一行中所有非基变量列的系数 $v_{ij}$​。
   • 判断: 如果这一行所有的 $v_{ij}$​ 都大于等于0，那么原始问题无解 (infeasible)，算法结束 。
3. 第三步：确定入基变量（主元列）
   • 操作: 如果主元行中存在系数 $v_{ij}​<0$，我们就需要进行对偶比率测试来找到入基变量。
   • 规则: 仅对那些 $v_{ij}​<0$ 的列，计算比率 $\overline{c}j/(-v{ij})$。选择使这个比率最小的列 $j$ 作为主元列 。
4. 第四步：进行主元变换 (Pivot)
   • 操作: 以主元行和主元列交叉处的元素 $v_{ij}$​ 为主元，进行一次标准的高斯-若尔当消元 。
   • 目的: 这次操作会将主元列变换成一个单位向量，从而完成出基变量和入基变量的交换，得到一张新的单纯形表 。然后，返回第一步，开始新一轮的迭代。

2.5 布兰德规则 (Bland's Rule)

Bland's Rule 包含两个部分的“最小索引”原则 ：

1. 选择出基变量 (确定主元行): 如果在解向量 $SOL$ 列中，有多个基变量的值为负，我们必须选择那个变量下标最小的作为出基变量 。例如，如果$x_5​$ 和 $x_2​$ 的值都是负数，因为 2<5，我们必须选择 $x_2$​ 所在的行作为主元行。
2. 选择入基变量 (确定主元列): 在确定主元行后，我们进行对偶比率测试。如果有多列同时得到了最小比率，我们必须选择那个变量下标最小的列作为主元列 。例如，如果 $x_1$​ 和 $x_4$​ 所在列的比率都是最小的，因为 1<4，我们必须选择 $x_1$​ 入基 。