单纯形法求解线性规划问题

用单纯形法求解线性规划的思路是：因为一般线性规划问题的线性方程组的变量数大于方程个数，所以它有不定的解。但可以从线性方程组中找出一个个单纯形，并从每一个单纯形中求得一组解，然后再判断该解使目标函数值是增大了还是变小了，以决定下一步单纯形的选择。这就是迭代过程，通过迭代使目标函数达到最大值或最小值。

其核心是变量迭代，其过程如图1-7 所示。

图1-7　单纯形法思路

注意：单纯形是指0 维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中有n+1 个顶点的多面体。例如，三维空间中的四面体，其顶点分别为（0，0，0），（1，0，0），（0，1，0），（0，0，1）。具有单位截距的单纯形的方程是

这样就得到了问题的最优解。

单纯形表如表1-3 所示。

表1-3

其中

例1-8　现在用例1-1的标准型来说明.

（1）根据例1-1的标准型，取松弛变量x3，x4，x5为基变量，它对应的单位矩阵为基。这时得到初始基可行解：

将有关数字填入表中，得到初始单纯形表，如表1-4 所示。(www.xing528.com)

表1-4　初始单纯形表

在表1-4中左上角的cj表示目标函数中各变量的价值系数。在 CB列填入初始基变量的价值系数，它们都为零，各非基变量的检验数为

（2）因检验数都大于零，且P1，P2都有正分量存在，转入下一步。

（3）max{σ1，σ2}=max{2，3}=3，对应的变量 x2为换入变量，计算θ：

它所在行对应的x5为换出变量。x2所在列和 x5所在行的交叉处[4]称为主元素或枢元素（pivot element）。

（4）以[4]为主元素进行旋转计算，即初等行变换，使P2变换为（0，0，1）T，在XB列中用 x2替换 x5，于是得到表1-5。

表1-5

XB列的数字是x3=2，x4=16，x2=3，于是得到新的基可行解X（1）=（0，3，2，16，0）T。目标函数取值z＝9。

（5）检查表1-5中所有的cj-zj，这时有 c1-z1=2，说明x1应为换入变量。重复（2）～（4）的计算步骤，得到表1-6。

表1-6