学了很长时间，一直不是很能理解，所以就准备写一篇。
这篇文章只讲单纯形算法。
假设我们已经得到了标准型：
\[\begin{aligned} \max:\sum\limits_{i=1}^na_ix_i\\ \sum\limits_{i=1}^nb_{j,i}x_i=c_j&,j=1,2\dots m\\ x_i\geqslant 0&,i=1,2\dots n \end{aligned}\]而得到最优解的过程就是：
找到一个基变量和非基变量，将他们交换。我们通过不断地交换，不断地让答案更优。
这就是在凸壳上不断向最优解移动的过程。
先据一组数据作为具体的例子：
\[max:5x_1+2x_2 \]\[\begin{cases} 30x_1+20x_2+x_3=160\\ 5x_1+x_2+x_4=15\\ x_1+x_5=4\\ x_1,x_2,x_3,x_4,x_5\geqslant 0 \end{cases}\]有 \(m\) 条限制，我们分别令 \(x_3,x_4,x_5\) 为其基变量，\(x_1,x_2\) 为非基变量。
我们可以得到
我们令所有的非基变量为 \(0\)，我们可以得到一组解 \(\begin{cases}x_1=0\\x_2=0\\x_3=160\\x_4=15\\x_5=4\end{cases}\)。
我们获得了一个小的可怜的答案——\(0\)。
而在我们要最大化的答案中，\(x_1\) 和 \(x_2\) 的系数均 \(>0\)，也就意味着，我们增大其中任何一个数又可以让答案变优，所以我们贪心地选择系数较大的 \(x_1\)。
我们把它从 \(0\) 增大到某一个正实数，我们需要找到它的上界，也就是在 \(x_1\) 不断地增加的过程中，哪一个非基变量会先变成 \(0\)。
仍然令其它非基变量是 \(0\)，我们可以得到三个基变量的限制：\(\begin{cases}x_3=160-30x_1\\x_4=15-5x_1\\x_5=4-x_1\end{cases}\)，他们分别要求 \(\begin{cases}x_1\leqslant \frac{16}{3}\\x_1\leqslant 3\\x_1\leqslant 4\end{cases}\)，其中最紧的限制为 \(x_4\)，我们就将 \(x_4\) 变成非基变量，把 \(x_1\) 变成基变量。我们就需要用 \(x_4\) 和其他的非基变量来替换 \(x_1\)，根据等式 \(x_4=15-5x_1-x_2\) 可以得到 \(x_1=3-\frac{1}{5}x_4-\frac{1}{5}x_2\)。
替换可以得到新的限制：
\[\begin{aligned} max:&15&-x_4&+x_2\\ x_3=&70&+6x_4&-14x_2\\ x_1=&3&-\frac{1}{5}x_4&-\frac{1}{5}x_2\\ x_5=&1&+\frac{1}{5}x_4&+\frac{1}{5}x_2\\ \end{aligned} \]这个限制我们可以得到解 \(\begin{cases}x_1=3\\x_2=0\\x_3=70\\x_4=0\\x_5=1\end{cases}\)。
接下来我们继续重复这个过程，发现 \(x_4\) 的系数是负的，我们交换它不会使得答案变优，所以我们只能替换 \(x_2\)。
仍然是有三条限制：\(\begin{cases}x_3=70-14x_2\\x_1=3-\frac{1}{5}x_2\\x_5=1+\frac{1}{5}x_2\end{cases}\)，三个方程分别解出来为 \(\begin{cases}x_2\leqslant 5\\x_2\leqslant 15\\x_2\geqslant -5\end{cases}\)，显然第三条限制是没有用的，其中最紧的限制是 \(x_3\) 的限制，所以考虑将 \(x_2\) 和 \(x_3\) 进行交换，得到 \(x_2=5-\frac{1}{14}x_3+\frac{3}{7}x_4\)。
替换得到：
\[\begin{aligned} max:&20&-\frac{4}{7}x_4&-\frac{1}{14}x_3\\ x_2=&5&-\frac{1}{14}x_3&+\frac{3}{7}x_4\\ x_1=&2&-\frac{1}{70}x_3&-\frac{2}{7}x_4\\ x_5=&6&+\frac{1}{70}x_3&+\frac{2}{7}x_4\\ \end{aligned} \]发现剩下的两个系数都是 \(<0\) 了，所以这就是可能的最优解了。
我们抽象一下刚才的过程，我们就可以得到一个具体的过程了：
找到最大的系数 \(a_i\)，如果其大于 \(0\)，我们找到所有对其限制最大的编号最小的一个基变量，将这两个变量进行一次交换，然后重复这个过程。
实现代码如下：
namespace XG{
double a[50][50],tr;
int n,m,ind[50];
void turn(int x,int y)
{
for(int i=0;i<=n;i++)
if(i!=x)
{
tr=a[i][y]/a[x][y];
for(int j=1;j<=m;j++)
a[i][j]-=a[x][j]*tr;
}
tr=a[x][ind[x]=y];
for(int i=1;i<=m;i++)
a[x][i]/=tr;
}
double solve()
{
while(1)
{
double maxn=0,lim=1e18;
int x=0,y=0;
for(int i=1;i<=m;i++)
if(a[0][i]>maxn)
x=i,maxn=a[0][i];
if(!x) break;
for(int i=1;i<=n;i++)
if(a[i][x]>0&&lim>a[i][m]/a[i][x])
lim=a[i][m]/a[i][x],y=i;
if(!y) break;
turn(y,x);
}
return -a[0][m];
}
}