用单纯型算法解线性规划问题
单纯型算法(simplex algorithm)可以很好地用于在有约束的条件下解线性方程组。下面的例子来自于《迷茫的旅行商》一书，问题的来源是一个求商品利润最大化问题。假设只生产三种产品，分别称为产品A、产品B、产品C，它们的量也分别相应使用变量A、B、C表示。生产产品需要输入两种原料，这里假设它们是镍和钢，库存量分别为100磅和200磅。生产产品A需要消耗3磅镍和4磅钢，B需要3磅镍和2磅钢，C则需要1磅镍和8磅钢。
可以得出这道题的线性规划模型为：
目标： 10A+5B+15C取最大值
约束条件：
3A+3B+1C≤100(镍)
4A+2B+8C≤200(钢)
A≥0，B≥0，C≥0
下面来求解这个线性方程组。先记利润Z=10A+5B+15C -----①
镍的剩余量 N=100-3A-3B-C -----②
钢的剩余量 S=200-4A-2B-8C -----③
由于要求Z的最大值，所以我们可以先假设B=C=0，由方程②和③，以及N≥0，S≥0可以得到A≤100/3，此时得到Z的最大值为1000/3，但这并不就是所有Z的取值中的最大值，这时我们可以通过换主元法，即将A用N来表示，至于为什么要这样表示，我认为，由于我们并不知道A、B、C的上界，但是我们知道A、B、C的下界，即A≥0，B≥0，C≥0，所以必须想办法，让方程①中的各未知数系数为负，这样，我们就可以根据各未知数的下界来求最大值。所以这里，我们将A=100/3-N/3-B-C/3，分别代入方程①和③得到新的方程组：
Z=1000/3-10*N/3-5B+35*C/3 -----①
A=100/3-N/3-B-C/3 -----②
S=200/3+4*N/3+2B-20*C/3 -----③
由新的方程①我们发现N和B前面的系数是负的，所以我们再假设N=B=0，根据方程②和③得出C≤10，此时Z的值为450，但根据上面的方程组还看不出来这个值是否就是Z的最大值，所以再用一次换元法，将C用S表示，即C=10+N/5+3*B/10-3*S/20，分别代入上面新方程组的方程①和②中，又得到了一个新的方程组：
Z=450-N-3*B/2-7*S/4 -----①
A=30-2*N/5-11*B/10+S/20 -----②
C=10+N/5+3*B/10-3*S/20 -----③
于是由上面的方程①我们已经可以清楚的看出，Z的最大值为450，此时N=B=S=0，A=30，C=10。因此，利润的最大值肯定不会超过450。
最后提一件小事，不知道是印刷错误还是作者计算错误，最后一步方程组的方程②和③和我计算出来的不一样，经过检验我确信自己计算没错，所以应该是书上的方程计算错误，书上给出的方程②和③分别为：
A=30-2*N/5-11*B/10-S/20 -----②
C=10-N/5-3*B/10-3*S/20 -----③
最近在读《迷茫的旅行商》，收获挺大的，虽然里面的许多算法都涉及不深，但从另一个角度来看，我们可以发现，原来一个TSP问题，可以引出如此多的问题，而且随着TSP研究的深入，各种高效算法层出不穷，很多算法现在都用在了各个领域，并取得了很好的效果。