线 性 规 划 算 法 详 解.pdfVIP

线性规划算法详解

线性规划

首先什么是线性规划，大致的定义我总结为在线性的目标和约束

中，找出一个最优解。

举个例子：

M1和M2两种原料用于生产内外墙涂料，M1日最大可用量24吨，

M2日最大可用量为6吨，外墙涂料每吨需要6吨M1，1吨M2，内墙

涂料每吨需要4吨M12，吨M2，外墙涂料每吨利润5个单位，内墙涂

料每吨利润4个单位。且市场需求调查数据得出，内墙日需求量不超

过外墙的日需求量+1吨，内墙最大日需求量为2吨

怎样在这样的各个线性的条件中，得到最优的内外墙生产吨数，

就是我们线性规划算法要做的事情。

设外墙生产x1吨,内墙生产x2吨,设利润为z，要得到z的最大

化，也就是最优解，上述条件罗列为公式可得出

6x1+4x2=24

x1+2x2=6

-x1+x2=1

z=5x1+4x2

如何从这个公式中求出最优解？有以下两大方法

我们将上述约束条件画图，y轴为x2，x轴为x1，得出如下：

圈红色的部分就是所有的可行解，表示这个区间内都的x1x2能满

足约束条件

对于我们的z函数，其实表示的是一条截距为z斜率为-(5-4)的

线性直线，我们要求z最大化的最优解，就是在所有的可行区域内找

到可以满足z曲线截距最大的点。

最后我们发现，可行区域内能让z函数达到最大截距的点就是我

圈出来的那个角点，z再增大的话，就超出可行区域了，所以不满足

要求，所以最终得出最优解为x1=3,x2=1.5

这就是图解法的做法，一个定理就是，线性规划的最优解总是发

生在约束几何平面的角点上，例如上面圈出来的点，先当做是个定理，

我也不知道怎么证明这个定理。

以上就是线性规划的图解法，优点是简单明了，缺点就是当参数

超过3个时，我们很难直观画出一个jihe几何平面来找角点，所以

我们需要下面的另一种解法。

单纯形法

当超过3个参数时，单纯形法就派上用场了，单纯形法首先要做

的就是把方程化为标准形式：

所有的变量都是非负数

所有的约束都是等式(非负限制除外)，且具有非负的右端项

像上述的方程，如果化为标准形式，将会是如下

6x1+4x2+s1=24

x1+2x2+s2=6

-x1+x2+s3=1

x2+s4=2

z=5x1+4x2+0s1+0s2+0s3+0s4

新加入的s1-4表示的是松弛变量(非负)，根据大于号小于号来决

定他们的正负号

对于标准化形式，我们设有n个参数，设列举出的约束方程个数

m，当m=n时，方程组就只有唯一的解，当mn时，说明有无穷个可行

解，也就是解是一个区域。

例如y=x+1单独这个约束方程，那么可行解就是这条直线上的所

有点，这个就是m=1,n=2的情况，如果再加上一个方程使得m=2，例

如y=-x,则是唯一的解了，解为(-0.5,0.5)

由上面的定理，最优可行解必然出现在几何空间上的角点

几何角点的代数定义

对于一个m*n的方程组，我们另n-m个变量为0，再去在m个方

程中求出其余的m个变量的值，如果有可行解，则这m个变量得出的

点就是这个超几何平面的角点。

例如y=x+1,xy都非负，这里m=1我们就有两种角点情况，一种是

x=0的角点，一种是y=0的角点，画图上便可只管看出。对于超3维

的几何面也是如此类推，虽然我不知道如何直观证明，但这就是个定

理。

所以我们线性规划最终zu做的事就是，找出适合的角点，并代入

最优的z方程，哪个得出的z最优，哪个角点就是我们的最优解！

但当参数十分多时，角点的数量就十分庞大，所以我们需要一个

智能的搜索过程，来寻找出最优角点的位置。

进基离基

我们每一次的寻找角点称之为迭代，每一次我们都从原点，也就

是非松弛变量全为0的时候开始

我们称令(n-m)个变量为0的这些变量为非基变量，令其余的m个

变量为基变量。

从原点开始，我们计算完z值后，就要