线性规划之单纯形算法
学了很长时间，一直不是很能理解，所以就准备写一篇。
这篇文章只讲单纯形算法。
假设我们已经得到了标准型：
而得到最优解的过程就是：
找到一个基变量和非基变量，将他们交换。我们通过不断地交换，不断地让答案更优。
这就是在凸壳上不断向最优解移动的过程。
先据一组数据作为具体的例子：
有 \(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{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\)。
替换得到：
发现剩下的两个系数都是 \(<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];
}
}