单纯形方法

是解线性规划问题最重要和最基本的一种方法。此种方法的运算过程大体上分为两大阶段进行的。第一阶级是求一个可行基及其对应的单纯形表。第二阶段是从一个可行基出发，通过换基选代，不断改进直至求出最优解。假设B是一个基，可把系数矩阵写成A＝ （B， N），其中，B＝ （P1 ，P2，…，Pm），N＝（Pm+1，P■+2，… P■）。把X写成〔XB，XN〕′，其中XB＝〔x1 ， x2，…，xm 〕′为对应于基B的基变量部分，XN＝〔 xm+1， xm+2， … ， xn 〕 ′为对应于N的非基变量部分。相应地，设C＝（CB， CN），其中CB＝（C1， C2，…，Cm ）， CN ＝（Cm+1，Cm+2，…，Cn）。这样约束条件AX ＝ b可以写成（B， N ）·（xB， xN）′=b，即BXB+NXN ＝ b，通过矩阵运算可求得XB ＝B-1 b -B-1NXN。上式就是用非基变量xm+1，xm+2，…，xn来表示基变量x1，x2，…xm的形式。对应基B的单纯形表可记为：单纯形表，就是把线性规划问题的基变量和目标函数用非基变量表示的形式。表中第一列的第一个分量就是对应于B基础解的目标函数值，其余m个分量就是对应于B的基础解中基变量的值。表中第一行除第一个分量外，其余n个分量为检验数，如果所有检验数均非正，那么这一基础可行解就是最优解。否则，换基迭代，求另外一个基对应的单纯形表，再观察所有检验系统是否均为非正，直至求出最优解为止。