修正单纯形法求解约束优化问题

单纯形法

需要解决的问题：

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

如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降；如何判断一个基本可行解是否为最优解。

minf（x）=-60x1-120x2s.t.9x1+4x2+x3=3603x1+10x2+x4=3004x1+5x2+x5=200xi≥0（i=1，2，3，4，5）（1）初始基本可行解的求法。当用添加松弛变量的方法把不等式约束换成等式约束时，我们往往会发现这些松弛变量就可以作为初始基本可行解中的一部分基本变量。例如：x1-x2+x3≤5x1+2x2+x3≤10

xi≥0引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式x1-x2+x3+x4=5x1+2x2+x3+x5=10

xi≥0（i=1，2，3，4，5）令x1=x2=x3=0，则可立即得到一组基本可行解x1=x2=x3=0，x4=5，x5=10同理在该实例中，从约束方程式的系数矩阵

94100a[p1，p2，p3，p4，p5]31001045001中可以看出其中有个标准基，即

100b010001与b对应的变量x3，x4，x5为基本变量，所以可将约束方程写成x3=360-9x1-4x2x4=300-3x1-10x2x5=200-4x1-5x2

0若令非基变量x1=x2=0，则可得到一个初始基本可行解x0tx=[0，0，360，300，200]

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

0对应的函数值为f（x）=0。

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