Linear programming

public 学习笔记 Comments

线性规划两种常见形式的转化

标准型：

松弛型：

下面是一个常用的标准型转松弛型套路：

原线性规划：

令 $x_{i+m}=b_i-\sum\limits_{j=1}^na_{i,j}x_j\ge 0$

那么有新的线性规划：

单纯形法求解线性规划

将上面的松弛型线性规划进行移项：

然后一直重复下面的操作：

  1. 在目标函数中找出一个 $c_e>0$ 的 $e$
  2. 在约束条件中找出满足 $a_{l,e}>0且\frac{a_{l,0}}{a_{l,e}}最大$ 的 $l$
  3. 将第 $l$ 个约束等式移项变形： $x_e=\frac{b_i}{a_{l,e}}-\sum\limits_{j=1,j\not=e}^n\frac{a_{l,j}}{a_{l,e}}x_j-\frac1{a_{l,e}}x_{l+m}$
  4. 将移项得到的等式带入其余的约束等式和目标函数中，消去所有的 $x_e$ ，添加上 $x_{l+m}$ ，并更新剩余项的系数

讨论下面几种边界情况：

  1. 当第一步无法找到合法的 $e$ 时，说明求出了最优解
  2. 当第二步无法找到合法的 $l$ 时，说明该线性规划无界

复杂度指数级，但跑的比谁都快

正确性:线性规划有界时解空间是一个凸形区域，因此单纯形算法求出的局部最优值即为全局最优值

当然有时候需要构造一组初始解出来（大部分时候不需要），可以使用如下技巧构造辅助线性规划：

容易看出如果该情况无解那么原问题无解

例题：

  • UVA Happiness
  • CC Flight Distance
  • TCO precious stones

整数线性规划

本来应该是 $NP-hard$ 问题

但是如果证明最优解一定是在整数解时可以取得的话可以用单纯形

原因还是来源于上面说过的凸形区域

或者可以一眼看出该线性规划的 $\boldsymbol A$ 是一个全幺模矩阵也行

对偶原理

考虑现在有如下线性规划：

利用待定系数法的思想可以知道，该线性规划的任意可行解$(x_1^{\times},x_2^\times,…,x_n^\times)$一定能表示成如下形式：

现在要找出 $\sum\limits_{i=1}^nc_ix_i$ 的下界，等价于找出 $\sum\limits_{i=1}^mb_iy_i$ 的上界

于是我们得到了一个新的线性规划：

同样的，将新得到的线性规划做类似转化可以转回原来的线性规划，我们称这两个线性规划互为对偶问题

互相转化的关键是这个等式： $\sum\limits_{i=1}^nc_ix_i\ge\sum\limits_{i=1}^mb_iy_i$ ，即等号右边的上界不超过等号左边的下界

上述等式即是线性规划弱对偶性，即对于两个线性规划的任意可行解 $\boldsymbol x^\times,\boldsymbol y^\times$，均满足 $\sum\limits_{i=1}^nc_ix_i^\times\ge\sum\limits_{i=1}^mb_iy_i^\times$

线性规划的对偶原理用矩阵的形式可以简单表示为：

下面证明一个重要定理：

线性规划对偶性：对于两个线性规划的任意最优解解 $\boldsymbol x^\times,\boldsymbol y^\times$，均满足 $\sum\limits_{i=1}^nc_ix_i^\times=\sum\limits_{i=1}^mb_iy_i^\times$

证明：

对于第一个线性规划，考虑构造一个函数 $f(\boldsymbol y)=\boldsymbol c^T\boldsymbol x+\boldsymbol y^T(\boldsymbol b-\boldsymbol A\boldsymbol x),\boldsymbol y\ge\boldsymbol0$

令 $g(\boldsymbol y)=\min\{f(\boldsymbol y)|\boldsymbol A\boldsymbol x\ge \boldsymbol b,\boldsymbol x\ge\boldsymbol0\}$

显然
$\forall \boldsymbol y,g(\boldsymbol y)\le \boldsymbol c^T\boldsymbol x^\times$

即$\max\{g(\boldsymbol y)\}=\boldsymbol c^T\boldsymbol x^\times$

转化问题：

当 $\boldsymbol c^T-\boldsymbol y^T\boldsymbol A\ge \boldsymbol0$ 时，$\min\{(\boldsymbol c^T-\boldsymbol y^T\boldsymbol A)\boldsymbol x\}=0$

当 $\boldsymbol c^T-\boldsymbol y^T\boldsymbol A\not\ge \boldsymbol0$ 时，$\min\{(\boldsymbol c^T-\boldsymbol y^T\boldsymbol A)\boldsymbol x\}=-inf$

简单分析与变形后可知：

得证

而且容易知道原问题和对偶问题同时取到目标取值~

利用上述两个定理容易证明出线性规划的互相松弛定理：

对于原问题和对偶问题的可行解 $\boldsymbol x^\times,\boldsymbol y^\times$ ，它们均为问题的最优解当前仅当如下条件被满足：

  • $\forall 1\le j\le n,s.t.\ x_j^\times=0或\sum\limits_{i=1}^ma_{i,j}y_i^\times=c_j$
  • $\forall 1\le i\le m,s.t.\ y_i^\times=0或\sum\limits_{j=1}^na_{i,j}x_i^\times=b_i$

对偶原理的几个性质：

  • 对于无限制变量 $x_i$ ，对偶后对应限制 $\sum\limits_{j=1}^ma_{j,i}y_j=c_i$
  • 对于变量 $x_i=0$ ，对偶后对应 $\sum\limits_{j=1}^ma_{j,i}y_j$ 无限制
  • 对于变量 $x_i\ge0$ ，对偶后对应限制 $\sum\limits_{j=1}^ma_{j,i}y_j\ge0$
  • 对于变量 $x_i\le0$ ，对偶后对应限制 $\sum\limits_{j=1}^ma_{j,i}y_j\le0$
  • 对于限制 $\sum\limits_{j=1}^ma_{j,i}y_j=c_i$ ，对偶后对应无限制变量 $x_i$
  • 对于限制$\sum\limits_{j=1}^ma_{j,i}y_j$ ，对偶后对应变量 $x_i=0$
  • 对于限制 $\sum\limits_{j=1}^ma_{j,i}y_j\ge0$ ，对偶后对应变量 $x_i\le0$
  • 对于限制 $\sum\limits_{j=1}^ma_{j,i}y_j\le0$ ，对偶后对应变量 $x_i\ge0$

对偶原理在网络问题中的运用

利用上述定理和性质可以很快证明如下两个结论：

  • 最小割和最大流是对偶问题
  • 二分图最大权匹配和最小费用流是对偶问题

证明比较容易，这里略去

例题：

  • [SHOI2004]最小生成树
  • CC Flight Distance

线性规划与半平面交的转化

  • 对于只有两个变量的线性规划，可以通过移项变成半平面交问题
  • 对于只用两个限制的线性规划，可以通过对偶原理+移项变成半平面交问题

例题：

  • poj equations

线性规划与网络流问题的转化

考虑到网络流问题的最优解都是整数解，因此在转化的时候务必记住判定列出的线性规划是不是全幺模矩阵否则不一定解出的最优解是整数最优解~

例题：

  • CC Chefbook
  • bzoj Orz the MST
  • [ZJOI2013]战线防守

线性规划与博弈

一个基本不可能填的坑

好难啊我不会纳什均衡，还是得cyktxdy学会了之后给我讲

ldxcaicaia loser😬😦😭😢😰

Glory is just in sight.