别线性规划

引入

• 做一把椅子：需 1 吨木材 + 2 个工时，利润 30 元。
• 做一张桌子：需 2 吨木材 + 1 个工时，利润 50 元。

$$\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}$$

• 线性规划中的每个不等式约束都描述了一个半平面，所有可行解的集合就是半平面交，因此可行解的集合就是一个凸多边形。
• 问题的最优解总可以取凸多边形的顶点。

标准型

$$\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. 添加负号转化最大最小问题和约束条件的方向。
2. 等式约束拆成两个方向相反的约束。
3. 如果变量没有正负数限制，将他替换成两个非负变量的差值。

对偶

1. 交换目标函数和约束符号的方向。
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}$$ $$\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，又因为右边两项非负，所以推出互补松弛性。

原始-对偶方法

$$\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}$$ $$\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}$$ $$I= \left\{i : (A^Ty-c)_i=0\right\}$$ $$\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$

$$\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}$$

全幺模矩阵

$$\det(\cdot)\in{0, 1, -1}.$$ $$\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. 再用最优解可在极点取得的性质，因此存在整数最优解。

单纯形法

$$\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. 找到原问题的一组可行解，然后一直执行换基操作，直到最优解不再改进。

定义

$$Ax + s = b$$

换基操作

$$A_B x_B + A_N x_N=b$$ $$A_B x_B = b - A_N x_N$$ $$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$$ $$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}$$

1. 选入基变量

1. 取检验数最大的那个（$\bar c_j$ 最大的）。
2. 取下标最小的那个（$j$ 最小的）。

2. 选出基变量

$$x_{B_i} = \bar b_i - \bar a_{i e},x_e$$

• 如果 $\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}}$$

3. pivot（换基）

$$x_{B_l}=\bar b_l-\sum_{j\in N}\bar a_{lj}x_j$$ $$x_{B_l}=\bar b_l-\bar a_{le}x_e-\sum_{j\in N\setminus{e}}\bar a_{lj}x_j$$ $$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}$$

3.1 更新其它约束行 $(i\neq l)$

$$x_{B_i}=\bar b_i-\bar a_{ie}x_e-\sum_{j\in N\setminus{e}}\bar a_{ij}x_j$$ $$\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}$$

• 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$）

$$\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 }$$

• 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$$ $$\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}}\ }$$

总结做法

1. 选 pivot 元素：出基行 $l$、进基列 $e$，pivot 值 $p=\bar a_{le}$。
2. pivot 行更新：整行除以 $p$，让 pivot 变成 1。
3. 消元：对每一行 $(r\neq l)$（包括目标行），做 $$\text{row}_r \leftarrow \text{row}_r - (\text{row}_r[e])\cdot \text{row}_l$$

P13337【模板】线性规划

1. 保证 $b_i$ 非负

2. 引入松弛和剩余变量：

1. $\le$：加松弛变量 $s_i\ge 0$。
   $$a_i x + s_i = b_i$$
   这条约束通常可以用 $s_i$ 直接入基。
2. $\ge$：减去剩余变量 $s_i\ge 0$。
   $$a_i x - s_i = b_i$$
   这里的系数是 $-1$，不能直接用 $s_i$ 当基变量（基需要像单位列那样的 $+1$）。
3. （=）：不加松弛也不加剩余，直接
   $$a_i x = b_i$$
   也没有现成的“单位列”可入基。

3. 引入人工变量：

• $\ge$：$a_i x - s_i + a_i = b_i$。
• $=$：$a_i x + a_i = b_i$。

4. 构造辅助目标函数

$$\min\ w=\sum a_i$$

5. 跑单纯形

6. 进入第 2 次单纯形

1. 把人工变量列删掉。
2. 处理“人工变量仍在基里”的情况。 即便 $w=0$，有时会出现某个人工变量仍是基变量，但它的值是 0。这时必须把它“换出基”，否则你删列会把基搞坏。
3. 做法：
   • 在该行里找一个非人工变量列，且该列系数不为 0，把它 pivot 进来，把人工变量 pivot 出去。
   • 如果这一行里除人工变量外所有系数都为 0，而且 RHS 也为 0，说明这条约束线性相关，可以把这行删除。

P3980 志愿者招募

$$\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}$$

P3337 防守战线

$$\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

$$\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$$ $$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)$。

$$(\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)$$ $$\bar P=(\bar p,\bar q)=\sum \lambda_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\le p_i,\ q_j\le q_i$$ $$k=\frac{B}{A}$$

• 若 $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)$ 是否异号，若相交就线段-直线求交点并更新。

结语

1. 弱对偶定理和强对偶定理。
2. 全幺模矩阵推出整数规划问题等价于线性规划问题，这个可以参见：https://www.luogu.com.cn/paste/xi6i8dkm。
3. 如果矩阵的每一列的正负 1 形成一个区间那么就是全幺模。
4. 单纯形的期望运行时间（参见平滑分析）。
5. 二分图匹配和网络流的 LP 可行域是 IP。
6. 原始-对偶方法里面问题 Q4 的可行性。