线性规划-对偶型-单纯型法-学习笔记
i207M
2019-02-20 16:42:13
## 线性规划标准型与对偶型
先说对偶型：
有什么用呢？比方说：
在 ? 天内，第 ? 天每陪妹子 1 小时就要付出 ?_? 的代价（陪了妹子就不能刷题了）；每连续的 7 天里至少陪妹子 7 个小时（不然妹子就跑了）；求至少需要付出多少代价，?≤10000；
但是，直接上差分约束，并没有什么好方法，因为ci不同，差分约束无法最大化答案；
**对偶！**
目标函数非常简单，差分约束条件可以写出来，那就走起；
# 看到的优秀讲解，茅塞顿开
对偶有什么用呢？变量多限制少不好弄，对偶后变量少限制多，但是可以结合实际取点一些限制！
[link](https://www.zhihu.com/question/26658861)
**给原材料定价，使得不低于售价**
对于[Farmville](https://vjudge.net/problem/TopCoder-13952)这道题（原题目为最小化，对偶为最大化），我们有若干$x_i\ge x_j+a_i$，花费b_i可以使$a_i-1$的边，我们先用直觉建图，然后$swap(flow,cost)$即可。
原题目为最大化，对偶为最小话，那就是边为$x_i\le x_j+a_i$，花费$b_i$可以使$a_i+1$。
**感觉和差分约束有千丝万缕的关系！**
--------------
## 单纯型法
解释不太清楚...
一种时间复杂度指数级的算法，但是因为有跑不满的信仰，所以在不特殊构造的情况下能跑几百的点。
[论文](https://wenku.baidu.com/view/ce5784754a7302768f99391d)
[zzq的Blog](http://www.cnblogs.com/zzqsblog/p/5457091.html)
简单的说，我们先要把一般的线性规划问题转化为标准型
几何意义：首先，最优解一定是在可行区域的边界取到的。单纯形法的过程就相当于沿着边界做爬山算法。
**要求**：$b_i\ge 0$（下面会说不满足了怎么办）
终止条件：
1. 若存在$c_i\ge 0$，则未终止，找到了可行解。
2. 若$c_i\le 0$，则找到了最优解。若存在$c_i=0$，则最优解不唯一。
过程：
1. 找到入基变量e。要求：第一个$i$，使得$c_i>0$
2. 找到出基变量l。要求：最小化$a[l][0]/a[l][e] > 0$
3. pivot，继续进行。
pivot的过程：看代码吧。
--------------
解决$b_i<0$
方法一：
方法二：
利用pivot操作，
在bi为负的时候，把所有基变量设为0不是一组合法的初始解，所以选择一个bi为负的基变量x[i+n]，然后在该约束右边找一个系数为正(即原系数为负)的非基变量进行转轴操作，如果没有系数为正显然就无解了。
-----------------
小Trick：
对于全幺模矩阵，直接用int存就好了。
全幺模矩阵：所有子矩阵（可以不连续）都是幺模矩阵。
幺模矩阵：行列式为1或-1.
判定全幺模矩阵的一些充要条件：
1. 能表示成网络流（能网络流我要你干甚）
2. 有一种列的排列能使得每行的1是连续的
```cpp
#define N 23
#define eps 1e-8
int n,m;
int id[N*2];
double a[N][N],ans[N];
void pivot(int l,int e)
{
swap(id[n+l],id[e]);
double t=a[l][e]; a[l][e]=1;
for(ri i=0; i<=n; ++i) a[l][i]/=t;
for(ri i=0; i<=m; ++i)
{
if(i==l) continue;
t=a[i][e]; a[i][e]=0;
for(ri j=0; j<=n; ++j)
a[i][j]-=t*a[l][j];
}
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
#endif
int typ; in(n,m,typ);
for(ri i=1; i<=n; ++i) a[0][i]=rd(),id[i]=i;
for(ri i=1; i<=m; ++i)
{
for(ri j=1; j<=n; ++j) a[i][j]=rd();
a[i][0]=rd();
}
while(1)
{
int l=0,e=0;
for(ri i=1; i<=m; ++i)
if(a[i][0]<-eps)
{
l=i;
break;
}
if(!l) break;
double t=-eps;
for(ri i=1; i<=n; ++i)
if(a[l][i]<t)
{
t=a[l][i];
e=i;
}
if(!e) {puts("Infeasible"); return 0;}
pivot(l,e);
}
while(1)
{
int l=0,e=0;
for(ri i=1; i<=n; ++i)
if(a[0][i]>eps)
{
e=i;
break;
}
if(!e) break;
double t=1e100;
for(ri i=1; i<=m; ++i)
if(a[i][e]>eps&&a[i][0]/a[i][e]<t)
{
t=a[i][0]/a[i][e];
l=i;
}
if(!l) {puts("Unbounded"); return 0;}
pivot(l,e);
}
printf("%.10f\n",-a[0][0]);
if(typ)
{
for(ri i=1; i<=m; ++i) ans[id[n+i]]=a[i][0];
for(ri i=1; i<=n; ++i) printf("%.10f ",ans[i]);
}
return 0;
}
```
-------
## 例题
BZOJ 3118
~~感觉像网络流，但其实不是~~
[膜Claris题解](https://www.cnblogs.com/clrs97/p/4403183.html)
设$x[i]$为第i条边的变化量，树边减少，非树边增加
对于每条非树边i(u,v)，在树上u到v路径上的所有边j都都要满足$W_i+X_i\geq W_j-X_j$
移项后得到$X_i+X_j\geq W_j-W_i$，对于对偶问题用单纯型法。