人工变量单纯形法之两阶段单纯形法.ppt

第五节 人工变量单纯性法之两阶段单纯形法 我们学会了用单纯性表来求解线性规划的最优解问题，如下图所示： 将上表转化为下表即可求解问题。 最后我们可得最优解情况： 1、无最优解：一非基向量的检验数σ为正， 且其对应的列向量没有正分量。 2、有最优解：最终可将所有的非基本量的检验数化为非正数。 即：判断： （a）若σj≤０（j＝１，２，…，n）得到最解； （b）某个σk0且aik≤０（i=1，2,…,m）则线性规划具有无界解。 （c）若存在σk0且aik (i=1,…,m)不全非正，则进行换基； 人工变量单纯形法之两阶段单纯形法 两阶段单纯形法也是一种人工变量法，它的算法可分为两个阶段：第一阶段，引入人工变量，构造一个具有标准基的新线性规划，求解这个新线性规划，其结果有两种可能：或者将原问题的约束方程组化成具有标准基的形式，或者提供信息，表明原问题没有可行解。第二阶段，利用第一阶段所得的标准基，对原问题求解。 例子： max Z=x1+2x2+5x3-3x4 s.t. x1+x2 =3 2x1-2x2-x3 =6 2x1+x2+x3+x4=11 X=0 这个例子用以前的方法难以求解，没有标准基，我们可以试想添加变量，将其变成标准形式。 max W=-y1-y2 s.t. y1+x1+x2 =3 y2+2x1-2x2-x3 =6 2x1+x2+x3+x4=11 X=0 Y=0 添加了人工变量，原线性规划与新线性规划的关系是什么呢？大家可以思考一下。 用表1-14表示新线性规划求解过程 易知，新线性规划（LP）2 ，具有以下3个特点： 1、 （LP）2存在可行解，Y=b， X=0 2、 （LP）2 必有最优解。 3、 （LP）2 存在一个标准基。 The End! * 0 CN CB b N B b XN XB Η’ CN’ 0 b’ N’ I b XN XB 1．人工变量的引入 设原问题为 引入人工变量y1,y2, …,ym ，构造新线性规划 0 , 0 b Y+AX . . W max : ) ( 2 1 2 3 3 = - - - - = X Y I t s y y y LP m … b 表1－14 两阶段单纯形法的步骤： （1）第一阶段：首先将原问题标准化，得到(LP)1 得到形如表（1-14）的最优单纯形表。若该表中的 ，则表明原问题没有可行解，应停止计算； 含有标准基的同解方程组，转（2）。 形式，引入必要的人工变量 ，构造新的 规划(LP)2 ，并用单纯形法解新规划(LP)2， 线性 若 ，表明已将原问题的约束方程组变换成了 （2）第二阶段：用第一阶段所得的含标准基的约束 方程组取代原问题的约束方程组，再用单纯形法求解。 *