单纯形法求解原理过程

需要解决的问题：

如何确定初始基本可行解；

如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降；

如何判断一个基本可行解是否为最优解。

min f(X)=-60x1-120x2

s.t. 9x1+4x2+x3=360

3x1+10x2+x4=300

4x1+5x2+x5=200

x i≥0 (i=1,2,3,4,5)

(1) 初始基本可行解的求法。当用添加松弛变量的方法把不等式约

束换成等式约束时，我们往往会发现这些松弛变量就可以作为

初始基本可行解中的一部分基本变量。

例如：x1-x2+x3≤5

x1+2x2+x3≤10

x i≥0

引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式

x1-x2+x3+x4=5

x1+2x2+x3+x5=10

x i≥0 (i=1,2,3,4,5)

令x1=x2=x3=0，则可立即得到一组基本可行解

x1=x2=x3=0，x4=5，x5=10

同理在该实例中，从约束方程式的系数矩阵

中可以看出其中有个标准基，即

与B对应的变量x3，x4，x5为基本变量，所以可将约束方程写成

X3=360-9x1-4x2

x4=300-3x1-10x2

x5=200-4x1-5x2

若令非基变量x1=x2=0，则可得到一个初始基本可行解X0

X0=[0,0,360,300,200] T

判别初始基本可行解是否是最优解。此时可将上式代入到目标函数中，得：F(X)=-60x1-120x2

对应的函数值为f(X0)=0。

由于上式中x1,x2系数为负，因而f(X0)=0不是最小值。因此所得的解不是最优解。

(2) 从初始基本可行解X0迭代出另一个基本可行解X1，并判断X1是否

为最优解。从一个基本可行解迭代出另一个基本可行解可分为

两步进行：

第一步，从原来的非基变量中选一个（称为进基变量）使其成为基本变量；

第二步，从原来的基本变量中选一个（称为离基变量）使其成为新的非基变量。

选择进基和离基变量的原则是使目标函数值得到最快的下降和使所有的基本变量值必须是非负。

在目标函数表达式中，非基变量x1,x2的系数是负值可知，若x1,x2不取零而取正值时，则目标函数还可以下降。因此，只要目标函数式中还存在负系数的非基变量，就表明目标函数还有下降的可能。也就还需要将非基本变量和基本变量进行对换。一般选择目标函数式中系数最小的（即绝对值最大的负系数）非基变量x2换入基本变量，然后从x3，x4，x5中换出一个基本变量，并保证经变换后得到的基本变量均为非负。

当x1=0，约束表达式为：

X3=360-4x2≥0

x4=300-10x2≥0

x5=200-5x2≥0

从上式中可以看出，只有选择

x2=min{}=30

才能使上式成立。由于当x2=30时，原基本变量x4=0，其余x3和x5都满足非负要求。因此，可以将x2，x4互换。于是原约束方程式可得到：4x2+x3=360-9x1

10x2 =300-3x1-x4

5x2+x5=200-4x1

用消元法将上式中x2的系数列向量变[4,10,5]T换成标准基向量[0,1,0]T。其具体运算过程如下：

-*4/10 : x3=240-78x1/10+4 x4/10

/10 : x2 =30-3x1/10-x4/10-*5/10 : x5=50-25x1/10+5x4/10

再将上式代入到目标函数式中，得到：

F(X)=-60x1-120x2=-3600-24 x1+12 x4

令非基本变量x1=x4=0，即可得到另一个基本可行解。

X1=[0,30,240,0,50] T

目标函数F(X1)=-3600，比前一值f(X0)=0小了3600。由得到的目标表达式中x1的系数是负的，因而基本可行解还不是最优解。

（3）继续求出第3个基本可行解，并判断是否为最优解。同理可求出下一个基本可行解X2。而在第2个基本可行解的目标函数表达式中只有x1的系数是负值。所以，应选取x1为进基变量。然后分析上面得到的约束函数表达式。从x2，x3和x5中选取一个离基变量，并保证变化后得到的基本变量均为非负。当x4=0时，约束表达式有：

X3=240-39x1/5≥0

x2=30-3x1/10≥0

x5=50-5x1/2≥0

从上式中可以看出：

x1=min{}=20

才能使约束方程成立。由于当x1=20时，原基本变量x5=0，其余x2，X3均为非负。因此，可以将x1和x5互换。并由第2基本可行解的约束方程得到：

x3-39x1/5=240+2x4/5

x2 +3x1/10=30-x4/10

5x1/2=50+x4/2 -x5

用消元法将上式中x1的系数[39/5,3/10,5/2]T变换成标准基向量

[0,1,0]T。即

x1=20+x4/5 -2x5/5

x2=24-4x4/25+3x5/25

x3=84-29x4/25+78x5/25

再将上式代入到目标函数表式中，

F(X)=-60x1-120x2=-3600-24 x1+12 x4=-4080+36x4/5+48x5/5

令非基本变量x4=x5=0，由此可得到第3个基本可行解X2X2=[x12, x22, x32, x42, x52] T=[20,24,84,0,0] T

代入目标函数中，得F(X2)=-4080是最小值。因为该式中的所有非基本变量x4，x5的系数都为正数。再做任何迭代运算都不可能使目标函数值下降了。所有此基本可行解X2就是最优解。