文章目录
- A. 单纯形法概述
- 1. 优化模型示例
- B. 理论基础
- C. 算法思想
- D. 实现算法
- 1. 线性规划的标准型
- 2. 顶点解的理解及表示
- 2.1 在标准型中变量取值为零的意义
- 2.2 顶点解的表示
- 3. 最优性判断
- 4. 解的更新
- 5. 完成迭代过程
- E. 单纯形法的基本概念与本文对照
- F. 文档源码
前言：书中得来意未通，笔下挥洒渐觉明。
如果文中有错误，或是笔误，或是理论错误，还请大家帮忙指明。
A. 单纯形法概述
单纯形法是一种求解线性规划问题的算法。线性规划是优化一个线性目标函数，同时满足一组线性约束条件。以下是对单纯形法的介绍。
1. 优化模型示例
考虑一个最小化的线性规划问题：
目标函数：
min
z
=
3
x
1
+
2
x
2
\text{min} \quad z = 3x_1 + 2x_2
minz=3x1+2x2
约束条件：
x
1
+
2
x
2
+
x
3
≥
4
,
3
x
1
+
x
2
−
x
4
≤
6
,
x
1
−
x
2
=
1
,
x
1
,
x
2
≥
0
,
x
3
,
x
4
≤
0.
\begin{align*} x_1 + 2x_2 + x_3 & \geq 4, \\ 3x_1 + x_2 - x_4 & \leq 6, \\ x_1 - x_2 & = 1, \\ x_1, x_2 & \geq 0, \\ x_3, x_4 & \leq 0. \\ \end{align*}
x1+2x2+x33x1+x2−x4x1−x2x1,x2x3,x4≥4,≤6,=1,≥0,≤0.
- 在线性规划问题中，可能存在无穷多的解满足这些约束条件。
- 我们的目标是在所有符合这些约束的解中找到一个使得目标函数 z z z 最小的解。
B. 理论基础
考虑以下线性规划模型并观察其可视化图像：
 |  |
可以总结出以下特性（完整的证明可以参照运筹学教材）：
- 可行域是凸集，一定有至少一个顶点是最优解。
- 任意非最优解的顶点一定存在至少一个目标值更优的邻近顶点解。
- 给定一个顶点及其相连的边，可以确定沿边移动时目标值是上升还是下降，从而识别是否存在更优的邻近顶点解。
C. 算法思想
根据上述理论，我们可以自然地给出单纯形法的基本流程：
- 选择一个顶点解作为当前解；
- 判断当前解是否为最优解：以最大化问题为例，如果沿任一邻边移动均导致目标值下降或不变，则该解为最优解；
- 如果当前解不是最优，更新为更优的邻近顶点，并返回到步骤2；否则，结束算法。
为便于理解，以下是求解过程的可视化示意图：
D. 实现算法
1. 线性规划的标准型
为方便使用单纯形法，必须将一般线性规划问题转化为标准型（最大化、等式约束、非负变量）。线性规划的标准型可用以下形式表示：
目标函数：
max
z
=
c
T
x
\text{max} \quad z = c^T x
maxz=cTx
约束条件：
A
x
=
b
x
≥
0
\begin{align*} Ax & = b \\ x & \geq 0 \end{align*}
Axx=b≥0
其中：
- x x x 为决策变量向量， x ∈ R n x \in \mathbb{R}^n x∈Rn。
- c c c 为目标函数的系数向量， c ∈ R n c \in \mathbb{R}^n c∈Rn。
- A A A 为约束条件的系数矩阵， A ∈ R m × n A \in \mathbb{R}^{m \times n} A∈Rm×n。
- b b b 为约束条件的常数向量， b ∈ R m b \in \mathbb{R}^m b∈Rm。
需要注意的是，任何线性规划问题均可转化为标准型。无论目标函数是最小化问题还是最大化问题，约束包括不等式约束或等式约束，都能应用相应方法进行转换。具体转化方法请参考以下链接：转化方法详解。
2. 顶点解的理解及表示
在上面的算法思想中，我们了解到求解过程是将当前解不断地从一个顶点转移到另一个更优的邻近顶点，那什么是顶点解，应该怎么进行表示，在这里我们进行分析。
2.1 在标准型中变量取值为零的意义
我们继续考虑上面的线性规划例子，并将其转化为标准型，加入松弛变量
s
1
,
s
2
,
s
3
s_1, s_2, s_3
s1,s2,s3：
在标准型中，变量包括 x 1 , x 2 , s 1 , s 2 , s 3 x_1, x_2, s_1, s_2, s_3 x1,x2,s1,s2,s3，每个变量取值为零表示相应的约束达到了边界。具体分析如下：
-
当 x 1 = 0 x_1 = 0 x1=0 时：
- 约束 x 1 ≥ 0 x_1 \geq 0 x1≥0 达到边界。
-
当 x 2 = 0 x_2 = 0 x2=0 时：
- 约束 x 2 ≥ 0 x_2 \geq 0 x2≥0 达到边界。
-
当 s 1 = 0 s_1 = 0 s1=0 时：
- 约束 x 1 + s 1 = 8 x_1 + s_1 = 8 x1+s1=8 转化为 x 1 = 8 x_1 = 8 x1=8，则约束 x 1 ≤ 8 x_1 \leq 8 x1≤8 达到边界。
-
当 s 2 = 0 s_2 = 0 s2=0 时：
- 约束 x 2 + s 2 = 5 x_2 + s_2 = 5 x2+s2=5 转化为 x 2 = 5 x_2 = 5 x2=5，则约束 x 2 ≤ 5 x_2 \leq 5 x2≤5 达到边界。
-
当 s 3 = 0 s_3 = 0 s3=0 时：
- 约束 x 1 + x 2 + s 3 = 10 x_1 + x_2 + s_3 = 10 x1+x2+s3=10 转化为 x 1 + x 2 = 10 x_1 + x_2 = 10 x1+x2=10，则约束 x 1 + x 2 ≤ 10 x_1 + x_2 \leq 10 x1+x2≤10 达到边界。
因此，每个变量均对应了一条约束，当该变量取值为零时，当前解位于对应的约束边界上。
2.2 顶点解的表示
在示例中，一个顶点具有两条邻边。当我们让两条邻边对应的变量取值为0时，就可以表示出该顶点。下面展示了所有顶点解及其变量取值为0的组合：
 |  |
下面我们对 s 2 = 0 s_2=0 s2=0 和 s 3 = 0 s_3=0 s3=0 能够得到 ( x 1 = 5 , x 2 = 5 ) (x_1=5,x_2=5) (x1=5,x2=5) 这个顶点，做具体的计算，作为一个举例：
3. 最优性判断
在之前的部分，我们分析了可以利用一些变量为零来指代一个顶点。接下来，继续分析确定一个顶点后，如何判断该顶点是否为最优解：即判断当前顶点沿邻边移动时，目标值是否可改善。若所有邻边均不可改善，则该顶点为最优解。
以顶点解(0,0)为例，邻边为 x 1 = 0 x_1=0 x1=0 和 x 2 = 0 x_2= 0 x2=0。我们以沿着 x 1 = 0 x_1=0 x1=0 移动为例进行分析：
-
首先，如何从数值变化上理解“沿着 x 1 = 0 x_1=0 x1=0 移动”？
- 这意味着保持
x
1
x_1
x1 为零，增大
x
2
x_2
x2 （另一条边界）。
- 如果顶点有多条边线，它们会如何变化？以下图为例，当顶点沿着
s
3
=
0
s_3 = 0
s3=0移动时，
s
1
s_1
s1 和
s
2
s_2
s2 均会随之增大。（在几何意义上，
s
1
=
0
s_1 = 0
s1=0 增大到
s
1
=
1
s_1 = 1
s1=1 意味着点到
s
1
=
0
s_1 = 0
s1=0的距离增加了1）
- 如果顶点有多条边线，它们会如何变化？以下图为例，当顶点沿着
s
3
=
0
s_3 = 0
s3=0移动时，
s
1
s_1
s1 和
s
2
s_2
s2 均会随之增大。（在几何意义上，
s
1
=
0
s_1 = 0
s1=0 增大到
s
1
=
1
s_1 = 1
s1=1 意味着点到
s
1
=
0
s_1 = 0
s1=0的距离增加了1）
- 这意味着保持
x
1
x_1
x1 为零，增大
x
2
x_2
x2 （另一条边界）。
-
其次，沿着 x 1 = 0 x_1=0 x1=0 移动时， z z z 如何变化？
- 此时 z = x 1 + 2 x 2 = 2 x 2 z = x_1 + 2x_2 = 2x_2 z=x1+2x2=2x2。当 x 2 x_2 x2 增大时， z z z 也随之增大。
由于当前顶点沿该邻边移动时 z z z 增大，因此该顶点不是最优解（若沿该边移动无法改善目标值，还需判断其他边）。
4. 解的更新
还是以顶点解(0,0)为例，邻边有两条 x 1 = 0 x_1=0 x1=0 和 x 2 = 0 x_2= 0 x2=0 ，由于 z = x 1 + 2 x 2 z = x_1 + 2x_2 z=x1+2x2，不管是沿哪条边移动都会增长 z z z值，那么应该选择哪一条边？选择的依据是目标值增长最快的方向。当 x 1 x_{1} x1 增加单位 1 1 1 时， z z z 增加了 x 1 x_{1} x1 的系数 1 1 1；当 x 2 x_{2} x2 增加单位 1 1 1 时， z z z 增加了 x 2 x_{2} x2 的系数 2 2 2。所以，通过系数的对比判断，选择沿着 x 1 = 0 x_1= 0 x1=0 移动，增加 x 2 x_2 x2，直到移动到下一个顶点，如下图所示，移动到了新顶点(0,5) 。
进一步分析
- 为什么不直接对比邻近顶点的目标值，选择最优的邻近顶点？设计算法时，一方面考虑效果，另一方面还要考虑效率。从效果来说，均达到了找到更优解的目的，只是选择最优的邻近顶点解可能在目标值上会更好一些；从效率来说，增长速度的比较 简单于 目标值的比较。
- 怎么从数值上判断是不是移动到了新的顶点？当沿着
x
1
=
0
x_1= 0
x1=0 移动，增加
x
2
x_2
x2 时，其它变量
s
1
,
s
2
,
s
3
s_1, s_2, s_3
s1,s2,s3也会随之变化，当
s
1
,
s
2
,
s
3
s_1, s_2, s_3
s1,s2,s3中有一个变量降到0时，即是到了新的顶点。
- 进一步，当沿着
x
1
=
0
x_1= 0
x1=0 移动，增加
x
2
x_2
x2 时，怎么能够判断出
s
1
,
s
2
,
s
3
s_1, s_2, s_3
s1,s2,s3中的哪个变量会先降到0？通过下面变换，利用
x
2
x_2
x2 表示其它变量，可以容易地判断出随着
x
2
x_2
x2 的增加哪个变量会先降到0。
- 进一步，当沿着
x
1
=
0
x_1= 0
x1=0 移动，增加
x
2
x_2
x2 时，怎么能够判断出
s
1
,
s
2
,
s
3
s_1, s_2, s_3
s1,s2,s3中的哪个变量会先降到0？通过下面变换，利用
x
2
x_2
x2 表示其它变量，可以容易地判断出随着
x
2
x_2
x2 的增加哪个变量会先降到0。
5. 完成迭代过程
- 判断顶点(0,5)是否为最优解。此时其邻边为 x 1 = 0 x_1=0 x1=0 和 s 2 = 0 s_2=0 s2=0，我们要分析沿这两条边移动目标值的变化。基于约束方程，可以用 x 1 x_1 x1 和 s 2 s_2 s2 表示 z z z，得到 z = x 1 − 2 s 2 + 10 z = x_1 - 2s_2 + 10 z=x1−2s2+10。在沿 s 2 = 0 s_2=0 s2=0 的邻边移动时，增大 x 1 x_1 x1 ， z z z 也会随之增加，因此顶点(0,5)不是最优解。
- 更新顶点解：由于 z = x 1 − 2 s 2 + 10 z = x_1 - 2s_2 + 10 z=x1−2s2+10，增加 s 2 s_2 s2 反而会使 z z z 减小，因此我们只能选择增大 x 1 x_1 x1，也就是开始沿着 s 2 = 0 s_2=0 s2=0 的邻边移动，直到到达(5,5)。
- 判断顶点(5,5)是否为最优解。其邻边为 s 2 = 0 s_2=0 s2=0 和 s 3 = 0 s_3=0 s3=0。沿两条邻边移动目标值的变化，用 s 2 s_2 s2 和 s 3 s_3 s3 表示 z z z，得到 z = − s 2 − s 3 + 15 z = -s_2 - s_3 + 15 z=−s2−s3+15。此时，无论是增加 s 2 s_2 s2 还是 s 3 s_3 s3，目标值均会下降。因此，顶点(5,5)为最优解，算法结束。
E. 单纯形法的基本概念与本文对照
在上面的介绍中，为了方便理解，并没有直接使用到教材中常用的一些概念，这里做一个表格对比这些概念与本文中所论述的部分（以顶点解(0,0)为例，邻边有两条 x 1 = 0 x_1=0 x1=0 和 x 2 = 0 x_2= 0 x2=0， z = x 1 + 2 x 2 z = x_1 + 2x_2 z=x1+2x2）：
| 单纯形法常用概念 | 本文的对应部分 |
|---|---|
| 非基变量 | 两条邻边 x 1 = 0 x_1=0 x1=0 和 x 2 = 0 x_2= 0 x2=0 ，其中 x 1 x_1 x1 和 x 2 x_2 x2 为非基变量。 |
| 基变量 | 除了非基变量，剩余的变量均是基变量。在非基变量确定之后，求解约束方程可以得到基变量的取值。 |
| 入基 | 如果沿着 x 1 = 0 x_1=0 x1=0 移动， x 2 x_2 x2 会增加，不再为0，那么 x 2 x_2 x2由非基变量转化为了基变量。 |
| 出基 | 如果沿着 x 1 = 0 x_1=0 x1=0 移动， x 2 x_2 x2 会增加，其它变量 s 1 , s 2 , s 3 s_1, s_2, s_3 s1,s2,s3也会随之变化，当 s 1 , s 2 , s 3 s_1, s_2, s_3 s1,s2,s3中有一个变量降到0时，该变量由基变量转化为了非基变量。 |
| 检验数 | 由于 z = x 1 + 2 x 2 z = x_1 + 2x_2 z=x1+2x2，当 x 1 x_{1} x1 增加单位 1 1 1 时， z z z 增加了 x 1 x_{1} x1 的系数 1 1 1；当 x 2 x_{2} x2 增加单位 1 1 1 时， z z z 增加了 x 2 x_{2} x2 的系数 2 2 2。 x 1 x_1 x1 和 x 2 x_2 x2 的系数反映了目标值的增长速度，而检验数就是 x 1 x_1 x1 和 x 2 x_2 x2 （边界对应的变量）在目标函数中的系数。 |
| 最优性判断：如果所有检验数都不为负，当前解为最优解。（最大化问题） | 如果沿着所有的邻边移动均不能改善目标值，即是最优解。 |
| 解的更新：通过交换基变量和非基变量 | 通过将当前解更新为更优的邻近顶点。 |
F. 文档源码
@[Toc]
前言：书中得来意未通，笔下挥洒渐觉明。
## A. 单纯形法概述
单纯形法是一种求解线性规划问题的算法。线性规划是优化一个线性目标函数，同时满足一组线性约束条件。以下是对单纯形法的介绍。
### 1. 优化模型示例
考虑一个最小化的线性规划问题：
**目标函数**：
$$
\text{min} \quad z = 3x_1 + 2x_2
$$
**约束条件**：
$$
\begin{align*}
x_1 + 2x_2 + x_3 & \geq 4, \\
3x_1 + x_2 - x_4 & \leq 6, \\
x_1 - x_2 & = 1, \\
x_1, x_2 & \geq 0, \\
x_3, x_4 & \leq 0. \\
\end{align*}
$$
- 在线性规划问题中，可能存在无穷多的解满足这些约束条件。
- 我们的目标是在所有符合这些约束的解中找到一个使得目标函数 $z$ 最小的解。
---
## B. 理论基础
考虑以下线性规划模型并观察其可视化图像：
<table style="border: none; border-collapse: collapse; width: 100%;">
<tr>
<td style="border: none; text-align: center; width: 50%;">
<img src="https://i-blog.csdnimg.cn/direct/a6be00131fe64aaf9b47daef35e6fbdd.png" alt="可行域图" style="width: 100px;"/>
<p></p>
</td>
<td style="border: none; text-align: center; width: 50%;">
<img src="https://i-blog.csdnimg.cn/direct/63564ea4cbd64240a0e5ceb171e63725.png" alt="可行域图" style="width: 200px;"/>
</td>
</tr>
</table>
可以总结出以下特性（完整的证明可以参照运筹学教材）：
1. 可行域是凸集，一定有至少一个顶点是最优解。
2. 任意非最优解的顶点一定存在至少一个目标值更优的邻近顶点解。
3. 给定一个顶点及其相连的边，可以确定沿边移动时目标值是上升还是下降，从而识别是否存在更优的邻近顶点解。
---
## C. 算法思想
根据上述理论，我们可以自然地给出单纯形法的基本流程：
1. 选择一个顶点解作为当前解；
2. 判断当前解是否为最优解：以最大化问题为例，如果沿任一邻边移动均导致目标值下降或不变，则该解为最优解；
3. 如果当前解不是最优，更新为更优的邻近顶点，并返回到步骤2；否则，结束算法。
为便于理解，以下是求解过程的可视化示意图：
---
## D. 实现算法
### 1. 线性规划的标准型
为方便使用单纯形法，必须将一般线性规划问题转化为标准型（最大化、等式约束、非负变量）。线性规划的标准型可用以下形式表示：
**目标函数**：
$$
\text{max} \quad z = c^T x
$$
**约束条件**：
$$
\begin{align*}
Ax & = b \\
x & \geq 0
\end{align*}
$$
其中：
- $x$ 为决策变量向量，$x \in \mathbb{R}^n$。
- $c$ 为目标函数的系数向量，$c \in \mathbb{R}^n$。
- $A$ 为约束条件的系数矩阵，$A \in \mathbb{R}^{m \times n}$。
- $b$ 为约束条件的常数向量，$b \in \mathbb{R}^m$。
需要注意的是，任何线性规划问题均可转化为标准型。无论目标函数是最小化问题还是最大化问题，约束包括不等式约束或等式约束，都能应用相应方法进行转换。具体转化方法请参考以下链接：[转化方法详解](https://www.cnblogs.com/haohai9309/p/18303895)。
### 2. 顶点解的理解及表示
在上面的算法思想中，我们了解到求解过程是将当前解不断地从一个顶点转移到另一个更优的邻近顶点，那什么是顶点解，应该怎么进行表示，在这里我们进行分析。
#### 2.1 在标准型中变量取值为零的意义
我们继续考虑上面的线性规划例子，并将其转化为标准型，加入松弛变量 $s_1, s_2, s_3$：
$$
\begin{array}{ll}
\max & z=x_{1}+2x_{2} \\
\text{s.t.} & x_1 + s_1 = 8 \\
& x_2 + s_2 = 5 \\
& x_1 + x_2 + s_3 = 10 \\
& x_1, x_2, s_1, s_2, s_3 \geq 0
\end{array}
$$
在标准型中，变量包括 $x_1, x_2, s_1, s_2, s_3$，**每个变量取值为零表示相应的约束达到了边界**。具体分析如下：
1. **当 $x_1 = 0$** 时：
- 约束 $x_1 \geq 0$ 达到边界。
2. **当 $x_2 = 0$** 时：
- 约束 $x_2 \geq 0$ 达到边界。
3. **当 $s_1 = 0$** 时：
- 约束 $x_1 + s_1 = 8$ 转化为 $x_1 = 8$，则约束 $x_1 \leq 8$ 达到边界。
4. **当 $s_2 = 0$** 时：
- 约束 $x_2 + s_2 = 5$ 转化为 $x_2 = 5$，则约束 $x_2 \leq 5$ 达到边界。
5. **当 $s_3 = 0$** 时：
- 约束 $x_1 + x_2 + s_3 = 10$ 转化为 $x_1 + x_2 = 10$，则约束 $x_1 + x_2 \leq 10$ 达到边界。
因此，每个变量均对应了一条约束，**当该变量取值为零时，当前解位于对应的约束边界上**。
#### 2.2 顶点解的表示
在示例中，一个顶点具有两条邻边。**当我们让两条邻边对应的变量取值为0时，就可以表示出该顶点**。下面展示了所有顶点解及其变量取值为0的组合：
<table style="border: none; border-collapse: collapse; width: 100%;">
<tr>
<td style="border: none; text-align: center; width: 50%;">
<img src="https://i-blog.csdnimg.cn/direct/4160682dd8064247928d52340348a454.png" alt="可行域图" style="width: 100px;"/>
<p></p>
</td>
<td style="border: none; text-align: center; width: 50%;">
<img src="https://i-blog.csdnimg.cn/direct/53ec6578fa7140ec9e5025756e0a6ccb.png" alt="可行域图" style="width: 200px;"/>
</td>
</tr>
</table>
下面我们对 $s_2=0$ 和 $s_3=0$ 能够得到 $(x_1=5,x_2=5)$ 这个顶点，做具体的计算，作为一个举例：
### 3. 最优性判断
在之前的部分，我们分析了可以利用一些变量为零来指代一个顶点。接下来，继续分析确定一个顶点后，如何判断该顶点是否为最优解：即判断当前顶点沿邻边移动时，目标值是否可改善。若所有邻边均不可改善，则该顶点为最优解。
以顶点解(0,0)为例，邻边为 $x_1=0$ 和 $x_2= 0$。我们以**沿着 $x_1=0$ 移动**为例进行分析：
- 首先，如何从数值变化上理解“沿着 $x_1=0$ 移动”？
- 这意味着保持 $x_1$ 为零，增大 $x_2$ （另一条边界）。
- 如果顶点有多条边线，它们会如何变化？以下图为例，当顶点沿着$s_3 = 0$移动时，$s_1$ 和 $s_2$ 均会随之增大。（在几何意义上，$s_1 = 0$ 增大到 $s_1 = 1$ 意味着点到$s_1 = 0$的距离增加了1）
- 其次，沿着 $x_1=0$ 移动时，$z$ 如何变化？
- 此时 $z = x_1 + 2x_2 = 2x_2$。当 $x_2$ 增大时，$z$ 也随之增大。
由于当前顶点沿该邻边移动时 $z$ 增大，因此该顶点不是最优解（若沿该边移动无法改善目标值，还需判断其他边）。
### 4. 解的更新
还是以顶点解(0,0)为例，邻边有两条 $x_1=0$ 和 $x_2= 0$ ，由于$z = x_1 + 2x_2$，不管是沿哪条边移动都会增长$z$值，那么应该选择哪一条边？选择的依据是**目标值增长最快的方向**。当 $x_{1}$ 增加单位 $1$ 时，$z$ 增加了 $x_{1}$ 的系数 $1$；当 $x_{2}$ 增加单位 $1$ 时，$z$ 增加了 $x_{2}$ 的系数 $2$。所以，通过系数的对比判断，选择沿着 $x_1= 0$ 移动，增加 $x_2$，**直到移动到下一个顶点**，如下图所示，移动到了新顶点(0,5) 。
**进一步分析**
- 为什么不直接对比邻近顶点的目标值，选择最优的邻近顶点？设计算法时，一方面考虑效果，另一方面还要考虑效率。从效果来说，均达到了找到更优解的目的，只是选择最优的邻近顶点解可能在目标值上会更好一些；从效率来说，增长速度的比较 **简单于** 目标值的比较。
- 怎么从数值上判断是不是移动到了新的顶点？当沿着 $x_1= 0$ 移动，增加 $x_2$ 时，其它变量$s_1, s_2, s_3$也会随之变化，当$s_1, s_2, s_3$中有一个变量降到0时，即是到了新的顶点。
- 进一步，当沿着 $x_1= 0$ 移动，增加 $x_2$ 时，怎么能够判断出$s_1, s_2, s_3$中的哪个变量会先降到0？通过下面变换，利用 $x_2$ 表示其它变量，可以容易地判断出随着 $x_2$ 的增加哪个变量会先降到0。
### 5. 完成迭代过程
- 判断顶点(0,5)是否为最优解。此时其邻边为 $x_1=0$ 和 $s_2=0$，我们要分析沿这两条边移动目标值的变化。基于约束方程，可以用 $x_1$ 和 $s_2$ 表示 $z$，得到 $z = x_1 - 2s_2 + 10$。在沿 $s_2=0$ 的邻边移动时，增大 $x_1$ ， $z$ 也会随之增加，因此顶点(0,5)不是最优解。
- 更新顶点解：由于 $z = x_1 - 2s_2 + 10$，增加 $s_2$ 反而会使 $z$ 减小，因此我们只能选择增大 $x_1$，也就是开始沿着 $s_2=0$ 的邻边移动，直到到达(5,5)。
- 判断顶点(5,5)是否为最优解。其邻边为 $s_2=0$ 和 $s_3=0$。沿两条邻边移动目标值的变化，用 $s_2$ 和 $s_3$ 表示 $z$，得到 $z = -s_2 - s_3 + 15$。此时，无论是增加 $s_2$ 还是 $s_3$，目标值均会下降。因此，顶点(5,5)为最优解，算法结束。
---
## E. 单纯形法的基本概念与本文对照
在上面的介绍中，为了方便理解，并没有直接使用到教材中常用的一些概念，这里做一个表格对比这些概念与本文中所论述的部分（以顶点解(0,0)为例，邻边有两条 $x_1=0$ 和 $x_2= 0$， $z = x_1 + 2x_2$）：
| **单纯形法常用概念** | **本文的对应部分**|
|-|-|
| **非基变量** | 两条邻边$x_1=0$ 和 $x_2= 0$ ，其中 $x_1$ 和 $x_2$ 为非基变量。 |
| **基变量** | 除了非基变量，剩余的变量均是基变量。在非基变量确定之后，求解约束方程可以得到基变量的取值。
| **入基** | 如果沿着 $x_1=0$ 移动，$x_2$ 会增加，不再为0，那么$x_2$由非基变量转化为了基变量。
| **出基** | 如果沿着 $x_1=0$ 移动，$x_2$ 会增加，其它变量$s_1, s_2, s_3$也会随之变化，当$s_1, s_2, s_3$中有一个变量降到0时，该变量由基变量转化为了非基变量。 |
| **检验数** | 由于 $z = x_1 + 2x_2$，当 $x_{1}$ 增加单位 $1$ 时，$z$ 增加了 $x_{1}$ 的系数 $1$；当 $x_{2}$ 增加单位 $1$ 时，$z$ 增加了 $x_{2}$ 的系数 $2$。 $x_1$ 和 $x_2$ 的系数反映了目标值的增长速度，而检验数就是$x_1$ 和 $x_2$ （边界对应的变量）在目标函数中的系数。 |
| **最优性判断：如果所有检验数都不为负，当前解为最优解。（最大化问题）**| 如果沿着所有的邻边移动均不能改善目标值，即是最优解。 |
| **解的更新：通过交换基变量和非基变量** | 通过将当前解更新为更优的邻近顶点。 |
![[Linux]线程概念与控制](https://i-blog.csdnimg.cn/direct/8e85f1dcb575490ba1cfe892c419b81b.png)
