线性规划中的对偶单纯形法（Dual Simplex Method in Linear Programming）
字数 3444 2025-12-14 10:33:05

线性规划中的对偶单纯形法（Dual Simplex Method in Linear Programming）

接下来，我将为你详细讲解“对偶单纯形法”。为了确保你能够循序渐进地理解，我将分步骤讲解，每个步骤都会细致准确地解释其原理和操作。

第一步：为什么需要对偶单纯形法？—— 回顾单纯形法与对偶理论

首先，我们回顾一下你已经知道的单纯形法。它是求解标准线性规划问题的主要方法，形式通常为：

  • 原始问题（P）：最小化 \(c^T x\)，满足 \(Ax = b, x \geq 0\)。
    单纯形法从一个基本可行解开始，在满足 \(x \geq 0\)（原始可行性）和 \(Ax=b\)（等式约束）的前提下，沿着可行域的顶点移动，逐步改进目标函数值，直至最优。

然而，在实践中有一种常见情况：我们可能很容易找到一个对偶可行解，但难以找到初始的原始可行解。

  • 对偶问题（D）：最大化 \(b^T y\)，满足 \(A^T y + s = c, s \geq 0\)（其中 \(y\) 是对偶变量，\(s\) 是对偶松弛变量）。
  • 对偶可行性：在单纯形表的表述中，它对应于所有检验数（Reduced Costs） \(\bar{c}_j = c_j - c_B^T B^{-1} A_j \leq 0\)（对于最小化问题）。这意味着当前解满足对偶问题的约束 \(s \geq 0\)，但其对应的原始变量可能不满足 \(x \geq 0\)，即原始不可行。

对偶单纯形法正是为解决这种场景而设计的。它的核心思想是：保持对偶可行性（即检验数 ≤ 0），通过迭代逐步消除原始不可行性（即使得所有基变量 ≥ 0）。当同时达到原始可行和对偶可行时，就得到了原始问题和对偶问题的最优解。

第二步：对偶单纯形法的标准形式与初始表

考虑线性规划问题：
Minimize \(c^T x\)
Subject to: \(Ax = b, x \geq 0\).

假设我们已经通过某种方式（比如增加人工变量后优化到对偶可行，或者在求解参数规划、整数规划的割平面时）得到了一个对偶可行基。这意味着对应的单纯形表具有以下特征：

  1. 基变量（BV） 部分：其取值 \(\bar{b} = B^{-1}b\) 中可能含有负分量（即原始不可行）。
  2. 检验数行：所有 \(\bar{c}_j \leq 0\)（对偶可行）。
    初始表看起来像是“最优”的（因为检验数满足最优性条件），但并不可行（因为基变量有负值）。这就是对偶单纯形法的起点。

第三步：对偶单纯形法的迭代步骤（核心算法）

每一步迭代都从一个对偶可行但原始不可行的基本解开始。步骤如下：

  1. 确定离基变量（Leaving Variable）：
  • 在当前基变量中，找到取值最负的那个变量。设其为 \(x_{Br}\)（第 \(r\) 个基变量），其值为 \(\bar{b}_r < 0\)。
  • 对应的行称为 枢轴行（Pivot Row） \(r\)。如果所有 \(\bar{b}_i \geq 0\)，则解已原始可行，达到最优，算法终止。
  1. 确定进基变量（Entering Variable）：
  • 检查枢轴行 \(r\) 中所有非基变量列的系数 \(a_{rj}\)（在单纯形表中是 \(\bar{A}_{rj}\)）。
  • 规则：对于所有满足 \(a_{rj} < 0\) 的列 \(j\)（因为需要维持对偶可行性），计算比值：\(\theta_j = \bar{c}_j / a_{rj}\)。由于 \(\bar{c}_j \leq 0\) 且 \(a_{rj} < 0\)，所以 \(\theta_j \geq 0\)。
  • 选择 \(\theta_j\) 最小（即绝对值最大，因为比值本身是非负的）的那个非基变量作为进基变量 \(x_k\)。
  • 原理：这个最小比值测试保证了当进行枢轴运算后，所有新的检验数 \(\bar{c}_j'\) 仍然保持 ≤ 0（即对偶可行性得以维持）。如果枢轴行中所有 \(a_{rj} \geq 0\)，则问题原始无可行解（对偶问题无界）。
  1. 枢轴运算（Pivot Operation）：
  • 以 \(a_{rk}\)（枢轴行 \(r\) 与进基变量列 \(k\) 的交点）为枢轴元（Pivot Element），执行与原始单纯形法完全相同的高斯-乔丹行变换。
  • 这一操作将离基变量 \(x_{Br}\) 换出基，将进基变量 \(x_k\) 换入基，更新整个单纯形表，包括基变量值和检验数行。
  1. 迭代：
    • 得到新的单纯形表后，返回步骤1。经过一次枢轴，至少那个最负的基变量会离基，新的基变量值可能仍然为负，但通常不可行性会得到改善或重新分布。算法持续进行，直到所有基变量非负。

第四步：一个简单的数值例子

考虑问题：
Minimize \(z = 3x_1 + 4x_2\)
Subject to:
\(x_1 + x_2 \geq 4\)
\(x_1 + 3x_2 \geq 6\)
\(x_1, x_2 \geq 0\)

引入剩余变量 \(x_3, x_4 \leq 0\) 将其转化为等式： \(-x_1 - x_2 + x_3 = -4\)， \(-x_1 - 3x_2 + x_4 = -6\)。令 \(x_3, x_4\) 为基变量，初始表为：

基 \(x_1\) \(x_2\) \(x_3\) \(x_4\) RHS
\(z\) -3 -4 0 0 0
\(x_3\) -1 -1 1 0 -4
\(x_4\) -1 -3 0 1 -6
  • 检验数行 \(\bar{c} = [-3, -4, 0, 0] \leq 0\)，对偶可行。
  • 基变量值 \((-4, -6) < 0\)，原始不可行。
  • 迭代1：
  • 离基变量：最负的RHS是 \(x_4 = -6\)（行2）。
  • 进基变量：行2中 \(a_{2j} < 0\) 的列是 \(x_1(-1)\) 和 \(x_2(-3)\)。计算比值：\(\theta_1 = (-3)/(-1) = 3\)， \(\theta_2 = (-4)/(-3) = 4/3\)。最小比值是 \(4/3\)，对应 \(x_2\) 进基。
  • 以 \(-3\) 为枢轴元进行旋转。
  • 迭代后得到新表（过程略），继续直到所有RHS非负。最终最优解为 \(x_1=3, x_2=1, z=13\)。

第五步：对偶单纯形法的优势与应用场景

  1. 添加新约束（如割平面）：在整数规划的分支定界或割平面法中，给松弛问题加入新的约束后，原最优解可能不再可行，但对偶可行性往往得以保持。此时使用对偶单纯形法从“对偶可行、原始不可行”的基点开始恢复最优性，比从头用原始单纯形法重启更高效。
  2. 灵敏度分析与参数规划：当约束的右端项 \(b\) 发生变化时，原始可行性可能被破坏，但对偶可行性通常不变，适合用对偶单纯形法重新优化。
  3. 求解上界约束或设置变量界：处理有上界约束的变量时，对偶单纯形法有特别高效的变形。
  4. 初始对偶可行基易得：对于某些形式的问题（如最小成本流问题的对偶），构造一个初始对偶可行基比构造原始可行基更容易。

总结：对偶单纯形法是原始单纯形法在对偶空间中的镜像。它通过保持对偶可行性，迭代修复原始可行性来求解线性规划。其核心迭代步骤包括选择最负的基变量离基，并通过一个最小比值测试选择进基变量以维持对偶可行性。它是运筹学中处理一系列高级优化问题（尤其是整数规划和灵敏度分析）不可或缺的工具。

线性规划中的对偶单纯形法（Dual Simplex Method in Linear Programming） 接下来，我将为你详细讲解“对偶单纯形法”。为了确保你能够循序渐进地理解，我将分步骤讲解，每个步骤都会细致准确地解释其原理和操作。 第一步：为什么需要对偶单纯形法？—— 回顾单纯形法与对偶理论 首先，我们回顾一下你已经知道的 单纯形法 。它是求解标准线性规划问题的主要方法，形式通常为： 原始问题（P） ：最小化 \( c^T x \)，满足 \( Ax = b, x \geq 0 \)。 单纯形法从一个 基本可行解 开始，在满足 \( x \geq 0 \)（原始可行性）和 \( Ax=b \)（等式约束）的前提下，沿着可行域的顶点移动，逐步改进目标函数值，直至最优。 然而，在实践中有一种常见情况：我们可能很容易找到一个 对偶可行解 ，但难以找到初始的 原始可行解 。 对偶问题（D） ：最大化 \( b^T y \)，满足 \( A^T y + s = c, s \geq 0 \)（其中 \( y \) 是对偶变量，\( s \) 是对偶松弛变量）。 对偶可行性 ：在单纯形表的表述中，它对应于所有 检验数（Reduced Costs） \( \bar{c}_ j = c_ j - c_ B^T B^{-1} A_ j \leq 0 \)（对于最小化问题）。这意味着当前解满足对偶问题的约束 \( s \geq 0 \)，但其对应的原始变量可能不满足 \( x \geq 0 \)，即原始不可行。 对偶单纯形法 正是为解决这种场景而设计的。它的核心思想是： 保持对偶可行性（即检验数 ≤ 0），通过迭代逐步消除原始不可行性（即使得所有基变量 ≥ 0） 。当同时达到原始可行和对偶可行时，就得到了原始问题和对偶问题的最优解。 第二步：对偶单纯形法的标准形式与初始表 考虑线性规划问题： Minimize \( c^T x \) Subject to: \( Ax = b, x \geq 0 \). 假设我们已经通过某种方式（比如增加人工变量后优化到对偶可行，或者在求解参数规划、整数规划的割平面时）得到了一个 对偶可行基 。这意味着对应的单纯形表具有以下特征： 基变量（BV） 部分：其取值 \( \bar{b} = B^{-1}b \) 中可能含有负分量（即原始不可行）。 检验数行 ：所有 \( \bar{c}_ j \leq 0 \)（对偶可行）。 初始表看起来像是“最优”的（因为检验数满足最优性条件），但并不可行（因为基变量有负值）。这就是对偶单纯形法的起点。 第三步：对偶单纯形法的迭代步骤（核心算法） 每一步迭代都从一个对偶可行但原始不可行的基本解开始。步骤如下： 确定离基变量（Leaving Variable） ： 在当前基变量中，找到 取值最负 的那个变量。设其为 \( x_ {Br} \)（第 \( r \) 个基变量），其值为 \( \bar{b}_ r < 0 \)。 对应的行称为 枢轴行（Pivot Row） \( r \)。如果所有 \( \bar{b}_ i \geq 0 \)，则解已原始可行，达到最优，算法终止。 确定进基变量（Entering Variable） ： 检查枢轴行 \( r \) 中所有 非基变量列 的系数 \( a_ {rj} \)（在单纯形表中是 \( \bar{A}_ {rj} \)）。 规则：对于所有满足 \( a_ {rj} < 0 \) 的列 \( j \)（因为需要维持对偶可行性），计算比值：\( \theta_ j = \bar{c} j / a {rj} \)。由于 \( \bar{c} j \leq 0 \) 且 \( a {rj} < 0 \)，所以 \( \theta_ j \geq 0 \)。 选择 \( \theta_ j \) 最小 （即绝对值最大，因为比值本身是非负的）的那个非基变量作为进基变量 \( x_ k \)。 原理 ：这个最小比值测试保证了当进行枢轴运算后，所有新的检验数 \( \bar{c} j' \) 仍然保持 ≤ 0（即对偶可行性得以维持）。如果枢轴行中所有 \( a {rj} \geq 0 \)，则问题原始无可行解（对偶问题无界）。 枢轴运算（Pivot Operation） ： 以 \( a_ {rk} \)（枢轴行 \( r \) 与进基变量列 \( k \) 的交点）为 枢轴元（Pivot Element） ，执行与原始单纯形法完全相同的 高斯-乔丹行变换 。 这一操作将离基变量 \( x_ {Br} \) 换出基，将进基变量 \( x_ k \) 换入基，更新整个单纯形表，包括基变量值和检验数行。 迭代 ： 得到新的单纯形表后，返回步骤1。经过一次枢轴，至少那个最负的基变量会离基，新的基变量值可能仍然为负，但通常不可行性会得到改善或重新分布。算法持续进行，直到所有基变量非负。 第四步：一个简单的数值例子 考虑问题： Minimize \( z = 3x_ 1 + 4x_ 2 \) Subject to: \( x_ 1 + x_ 2 \geq 4 \) \( x_ 1 + 3x_ 2 \geq 6 \) \( x_ 1, x_ 2 \geq 0 \) 引入剩余变量 \( x_ 3, x_ 4 \leq 0 \) 将其转化为等式： \( -x_ 1 - x_ 2 + x_ 3 = -4 \)， \( -x_ 1 - 3x_ 2 + x_ 4 = -6 \)。令 \( x_ 3, x_ 4 \) 为基变量，初始表为： | 基 | \(x_ 1\) | \(x_ 2\) | \(x_ 3\) | \(x_ 4\) | RHS | | :-- | :----: | :----: | :----: | :----: | :-: | | \(z\) | -3 | -4 | 0 | 0 | 0 | | \(x_ 3\)| -1 | -1 | 1 | 0 | -4 | | \(x_ 4\)| -1 | -3 | 0 | 1 | -6 | 检验数行 \( \bar{c} = [ -3, -4, 0, 0] \leq 0 \)， 对偶可行 。 基变量值 \( (-4, -6) < 0 \)， 原始不可行 。 迭代1 ： 离基变量：最负的RHS是 \( x_ 4 = -6 \)（行2）。 进基变量：行2中 \( a_ {2j} < 0 \) 的列是 \( x_ 1(-1) \) 和 \( x_ 2(-3) \)。计算比值：\( \theta_ 1 = (-3)/(-1) = 3 \)， \( \theta_ 2 = (-4)/(-3) = 4/3 \)。最小比值是 \( 4/3 \)，对应 \( x_ 2 \) 进基。 以 \( -3 \) 为枢轴元进行旋转。 迭代后得到新表（过程略），继续直到所有RHS非负。最终最优解为 \( x_ 1=3, x_ 2=1, z=13 \)。 第五步：对偶单纯形法的优势与应用场景 添加新约束（如割平面） ：在整数规划的分支定界或割平面法中，给松弛问题加入新的约束后，原最优解可能不再可行，但对偶可行性往往得以保持。此时使用对偶单纯形法从“对偶可行、原始不可行”的基点开始恢复最优性，比从头用原始单纯形法重启更高效。 灵敏度分析与参数规划 ：当约束的右端项 \( b \) 发生变化时，原始可行性可能被破坏，但对偶可行性通常不变，适合用对偶单纯形法重新优化。 求解上界约束或设置变量界 ：处理有上界约束的变量时，对偶单纯形法有特别高效的变形。 初始对偶可行基易得 ：对于某些形式的问题（如最小成本流问题的对偶），构造一个初始对偶可行基比构造原始可行基更容易。 总结 ：对偶单纯形法是原始单纯形法在对偶空间中的镜像。它通过 保持对偶可行性，迭代修复原始可行性 来求解线性规划。其核心迭代步骤包括选择最负的基变量离基，并通过一个最小比值测试选择进基变量以维持对偶可行性。它是运筹学中处理一系列高级优化问题（尤其是整数规划和灵敏度分析）不可或缺的工具。