单纯形法

字数 2435 2025-10-30 11:52:44

单纯形法

单纯形法是一种求解线性规划问题的经典算法。我将从线性规划的基本概念开始，逐步引导你理解单纯形法的原理和步骤。

线性规划的标准形式
首先，我们需要将任何线性规划问题转化为标准形式，这是应用单纯形法的前提。标准形式要求：
- 目标函数为最大化。
- 所有约束条件（除决策变量非负约束外）均为等式。
- 所有决策变量的取值均为非负。
其数学表达式为：
Maximize \(z = c_1x_1 + c_2x_2 + \dots + c_nx_n\)
Subject to:
\(a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1\)
\(a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2\)
\(\vdots\)
\(a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m\)
\(x_1, x_2, \dots, x_n \ge 0\)
其中，\(b_i \ge 0\)（可以通过等式两边乘以-1来保证）。

对于“≤”约束，我们通过添加一个松弛变量将其变为等式。对于“≥”约束，我们通过减去一个剩余变量并添加一个人工变量来处理（这部分属于两阶段法或大M法，是单纯形法的扩展）。
基本概念：基、基变量、基本可行解
假设我们有m个约束方程和n个决策变量（n > m）。在标准形式中，我们总可以找到一组由m个变量构成的集合，这组变量被称为基。基中的变量称为基变量，不在基中的变量称为非基变量。
- 基本解：令所有非基变量的值为0，然后通过求解由m个等式约束构成的方程组得到的解，称为一个基本解。

基本可行解：如果一个基本解同时满足所有变量的非负约束（即 \(x_i \ge 0\)），那么这个解就是一个基本可行解。

一个关键的几何洞察是：线性规划问题的可行域是一个凸多面体，而每个基本可行解恰好对应这个凸多面体的一个顶点（极点）。

单纯形法的核心思想
单纯形法的基本思想源于线性规划的基本定理：如果一个问题有最优解，那么至少有一个最优解是基本可行解（即顶点）。
因此，算法不需要在可行域内部无穷多个点中搜索，而只需要在有限个顶点（基本可行解）中进行搜索。单纯形法的步骤可以概括为：
- 初始化：找到一个初始的基本可行解（即一个顶点）。
- 最优性检验：判断当前的基本可行解是否是最优解。
- 迭代移动：如果不是最优解，就按照一定规则，移动到另一个相邻的、能使目标函数值改善（增大，对于最大化问题）的基本可行解（顶点）。
  这个过程反复进行，直到找到最优解，或者确定问题无界（目标函数值可以无限增大）。
单纯形表
为了高效地实现上述思想，我们使用单纯形表作为计算工具。它是一个表格，清晰地展示了当前解、目标函数值以及如何迭代的信息。
假设我们将线性规划问题写成增广矩阵的形式：

\[ \begin{array}{cccccc|c} x_1 & x_2 & \dots & x_n & s_1 & s_2 & \dots & RHS \\ \hline a_{11} & a_{12} & \dots & a_{1n} & 1 & 0 & \dots & b_1 \\ a_{21} & a_{22} & \dots & a_{2n} & 0 & 1 & \dots & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} & 0 & 0 & \dots & b_m \\ \hline -c_1 & -c_2 & \dots & -c_n & 0 & 0 & \dots & 0 \\ \end{array} \]

最后一行是目标函数的系数的相反数，称为**检验数行**。

单纯形法的步骤（以最大化为目标）
- 步骤1：建立初始单纯形表。 确保右下角值为0（当前目标函数值），并且存在一个单位矩阵作为初始基（例如，松弛变量构成的基）。
- 步骤2：最优性检验。 检查检验数行（最后一行）中所有非基变量对应的系数（检验数）。
  - 如果所有检验数都非负（≥ 0），那么当前的基本可行解就是最优解。计算结束。
  - 否则，选择最负的检验数对应的非基变量作为进基变量（这个变量将从0变为正值，有望改善目标函数）。
- 步骤3：确定离基变量。 查看进基变量所在的列（主元列）。
  - 如果主元列中所有元素都 ≤ 0，则问题无界，目标函数值可以无限增大。
  - 否则，对主元列中每个正的元素，计算其对应的右端项（RHS）与该元素的比值。选择比值最小的那一行所对应的基变量作为离基变量（这个变量将变为0）。这个比值准则保证了迭代后的解仍然是可行的（所有变量非负）。
- 步骤4：枢轴运算。 离基变量所在的行称为主元行，主元行和主元列交叉的元素称为主元。进行行初等变换（高斯-约当消元法），使得：
  1. 主元变为1。
  2. 主元列的其他所有元素（包括检验数行）变为0。
- 步骤5：迭代。 完成枢轴运算后，得到一张新的单纯形表，代表了一个新的基本可行解。返回步骤2。
这个过程持续进行，直到满足步骤2中的最优性条件（或发现无界）。

总结：单纯形法是一种顶点迭代算法。它从可行域的一个顶点（基本可行解）出发，沿着可行域的边，迭代地移动到能使目标函数改善的相邻顶点，直至找到最优顶点。单纯形表是执行这种迭代的高效计算工具。虽然理论上存在最坏情况是指数时间复杂度，但在实际应用中，它对于大规模线性规划问题通常非常有效。

单纯形法单纯形法是一种求解线性规划问题的经典算法。我将从线性规划的基本概念开始，逐步引导你理解单纯形法的原理和步骤。线性规划的标准形式首先，我们需要将任何线性规划问题转化为标准形式，这是应用单纯形法的前提。标准形式要求：目标函数为最大化。所有约束条件（除决策变量非负约束外）均为等式。所有决策变量的取值均为非负。其数学表达式为： Maximize \( z = c_ 1x_ 1 + c_ 2x_ 2 + \dots + c_ nx_ n \) Subject to: \( a_ {11}x_ 1 + a_ {12}x_ 2 + \dots + a_ {1n}x_ n = b_ 1 \) \( a_ {21}x_ 1 + a_ {22}x_ 2 + \dots + a_ {2n}x_ n = b_ 2 \) \( \vdots \) \( a_ {m1}x_ 1 + a_ {m2}x_ 2 + \dots + a_ {mn}x_ n = b_ m \) \( x_ 1, x_ 2, \dots, x_ n \ge 0 \) 其中，\( b_ i \ge 0 \)（可以通过等式两边乘以-1来保证）。对于“≤”约束，我们通过添加一个松弛变量将其变为等式。对于“≥”约束，我们通过减去一个剩余变量并添加一个人工变量来处理（这部分属于两阶段法或大M法，是单纯形法的扩展）。基本概念：基、基变量、基本可行解假设我们有m个约束方程和n个决策变量（n > m）。在标准形式中，我们总可以找到一组由m个变量构成的集合，这组变量被称为基。基中的变量称为基变量，不在基中的变量称为非基变量。基本解：令所有非基变量的值为0，然后通过求解由m个等式约束构成的方程组得到的解，称为一个基本解。基本可行解：如果一个基本解同时满足所有变量的非负约束（即 \( x_ i \ge 0 \)），那么这个解就是一个基本可行解。一个关键的几何洞察是：线性规划问题的可行域是一个凸多面体，而每个基本可行解恰好对应这个凸多面体的一个顶点（极点）。单纯形法的核心思想单纯形法的基本思想源于线性规划的基本定理：如果一个问题有最优解，那么至少有一个最优解是基本可行解（即顶点）。因此，算法不需要在可行域内部无穷多个点中搜索，而只需要在有限个顶点（基本可行解）中进行搜索。单纯形法的步骤可以概括为：初始化：找到一个初始的基本可行解（即一个顶点）。最优性检验：判断当前的基本可行解是否是最优解。迭代移动：如果不是最优解，就按照一定规则，移动到另一个相邻的、能使目标函数值改善（增大，对于最大化问题）的基本可行解（顶点）。这个过程反复进行，直到找到最优解，或者确定问题无界（目标函数值可以无限增大）。单纯形表为了高效地实现上述思想，我们使用单纯形表作为计算工具。它是一个表格，清晰地展示了当前解、目标函数值以及如何迭代的信息。假设我们将线性规划问题写成增广矩阵的形式： \[ \begin{array}{cccccc|c} x_ 1 & x_ 2 & \dots & x_ n & s_ 1 & s_ 2 & \dots & RHS \\ \hline a_ {11} & a_ {12} & \dots & a_ {1n} & 1 & 0 & \dots & b_ 1 \\ a_ {21} & a_ {22} & \dots & a_ {2n} & 0 & 1 & \dots & b_ 2 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_ {m1} & a_ {m2} & \dots & a_ {mn} & 0 & 0 & \dots & b_ m \\ \hline -c_ 1 & -c_ 2 & \dots & -c_ n & 0 & 0 & \dots & 0 \\ \end{array} \] 最后一行是目标函数的系数的相反数，称为检验数行。单纯形法的步骤（以最大化为目标）步骤1：建立初始单纯形表。确保右下角值为0（当前目标函数值），并且存在一个单位矩阵作为初始基（例如，松弛变量构成的基）。步骤2：最优性检验。检查检验数行（最后一行）中所有非基变量对应的系数（检验数）。如果所有检验数都非负（≥ 0），那么当前的基本可行解就是最优解。计算结束。否则，选择最负的检验数对应的非基变量作为进基变量（这个变量将从0变为正值，有望改善目标函数）。步骤3：确定离基变量。查看进基变量所在的列（主元列）。如果主元列中所有元素都 ≤ 0，则问题无界，目标函数值可以无限增大。否则，对主元列中每个正的元素，计算其对应的右端项（RHS）与该元素的比值。选择比值最小的那一行所对应的基变量作为离基变量（这个变量将变为0）。这个比值准则保证了迭代后的解仍然是可行的（所有变量非负）。步骤4：枢轴运算。离基变量所在的行称为主元行，主元行和主元列交叉的元素称为主元。进行行初等变换（高斯-约当消元法），使得：主元变为1。主元列的其他所有元素（包括检验数行）变为0。步骤5：迭代。完成枢轴运算后，得到一张新的单纯形表，代表了一个新的基本可行解。返回步骤2。这个过程持续进行，直到满足步骤2中的最优性条件（或发现无界）。总结：单纯形法是一种顶点迭代算法。它从可行域的一个顶点（基本可行解）出发，沿着可行域的边，迭代地移动到能使目标函数改善的相邻顶点，直至找到最优顶点。单纯形表是执行这种迭代的高效计算工具。虽然理论上存在最坏情况是指数时间复杂度，但在实际应用中，它对于大规模线性规划问题通常非常有效。