单纯形法简介
optimize_2
·
2023-09-19 18:48:07
·
个人记录
单纯形法简介
-1. 前置知识
初中数学。
0. 问题引入
某天我做到了 P6967 [NEERC2016] Delight for a Cat，是一道可爱的建图费用流题。结果我看题解出现了一个名词单纯形法，我就去学了一下。但是因为网上好多文章是面向学数学的大学生而不是学算法竞赛的高中生的，我花了点精力看懂了之后打算写一点东西。
先介绍一下题意：
有一只猫猫要在接下来的 n 个小时内，每个小时选择吃饭或者睡觉。第 i 个小时吃饭可以获得 e_i 的快乐值，睡觉可以获得 s_i 的快乐值。对于每段连续的 k 小时，必须至少有 E 个小时在吃饭，S 个小时在睡觉。给定 n, s_i, e_i, S, E, k ，求可能获得的最大快乐值。n, k \leq 1000 ，时间限制 2s。
接下来讲一下思路：
设第 i 小时的状态为 x_i \in \{0, 1\} ，0 代表吃饭了，1 代表睡觉了。
从 d 小时开始的连续 k 小时的连续段就有 sleep = \sum_{i = d}^{d + k - 1} x_i 小时在睡觉，有 eat = k - sleep 小时在吃饭。
那么连续 k 小时必须至少有 E 小时吃饭，S 小时睡觉的限制就可以写成
\forall d \in [1, n - k + 1], \sum_{i = d}^{d + k - 1} x_i \in [S, k - E]
我们发现，限制有很多种，有 \in {0, 1} 这种二值的，也有 \in [S, k - E] 这种属于一个区间的，我们想个办法把限制用一种统一的格式写起来。
考虑一个简单的不等式
0 \leq x_1 \leq b_1
b_2 \leq x_2
其中 x_1, x_2 是变量，b_1, b_2 是常量。可以再添加两个未知数 x_3, x_4 来把不等式转换成等式。
x_1 + x_3 = b_1
x_2 - x_4 = b_2
另外在单纯形法中，我们规定对于所有 i 都有 x_i \geq 0 。
另外，对于一个没有限制的 x ，可以把它拆成 x_5 - x_6 ，其中 x_5, x_6 \geq 0 。
同时，答案（我们要最大化或者最小化的目标）也应该被写成一个关于所有未知数的线性函数：
ans = \sum_{j = 1}^{n} c_jx_j
如果要最小化答案，可以把 a_i 都取相反数然后最大化。
那么我们就得到了线性规划问题的一般形式：
有关于 n 个 \geq 0 的未知数的 m 个线性方程组（线性就是一次的），要最大化一个关于这 n 个未知数的线性函数 z 。
用符号表达就是
\max \ z = \sum_{j = 1}^{n}c_jx_j
s.t.
\begin{cases}
\displaystyle a_{1,1}x_1 + a_{1,1}x_2+ ... + a_{1,n}x_n = b_1, \\
\displaystyle a_{2,1}x_1 + a_{2,2}x_2+ ... + a_{2,n}x_n = b_2, \\
...\\
\displaystyle a_{m,1}x_1 + a_{m,2}x_2+ ... + a_{m,n}x_n = b_m, \\
x_j \geq 0 , j \in \{1,2,\dots,n\} \\
n \leq m
\end{cases}
有人可能会问：这道题的前 $n$ 个 $x_i$（之所以说前 $n$ 个是因为我们后面添加了一些用来把不等式转成等式的未知数，只有前 $n$ 个表示了吃饭睡觉的状态）不是只能是 $0$ 或者 $1$ 吗，转换成线性规划怎么变成 $0 \leq x_i \leq 1$ 了？
因为这道题可以费用流（如果把每个点的流量式子列出来，会发现费用流解决的也是线性规划问题），所以最优解一定在整数点上。
感觉有点牵强，算了，本文章也没有打算证明，各位只要能看懂就行了，做题的时候能用就更好了，你大学数学要重新学一遍的，是你老师的事。
## 1. 一些解决问题的尝试
首先，你可以把 $x_i$ 叫做未知数，也可以叫做变量。
（可以想象一下我们在搓仪表盘，上面有很多滑块，每个都代表一个变量，有的东西大了就会带动别的东西变大变小。）
根据初中数学知识，通常情况下（不退化或者说方程组之间线性无关，如果你听不懂这些就当没看到这个括号里的内容），$n$ 个 $n$ 元一次方程有一组唯一解。
好我们解决了 $n = m$ 的情况，就是直接解出所有解然后算出答案，没法最小化最大化，因为就这一个解了，爱要不要。
遗憾的，如果 $n$ 大于 $m$ 怎么办？
我们可以在 $n$ 个变量中挑选出 $m$ 个变量作为幸运变量。这里假定是 $x_1, x_2, ..., x_m$ 这 $m$ 个。
唉，如果未知数是 $m$ 个就好了。
假设我们知道了剩下 $n - m$ 个没被选中的不幸运的变量的取值，未知数就真的变成 $m$ 个了。
所以如果我们知道了所有不幸运变量的取值，可以解出幸运变量的取值，也可以表示出答案。
现在我们把幸运变量叫做基变量，不幸运变量叫非基变量。
## 2. 重要结论
**非基变量都取 $0$ 是最优解的必要条件**。
这里给一个感性理解。非基变量都是 $0$ 代表卡到了某种边界。
举一个例子（懒得画图所以图和例子都来自 [OI-wiki](http://oi-wiki.com/math/simplex/)）
$$
\max \ z = x_1 + x_2
$$
$$
s.t \begin{cases}
2x_1 + x_2 + x_3 = 12 \\
x_1 + 2x_2 + x_4 = 9 \\
x_1, x_2, x_3, x_4 \geq 0
\end{cases}
$$
选择 $x_1$，$x_2$ 作为基变量，那么只要确定了 $x3, x3$ 的值，$x_1$, $x_2$ 就能被确定，从而进一步确定答案。
先画出一个平面直角坐标系，横轴代表 $x_1$，纵轴代表 $x_2
可以看到，所有合法的 (x_1, x_2) 的集合是阴影部分。
我们来考察一下，非基变量等于 0 究竟有什么意义。
令 x_3, x_4 = 0 ，限制变为
\begin{cases}
2x_1 + x_2 = 12 \\
x_1 + 2x_2 = 9 \\
x_1, x_2 \geq 0
\end{cases}
第一条限制规定了 (x_1, x_2) 必须在 2x_1+x_2=12 的直线上（就是图里比较陡峭的那条），第二条限制规定了 (x_1, x_2) 必须在 x_1 + 2x_2 = 9 的直线上（就是图里另一条）
所以当 x_3, x_4 = 0 时，(x_1, x_2) 落在了两条直线的交点，也是解集的边缘。
现在我们大胆猜测一下，当非基变量都为 0 时，我们得到的解一定在解集的边缘。
感性理解：每条限制规定了基变量解位于基变量空间中的某一半上（比如这个例子中，有两个基量时基变量空间是平面，限制规定基变量一定在直线的一侧也就是半个平面），而非基变量等于 0 则限制了一定在规定的这部分空间的边缘上（这里是在直线上），所有限制取交集，那基变量的解就位于解集的边缘。
我再举个例子，如果有 3 个基变量，那就有 3 条限制，同时基变量空间是三维的，每条限制给出了基变量都位于一个平面上，而在通常情况下（限制之间线性无关），三条平面有且仅有一个交点，这个点就是非基变量为 0 时基变量的解，也是解集的边缘。
那么为什么解集的边缘一定是最优解的充分条件呢？
还是考虑这个例子，我们要最大化 z = x_1 + x_2 ，或者你也可以写成 z = x_1 + x_2 + 0x_3 + 0x_4 ，取 x_1, x_2 作为基变量，在图里画出来 C = x_1 + x_2 这条直线。（C 是某个可以变化的量。）
发现如果这条直线和解集有交，那么交集里的点对应的 (x_1, x_2) 就能取到 z = C 。
那么我们把直线往上移动一点（增大 C ）直到直线与解集只有一个交点，由于解集是凸的，这个点就能取到最大的 z ，同时这个点也是解集的边缘点。所以令非基变量等于 0 是 z 最大的充分条件。
什么是“凸的”？
你可以理解为解集这个图画出来是凸的，没有凹下去的地方。
或者说，如果 (x_1, x_2, ..., x_m) 是一组解，(y_1, y_2, ..., y_m) 也是一组解，那么 (\frac{x_1 + y_1}{2}, \frac{x_2 + y_2}{2}, ..., \frac{x_m + y_m}{2}) 也应该是一组解。
为什么解集是凸的？
感性理解：还是上面的思路，对于一个平面来说每条限制给出了一条直线并且规定解集一定在直线的同一侧，所以解集的每条边都是某个限制对应的直线的一部分。如果解集中真的出现了凹陷，那么对于连接凹陷点的两条边，解集同时出现在了他们所对应的直线的两侧，这不符合事实。
每次选择一些非基变量置 0 ，几何意义就是在解集边缘上移动来寻找最优解。
这里放一张来自知乎的图以便于理解：
3. 重要结论引发的思路
非基变量取 0 是 z 取最大值的必要条件。
遗憾的，你不能随便取 m 个作为基变量，然后让剩下作为非基变量，并且让他们都变成 0 就说我取到最大值了。
所以为了找到最优的基变量选取方案，我们要从一组初始基变量开始调整。
在此之前，我们可以先使用和高斯消元一样的方法，让每个方程都只包含一个非基变量，并且系数为 1 。
举例：（基变量是 x_1, x_2 ）
\begin{cases}
2x_1 + x_2 + x_3 + 0x_4 = 12 \\
x_1 + 2x_2 + 0x_3 + x_4 = 9 \\
x_1, x_2, x_3, x_4 \geq 0
\end{cases}
我们可以对于每个限制都选一个基变量，并且在别的限制中消去这个变量，即通过方程组的加减让这个变量系数为 0 。这里第一条限制选择 x_1 ，第二条限制选择 x_2 。
\begin{cases}
2x_1 + 0x_2 + \frac{4}{3}x_3 + 0x_4 = 10 \\
0x_1 + \frac{3}{2}x_2 - \frac{1}{2}x_3 + x_4 = 3 \\
\end{cases}
然后把基变量的系数都变成 1 。
\begin{cases}
1x_1 + 0x_2 + \frac{2}{3}x_3 + 0x_4 = 5 \\
0x_1 +1 x_2 - \frac{1}{3}x_3 + \frac{2}{3} x_4 = 2 \\
\end{cases}
4. 单纯形法
单纯形法的核心流程就是从一组初始选定的基变量开始，不断修改选取的基变量来达到最大值。
那么每次调整基变量，我们就要选择一个非基变量替换掉一个基变量，同时再进行一下方程组的加减来让每个基变量都在一条限制中系数为 1 ，其余限制中系数为 0 。
接下来考虑调整基变量，那就要回答三个问题：
如何判断当前是不是最优解？
前面提到，当确定了非基变量（这里假设是 x_1, x_2, ..., x_m 是基变量，x_{m + 1}, x_{m + 2}, ..., x_n 是非基变量），那就能确定基变量从而进一步确定 z 。由于这都是线性方程组，所以基变量和非基变量的关系是线性的，那么 z 和非基变量的关系也是线性的，也就是说 z 一定形如：
z = C + \sum_{i = 1}^{m} \sigma_ix_{n + i}
由于最优解的非基变量都是 0 ，所以如果当前情况是最优解，那么非基变量不取 0 （比 0 大）一定会使得 z 变小。也就是说存在一个非基变量的系数 \sigma_i > 0 。
那么我们对于一组基变量的选取方案，算出每个非基变量的 \sigma ，如果都 \leq 0 就说明是最优解了，不然还得改动。
如果不是最优解，如何找到新的基变量？（这又被称为进基变量）
取最大的那个 \sigma 。
找到了一个新的基变量，得替换掉现有方案中的一个，替换哪个？（这又被称为出基变量）
由于我们选择了进基变量，而且这个变量的 \sigma （对答案的贡献系数）是正的，这意味着这个变量越大越好。
而非基变量都是 0 ，所以限制这个新的变量变大的只会是基变量。我们要选择一个对新变量限制最大的基变量踢掉，让它成为出基变量。
为了做到这一点，就得算出基变量对非基变量的限制。
这时候就体现出我们之前让每条限制只含有一个基变量的作用了。
首先我们找到所有包含进基变量的限制（系数不等于 0 ，系数等于 0 的限制和进基变量无关即对进基变量无约束，不用考虑了）。
假设我们选中的进基变量是 x_{m + i} ，目前选择的基变量是 x_1, x_2, ..., x_m ，那么包含基变量 x_j 的一条限制形如
0x_1 + 0x_2 + ... + 1x_j + ... + 0x_m + k_1x_{m + 1} + k_2x_{m + 2} + ... + k_ix_{m+i}+...+k{n - m}x_n = b
由于非基变量都是 0 （除了我们选定的进基变量 x_{m + i} ），实际上这个方程只有两个变量
x_j + k_ix_{m+i} = b
由于 x_j 即将变成非基变量，他的取值也会变成 0 ，所以这个方程能让 x_{m+i} 最大取到 \frac{b}{k_i} 。
有个问题：如果有 \frac{b}{k_i} < 0 怎么办？由于你的 x_{m+i} \geq 0 ，这意味着如果你要把 x_j 从基变量里踢出（让它等于 0 ）的话，就无解了，所以 \frac{b}{k_i} < 0 的限制也不用考虑。那我们选择所有限制的常数项除以进基变量系数大于 0 的限制里最小的那条限制的基变量踢掉就好了。
现在我们确定了进出基变量，再把方程组加加减减让进基变量在出基变量那条限制中系数为 1 ，在其他限制中系数为 0 就解决了。
5. 单纯形表
单纯形表实际上是把单纯形法的流程一般化。
其实到这里，如果你看懂了前面的内容，就已经理解了单纯形法的原理，可以直接写个代码冲例题了。
所以你不如去看 OI-wiki。
参考资料
http://oi-wiki.com/math/simplex/
https://zhuanlan.zhihu.com/p/623374447
https://zhuanlan.zhihu.com/p/622997038
https://www.bilibili.com/video/BV1824y137JU （这个对于单纯形表流程的讲解很详细，可以看看）