Linear Programming & Simplex Method

翻了两本书和四五篇论文的笔记总和……

Linear Programming & Simplex Method

Linear Programming

Optimization goal 最优化目标：某个线性函数值。

Subject to 限制于：线性等式或不等式组。

Namely 形式化：

$$ \begin{align} \max (\min) ~&\bold c^T\bold x \\ \text{s.t.} ~ &\bold A \bold x\le(=/\ge) \mathrm {\bold b} \\ & \bold x \ge \bold0 \end{align} $$

Standard Form

$$ \begin{align} \max~ &\bold c^T\bold x\\ \text{s.t.} ~& \bold A\bold x\le \bold b \\ &\bold x \ge \bold0 \end{align} $$

Relaxation

$$ \begin{align} \max ~& \bold c^T\bold x \\ \text{s.t.} ~& \bold A\bold x=\bold b \\ & \bold x\ge \bold 0 \end{align} $$

Transformation

With Minimum Goal

$$ \min \bold c^T\bold x \Leftrightarrow-(\max\bold {(-c)}^T \bold x) $$

With Equality Condition

$$ \sum_j a_{i,j} x_j=b_i \Leftrightarrow \begin{cases} \sum_j a_{i,j}x_j\le b_i \\ \sum_ja_{i,j}x_j\ge b_i \end{cases} $$

With Greater Inequality Condition

$$ \sum_j a_{i,j}x_j\ge b_i \Leftrightarrow \sum_j (-a_{i,j})x_j\le-b_i $$

Without Non-negative Constraint

$$ x_i \not \ge 0 \Leftrightarrow \begin{cases} x_i \leftarrow x_{i1}-x_{i2} \\ x_{i1},x_{i2} \ge 0 \end{cases} $$

From Standard Form To Relaxation

$$ \sum_j a_{i,j}x_j\le b_i \to \sum_j a_{i,j}x_j+x_{n+i}=b_i, x_{n+i} \ge 0 $$

Some Examples

Ex. (最短路) $ n $ 点 $ m $ 边带权无向图，求 $ s $ 到 $ t $ 最短路。

M. $ \min \{d_t:d_s=0, d_{v,i} \le d_{u,i}+w_{u,v}, \forall (u,v)\in E\} $ .

Ex. (最优资源配置) $ m $ 资源 $ n $ 项目，每个资源上限 $ b_j(1\le j\le m) $. 第 $ i $ 个项目做出 $ x_i $ 的成果量，可获得 $ c_ix_i $ 的收益，同时消耗第 $ j $ 种资源 $ a_{i,j}x_i $ . 求最大收益.

M. $ \max\{c_ix_i:\sum_{i=1}^n a_{i,j} x_i\le b_j,1\le j\le m; x_i\ge 0,1\le i\le n \} $ .

Ex. (最佳物资供给) $ m $ 需求. 对 $j $ 需求需要 $ b_j $ 的资源. 有 $ n $ 种物资，其中第 $ i $ 种可以给第 $ j $ 种需求 $ a_{i,j} $ 的量. 假设第 $ i $ 种物资供给了 $ x_i $ 单位，需支付费用 $ c_ix_i $ . 最小化总费用.

M. $\min\{ c_ix_i:\sum_{i=1}^ma_{i,j}x_j\ge b_j,1\le j\le m;x_i\ge 0,1\le i\le n \}$ .

Ex. (多物网络流) $ n $ 点有向图，$ i $ 到 $ j $ 流量限制为 $ l_{i,j} $ . 现有 $ p $ 商品线路，第 $ i $ 条从 $ s_i $ 向 $ t_i $ 运输 $ d_i $ 个商品，求是否存在可行解.

M. $\max\{ 0:f_{k,u,v}\le l_{u,v},\sum_kf_{k,u,v}\le l_{u,v}, f_{k,u,v}=-f_{k,v,u},\sum_if_{k,u,i}=0,\sum_i f_{k,s_i,v}=d_i \}$ .检查是否有解即可.

N. 该问题不存在 LP 意外的高效做法.

Simplex Method

在松弛型中，称 $ (x_i)_{i=1}^n $ 为非基变量，赋初值为 $ 0 $ ；称 $ (x_i)_{i=n+1}^{n+m} $ 为基变量，赋初值为 $ b_{i-n} $ .

易看出当 $ (b_i)_{i=1}^n \ge 0 $ 时此初始状态为可行解，考虑找出两个交换可以优化的变量，执行转轴。

Pivot(l, e)

交换基变量 $ x_{n+l} $ 与非基变量 $ x_e $ 的表达式，使得二者位置互换。

$$ x_{n+l}=b_l-\sum_ja_{i,j}x_j \\ x_e={1\over a_{l,e}}(b_l-\sum_{j\neq e}a_{l,j}x_j-x_{n+l}) $$

交换下标。若需记录方案则多记录一下原来对应的下标。

Optimization

优化基础可行解。

1. 选 $ x_e : c_e\ge 0 $ ;
2. 找 $ x_{n+l} : a_{l,e}>0,\max {b_l \over a_{l,e}} $ ;
3. pivot(l, e);
4. 重复 1°.

算法停止，当且仅当

1. 找不出 $ e $ ，此时满足各条件；
2. 找不出 $ l $ ，此时无界，最优解为 $ +\infty $ .

该算法自然是完备的。

Initialization

以上我们假定了 $ \forall b_i\ge 0 $ ，如果没有这个条件，我们需要引入一个辅助 LP 来确定初值。

$$ \begin{align} \max ~&-x_0 \\ \text{s.t.} ~& x_{i+n}=b_i-\sum_j a_{i,j}x_j+x_0 \\ & x_i \ge 0 \end{align} $$

这种构造使得这个新 LP 问题使用上述过程必然可以找到一组可行解（只要存在；如果不存在那么可行域必为空）。

可知当 $ x_0=0 $ 时，各初解满足，可以开始执行前述二过程找最优解。

Complexity

只需分析 pivot 的执行次数。这是 $ \mathcal O{n+m\choose n} $ 的. 空间是 $ \mathcal O(nm) $ 的. 差不多可以认为 $ \mathcal O($存的下$)=\mathcal O($跑得过$) $ .

LP on Network Flow

Maxflow

$$ \begin{align} \max ~&\sum_v f_{s,v}\\ \text{s.t.} ~&\sum_v f_{u,v}-\sum_vf_{v,u}=0\\ &f_{u,v}\le c_{u,v}\\ &f_{u,v}\ge 0 \end{align} $$

分别是流量平衡条件，流量限制，流量非负.

Mincost Maxflow

同上，将目标函数修改为 $ \min \sum_{(u,v)\in E}f_{u,v}w_{u,v} $ 即可.

Maximum Bipartite Matching

$$ \begin{align} \max ~& \sum_{x\in X,y\in Y} f_{x,y} \\ \text{s.t.}~&\sum_{u\in X} f_{u,v}\le 1 \\ &\sum_{v\in Y} f_{u,v} \le 1 \end{align} $$

Maximum Weight Bipartite Matching

同上，目标函数改为 $ \max \sum_{x\in X,y\in Y} f_{u,v}w_{u,v} $ .

Duality

有时候考虑对偶问题有助于我们更好的分析问题的性质和建模。

对偶：将约束视为变量，约束之间的关系视为新的约束，形式化说来

$$ \begin{align} &(\text {LP})\min \{\bold c^T\bold x: \bold A\bold x\le\bold b,\bold x\ge 0,\bold x\in\mathbb R^n\} \\ &(\text {LD})\max \{\bold b^T\bold y: \bold A^T\bold y\ge\bold c, \bold y\ge 0,\bold y\in\mathbb R^m \} \end{align} $$

(LP) 与 (LD) 互为对偶问题. 并且显然 $ \text{opt(LP)}\ge \text{opt(LD)} $ . 更进一步我们有

Theorem(强对偶定理) 当存在最优解，上式等号恒成立.

有些性质和总结

1. 原问题的变量对应对偶问题的约束条件；
2. 原问题的约束条件对应对偶问题的变量；
3. 原问题与对偶问题的目标函数方向相反；
4. 原问题无约束对应对偶问题变量为零，反之亦然；
5. 对偶问题的对偶问题是原问题.

Some Examples

最大流最小割 假设汇点回流到源点，我们有 $ \max \{f_{t,s} : f_{u,v}\le c_{u,v},\sum_v f_{u,v}=\sum_vf_{v,u},f_{u,v}\ge0 \} $ .

令 $ p_u:=[u\in S], d_{u,v}:=\max\{p_u-p_v,0\} $ ，则最小割为 $ \min\{ \sum_{(u,v)\in E} c_{u,v}d_{u,v}:d_{u,v}-p_u+p_v\ge 0,p_s-p_t\ge 1,p_u,d_{u,v}\in \{0,1\} \} $ .

最大流的对偶问题是 $ \min\{ \sum_{(u,v)\in E} c_{u,v}d_{u,v}:d_{u,v}-p_u+p_v\ge0,p_s-p_t\ge1,d_{u,v}\ge0 \} $ .

据说可以证得一定存在最优解使得 $ p_u\in\{0,1\} $ ，这样就证明了最大流最小割定理了.

二分图最大匹配最小点覆盖 二分图最大匹配 $ \max\{\sum_{u\in X,v\in Y} f_{u,v} : \sum_{u\in X}f_{u,v}\le1,\sum_{v\in Y}f_{u,v}\le1 \} $ .

对偶问题为 $ \min\{\sum_{u\in X}p_u+\sum_{v\in Y}p_v:p_u+p_v\ge1,p_u,p_v\ge0 \} $ .

二分图最大权匹配最小顶标和 二分图最大权匹配 $ \max\{ \sum_{u\in X,v\in Y} c_{u,v}f_{u,v} :\sum_{x\in X}f_{u,v}\le1,\sum_{v\in Y} f_{u,v}\le1 \} $ .

对偶问题为 $ \min\{ \sum_{u\in X}p_u+\sum_{v\in Y}p_v :p_u+p_v\ge w_{u,v}, p_u,p_v\ge0 \} $ .

Integer Programming

考虑取值范围为整数的整数规划问题 Integer Programming 及其对偶

$$ \begin{align} &(\text {IP})\min \{\bold c^T\bold x: \bold A\bold x\le\bold b,\bold x\ge 0,\bold x\in\mathbb Z^n\} \\ &(\text {ID})\max \{\bold b^T\bold y: \bold A^T\bold y\ge\bold c, \bold y\ge 0,\bold y\in\mathbb Z^m \} \end{align} $$

因为 (IP) 比 (LP) 紧，所有应该有 $ \text{opt(LP)}\le\text{opt(IP)} $ ，考虑对称性和强对偶定理，则一般我们有

$$ \text{opt(ID)}\le\text{opt(LD)}=\text{opt(LP)}\le\text{opt(IP)} $$

虽然有看起来不错的性质，但是

Theorem 求解整数规划问题是 NP-hard 的.

那么我们只考察一些特殊情况.

Totally Unimodular Matrix

全幺模矩阵指该矩阵的任意一个行列数相等的满秩的子矩阵的行列式值都为 $ \pm 1 $ . $ A $ 是全幺模的一个充分条件为

• $ A $ 全由 $ -1,0,1 $ 构成；
• $ A $ 每列最多包含两个非零数；
• $ A $ 的行可以被划分为两个集合 $ B,C $ ，若有一行包含相同符号的非零数则被分在不同集合，否则相同.

一个我们更为关心的性质是如果一个 LP 的系数矩阵是全幺模的，那么单纯性涉及到的所有约束系数都是 $ -1,0,1 $ 之中一个，也即 LP 与 IP 得到的解在这种情况下是相同的.

某些非常特殊的 DP 和所有网络流问题的约束矩阵都是全幺模的.

LP on Game Theory

来看看 LP 在博弈论里的用处.

Nash Equilibrium

Nash 均衡指在二人或多人博弈中的这样一种状态，任何一方单方面更改策略都不能使自己获得更高收益.

如果在一个策略组合中，每个人的策略都是固定的，那么称此为纯策略 Nash 均衡. 如果每个人的策略是以一定概率组合起来的，则称混合策略 Nash 均衡.

Theorem 对于任意一个决策数有限的零和博弈，存在至少一个混合策略 Nash 均衡.

那么这种情况就可以将问题转化为可以用 LP 来做了.