线性规划

Published: June 27, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 线性规划原理
  • 转换为标准型
  • 转换为松弛型
  • 线性规划几何解释
• 单纯形算法
• 整数规划与全幺模矩阵
• 对偶线性规划
• 对偶线性规划的应用
  • 最大流和最小割
  • 二分图最大权匹配和最小顶标和
  • 最小费用最大流和最短路
• 参考资料

线性规划原理

线性规划用于在某个约束条件下，优化某个线性函数。其标准型如下：

$$\left. \begin{array}{lc} \max & c^Tx\\ s.t. & Ax\leq b\\ & x\geq 0 \end{array} \right.$$

我们可以通过加入一些松弛变量，将其变成松弛型：

$$\left. \begin{array}{lc} \max & c^Tx\\ s.t. & Ax = b\\ & x\geq 0 \end{array} \right.$$

其中所有涉及的数值都是实数，$A\in \mathbb{R}^{m\times n},c,x\in \mathbb{R}^n,b\in \mathbb{R}^m$。定义$P=\left\{x\mid Ax=b\land x\geq 0\right\}$，即所有可行解的集合。

我们下面的讨论均认为$A$的行向量是线性无关的，即$m\leq n$。

转换为标准型

如果约束公式形式为$\sum_j a_{ij}x_j \geq b_i$，那么我们可以记

$$a'_{ij}=-a_{ij}$$

并将约束公式替换为

$$\sum_j a'_{ij}x_j \leq -b_i$$

如果约束条件为$\sum_j a_{ij}x_j = b_i$，可以拆分成两个约束条件$\sum_j a_{ij}x_j \leq b_i$以及$\sum_j a_{ij}x_j \geq b_i$。

如果某个变量$x_i$没有约束，那么可以替换为$x_i=x_i'-x''_i$，其中$x'_i,x''_i\geq 0$。

转换为松弛型

如果约束条件形式为$\sum_j a_{ij}x_j \leq b_i$，我们可以增加一个松弛变量$s_i$，满足$s_i\geq 0$，并将约束公式替换为$\sum_j a_{ij}x_j+s_i=b_i$。

线性规划几何解释

所有满足线性规划的$m+n$个约束条件的向量集合$P$，我们可以将其理解为$\mathbb{R}^{n-m}$空间中用半平面切出的凸包。凸包的特点就是$P$中任意两点$a,b$指定的直线上的所有点也是$P$中的点。

命题1：在凸包顶点处可以取得线性规划的最优解

假设我们在凸包非顶点处$x$上取到了最优解。那么一定存在某个非$0$向量$d$，满足$x\pm d\in P$，即$A(x\pm d)=b\Rightarrow Ad=0$。如果$x_i=0$，那么一定有$d_i=0$。且由于$x$上是最优解，我们可以推出$c^Td=0$。

由于$d$非0，因此一定存在某个$i$，满足$x_i,d_i>0$（否则我们取$-d$即可），我们选择一个合适的$\lambda$，满足$x_i-\lambda d_i=0$,即我们从$x$转移到$x'=x-\lambda d$处，且$x'\geq 0$，这时候依旧能取到最优解，但是一个新的维度被赋值为$0$。

重复上面这个过程，直到找到某个顶点为止，很显然流程必定会终止。

命题2：对于任意$x\in P$，定义$B={i\mid x_i>0}$。那么$x$是凸包上的某个顶点，当且仅当$A_B$的列向量线性无关，这里$A_B$表示由$B$中下标指定的$A$中的列组成的子阵。

比如

$$x=\left[\begin{array}{c} 2\\0\\1\\0 \end{array}\right] \\ A=\left[\begin{array}{cccc} 2&1&3&0\\7&3&2&1\\0&0&0&5 \end{array}\right]$$

那么$B={1,3}$，

$$A_B=\left[\begin{array}{cc} 2&3\\7&2\\0&0 \end{array}\right]$$

由于$A_B$的列向量线性无关，因此$x$是凸包上的某个顶点。

这里给一下证明：

先证明充分性。假设$x$不是顶点，那么存在某个$d$，满足$x\pm d\in P$，即$Ad=0$，且$x_i=0\Rightarrow d_i=0$。而$Ad=0$可以推出$A_Bd_B=0$，其中$d_B\neq 0$，这与$A_B$的列线性无关相悖，因此假设不成立。

再证明必要性。如果$A_B$线性无关，那么一定存在某个向量$d_B$满足$A_Bd_B=0$，我们用$0$填充$d$的其它维度，将其扩展为长度为$n$的向量，这样一定有$Ad=0$，即$x\pm d\in P$，即$x$不是顶点。

命题3：$x$是一个顶点，当且仅当存在存在某个$C\subseteq N={1,\ldots,n}$，满足$|C|=m$，且$A_C$是非奇异矩阵，$x_C=A_C^{-1}b_C\geq 0$，$x_{N/C}=0$。

证明：

必要性：由于行向量线性无关，因此如果$x$是顶点，我们可以将$A_B$扩充为$A_C$。

充分性：对应的如果我们找到这样一个$C$，由于$Ax=b$，且$x\geq 0$，因此$x\in P$，假如$x$不是顶点，就能找到这样的$d$，满足满足$x\pm d\in P$。当然根据$d_C$非0且$A_Cd_C=0$，可以推出$A_C$的为奇异矩阵。

现在我们就得到了一个获取线性规划最优解的简单算法，遍历所有凸包上的顶点，并判断其是否是最优解。但是不幸的是，虽然我们可以$O(m^3)$时间复杂度内判断矩阵是否奇异，但是$C$共有${n\choose m}$种可能的选择，而这是指数级别的。

单纯形算法

单纯形算法的实践表明，一般pivot执行次数为$2(m+n)$次以内。

整数规划与全幺模矩阵

定义：一个方矩是幺模矩阵（Unimodular matrix），当且仅当这个方阵的行列式值为$\pm 1$

幺模矩阵的性质：

• 单位矩阵是幺模矩阵
• 置换矩阵是幺模矩阵
• 幺模矩阵的转置是幺模矩阵
• 幺模矩阵交换两行或两列后依旧是幺模矩阵
• 幺模矩阵的某一行（列）加上另外一行（列）乘上某个常数得到的矩阵还是幺模矩阵
• 幺模矩阵的逆矩阵是幺模矩阵
• 两个幺模矩阵的乘积是幺模矩阵

定义：一个矩阵是全幺模矩阵（Total Unimodular matrix），当且仅当这个矩阵的任意非奇异子阵都是幺模矩阵

全幺模矩阵的性质：

• 一个矩阵是全幺模矩阵的必要条件是矩阵的每个元素都是$-1,0,1$，但这不是充分条件，比如 $\left[\begin{array}{cc} 1&1\\ -1&1 \end{array}\right]$ 就不是全幺模矩阵。
• 全幺模矩阵交换两行或两列后依旧是全幺模矩阵
• 全幺模矩阵的任意子阵还是全幺模矩阵
• 如果$A$是全幺模矩阵，那么$[A,-A],[A,I],-A,A^T$都是全幺模矩阵

命题1：如果矩阵$A,b$都是整数上的矩阵，且$A$是全幺模矩阵，那么线性规划凸包上的所有顶点都是整数顶点

证明：

根据线性规划几何解释中的命题3可知，$P$中的任意顶点$x$，可以找到$A$的某个非奇异子阵$A_C$，满足$x_C=A_C^{-1}b$，且$A_{N/C}=0$。由于$A$是全幺模矩阵，因此$A_C$是幺模矩阵也是全幺模矩阵，利用伴随矩阵法我们对$A_C$进行求逆，会发现$A_C^{-1}$中的所有元素都是整数。因此$x_C$的所有元素也是整数。

命题2：如果矩阵$A,b$都是整数上的矩阵，且$A$是全幺模矩阵，那么线性规划的最优解$x$是整数向量

证明：

线性规划的最优解在某个顶点取到，而所有顶点都是整数顶点，因此命题得证。

命题3：无向二分图的关联矩阵是全幺模矩阵

（无向二分图的关联矩阵为行表示结点，列表示边，如果结点和边关联，则单元格值为1，否则为0）

证明：

根据归纳法进行证明，考虑大小为1的子阵，其行列式取值只能为$0,\pm 1$。

现在假设所有大小小于$n$的子阵都是全幺模矩阵。现在考虑大小为$n+1$的子阵。这里考虑三种情况：

1. 如果存在一列全为0，那么行列式值只能为0。
2. 如果存在一列只有一个1，那么我们可以得出行列式值为去除这一列这一行的代数余子式，而余子式的取值仅可能为$0,\pm 1$（根据归纳法）。
3. 否则所有列都有两个1，那么如果我们将所有行都加总，但是左边子图顶点对应的行的系数为1，右边子图的顶点对应的行的系数为-1，那么加总和为0，这意味着矩阵的行线性相关，因此行列式值为0。

命题4：有向图的关联矩阵是全幺模矩阵

（有向图的关联矩阵为行表示结点，列表示边，每条边与入点的单元格值为1，与出点的单元格值为-1，否则为0）

证明：

与命题3相同，第二步的条件是存在一列只有一个数非0，第三步的证明中所有行的系数都为1。

提供一道题目。

命题5：线性规划求解二分图最大匹配的系数矩阵是全幺模矩阵

举个例子，左右各有两个顶点，其中左1和左2均与右1和右2有连边，那么它们系数矩阵为：

$$A= \left[ \begin{array}{cccc} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{array} \right]$$

向量$b$为：

$$b=\left[ \begin{array}{c} 1\\ 1\\ 1\\ 1 \end{array} \right]$$

这时候满足$Ax\leq b$。之后我们加入松弛变量，得到

$$[A,I]x'=b$$

其中$A$的左边是一个二分图的关联矩阵，右边是单位矩阵，满足全幺模矩阵的条件。

命题5：线性规划求解最大流的系数矩阵是全幺模矩阵

举个例子，源点是1，汇点是4，1到2连容量为$c_{1,2}$的边，1到3连容量为$c_{1,3}$的边，2到4连容量为$c_{2,4}$的边，3到4连容量为$c_{3,4}$的边。那么它们的约束方程为：

$$A=\left[ \begin{array}{cccc} -1 & 0 & 1 & 0\\ 0 & -1 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right]$$

向量$b$为：

$$b= \left[ \begin{array}{c} 0\\ 0\\ c_{1,2}\\ c_{1,3}\\ c_{2,4}\\ c_{3,4} \end{array} \right]$$

这时候满足$Ax\leq b$，我们加入松弛变量后得到：

$$[A,I]x'=b$$

这里$A$的前两行是有向边关联矩阵的子阵，下面是4行是单位矩阵，因此$A$是全幺模矩阵，对应的系数矩阵$[A,I]$也是全幺模矩阵。

命题6：线性规划求解最小费用最大流的系数矩阵是全幺模矩阵

举个例子，源点是1，汇点是4，1到2连容量为$c_{1,2}$的边，费用为$C_{1,2}$，1到3连容量为$c_{1,3}$的费用为$C_{1,3}$边，2到4连容量为$c_{2,4}$的费用为$C_{2,4}$边，3到4连容量为$c_{3,4}$的费用为$C_{3,4}$边。首先可以求出最大流为$f$，那么系数矩阵为：

$$A=\left[ \begin{array}{cccc} 1 & 1 & 0 & 0\\ -1 & -1 & 0 & 0\\ -1 & 0 & 1 & 0\\ 0 & -1 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{array} \right]$$

向量$b$为：

$$b= \left[ \begin{array}{c} f\\ -f\\ 0\\ 0\\ c_{1,2}\\ c_{1,3}\\ c_{2,4}\\ c_{3,4} \end{array} \right]$$

这时候满足$Ax\leq b$，我们加入松弛变量后得到：

$$[A,I]x'=b$$

这里$A$的第1行、第2行、第3到4行，第5到8行全是全幺模矩阵的子阵，因此矩阵$A$是全幺模矩阵，故$[A,I]$也是全幺模矩阵。

对偶线性规划

线性规划的原始型：

$$\left. \begin{array}{lc} \max & c^Tx\\ s.t. & Ax\leq b\\ & x\geq 0 \end{array} \right.$$

它的对偶型：

$$\left. \begin{array}{lc} \min & b^Ty\\ s.t. & A^Ty\geq c\\ & y\geq 0 \end{array} \right.$$

对偶型有以下性质：

• 设$x$是线性规划最优值对应的解，而$y$是对偶型最优值对应的解，那么一定有$c^Tx=b^Ty$。
• 如果原始型无解，那么对偶型则无界。
• 对偶线性规划的对偶是原始线性规划。

这里稍微提一个对偶的技巧。

对于一类线性规划：

$$\left. \begin{array}{lc} \max & c^Tx\\ s.t. & Ax= b\\ & x\geq 0 \end{array} \right.$$

其对偶后的形式为

$$\left. \begin{array}{lc} \min & b^Ty\\ s.t. & A^Ty\geq c\\ \end{array} \right.$$

注意对偶形式中$y\geq 0$这个约束条件不见了。

对偶线性规划的应用

最大流和最小割

最大流的线性规划形式为：

$$\left. \begin{array}{lc} \max & f_{t,s}\\ s.t. & f_{i,j} \leq u_{i,j}\\ & \sum_{(j,i)\in E'}f_{j,i}=\sum_{(i,j)\in E'}f_{i,j}, \forall i\in V\\ & f_{i,j} \geq 0 \end{array} \right.$$

这里$E'=E+(t,s)$，$u_{i,j}$表示边$(i,j)$的容量。

其对偶形式为：

$$\left. \begin{array}{lc} \min & \sum_{(i,j)\in E}u_{i,j}d_{i,j}\\ s.t. & d_{i,j}+y_{i}-y_{j}\geq 0\\ & y_{t}-y_{s}\geq 1\\ & d_{i,j} \geq 0 \end{array} \right.$$

我们可以理解$d_{i,j}$表示是否要删除边$(i,j)$，删除为$1$，不删除为$0$。而$y_i$表示从$s$到$i$的最短路径。很显然在最小割后，不存在从$s$到$t$的路径（即至少需要经过一条被割去的边）。因此下面的公式就是最小割的线性规划公式。

二分图最大权匹配和最小顶标和

对于二分图，其顶点分成两个集合$L$和$R$。

二分图最大权匹配的线性规划形式为：

$$\left. \begin{array}{lc} \max & \sum_{(i,j)\in E}w_{i,j}f_{i,j} \\ s.t. & \sum_{(i,j)\in E}f_{i,j}\leq 1, \forall i\in L\\ & \sum_{(i,j)\in E}f_{i,j}\leq 1, \forall j\in R\\ & f_{i,j} \in \{0,1\} \end{array} \right.$$

其对偶形式为：

$$\left. \begin{array}{lc} \min & \sum_{i\in L} p_i+\sum_{i\in R} p_i \\ s.t. & p_i+p_j\geq w_{i,j}\\ & p_i\geq 0 \end{array} \right.$$

下面这个对偶形式实际上是最小顶标和的线性规划形式。

最小费用最大流和最短路

对于给定的费用网络$G=(V,E)$，最小费用流问题（不要求最大）对应的线性规划形式为：

$$\left. \begin{array}{lc} \max & \sum_{(i,j)\in E}-c_{i,j}f_{i,j} \\ s.t. & f_{i,j} \leq u_{i,j}\\ & f_{t,s}=F\\ & \sum_{(j,i)\in E'}f_{j,i}=\sum_{(i,j)\in E'}f_{i,j}, \forall i \in V\\ & f_{i,j} \geq 0 \end{array} \right.$$

将其转换为对偶形式：

$$\left. \begin{array}{lc} \min & \sum_{(i,j)\in E}u_{i,j}y_{i,j} +Fy_{t,s}\\ s.t. & y_{i,j}+z_i-z_j\geq -c_{i,j}\\ & y_{t,s}+z_t-z_s\geq 0\\ & y_{i,j} \geq 0,\forall (i,j)\in E \end{array} \right.$$

题目1：给定一个连同无向图$G=(V,E)$，$n=|V|$。其中边$(u,v)$有一个非负长度$l_{u,v}$和非负的费用$c_{u,v}$。现在我们允许将每条边的长度延长某个非负距离$y_{u,v}$，每单位的费用为$c_{u,v}$。现在要求计算通过延长边，使得从顶点$1$到顶点$n$最短距离不小于$m$，要求计算最小的总费用$\sum_{i}c_ix_i$。其中$1\leq V,E\leq 10^3$，$0\leq l_{i,j},c_{i,j}\leq 10^2$

建立线性规划公式可以得出：

$$\left. \begin{array}{lc} \min & \sum_{(i,j)\in E}c_{i,j}y_{i,j}\\ s.t. & y_{i,j}+z_i-z_j\geq -l_{i,j}\\ & z_t-z_s\geq U\\ & y_{i,j} \geq 0,\forall (i,j)\in E \end{array} \right.$$

考虑它的对偶形式：

$$\left. \begin{array}{lc} \max & \sum_{(i,j)\in E}-l_{i,j}f_{i,j}+Uf_{t,s} \\ s.t. & f_{i,j} \leq c_{i,j}\\ & f_{t,s}\leq +\infty\\ & \sum_{(j,i)\in E'}f_{j,i}=\sum_{(i,j)\in E'}f_{i,j}, \forall i \in V\\ & f_{i,j} \geq 0 \end{array} \right.$$

即要求找到一个网络的最小费用流（注意不一定最大）。我们可以建立网络流来求解。

题目2：给定一个连同无向图$G=(V,E)$，$n=|V|$。其中边$i$有一个非负长度$l_i$和非负的费用$c_i$。现在我们允许将每条边的长度延长某个非负距离$x_i$，每单位的费用为$c_i$。要求回答$m$个请求，每个请求给定费用上限$C$，要求总费用且总费用$\sum_{i}c_ix_i\leq C$，问从顶点$1$到顶点$n$的最远距离是多大。其中$2\leq V\leq 100$，$V-1\leq E\leq 10^3$。$1\leq m,C\leq 10^5$。其中$l_i$和$c_i$都是非负整数，且$1\leq l_i,c_i\leq 10$。

提供一道题目。

我们可以用二分法来校验，即我们只需要负责计算最远距离为$d$的时候，最小的费用是多少。这就转换为题目1了。这样还是比较慢的。

注意观察我们最后得到的公式：$\sum_{(i,j)\in E}-c_{i,j}f_{i,j}+Uf_{t,s}$。这等价于我们在计算最大流的时候按照最小费用路径增广，且只要费用路径的总费用不超过$U$我们就继续增广。由于所有$l_i,c_i$都是整数，因此边上的流量以及整个网络的流量都是整数。且根据最小费用流的性质知道，当我们按照最小费用路径增广的时候，最小费用路径的总费用是递增的。因此我们可以发现对于$U\in [x,x+1)$的时候，$f_{t,s}$以及$\sum_{(i,j)\in E}-c_{i,j}f_{i,j}$都是常数，扩容费用和$U$的关系为$cost(U)=aU+b$，即是一个线性函数，且$cost$函数在整个定义域中都是递增函数。

因此我们可以不断沿着最短路径进行增广。由于流量上限最多为$10m$，因此我们可以用费用流算法求解的时间复杂度为$O(10mn^2+q\log_2q)$。

题目3：给定一个连同无向图$G=(V,E)$，$n=|V|$。其中边$(u,v)$有一个非负长度$l_{u,v}$和非负的费用$c_{u,v}$。现在我们允许将每条边的长度延长某个非负距离$y_{u,v}$，延长的上限为$t_{u,v}$，每单位的费用为$c_{u,v}$。现在要求计算通过延长边，使得从顶点$1$到顶点$n$最短距离不小于$m$，要求计算最小的总费用$\sum_{i}c_ix_i$。其中$1\leq V,E\leq 10^3$，$0\leq l_{i,j},c_{i,j}\leq 10^2$

建立线性规划公式可以得出：

$$\left. \begin{array}{lc} \min & \sum_{(i,j)\in E}c_{i,j}y_{i,j}\\ s.t. & y_{i,j}+z_i-z_j\geq -l_{i,j}\\ & z_t-z_s\geq U\\ & -y_{i,j}\geq -t_{i,j}\\ & y_{i,j} \geq 0,\forall (i,j)\in E \end{array} \right.$$

考虑它的对偶形式：

$$\left. \begin{array}{lc} \max & \sum_{(i,j)\in E}-l_{i,j}f_{i,j}+Uf_{t,s}+\sum_{(i,j)\in E}-t_{i,j}p_{i,j}\\ s.t. & f_{i,j}-p_{i,j} \leq c_{i,j}\\ & f_{t,s}\leq +\infty\\ & \sum_{(j,i)\in E'}f_{j,i}=\sum_{(i,j)\in E'}f_{i,j}, \forall i \in V\\ & f_{i,j} \geq 0\\ & p_{i,j} \geq 0 \end{array} \right.$$

由于$t_{i,j}\geq 0$，因此当$p_{i,j}=\max(f_{i,j}-c_{i,j},0)$的时候目标公式可以取到最大值。因此我们可以删除$p$。得到

$$\left. \begin{array}{lc} \max & \sum_{(i,j)\in E}-l_{i,j}f_{i,j}+Uf_{t,s}+\sum_{(i,j)\in E}-t_{i,j}\max(f_{i,j}-c_{i,j},0)\\ s.t. & f_{t,s}\leq +\infty\\ & \sum_{(j,i)\in E'}f_{j,i}=\sum_{(i,j)\in E'}f_{i,j}, \forall i \in V\\ & f_{i,j} \geq 0 \end{array} \right.$$

我们可以理解为对于任意网络中的边$(i,j)$，我们能支付额外的$t_{i,j}$单位费用将其扩容。这个可以通过加入一条费用为$l_{i,j}+t_{i,j}$且容量为无穷的边来实现。

提供一道题目。

参考资料

• https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/LinearProgrammingI.pdf
• Totally Unimodular Matrix
• 《浅谈线性规划与对偶问题》 by 董克凡