单纯形

本来说高考不考线性规划，还是躲不过233，结果听说高考又要考线性规划了。。

这玩意学了我一下午和一晚上qwq，晚上躺床上终于想明白了呜呜呜

线性规划标准型：有n个变量和m个约束，第 $i$ 个约束形如

\sum_{j=1}^na_{ij}x_j\leq b_i

要求最大化

\sum_{j=1}^nc_jx_j

其中要求每个 $x_j$ 都非负。

小于等于不好处理，用一个常用trick把小于等于转化成等于。就是每个式子都添一个变量。
松弛型：

\sum_{j=1}^na_{ij}x_j+x_{i+n}=b_i

这时还是要求每个变量非负，就与上面标准型等价。

这时因为所有式子都是等式的形式，所有式子就是方程组，考虑用矩阵解决。

接下来就是单纯形的内容了：

我们把目标函数写在矩阵第 $0$ 行， $b_i$ 写在矩阵第 $0$ 列， $a_{ij}$ 写在 $1$ 到 $m$ 行 $1$ 到 $n$ 列。

根据线性代数的知识，我们对这个矩阵做任何初等变换都与原方程组等价。

不过要警惕：我们没有在矩阵中体现每个变量都非负。没有关系，等式在矩阵，不等式在心中。

单纯形的思路就是对这个矩阵做初等变换，直到可以发现一组“平凡解”。

举例子，什么时候是平凡解？
当目标函数的系数都为负，且每个约束对应的等式中有一个专属的变量（只有它自己有，称为“基变量”），且此基变量系数为 $1$ ，且 $b_i$ 都非负时，我们可以把所有除基变量外的变量全都赋成 $0$ ，基变量赋为它式子里的常数项。显然这样满足所有约束，且最大化了目标函数。
（在上面松弛型的式子中 $x_{i+n}$ 即为每个等式的基变量）

先假设初始的矩阵中已经满足常数都非负。那么发现初始矩阵只有“目标函数的系数都为负”的条件不满足。那么我们考虑维持其他性质的基础上消除目标函数中的正系数。具体操作为先选出一个正系数的变量 $x_j$ ，再去下面找一个 $a_{ij}>0$ 且 $\frac{b_i}{a_{ij}}$ 最小的 $i$ ，在此方程中把 $x_j$ 的系数约成 $1$ ，再用这个方程把其他所有方程中的 $x_j$ 都消掉。此时 $x_j$ 成为第 $i$ 个方程的基变量。而 $a_{ij}>0$ 且 $\frac{b_i}{a_{ij}}$ 最小保证了操作完后所有 $b_i$ 仍非负。

看起来很暴力还容易没有效果？/xk这算法就是这么玄学，不过结论是不断迭代之后一定会得到满足条件的矩阵，这时只要取出“平凡解”即可。

那么如果不满足初始矩阵中常数都非负呢？我们还是不断执行初等变换使得满足条件。找出一个 $i$ 使得 $b_i<0$ ，然后找出一个 $j$ 使得 $a_{ij}<0$ ，发现把 $a_{ij}$ 变为基变量的过程会让 $b_i$ 变号，于是执行相似的过程即可。这样不断迭代一定会得到满足条件的矩阵。（如果有解）这个过程叫“初始化”

现在讨论一下无解和解无界的情况。
首先若无解，则我们一定需要执行初始化。且不会成功。（否则就有解了鸭）具体的是我们找到一个 $i$ 之后找不到对应的 $j$ 。这时相当于发现一些非负数加起来小于零。显然无解。
若解无界，我们一定能成功初始化。然后对于一个 $j$ 找不到 $a_{ij}>0$ 。这时我们可以把 $x_j$ 赋成无穷大，不会影响约束的满足，目标函数也就变成了无穷大。

以上是我的理解，正常的可以看16年论文，zzq博客，这篇最易懂的博客。

然后有一个trick。看起来我们的矩阵需要是 $(n+m)*m$ 的，因为新建了 $m$ 个变量。不过我们发现有 $m$ 个变量是基变量，满足系数是 $1$ 且仅在一个方程中出现。这时我们就可以不记录这 $m$ 个变量，矩阵缩小为 $n*m$ 。当换基变量时需要注意。

复杂度：一次pivot的复杂度是nm，多少次不一定哦，有可能达到指数级，不过一般情况下很优秀

这里可以说一下有多优秀，可以有一个印象，考场上敢写单纯形。[NOI2008]志愿者招募这题正解应该是费用流，但是挺难想的。而建出线性规划模型是不需要动脑子的，而且直接单纯形跑得飞快，吊打费用流。矩阵大小为 $n*m=10^7$ 。我也不知道为啥能跑过woc，这 pivot 次数都是常数了？

#include<bits/stdc++.h>
using namespace std;
const int N=30;
const double eps=1e-7;
int n,m,op,id[N*2];double a[N][N],ans[N];
int read(){
    int x=0,c,f=1;
    while(!isdigit(c=getchar()))c=='-'?f=-1:0;
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x*f;
}
void pivot(int x,int y){
    for(int i=0;i<=n;i++)if(i!=y)a[x][i]/=a[x][y];
    a[x][y]=1/a[x][y];swap(id[x+n],id[y]);
    for(int i=0;i<=m;i++)if(i!=x&&abs(a[i][y])>eps){//这里这个大于eps的剪枝也很关键。
        for(int j=0;j<=n;j++)if(j!=y)a[i][j]-=a[i][y]*a[x][j];
        a[i][y]=-a[i][y]*a[x][y];
    }
}
int main(){
    n=read();m=read();op=read();id[0]=1e9;
    for(int i=1;i<=n;i++)a[0][i]=read();
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)a[i][j]=read();
        a[i][0]=read();
    }
    for(int i=1;i<=n+m;i++)id[i]=i;
    while(1){
        int x=0,y=0;
        for(int i=1;i<=m;i++)if(a[i][0]<-eps&&(!x||rand()&1))x=i;if(!x)break;
        for(int i=1;i<=n;i++)if(a[x][i]<-eps&&(!y||rand()&1))y=i;
        if(!y)puts("Infeasible"),exit(0);pivot(x,y);
    }
    while(1){
        int x=0,y=0;double mn;
        for(int i=1;i<=n;i++)if(a[0][i]>eps&&(!y||rand()&1))y=i;if(!y)break;
        for(int i=1;i<=m;i++)if(a[i][y]>eps&&(!x||a[i][0]/a[i][y]<mn-eps))mn=a[i][0]/a[i][y],x=i;
        if(!x)puts("Unbounded"),exit(0);pivot(x,y);
    }
    printf("%.8f\n",-a[0][0]);if(!op)return 0;
    for(int i=1;i<=m;i++)if(id[i+n]<=n)ans[id[i+n]]=a[i][0];
    for(int i=1;i<=n;i++)printf("%.8f ",ans[i]);puts("");
    return 0;
}

存疑：第二个while里的y如果在所有>0的列中随机选的话A不了模板，会误判成Unbounded。
选择第一个>0的列的代码会被这组数据卡成死循环。

4 2 0
-12 -1 3 2
9 1 -9 -2 0
-6 -1 3 1 0

现在看来没有锅的是选择a[0][i]最大的列。不知原理。
2.19补：
疑难问题解决了。
“第二个while里的y如果在所有>0的列中随机选的话A不了模板，会误判成Unbounded“。这个问题是我自己写挂了。在取最小的 $$a[i][0]/a[i][y]$$ 时这个值有可能会非常大，导致 $10^{18}$ 这个无穷大不够大。改进一下写法即可。
而死循环的问题，这就是单纯形的一个经典的问题，循环。可能经过一系列转轴之后目标值不变，而所有系数又回到之前的某个状态，造成死循环。这个问题的解决方法有两个，一个是加入随机扰动，一个是使用Bland规则。一个优化。
而选择第一个>0的列看起来就是运用了bland规则啊？为什么还会死循环？注意我们现在没有在矩阵中体现基变量，导致我们矩阵中变量的编号与在矩阵中的坐标并不是一样的。所以按在矩阵中的编号选的话并没有遵循bland规则。比较时应该用记的 $id[]$ 比较。为了避免麻烦直接加入随机扰动就好了。。
而那个选择a[0][i]最大的列的方法却是典型的错误做法，是可以被卡成死循环的。

2.18补：写成这样完整矩阵还有一点好处就是把这个矩阵整体翻转，然后最大化变最小化，大于等于变小于等于，就是对偶问题了。（先别转化成松弛型）

这里要注意，现在提到的是对称对偶线性规划，需要满足的条件是全部变量均为非负全部约束条件均为不等式，对极大化问题为 $\leq$ ，对极小化问题为 $\geq$ 。如果不满足考虑把不等式变号之类的。
完整版的规则应该是这样的：最大化问题中的非负变量对应最小化问题中的 $\geq$ ，非正变量对应 $\leq$ ， $\leq$ 对应非负变量， $\geq$ 对应非正变量， $=$ 对应无约束变量。从最小化问题对应回去也成立。

转化成对偶问题有什么好处呢？
论文中提到如下几点：

省去初始化。如果我们发现原线性规划中约束的常数项有负数，那是要进行初始化的。但是如果此时发现目标函数的系数都非负，那么我们转化成对偶问题，即把整个矩阵转置之后就可以得到常数项非负的线性规划，省去初始化。
转化为半平面交。众所周知，只有两个变量的线性规划可以表述成半平面交问题，这可以快速求解。于是因为只有两个约束的线性规划的对偶问题只有两个变量，那么对偶之后便可以快速求解。
转化为网络流。众所周知，如果线性规划中每个变量最多在两个约束中出现，且系数分别为 $\pm1$ ，则它可以根据网络流的流量平衡来建图。把每个约束看作一个点，一个变量看作一条边，再把正数看作出度，负数看作入度，直接建图就好了。但是一般的线性规划不容易满足这个鸭。不过如果我们发现每个约束中最多有两个变量，且他们系数为 $\pm1$ ，那把矩阵转置之后就满足了前面的性质，即它的对偶问题可以转化为网络流。那么直接对偶后求解即可。

还有些变态题目需要输出方案，那么我们需要找到原问题与对偶问题最优方案之间的关系。

（互松弛定理）若x，y分别是原问题及其对偶问题的可行解，那么 x，y都是最优解当且仅当下列两个条件被同时满足：

对于所有 $1\leq j\leq n$ ：满足 $x_j=0$ 或 $\sum_{i=1}^ma_{ij}y_i=c_j$
对于所有 $1\leq i\leq m$ ：满足 $y_i=0$ 或 $\sum_{j=1}^na_{ij}x_j=b_i$

用人话说。这个定理描述的是对于两个问题的可行解x和y，他们如果是最优解，一定满足：
对于矩阵中的每一列，要么这一列对应的原问题的变量取值为 $0$ ，要么这一列对应的对偶问题的约束取等。
对于矩阵中的每一行，要么这一行对应的对偶问题的变量取值为 $0$ ，要么这一行对应的原问题的约束取等。

这样描述应该直观多了。那么这个定理有什么用处呢？当我们求出了对偶问题的一个最优解y，想求出原问题的最优解x，我们只需要让x满足上面两个条件，又满足原问题的约束，再求一个可行解即可。这时不需要最优化目标函数取值了，一般就变成了一个容易的问题。
如：若我们把原问题转化为费用流，则原问题满足一个约束中最多两个变量，都为 $\pm1$ ，问题就变成了一个差分约束系统求可行解的问题，上最短路算法即可。
对于对偶问题是半平面交的线性规划，因为只有两个约束，可以推出最多有两个变量非 $0$ （根据线性性），然后我就不太会了。。。然后貌似可以只列一个二元方程组，然后解出解的系数表达式，要让两个变量都 $\geq 0$ ，可以得到系数之间的关系，然后排个序搞一搞就好了？？我是口胡大师QAQ

还有一点，就是原问题的无解对应对偶问题的解无限制，原问题的解无限制对应对偶问题的无解。

还有一个需要提，就是线性规划问题一般转化成的是点带供需的最小（大）费用可行流，一般需要转化成上下界费用流来解决，但是如果我们发现流满即能满足约束，那就直接最小（大）费用最大流即可。还有就是当可以判断不等式一定会取等时直接改成等号就行，就不用添加辅助变量了。

有一个题，做了应该就算毕业了。三道一样的原题______

Prutekoi's blog

线性规划，单纯形和对偶问题

单纯形

求和技巧（min_25筛和被吊打的杜教筛）