线性规划

Published: by Creative Commons Licence

  • 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={x\mid Ax=b\land x\geq 0}$,即所有可行解的集合。

我们下面的讨论均认为$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,\pm 1$。

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

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

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

证明:

与命题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} \max & \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}$且容量为无穷的边来实现。

提供一道题目

参考资料