单纯形法Simplex Method
单纯形法（Simplex Method） 是一种求解线性规划（Linear Programming, LP）问题的经典算法，由乔治·丹齐格（George Dantzig）于1947年提出。它是一种迭代方法，旨在通过从一个可行解移动到另一个可行解来找到目标函数的最优值。
1. 线性规划的标准形式
单纯形法解决的标准线性规划问题可以表示为：
最大化
z
=
c
T
x
\text{最大化 } z = c^T x
最大化 z=cTx
约束条件：
A
x
≤
b
,
x
≥
0
\text{约束条件：} \quad Ax \leq b, \, x \geq 0
约束条件：Ax≤b,x≥0
其中：
- c c c 是目标函数的系数向量。
- A A A 是约束系数矩阵。
- b b b 是约束的右端常数向量。
- x ≥ 0 x \geq 0 x≥0 是非负性约束。
通过适当的变量变换和引入松弛变量，可以将问题标准化为：
最大化
z
=
c
T
x
\text{最大化 } z = c^T x
最大化 z=cTx
约束条件：
A
x
=
b
,
x
≥
0
\text{约束条件：} \quad Ax = b, \, x \geq 0
约束条件：Ax=b,x≥0
2. 核心思想
单纯形法利用凸多面体的几何性质来求解线性规划问题。线性规划的约束形成了一个凸可行域，其顶点（角点）是可能的解。
单纯形法的核心思想是：
- 从一个顶点开始： 选择一个初始的可行解作为起点。
- 迭代更新： 沿着凸多面体的边移动到一个更优的顶点。
- 终止条件： 当到达最优解时停止（即目标函数值不能再改进）。
3. 单纯形法的步骤
-
引入松弛变量： 将 A x ≤ b Ax \leq b Ax≤b 转化为等式约束 A x + s = b Ax + s = b Ax+s=b，其中 s ≥ 0 s \geq 0 s≥0 是松弛变量。
-
初始化： 选择一个初始的可行解（通常是基本可行解，包含松弛变量）。
-
构造初始表格：
- 每一列对应一个变量（包括原始变量和松弛变量）。
- 行表示约束条件。
-
检验最优性：
- 如果目标函数的系数中（在检验行中）所有系数都是非负的，则当前解为最优解。
-
变量换入与换出：
- 找到检验行中最负的变量系数（入基变量）。
- 使用最小比值法确定换出的变量（离基变量）。
-
更新表格：
- 使用高斯消元法更新表格，生成新的基本可行解。
-
重复步骤 4-6，直到找到最优解。
4. 单纯形法的特点
-
优点：
- 对小规模线性规划问题非常高效。
- 几何意义直观。
-
缺点：
- 在最坏情况下，可能遍历指数级的顶点数（但实际应用中很少发生）。
-
改进：
- 后续算法（如内点法）更适合大规模问题。
5. 举例：
问题：
最大化：
z
=
3
x
1
+
5
x
2
z = 3x_1 + 5x_2
z=3x1+5x2
约束条件：
x
1
+
2
x
2
≤
8
x_1 + 2x_2 \leq 8
x1+2x2≤8
2
x
1
+
x
2
≤
6
2x_1 + x_2 \leq 6
2x1+x2≤6
x
1
,
x
2
≥
0
x_1, x_2 \geq 0
x1,x2≥0
步骤：
-
引入松弛变量： x 3 x_3 x3 和 x 4 x_4 x4，将约束转化为：
x 1 + 2 x 2 + x 3 = 8 x_1 + 2x_2 + x_3 = 8 x1+2x2+x3=8
2 x 1 + x 2 + x 4 = 6 2x_1 + x_2 + x_4 = 6 2x1+x2+x4=6 -
初始表格：
- 列： x 1 , x 2 , x 3 , x 4 x_1, x_2, x_3, x_4 x1,x2,x3,x4
- 行：约束 + 目标函数
-
迭代优化：
- 使用检验系数更新目标函数值。
- 找到最优解： x 1 = 2 , x 2 = 3 , z = 21 x_1 = 2, x_2 = 3, z = 21 x1=2,x2=3,z=21。
6. 几何解释
单纯形法在几何上相当于在多面体的顶点之间沿边移动，每次选择目标函数值最大的方向，直到找到最优解。
总结
单纯形法是一种高效的线性规划求解方法，虽然在理论上存在指数级复杂度，但在实际应用中表现非常优异。它通过沿凸多面体边界移动找到最优解，是解决小规模线性规划问题的经典算法。