线性规划

Published: by Creative Commons Licence

  • Tags:

线性规划原理

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

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

其中所有涉及的数值都是实数,$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$,那么我们可以记

并将约束公式替换为

如果约束条件为$\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$中的列组成的子阵。

比如

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

由于$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}$种可能的选择,而这是指数级别的。

对偶线性规划

线性规划的原始型:

它的对偶型:

对偶型有以下性质:

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

单纯形算法

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

整数规划与全幺模矩阵

定义:一个方矩是幺模矩阵(Unimodular matrix),当且仅当这个方阵的行列式值为$\pm 1$

幺模矩阵的性质:

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

定义:一个矩阵是全幺模矩阵(Total Unimodular matrix),当且仅当这个矩阵的任意非奇异子阵都是幺模矩阵

全幺模矩阵的性质:

  • 一个矩阵是全幺模矩阵的必要条件是矩阵的每个元素都是$-1,0,1$,但这不是充分条件,比如 就不是全幺模矩阵。
  • 全幺模矩阵交换两行或两列后依旧是全幺模矩阵
  • 全幺模矩阵的任意子阵还是全幺模矩阵
  • 如果$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有连边,那么它们系数矩阵为:

向量$b$为:

这时候满足$Ax\leq 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}$的边。那么它们的约束方程为:

向量$b$为:

这时候满足$Ax\leq 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$,那么系数矩阵为:

向量$b$为:

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

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

参考资料