• 2021 年国家集训队论文 南京外国语学校 丁晓漫 再探线性规划对偶在信息学竞赛中的应用
• 算法设计与分析（2024 年春季学期）栗师 Linear Programming
• Summer School (July 12 — July 16, 2024) 栗师 Combinatorial Optimization Via Linear Programming
• 线性规划与网络流 Larunatrecy
• 《再探线性规划对偶在信息学竞赛中的应用》 - 学习笔记 - p_b_p_b - 博客园
• 线性规划 - ez_lcw - 博客园
• 费用流线性规划对偶的构造方案 - 洛谷专栏
• 数学规划与运筹学 (12) 内点法 - 知乎
• 【线性规划(七)】内点法 - 知乎
• 数学规划与运筹学 (11) Khachyian 椭球法 - 知乎
• Linear Programming - The Simplex Algorithm(1) - 知乎
• 浅谈 OI 中的一些对偶类问题 - 洛谷专栏
• 对偶 - 题单 - 洛谷 | 计算机科学教育新生态 来自 教寺院训练营，私有状态。
• 线性规划基础 - OI Wiki
• Wikipedia

Linear Programming

Introduction

---

$$\begin{aligned} \min\quad 7x_1+4x_2& \quad \text{s.t.}\\ x_1+x_2&\geq 5\\ x_1+2x_2&\geq 6\\ 4x_1+x_2&\geq 8\\ x_1,x_2&\geq 0 \end{aligned}$$

---

$$\begin{aligned} \min\quad c_1x_1+c_2x_2+\dots+c_n x_n& \quad \text{s.t.}\\ a_{1,1}x_1 + a_{1,2}x_2 + \cdots + a_{1,n}x_n&\geq b_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + \cdots + a_{2,n}x_n&\geq b_2 \\ \vdots \qquad \vdots \qquad \vdots \qquad \vdots \qquad \\ a_{m,1}x_1 + a_{m,2}x_2 + \cdots + a_{m,n}x_n&\geq b_m \\ x_1,x_2,\cdots,x_n&\geq 0 \end{aligned}$$ $$x := \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \in \mathbb{R}^n$$ $$c := \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix} \in \mathbb{R}^n$$ $$A := \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{pmatrix} \in \mathbb{R}^{m \times n}$$ $$b := \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} \in \mathbb{R}^m$$ $$\begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&\geq b\\ x&\geq 0 \end{aligned}$$

• 如果求 $\max$ 就是求目标函数的相反数的 $\min$。
• 如果取值是 $x_i\geq -a$ 则可以用 $x_i+a$ 代替 $x_i$。
• 如果某个变量 $x_i$ 没有约束，引入两个新的变量 $x_i',x_i''$ 用 $x_i'-x_i''$ 代替 $x$。
• 如果是 $\leq$ 号，那条限制乘上 $-1$。
• 如果是 $=$ 号，那么再拼一个 $\leq$ 的限制出来就可以强行取等。

---

---

$$\lambda_1 + \lambda_2 + \cdots + \lambda_t = 1,$$ $$\lambda_1 x^{(1)} + \lambda_2 x^{(2)} + \cdots + \lambda_t x^{(t)} = x.$$

---

• 如果可行域为空，最小值是 $\infty$。
• 如果可行域 unbounded，也就是存在方向使目标函数可以无限减小，最小值是 $-\infty$。

Methods for Solving Linear Programs

---

$$\begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&= b\\ x&\geq 0 \end{aligned}$$ $$\begin{aligned} \min\quad 1^{\mathsf T}a& \quad \text{s.t.}\\ Ax+a&= b\\ x,a&\geq 0 \end{aligned}$$ $$\begin{aligned} \min\quad c^{\mathsf T}x+M1^{\mathsf T}a& \quad \text{s.t.}\\ Ax+a&= b\\ x,a&\geq 0 \end{aligned}$$

---

---

---

Linear Programming Duality

$$\begin{aligned} \min\quad 7x_1+4x_2& \quad \text{s.t.}\\ x_1+x_2&\geq 5\\ x_1+2x_2&\geq 6\\ 4x_1+x_2&\geq 8\\ x_1,x_2&\geq 0 \end{aligned}$$ $$7x_1+4x_2\geq 3(x_1+x_2)+(4x_1+x_2)\geq 3\times 5+8=23$$ $$\begin{aligned} \max\quad 5y_1+6y_2+8y_3& \quad \text{s.t.}\\ y_1+y_2+4y_3&\leq 7\\ y_1+2y_2+y_3&\leq 4\\ y_1,y_2,y_3&\geq 0 \end{aligned}$$ $$\begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&\geq b\\ x&\geq 0 \end{aligned}$$ $$\begin{aligned} \max\quad b^{\mathsf T}y& \quad \text{s.t.}\\ A^{\mathsf T}y&\leq c\\ y&\geq 0 \end{aligned}$$ $$A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 4 & 1 \end{pmatrix}$$ $$b = \begin{pmatrix} 5 \\ 6 \\ 8 \end{pmatrix}$$ $$c = \begin{pmatrix} 7\\ 4 \end{pmatrix}$$

• 弱对偶定理 Weak Duality Theorem：$D\leq P$
• 强对偶定理 Strong Duality Theorem：$D=P$

设 $x^*$ 为原线性规划问题的解，$y^*$为对偶线性规划问题的解：

$D=b^{\mathsf T}y^*\leq (Ax^*)^{\mathsf T}y^*=(x^*)^{\mathsf T}A^{\mathsf T}y^*\leq (x^*)^{\mathsf T}c=c^{\mathsf T}x^*=P$

事实：如果一个点 $x$ 不属于多面体 $\mathcal P$，那么存在一个超平面将 $x$ 与 $\mathcal P$ 分开。

引理 Farkas Lemma：$Ax=b,x\geq 0$ 无可行解，当且仅当存在 $y$ 使得 $y^{\mathsf T} A \geq 0$ 且 $y^{\mathsf T} b \lt 0$ 可行。

$b\notin\{Ax:x\geq 0\}$，因此存在一个超平面将 $b$ 与 $\{Ax : x \geq 0\}$ 分开。

记该超平面为 $y^{\mathsf T} z = g$，则对于所有 $x \geq 0$ 有：$y^{\mathsf T} b \lt g$ 且 $y^{\mathsf T}Ax \gt g$。

由此可得：$g < 0$ 且 $y^ A \geq 0$。

因此：$y^{\mathsf T}b < g < 0$。

引理 Farkas Lemma 的变形：$Ax\leq b,x\geq 0$ 无可行解，当且仅当存在 $y$ 使得 $y^{\mathsf T} A \geq 0$ 且 $y^{\mathsf T} b\lt 0$ 且 $y\geq 0$ 可行。

改写为等价形式：$Ax+x'=b$，$x,x'\geq 0$。

即 $(A,I)\begin{pmatrix}x\\x'\end{pmatrix}=b,\begin{pmatrix}x\\x'\end{pmatrix} \geq 0$。

根据 Farkas 引理，存在 $y$ 使得 $y^{\mathsf T}(A,I)\geq 0,y^{\mathsf T}b\lt 0$。

等价于 $y^{\mathsf T}A\geq 0,y\geq 0,y^{\mathsf T}b\lt 0$。

对于任意 $\varepsilon > 0$，方程组 $\begin{pmatrix}-A & c^{\mathsf T} \end{pmatrix} x \le \begin{pmatrix}-b \\ P - \varepsilon \end{pmatrix}, x \geq 0$无可行解。

根据 Farkas 引理，存在 $y \in \mathbb{R}^m, y \geq 0$ 和 $\alpha \geq 0$，使得 $(y^{\mathsf T}, \alpha) \begin{pmatrix}-A & c^{\mathsf T} \end{pmatrix} \geq 0, (y^{\mathsf T}, \alpha) \begin{pmatrix}-b \\ P - \varepsilon \end{pmatrix} < 0$。

我们可以证明 $\alpha > 0$。不失一般性，假设 $\alpha = 1$，则有：$-y^{\mathsf T} A + c^{\mathsf T} \geq 0,- y^{\mathsf T} b + P - \varepsilon < 0$。

等价于 $A^{\mathsf T} y \le c, b^{\mathsf T} y > P - \varepsilon$。

由于该结论对任意 $\varepsilon > 0$ 都成立，因此$D > P - \varepsilon \implies D = P$，因为 $D \leq P$。

---

$$\begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&\leq b\\ x&\geq 0 \end{aligned}$$

1. 检查原始可行性：询问问题 $Ax\leq b,x\geq 0$ 是否有解。若无则 Infeasible。
2. 检查对偶可行性：询问问题 $A^{\mathsf T}y\leq c,y\geq 0$ 是否有解。若无则 Unbounded。
3. 询问问题：
   $$\begin{aligned} c^{\mathsf{T}}x&\leq b^{\mathsf{T}} y\\ Ax&\leq b\\ x&\geq 0\\ A^{\mathsf{T}}y&\leq c\\ y&\geq 0 \end{aligned}$$
   根据强对偶定理，这个问题必然有解 $(x^*,y^*)$ 对应原始问题和对偶问题的最优解。

Integral Polytopes: Exact Algorithms Using LP

---

$$\begin{aligned} \min\quad \sum\limits_{e\in E} w_ex_e& \quad \text{s.t.}\\ \sum\limits_{e\in \delta(v)}x_e&\leq 1\quad \forall v\in L\cup R\\ x_e&\in \{0,1\}\quad \forall e\in E \end{aligned}$$ $$x_e\in \{0,1\}\quad \forall e\in E$$ $$x_e\geq 0\quad \forall e\in E$$

选一个 $x$ 在可行域 $P$ 中

相当于证明：若 $x$ 不是整点则能推到 $x$ 不是极点。

而极点不能被凸组合出来，所以等价于不是整点的话，找到 $x',x''\in P$，且 $x'\neq x''$，且 $x=\frac{1}{2}(x'+x'')$ 即可。

• 第一种情况：那些 $0\lt x_e\lt 1$ 的边出现了环。

我们对环用蓝色和红色染色。对于 $x'$，给每条蓝边 $+\epsilon$，红边 $-\epsilon$。对于 $x''$，给每条蓝边 $-\epsilon$，红边 $+\epsilon$。

• 第二种情况：那些 $0\lt x_e\lt 1$ 的边形成了森林（就是无环）。

我们把叶子拿出来，选一条从叶子到叶子的路径，用蓝色红色染色。对于 $x'$，给每条蓝边 $+\epsilon$，红边 $-\epsilon$。对于 $x''$，给每条蓝边 $-\epsilon$，红边 $+\epsilon$。

所以不是整点的点我们总能找到 $x',x''$ 凸组合出来。那么极点就一定都是整点了。

---

$$\forall e\in E,0\leq f(e)\leq c_e\\ \forall v\in V\setminus\{s,t\},\sum\limits_{e\in \delta^\text{in}(v)} f(e)=\sum\limits_{e\in \delta^\text{out}(v)} f(e)$$ $$\begin{aligned} \max\quad \sum\limits_{e\in \delta^\text{in}(t)} x_e& \quad \text{s.t.}\\ x_e&\leq c_e\quad &\forall e\in E\\ \sum\limits_{e\in \delta^\text{in}(v)} x_e-\sum\limits_{e\in \delta^\text{out}(v)} x_e&=0\quad &\forall v\in V\setminus\{s,t\}\\ x_e&\geq 0\quad &\forall e\in E \end{aligned}$$

任选一个 $s\text{-}t\ \text{flow}$ $x$，包含 $0\lt x_e\lt 1$ 的边集叫做 $E'$。

那么每个 $v\notin \{s,t\}$ 都必须有 $0$ 条或者 $\geq 2$ 条边在 $E'$ 中（$1$ 条的话显然整数和分数之间不会流守恒）。

忽略掉 $E'$ 中边的方向，那么他含有一个环或者存在一条 $s\text{-}t$ 的路径。

那么把环或者路径拿出来整体 $+\epsilon$ 或 $-\epsilon$。

$$\begin{aligned} \max\quad d^{\mathsf T}x& \quad \text{s.t.}\\ \begin{pmatrix}B'\\-B'\\I\end{pmatrix}x&\leq \begin{pmatrix}0\\0\\c\end{pmatrix}\\ x&\geq 0 \end{aligned}$$ $$\begin{aligned} B_{v,e}=\begin{cases} +1&,e\in \delta^{\text{in}}(v)\\ -1&,e\in \delta^{\text{out}}(v)\\ 0&,\text{otherwise} \end{cases} \end{aligned}$$ $$d_e=\begin{cases}1&,e\in \delta^{\text{in}}(t)\\0&,\text{otherwise}\end{cases}$$ $$\begin{aligned} \min\quad \sum\limits_{e\in E}c_ey_e& \quad \text{s.t.}\\ \pi_v-\pi_u+y_{(u,v)}&\geq 0\quad &\forall (u,v)\in E\\ \pi_s-\pi_t&\geq 1\\ y_e&\geq 0\quad &\forall e\in E \end{aligned}$$ $$\begin{aligned} \min\quad 0^{\mathsf T}u+0^{\mathsf T}v+c^{\mathsf T}y& \quad \text{s.t.}\\ (B')^{\mathsf T}u+(-B')^{\mathsf T}v+I^{\mathsf T}y&\geq d\\ u,v,y&\geq 0 \end{aligned}$$

---

$$\begin{aligned} \min\quad \sum\limits_{i\in [n]}x_iw_i& \quad \text{s.t.}\\ \sum\limits_{i\in[n]:t\in[s_i,f_i)} x_i&\leq 1\quad &\forall t\in [T]\\ x_i\geq 0 \end{aligned}$$

• 如果一个多胞体 $P$ 是 $Ax\geq b,x\geq 0$ 的可行域，并且 $A$ 是 TUM 矩阵，$b$ 是 Integral 的，则 $P$ 是 Integral Polytope。
• 一个矩阵 $A\in\{0,1\}^{m\times n}$ 如果 $1$ 在每一列中形成一个区间，则 $A$ 是 TUM 矩阵。

• 如果 $A'\in \{0,\pm 1\}^{n\times n}$ 满足 $A'$ 每行最多一个 $1$ 最多一个 $-1$，那么 $\det(A')\in\{0,\pm 1\}$。
• 如果 $A\in \{0,\pm 1\}^{m\times n}$ 满足 $A$ 每行最多一个 $1$ 最多一个 $-1$，那么 $A$ 是 TUM 矩阵。证出上一条显然可以得到。故而可以得到推论：$s\text{-}t\ \text{flow}$ 的 LP 可行域是 Integral Polytope。
• 二分图的“边-点关联矩阵”是 TUM 矩阵。故而可以得到推论：二分图最大权匹配的 LP 可行域是 Integral Polytope。

---

$$\begin{aligned} \min\quad \sum\limits_{e}w_ex_e& \quad \text{s.t.}\\ x_e&\leq c_e\\ \sum\limits_{e\in \delta^\text{out}(v)} x_e-\sum\limits_{e\in \delta^\text{in}(v)} x_e&\leq b_v\\ x_e&\geq 0 \end{aligned}$$ $$\begin{aligned} \max\quad \sum\limits_{u}-b_up_u-\sum\limits_{e}c_ez_e& \quad \text{s.t.}\\ p_v-p_u-z_{(u,v)}&\leq w_{(u,v)}\\ p_u,z_e&\geq 0 \end{aligned}$$

Examples in OI

P3337 [ZJOI2013] 防守战线

$$\begin{aligned} \min\quad \sum\limits_{i\in[1,n]}C_ix_i& \quad \text{s.t.}\\ \sum\limits_{i\in [l_j,r_j]} x_i&\geq D_j\\ x_i&\geq 0 \end{aligned}$$

P3980 [NOI2008] 志愿者招募

$$\begin{aligned} \min\quad \sum\limits_{j\in[1,m]}c_jx_j& \quad \text{s.t.}\\ \sum\limits_{i\in [s_j,t_j]} x_j&\geq a_i\\ x_j&\geq 0 \end{aligned}$$ $$\begin{aligned} \max\quad \sum\limits_{i\in[1,n]}a_iy_i& \quad \text{s.t.}\\ \sum\limits_{i\in [s_j,t_j]} y_i&\leq c_j\\ y_i&\geq 0 \end{aligned}$$

教寺院训练营 模拟赛 R5 A. 放犬多

$$\begin{aligned} \max\quad \sum\limits_{e\in E}w_ex_e& \quad \text{s.t.}\\ \sum\limits_{e\in \operatorname{Path}(u_j,v_j)} x_e&\leq c_j\\ x_e&\geq 0 \end{aligned}$$

QOJ5036 卑鄙的下毒人

QOJ4899 机器

$$\begin{aligned} \max\quad \sum\limits_{e}w_ex_e& \quad \text{s.t.}\\ x_e&\leq c_e\\ \sum\limits_{e\in \delta^\text{out}(v)} x_e-\sum\limits_{e\in \delta^\text{in}(v)} x_e&=0\\ x_e&\geq 0 \end{aligned}$$ $$\begin{aligned} \min-\sum\limits_{e}c_ez_e& \quad \text{s.t.}\\ p_v-p_u-z_{(u,v)}&\leq w_{(u,v)}\\ z_e&\geq 0 \end{aligned}$$ $$\sum \infty\max\{0,p_u+(h_u-h_v)-p_v\}+\sum \max\{0,p_s+(-a_{i,j})-p_i\}+\sum \max\{0,p_i+(-b_{i,j})-p_s\}$$

CF1765J Hero to Zero

$$\sum p_i+\sum q_j+\sum (c_{i,j}-p_i-q_j)$$ $$(\sum c_{i,j})-(n-1)(\sum p_i+\sum q_j)$$ $$\begin{aligned} \min\quad \sum c_{i,j}x_{i,j}& \quad \text{s.t.}\\ \sum\limits_{1\leq j\leq n} x_{i,j}&=1\quad &\forall 1\leq i\leq n\\ \sum\limits_{1\leq i\leq n} x_{i,j}&=1\quad &\forall 1\leq j\leq n\\ x_{i,j}&\geq 0 \end{aligned}$$

ABC224H Security Camera 2

$$\begin{aligned} \min\quad \sum a_ix_i+\sum b_jy_j& \quad \text{s.t.}\\ x_i+y_j&\geq c_{i,j}\\ x_i,y_j&\geq 0 \end{aligned}$$ $$\begin{aligned} \max\quad \sum c_{i,j}z_{i,j}& \quad \text{s.t.}\\ \sum\limits_{L+1\leq j\leq L+R}z_{i,j}&\leq a_i\quad &\forall 1\leq i\leq L\\ \sum\limits_{1\leq i\leq L}z_{i,j}&\leq b_j\quad &\forall L+1\leq j\leq L+R\\ z_{i,j}&\geq 0 \end{aligned}$$

CF605C Freelancer's Dreams

$$\begin{aligned} \min\quad \sum z_i& \quad \text{s.t.}\\ \sum a_iz_i&\geq p\\ \sum b_iz_i&\geq q\\ z_i&\geq 0 \end{aligned}$$ $$\begin{aligned} \max\quad px+qy& \quad \text{s.t.}\\ a_ix+b_iy&\leq 1\\ x,y&\geq 0 \end{aligned}$$