现在数学课也正好在讲线性规划呢。。虽然学的根本不是一种东西
感觉历年来讲线性规划的都讲的不是很好啊。。
以及代码写得真是太丑了！
1.线性规划
线性规划：给定\(n\)个变量和\(m\)个关于这\(n\)个变量的线性约束条件，求解一个关于这\(n\)个变量的线性函数的最值。
标准型：
最大化\(\sum_{i=1}^{n}c_i x_i\)
满足约束
\(\sum_{i=1}^{n}a_{j,i}x_i\le b_i(j\in[1,m])\)
\(x_i\ge 0(i\in[1,n])\)
显然，对于任意一个线性规划，我们总有办法将其转化为标准形式——通过添加负号，将一个变量表示为两个变量的差等。
有时我们也可以将\(a\)数组表示成矩阵的形式。
松弛型：
最大化\(\sum_{i=1}^{n}c_i x_i\)
满足约束
\(x_{n+j}=b_j-\sum_{i=1}^{n}a_{j,i}x_i(j\in [1,m])\)
\(x_i\ge 0(i\in[1,n+m])\)
松弛型可以很容易地由标准型转化得来。
2.单纯形法
在空间中，线性规划的几何概念是：在一个\(n\)维空间中，有\(m\)个半平面，在这些半平面的交中选择一个使函数\(f(x)=\sum_{i=1}^{n}c_i a_i\)最大的值。
那么我们可以将\(\sum_{i=1}^{n}c_i a_i=f(x)\)看成是另一个平面，随着\(f(x)\)的不断增大这个平面在空间中会不断平移，最终当平移到与可行区域（也就是之前\(m\)个半平面的交）交与不交的临界处时\(f(x)\)就取到了最大值。那么显然这个最大值会产生在某一个顶点（或者一条棱、一个面等，也可以视为顶点）上。并且，由于形成的区域是凸的，所以我们可以在形成的凸包的顶点上不断地走，若旁边的顶点比这个点更优则走过去；若没有更优的点，那么这个点一定是最优点。这就是单纯形法。
那么如何实现“在凸包上行走”呢？
就要借助线性规划的松弛型与“转轴”操作了。
在松弛型中，若要满足当前解在一个顶点上，那么在\(x_i(i\in[1,n+m])\)中，必定有\(n\)个为\(0\)。
我们可以一开始令\(x_i(i\in[1,n])\)都是\(0\)，那么它一定在一个顶点上。但它不一定是可行的。可以发现，当且仅当所有\(b\)非负时该解可行。
假设该解为可行解（不可行的解决方法后面会说），显然当前的函数值\(f(x)=0\)，那么我们可以通过所谓的“转轴”操作改变取\(0\)的\(x\)变量以实现“在凸包上行走”，并不断增加答案的值。
3.转轴操作
转轴操作的字面理解：
假设称所有取\(0\)的\(x\)的集合为A，其他的\(x\)的集合为B
在一个线性规划
最大化\(\sum_{i=1}^{n}c_i x_i\)
满足约束
\(x_j=b_j-\sum_{i\in A}a_{j,i}x_i(j\in B)\)
\(x_i\ge 0(i\in A\cup B)\)
中，一个当前可行解的所有不含有等号约束的\(x\)都将取\(0\)，可以理解为将这几个x定为坐标轴，当前可行解就在原点上。
那么更换取\(0\)的\(x\)变量就是在线性规划本质不发生改变的情况下交换两个变量的约束条件。
假设我们要交换\(x_l\)和\(x_e\)的约束且存在约束\(x_l=b_l-\sum_{i\in A}a_{l,i}x_i\)
那么将所有式子（包括\(f(x)\)）中的\(x_l\)和\(x_e\)依照上式替换就可以了，初中数学问题。
4.初始化
构造法
这是《算法导论》上给出的方法，也是最常用的，我在这里称它为构造法。
为了将所有的\(b\)变为非负，首先构造一个新的线性规划：
最大化\(-x_0\)
满足约束
\(x_{n+j}=b_j-\sum_{i=1}^{n}a_{j,i}x_i+x_0(j\in [1,m])\)
\(x_i\ge 0(i\in[0,n+m])\)
那么这个线性规划一开始也是无初始可行解的。不过我们可以找出最小的\(b\)所在的约束\(m\)然后执行\(pivot(m,0)\)，那么每一个约束都会加上\(-b_j\)，显然所有的\(b\)都会变为正。我们再删掉这个\(0\)即可。
但是不着急。我们还可以利用这个\(0\)来判断这个线性规划是否有解。我们解出新的线性规划，如果答案为\(0\)，说明这个\(x_0\)的确没什么用，也就是有解。否则，一定无解。
最后再删除\(x_0\)就可以开始解有初始可行解的线性规划了。
随机法
这是@wyh2000大神犇教我的方法。我就叫它随机法好了。
我们每一次在负的\(b\)中随机选择一个\(l\)，若找不到，说明已经满足了所有\(b\)大于\(0\)。否则在该\(b\)所在约束中找出一个\(a\)为负的\(e\)。若找不到，因为\(x\)有非负约束，那么这个不等式永远无法满足。若能找到，执行\(pivot(l,e)\)。这样一定能将当前的\(b\)变成正的。这样做直到\(b\)全部为正为止。
实测这样初始化的效率很高。不过由于是随机化算法，可能会出现一些奇怪的事情导致精度不够等。不过概率比较小。
5.对偶性
对于一个线性规划
最大化\(\sum_{i=1}^{n}c_i x_i\)
满足约束
\(\sum_{i=1}^{n}a_{j,i}x_i\le b_i(j\in[1,m])\)
\(x_i\ge 0(i\in[1,n])\)
那么它的对偶线性规划为
最小化\(\sum_{i=1}^{m}b_i y_i\)
满足约束
\(\sum_{i=1}^{m}a_{i,j}y_i\ge c_i(j\in[1,n])\)
\(y_i\ge 0(i\in[1,m])\)
这两个线性规划的答案是相同的。详细证明参考《算法导论》。
也可以视为将线性规划表示为一个\((m+1)\times(n+1)\)的矩形后转置后所表示的线性规划取最小值。