别线性规划
ZJH234567
·
·
算法·理论
引入
线性规划是研究线性约束条件下线性目标函数最值的方法总称，如网络流等。OI 很少会出现只能用线性规划算法解决的问题，绝大多数这类问题可以通过网络流建模等方法更高效地解决。
举个例子：
你是一个工厂老板，仓库里有 10 吨木材 和 8 个工时，你可以生产两种产品：椅子 和 桌子。
- 做一把椅子：需 1 吨木材 + 2 个工时，利润 30 元。
- 做一张桌子：需 2 吨木材 + 1 个工时，利润 50 元。
你的目标：决定生产多少椅子 （x_1） 和多少桌子 （x_2），使得总利润最大。
把这个问题建模成 LP 就是：
\begin{aligned}
\text{Maximize } & Z = 30x_1 + 50x_2 \quad (\text{总利润}) \\
\end{aligned}
\begin{aligned}
\text{s.t.} \quad & 1x_1 + 2x_2 \le 10 \quad (\text{木材限制}) \\
& 2x_1 + 1x_2 \le 8 \quad (\text{工时限制}) \\
& x_1, x_2 \ge 0
\end{aligned}
（此处忽略掉整数限制）
我们把这个东西画到平面上会发现一些性质：
加上整数限制的 LP 问题是一类整数规划问题，而并非简单的线性规划问题（当然如果系数矩阵是全幺模矩阵，整数规划问题和线性规划问题是等价的，否则很多是 NP-Hard 的，比如背包）。
标准型
通常规定为：
\begin{aligned} \text{maximize} \quad & \mathbf{c}^T \mathbf{x} \\
\end{aligned}
\begin{aligned}\text{subject to} \quad & \mathbf{A} \mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge 0 \end{aligned}
三种要求：目标函数，约束条件和非负限制（单纯形法的基础）。
一些常用技巧：
- 添加负号转化最大最小问题和约束条件的方向。
- 等式约束拆成两个方向相反的约束。
- 如果变量没有正负数限制，将他替换成两个非负变量的差值。
对偶
| 原问题 （Primal） |
对偶问题 （Dual） |
| Maximize \mathbf{c}^T \mathbf{x} |
Minimize \mathbf{b}^T \mathbf{y} |
| \mathbf{A} \mathbf{x} \le \mathbf{b} |
\mathbf{A}^T \mathbf{y} \ge \mathbf{c} |
| \mathbf{x} \ge 0 |
\mathbf{y} \ge 0 |
原问题转对偶问题的过程一共需要 3 步：
1. 交换目标函数和约束符号的方向。
2. 将约束条件的系数矩阵转置。
3. 将原目标函数的系数列向量和原约束条件的列向量交换。
### 举个例子
将上面的例子作为原问题建模（为方便表示系数矩阵发生转置就把条件一 $x_2$ 的系数改成 3）：
$$
\begin{aligned}
\text{Maximize } & Z = 30x_1 + 50x_2 \quad (\text{总利润}) \\
\end{aligned}
$$
$$
\begin{aligned}
\text{s.t.} \quad & 1x_1 + 3x_2 \le 10 \quad (\text{木材限制}) \\
& 2x_1 + 1x_2 \le 8 \quad (\text{工时限制}) \\
& x_1, x_2 \ge 0
\end{aligned}
$$
给问题对偶一下就变成了需要用最小代价收购木材和工时，单位木材和工时分别设置一个价格 $y_1$ 和 $y_2$，使得老板获得的利润不能低于他卖产品获得的利润，求出每个单位木材和工时的价格。
对偶问题建模：
$$
\begin{aligned}
\text{Minimize } & W = 10y_1 + 8y_2 \quad (\text{总花费}) \\
\end{aligned}
$$
$$
\begin{aligned}
\text{s.t.} \quad & 1y_1 + 2y_2 \ge 30 \quad (\text{椅子价格}) \\
& 3y_1 + 1y_2 \ge 50 \quad (\text{桌子价格}) \\
& y_1, y_2 \ge 0
\end{aligned}
$$
### 三大定理：
1. **弱对偶定理 ：**
$$ \mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y}$$
即：任意可行解的目标函数值，原问题（最大化） $\le$ 对偶问题（最小化）。这为我们提供了上下界估算。
2. **强对偶定理：**
如果原问题和对偶问题都有界，原问题有最优解 $x^*$，则对偶问题也有最优解 $y^*$，且：
$$ \mathbf{c}^T \mathbf{x}= \mathbf{b}^T \mathbf{y}$$
**应用：** 可以把最小化问题转化为最大化问题然后使用单纯形，或者原问题变量少，约束多，对偶完了就是变量多约束少。
3. **互补松弛性 （Complementary Slackness）：**
一个可行解是最优解：对于原问题的第 $i$ 个约束，如果没取到等号（松弛了），则对偶变量 $y_i$ 必须为 0，反之亦然。
$$ (\mathbf{b} - \mathbf{A}\mathbf{x}) \cdot y = 0$$
$$ (\mathbf{c} - \mathbf{A}^T\mathbf{y}) \cdot x = 0$$
**应用：** 原始对偶方法要用。
**证明：**
对任意可行解 $x,y$，有
$$
c^\top x \le b^\top y
$$
考虑两者之差：
$$
\begin{aligned}
b^\top y - c^\top x
&= y^\top b - x^\top c\\
&= y^\top b - x^\top A^\top y + x^\top(A^\top y - c) \\
&= y^\top(b - Ax) + x^\top(A^\top y - c)
\end{aligned}
$$
根据强对偶定理，两者之差为 0，又因为右边两项非负，所以推出互补松弛性。
## 原始-对偶方法
这个东西是解决线性规划问题的一类方法，最小费用最大流里面的 SSP 算法用的也是这个思想。
大体思路：先给出一个可行解，通过求解一系列相对简单的辅助问题，来逐步逼近原问题的最优解，对于原问题 $Q1$：
$$
\begin{aligned} \text{minimize} \quad & \mathbf{c}^T \mathbf{x} \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \mathbf{A} \mathbf{x} \ge \mathbf{b} \\ & \mathbf{x} \ge 0 \end{aligned}
$$
将这个问题转化为对偶问题 $Q2$：
$$
\begin{aligned} \text{maximize} \quad & \mathbf{b}^T \mathbf{y} \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \mathbf{A^T} \mathbf{y} \le \mathbf{c} \\ & \mathbf{y} \ge 0 \end{aligned}
$$
根据互补松弛性，只需要找到一个可行解，使得 $$\mathbf{x^T} \mathbf{(A^Ty-c)} = 0$$，这个可行解就是最优解。
计算对偶问题紧约束的集合
$$
I= \left\{i : (A^Ty-c)_i=0\right\}
$$
那么原问题可以转化为问题 $Q3$：
$$
\begin{aligned} \text{minimize} \quad & \mathbf{1}^T \mathbf{z} \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \mathbf{A} \mathbf{x} + \mathbf{z} = \mathbf{b} \\ & \mathbf{z} \ge 0 \end{aligned}
$$
- $$x_i \ge 0 \quad \forall i \in I$$
- $$x_i = 0 \quad \forall i \notin I$$
如果问题 Q3 的最优解是 $0$，说明满足互补松弛性，此时的 $x$ 就是原问题最优解。
给问题 $Q3$ 对偶一下成问题 $Q4$。
$$
\begin{aligned} \text{maximize} \quad & \mathbf{b}^T \mathbf{y} \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \sum_j a_{ji} \times y_j \le 0 \ \quad \forall i \in I& \\ \mathbf{b}^T \mathbf{y} \le 1 \end{aligned}
$$
想办法利用 $Q4$ 的解改进 $Q2$ 的解，将问题 $Q2$ 的解 $y_{Q2} = y_{Q2}+\epsilon y_{Q4}$，在选取的 $\epsilon$ 满足要求的情况下，$y_{Q2}$ 一定是一组可行解，且目标函数值会更优。
选取 $\epsilon$ 的具体方法式子推一推就行。
如果 $\epsilon = +\infty$，那么对偶问题无界，原问题不可解。
## 全幺模矩阵
这个东西可以判定判定这个线性规划问题的最优解是否是整数解，这样可以把整数规划问题转化为线性规划问题来求解。
矩阵 $A\in R^{m\times n}$ 称为全幺模（TU），当且仅当它的任意子矩阵（从 $A$ 中取同样行列数得到的方阵）的行列式都属于
$$
\det(\cdot)\in{0, 1, -1}.
$$
对于全幺模矩阵 $A \in Z^{m+n},b\in Z^m ,C\in Z^n$ 的线性规划问题
$$
\begin{aligned} \text{maximize} \quad & \mathbf{c}^T \mathbf{x} \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \mathbf{A} \mathbf{x} \le \mathbf{b} \\ & \mathbf{x} \ge 0 \end{aligned}
$$
如果有界，最优解一定是整数解。
证明思路是：
1. **先证明：当 $A$ TU 且 $b$ 整数时，${x\mid Ax\le b}$ 的所有极点都是整数**。
2. **再用最优解可在极点取得的性质**，因此存在整数最优解。
严谨证明参见：https：//www.luogu.com.cn/paste/xi6i8dkm。
常见的图论模型中，网络流、最短路、二分图等对应的线性规划问题的系数矩阵都是全幺模矩阵。
一个引理是如果矩阵的每一列的 1 形成一个区间那么就是全幺模，当然给这个矩阵转置一下也成立。
严格证明需要使用 Ghouila–Houri 判据，这里不展开。
## 单纯形法
单纯形法的时间复杂度的渐进上界是 $O(2^n nm)$ 或 $O(2^n m^2)$，其中 $n$ 是变量数，$m$ 是约束数，实际使用非常快，和网络流一样就是 $O(能过)$。
单纯形法主要是解决**标准形式**的线性规划问题：
$$
\max\ \sum_{j=1}^n c_j x_j \quad
\text{s.t. }\sum_{j=1}^n a_{ij}x_j \le b_i\ (i=1..m),\ x_j\ge 0
$$
算法大体思路：
1. 先将线性规划问题转化为标准形式，然后将 $m$ 个约束作为线性方程组求解（要求 rank A=m）。
2. 然后对于每个线性方程添加松弛变量。
3. 找到原问题的一组可行解，然后一直执行换基操作，直到最优解不再改进。
### 定义
把不等式变成等式：加松弛变量 $s_i\ge 0$。
$$
Ax + s = b
$$
总变量数变成 $n+m$。选出 $m$ 个变量当作**基变量**（它们对应的系数矩阵可逆），其余是**非基变量**。令非基变量全为 0，就能解出基变量的值——这就是一个**基本解**；若基变量也都 $\ge 0$，就是**基本可行解**，对应一个顶点。
初始时如果 $b\ge 0$，基本可行解直接令非基变量全部为 0，基变量是 $b$ 即可。
否则需要两次单纯形先求出可行解。
### 换基操作
把当前状态理解成一组方程（把基变量用非基变量表示）：
给定一个基 $B=(B_1,B_2,\dots,B_m)$（大小 $m$）和非基 $N=(N_1,N_2,\dots,N_n)$（其余变量），把等式
$$
A_B x_B + A_N x_N=b
$$
移项：
$$
A_B x_B = b - A_N x_N
$$
则（由于最开始的保证 $A_B$ 一定）
$$
x_B = A_B^{-1}b - A_B^{-1}A_Nx_N
$$
记
$$
\bar b = A_B^{-1}b,\qquad
\bar A = A_B^{-1}A_N
$$
那么：
$$
x_{B}=\bar b-\bar Ax_N
\tag{D1}
$$
目标函数
$$
z=c_B^\top x_B + c_N^\top x_N
$$
代入 $D1$ 得：
$$
z=c_B^\top \bar b + \Big(c_N^\top - c_B^\top A_B^{-1}A_N\Big)x_N
$$
记
$$
z_0=c_B^\top\bar b,\qquad
\bar c^\top= c_N^\top - c_B^\top \bar A
$$
得到
$$
z = z_0 + \sum_{j\in N}\bar c_j x_j
\tag{D2}
$$
这里 $\bar c_j$ 就是 **检验数**（在 max 下，$\bar c_j>0$ 表示让 $x_j$ 从 0 增大能让 $z$ 增大）。
#### 1. 选入基变量
最大化问题里，如果存在某个非基变量 $x_j$ 使 $\bar c_j>0$，说明增大它可以让 $z$ 变大 ⇒ 它是候选“入基”变量，选择入基变量有两种常用的好写的规则：
1. 取检验数最大的那个（$\bar c_j$ 最大的）。
2. 取下标最小的那个（$j$ 最小的）。
第 1 种可能会循环但是效率高，第 2 种更稳定但是效率低。
#### 2. 选出基变量
让 $x_e$ 增大时，基变量由 $D1$ 变化：
$$
x_{B_i} = \bar b_i - \bar a_{i e},x_e
$$
为了保持可行性 $x_{B_i}\ge 0$，需要
- 如果 $\bar a_{ie}>0$，则 $x_e \le \bar b_i/\bar a_{ie}$。
- 如果 $\bar a_{ie}\le 0$，则这一行不对 $x_e$ 上界造成限制（增大 $x_e$ 不会让该基变量变负）。
所以可行域允许的最大步长是
$$
x_e \le \min_{i:\bar a_{ie}>0}\frac{\bar b_i}{\bar a_{ie}}
$$
取达到最小值的那一行 $l$ 作为出基变量 $x_{B_l}$。这就是最小比值检验。
若所有 $\bar a_{ie}\le 0$，则 $x_e$ 没上界，且 $\bar c_e>0$ 会使 $z\to+\infty$，所以是 **无界**。
#### 3. pivot（换基）
设进基变量是 $x_e\in N$，出基变量是 $x_{B_l}$。
从出基那一行 $D1$ 取出：
$$
x_{B_l}=\bar b_l-\sum_{j\in N}\bar a_{lj}x_j
$$
把 $x_e$ 单独拎出来：
$$
x_{B_l}=\bar b_l-\bar a_{le}x_e-\sum_{j\in N\setminus{e}}\bar a_{lj}x_j
$$
移项并除以 $\bar a_{le}$（注意 pivot 元要求 $\bar a_{le}>0$ 才会被选为出基行）：
$$
x_e=\frac{\bar b_l}{\bar a_{le}}-\frac{1}{\bar a_{le}}x_{B_l}-\sum_{j\in N\setminus{e}}\frac{\bar a_{lj}}{\bar a_{le}}x_j
\tag{P0}
$$
现在把 $P0$ 代入所有其它行和目标行，使字典恢复成“基变量 = 常数 − 非基线性组合”的形式。
##### 3.1 更新其它约束行 $(i\neq l)
原来第 i 行：
x_{B_i}=\bar b_i-\bar a_{ie}x_e-\sum_{j\in N\setminus{e}}\bar a_{ij}x_j
代入 P0：
\begin{aligned}
x_{B_i}
&=\bar b_i-\bar a_{ie}\Big(\frac{\bar b_l}{\bar a_{le}}-\frac{1}{\bar a_{le}}x_{B_l}-\sum_{j\neq e}\frac{\bar a_{lj}}{\bar a_{le}}x_j\Big)
-\sum_{j\neq e}\bar a_{ij}x_j\\
&=\underbrace{\Big(\bar b_i-\bar a_{ie}\frac{\bar b_l}{\bar a_{le}}\Big)}_{\bar b'_i}
-\underbrace{\Big(-\bar a_{ie}\frac{1}{\bar a_{le}}\Big)}_{\text{系数对 }x_{B_l}}
x_{B_l}
-\sum_{j\neq e}\underbrace{\Big(\bar a_{ij}-\bar a_{ie}\frac{\bar a_{lj}}{\bar a_{le}}\Big)}_{\bar a'_{ij}}x_j
\end{aligned}
在新字典里，x_{B_l} 已经变成非基变量（因为它离开了基），所以它会出现在右侧。这没问题：新非基集合是 N'=(N\setminus{e})\cup{B_l}。
因此更新公式：
- RHS：
\boxed{\ \bar b'_i=\bar b_i-\bar a_{ie}\frac{\bar b_l}{\bar a_{le}}\ }\quad (i\neq l)
- 非进基列 j\neq e：
\boxed{\ \bar a'_{ij}=\bar a_{ij}-\bar a_{ie}\frac{\bar a_{lj}}{\bar a_{le}}\ }\quad (i\neq l,\ j\neq e)
- 对新加入的非基变量 x_{B_l} 的系数（如果你显式保留这列）：
\boxed{\ \bar a'_{i,B_l}= -\bar a_{ie}\frac{1}{\bar a_{le}}\ }\quad (i\neq l)
3.2 更新 pivot 行（新的基变量是 x_e）
由 P0 直接得到新基行（把它写成“基变量 = 常数 − …”）：
\boxed{
x_e=\underbrace{\frac{\bar b_l}{\bar a_{le}}}_{\bar b'_e}
-\frac{1}{\bar a_{le}}x_{B_l}
-\sum_{j\neq e}\frac{\bar a_{lj}}{\bar a_{le}}x_j
}
即 pivot 行更新：
- RHS：\bar b'_e=\bar b_l/\bar a_{le}。
- 对 (j\neq e)：\bar a'_{e j}= \bar a_{l j}/\bar a_{le}（注意在字典写法里右侧是 “（-\bar a'_{e j}x_j）”，所以很多实现里会存带符号的系数；你只要一致就行）。
- 对离基变量 (B_l)：系数是 (1/\bar a_{le})（同样注意符号约定）。
3.3 更新目标行
原来目标：
z=z_0+\bar c_e x_e+\sum_{j\neq e}\bar c_j x_j
代入 P0：
\begin{aligned}
z
&=z_0+\bar c_e\Big(\frac{\bar b_l}{\bar a_{le}}-\frac{1}{\bar a_{le}}x_{B_l}-\sum_{j\neq e}\frac{\bar a_{lj}}{\bar a_{le}}x_j\Big)+\sum_{j\neq e}\bar c_j x_j\\
&=\underbrace{\Big(z_0+\bar c_e\frac{\bar b_l}{\bar a_{le}}\Big)}_{z_0'}
+\underbrace{\Big(-\bar c_e\frac{1}{\bar a_{le}}\Big)}_{\text{对 }x_{B_l}\text{ 的新检验数}}x_{B_l}
+\sum_{j\neq e}\underbrace{\Big(\bar c_j-\bar c_e\frac{\bar a_{lj}}{\bar a_{le}}\Big)}_{\bar c'_j}x_j
\end{aligned}
所以：
- 新目标常数项：
\boxed{\ z_0' = z_0 + \bar c_e\frac{\bar b_l}{\bar a_{le}}\ }
- 新检验数（对原非基 j\neq e）：
\boxed{\ \bar c'_j = \bar c_j-\bar c_e\frac{\bar a_{lj}}{\bar a_{le}}\ }\quad (j\neq e)
- 对新非基变量 x_{B_l} 的检验数：
\boxed{\ \bar c'_{B_l} = -\bar c_e\frac{1}{\bar a_{le}}\ }
总结做法
单纯形表其实就是把字典的系数整理成一个表，并把“更新字典”实现成一次 pivot：
- 选 pivot 元素：出基行 l、进基列 e，pivot 值 p=\bar a_{le}。
- pivot 行更新：整行除以 p，让 pivot 变成 1。
- 消元：对每一行 (r\neq l)（包括目标行），做
\text{row}_r \leftarrow \text{row}_r - (\text{row}_r[e])\cdot \text{row}_l
P13337【模板】线性规划
要输出方案数，直接将非基变量输出就行，问题在于不保证 b_i \ge 0，所以需要两次单纯形，第一次单纯形求解一组可行解，第二次单纯形求解最大目标值，这里讲解第一次单纯形的方法。
1. 保证 b_i 非负
如果 b_i \le 0，就将整行乘以 -1，使得 RHS 非负。
2. 引入松弛和剩余变量：
-
\le：加松弛变量 s_i\ge 0。
a_i x + s_i = b_i
这条约束通常可以用 s_i 直接入基。
-
\ge：减去剩余变量 s_i\ge 0。
a_i x - s_i = b_i
这里的系数是 -1，不能直接用 s_i 当基变量（基需要像单位列那样的 +1）。
-
（=）：不加松弛也不加剩余，直接
a_i x = b_i
也没有现成的“单位列”可入基。
3. 引入人工变量：
所以对 2、3 两类，要引入 人工变量 a_i\ge 0：
4. 构造辅助目标函数
不管你原来要 max 还是 min，它的目标是把所有人工变量都压到 0。
常见写法：
\min\ w=\sum a_i
如果最优值 w>0：说明无论怎么选 x，都必须让至少一个人工变量 > 0 才能满足等式系统 ⇒ 原问题 不可行。
5. 跑单纯形
初始基变量就是人工变量，初始 RHS 就是 b_i。
6. 进入第 2 次单纯形
- 把人工变量列删掉。
- 处理“人工变量仍在基里”的情况。
即便 w=0，有时会出现某个人工变量仍是基变量，但它的值是 0。这时必须把它“换出基”，否则你删列会把基搞坏。
- 做法：
- 在该行里找一个非人工变量列，且该列系数不为 0，把它 pivot 进来，把人工变量 pivot 出去。
- 如果这一行里除人工变量外所有系数都为 0，而且 RHS 也为 0，说明这条约束线性相关，可以把这行删除。
P3980 志愿者招募
题意：
这个项目需要 n 天才能完成，其中第 i 天至少需要 a_i 个人。布布通过了解得知，一共有 m 类志愿者可以招募。其中第 i 类可以从第 s_i 天工作到第 t_i 天，招募费用是每人 c_i 元，求最小花费。
题解：
设 $x_i$ 表示第 $i$ 个志愿者是否选择，$b_{ij}$ 表示第 $i$ 个志愿者在第 $j$ 天是否工作，那么问题就是：
$$
\begin{aligned} \text{minimize} \quad & \sum_{i=1}^m c_i x_i \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \sum_{i=1}^m b_{ji} x_i \ge a_j \quad (j=1,2,\dots,n) \\ & x_i \ge 0 \end{aligned}
$$
因为单纯形法是求解最大化目标的问题，给问题对偶一下：
$$
\begin{aligned} \text{maximize} \quad & \sum_{j=1}^n a_j y_j \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \sum_{i=1}^n b_{ij} y_i \le c_j \quad (j=1,2,\dots,m) \\ & y_i \ge 0 \end{aligned}
$$
因为每个志愿者可以工作的区间是连续的，所以 b 每一行的 1 构成一个区间，转置一下满足引理的判定条件，所以 b 是全幺模矩阵，可以将问题转化为线性规划问题，直接用单纯形法求解即可。
## P3337 防守战线
题意：
战线可以看作一个长度为 $n$ 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第 $i$ 号位置上建一座塔有 $C_i$ 的花费，且一个位置可以建任意多的塔，费用累加计算。有 $m$ 个区间 $[L_1, R_1], [L_2, R_2], \cdots, [L_m, R_m]$，在第 $i$ 个区间的范围内要建至少 $D_i$ 座塔。求最少花费。
$n \le 1000,m \le 10000$。
题解：
设 $x_i$ 表示序列第 $i$ 个位置选了几个塔，$b_{ij}$ 表示对于第 $i$ 个区间第 $j$ 个位置是否在区间里面，那么问题就是：
$$
\begin{aligned} \text{minimize} \quad & \sum_{i=1}^n c_i x_i \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \sum_{i=1}^n b_{ji} x_i \ge d_j \quad (j=1,2,\dots,m) \\ & x_i \ge 0 \end{aligned}
$$
因为单纯形法是求解最大化目标的问题，给问题对偶一下：
$$
\begin{aligned} \text{maximize} \quad & \sum_{j=1}^m d_j y_j \\
\end{aligned}
$$
$$
\begin{aligned}\text{subject to} \quad & \sum_{i=1}^m b_{ij} y_i \le c_j \quad (j=1,2,\dots,n) \\ & y_i \ge 0 \end{aligned}
$$
因为区间的位置是连续的，同上是全幺模矩阵，所以可以直接单纯形。
## SGU 278 Fuel
题意：
一个燃料站有无限量的 $N$ 种燃料。每种燃料的密度为 $a_i$ ，成本为 $b_i$ ，强度为 $c_i$ 。 $m$ 公斤这种燃料的体积为 $ m \times a_i$ ，强度为 $m \times c_i$ ，成本为 $m \times b_i$ 美元。您的汽车可以储存各种燃料的混合物，但总容量不得超过 $A$ 。你有 $B$ 美元。你的任务是确定你能购买的最大燃料体积。请注意，你可以购买任何非负数的任何种类的燃料，而不一定是整数。（注意到这个体积计算公式不满足物理公式）
提示：这题考虑单老哥。
题解：
设 $m_i$ 表示燃料 i 购买的重量：
$$
\max \sum_{i=1}^N c_i m_i
$$
$$
\text{s.t.}\quad \sum a_i m_i \le A,\quad \sum b_i m_i \le B,\quad m_i\ge 0
$$
发现这个线性规划只有两个约束，因为最优解一定会落在顶点上，所以最优解最多用到两种燃料，但是不能直接枚举 $O(n^2)$ 会超时。
令
$$
x_i = c_i m_i \quad (\text{第 }i\text{ 种燃料贡献的强度})
\Rightarrow m_i = \frac{x_i}{c_i}
$$
代回约束：
$$
\sum \frac{a_i}{c_i} x_i \le A,\qquad
\sum \frac{b_i}{c_i} x_i \le B,\qquad
x_i\ge 0
$$
目标变成
$$
\max \sum x_i
$$
解释非常直观：
- 想获得 **1 单位强度**，用燃料 $i$ 要消耗
$$
p_i=\frac{a_i}{c_i}\ (\text{体积/强度}),\quad q_i=\frac{b_i}{c_i}\ (\text{金钱/强度})
$$
- 所以每种燃料对应平面点 $P_i=(p_i,q_i)$。
如果总强度 $S=\sum x_i$，则总消耗为
$$
(\text{体积},\text{金钱})=
\left(\sum p_i x_i,\ \sum q_i x_i\right)
= S\cdot \left(\sum \lambda_i p_i,\ \sum \lambda_i q_i\right)
$$
其中 $\lambda_i=x_i/S$，满足 $\lambda_i\ge 0,\ \sum\lambda_i=1$。
也就是说，“单位强度的平均消耗点”
$$
\bar P=(\bar p,\bar q)=\sum \lambda_i P_i
$$
可以是 **所有点 $P_i$ 的凸包中的任意点**。
而可行性要求
$$
S\bar p\le A,\quad S\bar q\le B
\Rightarrow
S\le \min\left(\frac{A}{\bar p},\frac{B}{\bar q}\right)
$$
因此答案变为：
> 在凸包 $\text{conv}({P_i})$ 上，最大化
>
> $$
> F(p,q)=\min\left(\frac{A}{p},\frac{B}{q}\right)
> $$
若存在 $P_j=(p_j,q_j)$ 满足
$$
p_j\le p_i,\ q_j\le q_i
$$
则燃料 $i$ 每 1 强度消耗不优于 $j$，永远没必要用 $i$。
所以先按 $p$ 升序，保留 $q$ 严格下降的一条链即可。
设
$$
k=\frac{B}{A}
$$
对任意点 $(p,q)$：
- 若 $q\le kp$，则 $\frac{A}{p}\le \frac{B}{q}$，体积约束更紧，$F(p,q)=\frac{A}{p}$。
- 若 $q\ge kp$，则钱更紧，$F(p,q)=\frac{B}{q}$。
因此最优点要么：
1. 落在某个凸包顶点（只卡住一个约束时），
2. 落在凸包边与直线 $q=kp$ 的交点（两个约束同时卡住：$\frac{A}{p}=\frac{B}{q}$，此时一定最优）。
做法：
- 先对所有凸包顶点算 $F$ 更新答案；
- 再扫描每条边，判断端点 $(f=q-kp)$ 是否异号，若相交就线段-直线求交点并更新。
复杂度：$O(N\log N)$。
## 结语
比较遗憾的是写的东西在线性规划里面偏简单，并没有将线性规划和其他算法联系起来（比如网络流）等。
因时间关系，很多东西的证明被一笔带过或没有，在此将本文并未证明的东西列出来：
1. 弱对偶定理和强对偶定理。
2. 全幺模矩阵推出整数规划问题等价于线性规划问题，这个可以参见：https://www.luogu.com.cn/paste/xi6i8dkm。
3. 如果矩阵的每一列的正负 1 形成一个区间那么就是全幺模。
4. 单纯形的期望运行时间（参见平滑分析）。
5. 二分图匹配和网络流的 LP 可行域是 IP。
6. 原始-对偶方法里面问题 Q4 的可行性。
后续填坑。