定义
一般存在两种形式：标准型和松弛形。
标准型形如：
\[\max \sum\limits_{i = 1} ^ n c_i \times x_i \] \[\sum\limits_{j = 1} ^ n a_{i, j} \times x_j \le b_i \quad \quad (i \in [1, m]) \] \[x_i \ge 0 \quad \quad (i \in [1, n]) \]松弛形是由标准型转化而来的，当然也可以转化回标准型。
具体地，对于每条不等式添加辅助变量 \(x_{i + n}\)，将不等式写成等式的形式：
\[\sum\limits_{j = 1} ^ n a_{i, j} \times x_j + x_{i + n} = b_i \Longleftrightarrow x_{i + n} = b_i - \sum\limits_{j = 1} ^ n a_{i, j} \times x_j \quad \quad (i \in [1, m]) \] \[x_i \ge 0 \quad \quad (i \in [1, n + m]) \]一般地，对于 \(a = b\) 限制，我们将其看作 \(a \le b, -a \le -b\) 转化为标准型。
全幺模矩阵
以下三个条件同时满足的矩阵 \(A\) 我们称之为全幺模矩阵：
-
矩阵中只存在 \(-1, 0, 1\) 这三种数字。
-
矩阵中同一列中至多两个位置非 \(0\)。
-
能将行分为两个集合，满足 \(\forall i, j, k, A_{i, k} \ne 0, A_{j, k} \ne 0\) 若 \(A_{i, k} = A_{j, k}\) 那么 \(i, j\) 划分在不同集合，否则划分在相同集合。
引理
我们不加证明地给出（利用下文的单纯性法不难证明）：
若标准型线性规划中 \(a\) 构成的矩阵为全幺模矩阵，那么该线性规划的最优解变量取到的一定为整数。
基本的例子
最短路
定义 \(d_i\) 为起点 \(s\) 到 \(i\) 的最短路。
\[\max d_t \] \[d_s = 0 \] \[d_v \le d_u + w_{u, v} \quad \quad ((u, v) \in E) \]最大流
定义 \(f_{u, v}\) 为 \(u \rightarrow v\) 的流量函数，为了方便我们加入边 \(t \rightarrow s\) 流量为 \(\infty\)，同时要求源汇点流量守恒：
\[\max f_{t, s} \] \[f_{u, v} \le c_{u, v} \quad \quad ((u, v) \in E) \] \[\sum\limits_{(i, u) \in E} f(i, u) = \sum_{(u, i) \in E} f(u, i) \]单纯性法
解决一般线性规划问题方法。
引理一
- 标准型线性规划的可行域为 \(n\) 维空间中的凸多边形
考虑使用归纳法，以三维空间中为例，多维空间中类似：
一条限制本质上是规定解在一个平面的一侧，也即将可行域削去一部分，易知不断消去凸多边形的一部分后还是凸多边形。
引理二
- 线性规划的解关于可行域的函数为单峰函数（可能有平台）
反证法，以二维线性规划为例：
假设存在两个峰 \((x_1, y_1, z_1), (x_2, y_2, z_2)\) 那么存在 \((x, y)\) 在两峰连线投影的平面上（可行域为凸多边形），满足该点在两峰连接直线上对应点为 \((x, y, z)\) 原本的函数值为 \(z'\) 有 \(z' < z\)。
又因为目标函数为线性函数，直线上的点位置线性变化，则有函数值也应该线性变化，所以应该有 \(z = z'\) 矛盾。
引理三
- 线性规划的最优解在可行域的边界上取到
反证法，以二维线性规划为例：
因为不在可行域的边界上，那么对于任意一个变量都可以*加减。
若目标函数中存在系数 \(> 0\) 的变量，那么直接将其变大，矛盾；否则最优解唯一，全为 \(0\)，处在边界上。
由引理二，不难得到一个初步的想法：不断调整解使得答案变大，迭代到不存在更优解为止。
那么存在两个问题：
-
如何找到一组初始解。
-
如何进行调整，并且判断不存在更优解。
为了方便起见，我们仅解决松弛形线性规划。
对于问题 \(1\) 若满足 \(\forall i \in [1, m], b_i \ge 0\) 那么可以直接令：\(x_i = 0(i \in [1, n]), x_{i + n} = b_i(i \in [1, m])\) 即可得到初始解。
若不满足 \(b\) 非负，暂时先不考虑，先解决 \(b\) 非负的情况。
在解决问题 \(2\) 之前，先引入一些定义：
一些定义
在松弛形当中，\(x_{1 \sim n}\) 出现在所有式子当中（包含目标函数），\(x_{n + 1 \sim n + m}\) 仅出现在一个式子当中，我们将所有限制变形为：
\[x_{i + n} = b_i - \sum\limits_{j = 1} ^ n a_{i, j} \times x_j \]那么在所有等式当中 \(x_{n + 1 \sim n + m}\) 只出现在等式左侧且只出现一次并且不在目标函数当中，\(x_{1 \sim n}\) 只出现在等式右侧以及目标函数当中我们称 \(x_{n + 1 \sim n + m}\) 为基变量，\(x_{1 \sim n}\) 为非基变量。
同时因为 \(x_{1 \sim n}, x_{n + 1 \sim n + m}\) 的地位实际上是 等价 的，因此我们可以选择第 \(o\) 个式子，非基变量 \(x_e\) 满足 \(a_{o, e} \ne 0\) 将 \(x_e\) 看作基变量，\(x_{o + n}\) 看作非基变量，再将其他等式和目标函数中的 \(x_e\) 用等式右侧表示，这样就完成了基变量和非基变量的互换，我们称这个操作为转轴 \(pivot(o, e)\)。
同时，在转轴过程中本质上是将 \(x_e\) 卡到了上限，也就是达到了可行域边界上，这也是为什么这个过程叫做转轴的原因（从一个边界转到另一个边界）。
有了转轴操作和引理三，我们可以自然地联想到：
- 使用转轴操作进行调整，直到不存在方法继续转轴调整停止
此时我们发现，只需要找到 \(c_e > 0\) 的变量 \(x_e\)，然后找到满足 \(a_{o, e} > 0\) 的 \(o\) 那么转轴 \(pivot(o, e)\) 则有：
\[x_e = \frac{1}{a_{o, e}}(b_o - \sum_i a_{o, i} \times x_i - x_{i + n}) \]因为一开始保证了 \(b_o > 0\) 所以将其带入目标函数时常数变大。
同时由于上述的策略，可知 \(\forall i, c_i \le 0\) 时达到最优，答案即为常数部分。
但这里存在两个问题：
-
可能 \(\forall o, a_{o, e} \le 0\)
-
转轴时将上式带入其他式子后我们无法保证其他式子常数项继续非负（上式常数项显然仍非负）。
对于问题 \(1\)，可知此时 \(x_e\) 可取 \(+\infty\) 因此可以直接判断原问题*。
对于问题二，我们发现只需 \(\forall i\) 满足：
\[\frac{b_o}{a_{o, e}} \times a_{i, e} \le b_i \]移项（由之前的限制 \(a_{o, e} > 0\) 得 \(a_{i, e} > 0\) 否则一定可行）可得：
\[\frac{b_o}{a_{o, e}} \le \frac{b_i}{a_{i, e}} \]那么只需挑选 \(\frac{b_i}{a_{i, e}}\) 最小的 \(o \leftarrow i\) 即可。
回到一开始不保证 \(b_i\) 非负的限制，此时我们发现我们必须将原线性规划转化成另一个线性规划满足该线性规划 \(b_i\) 非负才能进行。
根据上面挑选最小的思路，我们直接考虑引入辅助线性规划：
\[\max -x_0 \] \[x_{i + n} = b_i - \sum\limits_{j = 1} ^ n a_{i, j} \times x_j + x_0 \]那么如果 \(x_0 = 0\) 那么此时的一组解带入原问题也满足，否则显然原线性规划无解。
类似地，我们找到 \(b_i < 0\) 且最小的 \(b_o\)，执行 \(pivot(o, 0)\) 此时所有 \(b_i \ge 0\) 即可进行之前所述说的流程。
执行完毕以后，我们需要把原线性规划转化为该线性规划，由于此时满足 \(x_0 = 0\)，分以下两种情况讨论：
-
若 \(x_0\) 为非基变量，那么直接忽略 \(x_0\) 的限制（将 \(x_0\) 前系数置为 \(0\)）即可。
-
否则，寻找合适的非基变量 \(e\) 进行转轴操作转化为 \(1\)。注意到此时最优解必然满足非基变量为 \(0\) 又 \(x_0 = 0\) 可得 \(b_i = 0\) 因此随意找一个 \(a \ne 0\) 的非基变量转轴即可（若不存在则可直接忽略该式）。
同时，由于转轴过程中目标函数也会改变，因此可以维护一个辅助数组以维护目标函数的变化。
事实上，单纯性算法单次 \(pivot\) 复杂度 \(\mathcal{O(nm)}\) 但总调用次数却是指数级的。
但在一般随机数据下表现优秀，调用次数可以达到低于 \(n + m\) 级别，因此通常可以跑 \(n, m = 3e2\) 左右的数据，更大范围也可以大胆尝试。
实现时不需要真的加入基变量，因为所有变量互相等价且基变量系数恒定，因此只需记录非基变量的系数即可。
若要输出方案，则还需记录基变量对应的原变量编号。
对偶原理
将线性规划描述成矩阵的形式：
\[\max c ^ T x : Ax \le b, x \ge 0 \] \[\min b ^ T y : A ^ Ty \ge c, y \ge 0 \]两者最优解的答案相同。
此原理在线性规划当中十分通用。
互松弛定理
给出原线性规划和对偶线性规划最优解之间的关系。
- 若 \(x, y\) 分别为原问题及其对偶问题的可行解，那么 \(x, y\) 同为最优解 当且仅当：
- \(\forall 1 \le i \le n:x_i = 0\) 或 \(\sum\limits_{j = 1} ^ m a_{j, i} \times y_j = c_i\)
- \(\forall 1 \le i \le m:y_i = 0\) 或 \(\sum\limits_{j = 1} ^ n a_{i, n} \times x_j = b_i\)
通常在求解出对偶线性规划的最优解后通过限制导出原问题最优解的方案。
举例
最大流最小割
最小割可描述为：
\[\min \sum\limits_{(u, v) \in E} c_{u, v} \times g_{u, v} \] \[g_{u, v} - h_u + h_v \ge 0 \quad \quad ((u, v) \in E) \] \[h_s - h_t \ge 1 \] \[h_i, g_{u, v} \in \{0, 1\} \]最大流的对偶问题为：
\[\min \sum\limits_{(u, v) \in E} c_{u, v} \times g_{u, v} \] \[g_{u, v} + h_u - h_v - k_u + k_v \ge 0 \quad \quad ((u, v) \in E) \] \[h_t - h_s - k_t + k_s \ge 1 \]令 \(h_u \leftarrow k_u - h_u\) 得：
\[\min \sum\limits_{(u, v) \in E} c_{u, v} \times g_{u, v} \] \[g_{u, v} - h_u + h_v \ge 0 \quad \quad ((u, v) \in E) \] \[h_s - h_t \ge 1 \]此处不加证明地给出上述线性规划的最优解与最小割线性规划最优解相等。
二分图最大权匹配与最小标顶和
易得二分图最大权匹配线性规划：
\[\max \sum\limits_{u \in X, v \in Y} w_{u, v} \times f_{u, v} \] \[\sum\limits_{v \in Y} f_{u, v} \le 1 \] \[\sum\limits_{u \in X} f_{u, v} \le 1 \] \[f_{u, v} \in \{0, 1\} \]易知该矩阵为全幺模矩阵，因此实数线性规划与整数线性规划结果相同。
其对偶问题：
\[\min \sum\limits_{u \in X} p_u + \sum\limits_{v \in Y} q_v \] \[p_u + q_v \ge w_{u, v} \quad \quad ((u, v) \in E) \]即为二分图最小标顶和。