1. 单纯形法基础概念
单纯形法是解决线性规划问题的经典算法，由美国数学家乔治·丹齐格于1947年提出。它的核心思想是通过迭代的方式，在可行域的顶点（即基可行解）之间移动，逐步逼近最优解。想象一下，你在一片多边形的森林里寻找最高点，单纯形法就像沿着山脊一步步攀登，直到找到顶峰。
单纯形法的数学基础建立在三个关键定理上：
- 凸集定理：线性规划的可行域一定是凸集
- 顶点对应定理：基可行解对应可行域的顶点
- 最优解存在定理：如果存在最优解，必定能在基可行解中找到
在实际应用中，我们通常会将问题转化为标准型：
- 目标函数求最大值
- 约束条件均为等式
- 决策变量非负
例如，将不等式约束2x₁ + x₂ ≤ 40转化为标准型时，需要添加松弛变量x₃，得到2x₁ + x₂ + x₃ = 40，其中x₃ ≥ 0。
2. 单纯形表构建与初始化
单纯形表是单纯形法的核心工具，它将所有计算信息整合在一张表格中。以一个实际生产问题为例：
假设某工厂生产两种产品，目标函数为：
max Z = 3x₁ + 4x₂受限于资源约束：
2x₁ + x₂ ≤ 40 x₁ + 3x₂ ≤ 30 x₁, x₂ ≥ 0构建步骤：
引入松弛变量x₃、x₄，转化为标准型：
max Z = 3x₁ + 4x₂ + 0x₃ + 0x₄ s.t. 2x₁ + x₂ + x₃ = 40 x₁ + 3x₂ + x₄ = 30初始化单纯形表：
| Cⱼ | 3 | 4 | 0 | 0 |
|---|---|---|---|---|
| C_B 基变量 | b | x₁ | x₂ | x₃ |
| 0 x₃ | 40 | 2 | 1 | 1 |
| 0 x₄ | 30 | 1 | 3 | 0 |
| σⱼ | 3 | 4 | 0 |
关键元素解析：
- 基变量：初始选择松弛变量x₃、x₄
- 检验数σⱼ：计算公式为σⱼ = cⱼ - Σcᵢaᵢⱼ
- θ列：用于确定出基变量，初始可留空
3. 迭代过程详解
第一次迭代：
入基变量选择：选择检验数最大的非基变量x₂（σ₂=4）
出基变量确定：
- 计算θ比值：θ₃=40/1=40，θ₄=30/3=10
- 选择最小正值θ₄=10，对应x₄出基
行变换：
- 将x₂的系数列变为[0,1]ᵀ
- 对第二行进行归一化：(x₁ + 3x₂ + x₄ = 30) ÷ 3
- 用第一行减去新第二行的适当倍数消去x₂
变换后的单纯形表：
| Cⱼ | 3 | 4 | 0 | 0 |
|---|---|---|---|---|
| C_B 基变量 | b | x₁ | x₂ | x₃ |
| 0 x₃ | 30 | 5/3 | 0 | 1 |
| 4 x₂ | 10 | 1/3 | 1 | 0 |
| σⱼ | 5/3 | 0 | 0 |
最优解判定：检验数σ₁=5/3 > 0，需要继续迭代
第二次迭代：
- 入基变量选择x₁（σ₁=5/3）
- 出基变量计算θ：θ₃=30/(5/3)=18，θ₂=10/(1/3)=30
- 选择x₃出基，进行行变换
最终单纯形表：
| Cⱼ | 3 | 4 | 0 | 0 |
|---|---|---|---|---|
| C_B 基变量 | b | x₁ | x₂ | x₃ |
| 3 x₁ | 18 | 1 | 0 | 3/5 |
| 4 x₂ | 4 | 0 | 1 | -1/5 |
| σⱼ | 0 | 0 | -1 |
此时所有检验数≤0，得到最优解：
- x₁=18，x₂=4
- 最大利润Z=3×18 + 4×4=70
4. 特殊情况处理
退化现象：当基变量取值为0时，可能出现迭代循环。解决方法包括：
- 布兰德规则：按字典序选择入基和出基变量
- 扰动法：对约束条件进行微小扰动
无界解识别：当存在检验数>0且对应系数列全部≤0时，目标函数值可以无限增大。例如：
max Z = x₁ + x₂ s.t. x₁ - x₂ ≤ 1 -x₁ + x₂ ≤ 1当选择x₂入基时，其系数列为[-1,1]ᵀ，θ计算会出现无限大。
多重最优解：当非基变量检验数为0时，存在多个最优解。例如将目标函数改为Z=3x₁+3x₂时，最终表中x₃的检验数为0，表示可以构造无穷多最优解。
5. 实际应用技巧
避免计算错误的三个关键检查点：
- 每次迭代后，基变量的系数矩阵应是单位阵
- 检验数σⱼ应满足cⱼ - C_B·B⁻¹·Aⱼ = 0（对基变量）
- 常数项b列应始终保持非负
提高计算效率的方法：
- 修正单纯形法：只存储和计算必要的矩阵部分
- 产品形式逆：避免每次迭代都重新计算逆矩阵
- 使用稀疏矩阵技术处理大规模问题
常见误区警示：
- 忽略标准型转换时松弛变量的符号（≤加松弛，≥减剩余）
- 选择入基变量时只看绝对值而忽略符号
- 在θ计算中未排除分母≤0的情况
我在实际项目中曾遇到一个典型错误案例：在处理最小化问题时，误将检验数符号判断标准与最大化问题混淆，导致算法无法收敛。经过仔细检查单纯形表构造规则后才发现问题所在。这也提醒我们，建立标准的计算流程检查表非常重要。
