学步园

线性规划就是给一堆变量的限制，然后求目标函数的最大值。

标准形式就是：

       给定A[n][m], C[n], B[m]

        Max ∑C[i]X[i]

       并且 ∑A[j][i]X[i] ≤ B[j] , X[i]>=0

所有的线性规划都可以转换为标准形式。通过两边乘以负一，一个变量变成两个，一条式子变成两条。

解决线性规划的一个经典非多项式算法就是单纯形算法（Simplex Algorithm），那么单纯形是究竟是神马东西来的呢？ 其实单纯形就是一个简单的图形（没有边与边相交的凸的图形）。线性规划的可行域放在一个N维空间里就是单纯形。

单纯形的重要理论是，如果一个线性规划有解，那么这个解必然在单纯形的一个端点上（如果有多个解，还可能在多个点上），找这个点的方法很简单，就是先弄到一个点，然后不断移动这个点，达到最优值为止。

理论上来说，n-1条限制式可以确定一个点，那么平面上最多有C(n-1, m)个点（显然单纯形上的端点没有那么多。。。我总是觉得单纯形上的点与n同阶），所以这个算法的时间复杂度是非多项式的。

说了一大堆理论上的东西，现在说实现的问题。首先，单纯形算法要把标准型转成松弛型的：

        Max ∑C[i]X[i] + const

       并且 ∑A[j][i]X[i] +X[n+j] = B[j] , X[i]>=0X[n+j]

这个东西叫做松弛变量，当有n-1个松弛变量为0时，就说明当前的点滑到了某个单纯形的端点上。

我们要做的就是不断进行调整操作，把某个非松弛变量和某个松弛变量（称为入基和出基）互换。找的方法是，找一个对应C[i]最大的变量作为入基，再找一个b[] / a[][k]最小的那条限制的松弛变量作为出基。每次互换都使目标函数中的const变大。当目标函数中的C[i]全部为非正数时，const就为最优值了。

其实simplex的编程复杂度其实不高，从松弛型开始到出解这个过程只用了70行(本人无压行习惯，所有"{"和"}"均占一行)。
最后本人很疼的做了一个速度测试，就是分别用匈牙利算法、带花树、Simplex做匈牙利匹配。测试数据自己随机生成，两边的点都为|V|，边数|E|约为2|V|。对于现行规划来说，变量有2|V|个，限制有2|V|条。以下是测试结果：

编号：Blossom总分：100.0第一题：match用时：0.20s编号用时空间0(match1.in)0.03s4.14M1(match2.in)0.02s4.14M2(match3.in)0.03s4.14M3(match4.in)0.02s4.14M4(match5.in)0.02s4.14M5(match6.in)0.02s4.14M6(match7.in)0.02s4.14M7(match8.in)0.02s4.14M8(match9.in)0.03s4.14M9(match10.in)0.02s4.14M编号：Hungary总分：100.0第一题：match用时：0.18s编号用时空间0(match1.in)0.02s4.14M1(match2.in)0.02s4.14M2(match3.in)0.03s4.14M3(match4.in)0.02s4.14M4(match5.in)0.02s4.14M5(match6.in)0.02s4.14M6(match7.in)0.03s4.14M7(match8.in)0.02s4.14M8(match9.in)0.02s4.14M9(match10.in)0.02s4.14M编号：Simplex总分：100.0第一题：match用时：0.62s编号用时空间0(match1.in)0.03s35.72M1(match2.in)0.03s35.73M2(match3.in)0.03s35.73M3(match4.in)0.03s35.73M4(match5.in)0.06s35.73M5(match6.in)0.08s35.73M6(match7.in)0.06s35.73M7(match8.in)0.08s35.73M8(match9.in)0.08s35.73M9(match10.in)0.14s35.73M

 数据大小为：

10 20 50 100 200 300 300 300 400 500

对测试结果不发表意见。