单纯形方法课件

1、2.3 单纯形方法典式基本定理单纯形方法单纯形表（单纯形方法的实现）1947年由Dantzig提出，被称为20世纪最好的十个算法之一，是迄今为止解决线性规划问题的最成熟的方法。定理2.2.6 一个标准的LP问题如果有有限的最优值， 则一定存在一个基本可行解是最优解。主要思想： 1）先找一个基本可行解2）判断是否为最优解3）是，stop；不是，再找一个更好的?已有初始解线性规划的标准形式：=1 典式(定义)1 典式（定义）典式的特点：1、约束条件中含有一个单位矩阵； 2、目标函数中不含基变量。000001100010=1 典式（定义）000001100010=1 典式（定义）问题：如何判断一个基

2、本可行解是否为最优解呢？典则形式的LP问题中，目标函数中的变量系数的符号，对于判断某一个基本可行解是不是最优解非常重要。本例中 是什么？典则形式的LP问题中，目标函数系数向量的负向量。 称为检验数向量.2 基本定理定理2.3.1 例如：2 基本定理例如：定理2.3.2则原问题无界。2 基本定理例如：定理2.3.3对应则2 基本定理定理2.3.4 对于任何非退化的线性规划问题，从任何基本可行解开始，经过有限多次迭代，或者得到一个基本可行的最优解，或者作出该线性规划问题无界的判断。3 单纯形方法Step 1 将线性规划问题化成典式,求出各个非基变量的检验数。Step 2 判断所有非基变量的检验数是

3、否非正,若是,则结束；否则转step 3。Step 3 选取一个检验数大于零的非基变量为进基变量；Step 4 若进基变量所对应的约束条件系数全为非正数,则原问题无界,结束；否则,按最小比值原则确定出基变量；Step 5 进行迭代(用方程组的初等行变换法确定新的基对应的典式及检验数),转step 2。 Z 0 1 -2 0 0 0 x1 x4 x5 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1 2x1 x2 x3 x4 x5 RHS Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 1检验数转

4、轴元 Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 1 Z 0 0 0 -0.5 -0.5 -1.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 最优解：x*=(6.5, 2.5, 0.5, 0, 0)T最优值：z*= -1.5 Z 0 1 2 0 0 0 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5x1 x2 x3 x4 x5 Z 0 0 0 1.5 -2.5 -3.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 此问题无界RHS例3：解LP问题4 单纯形表 Z 0 0 0 0 -1 18 x1 x4 x2 1 0 1 0 0 0 0 3 1 -1 0 1 -3/2 0 1/2 4 6 3x1 x2 x3 x4 x5 Z 0 0 0 0 -1 18 x1 x3 x2 1 0 0 -1/3 1/3 0 0 1 1/3 -1/3 0 1 0 1/2 0 2 2 6 此问