线性规划单纯形法小结.ppt

《线性规划单纯形法小结.ppt》由会员分享，可在线阅读，更多相关《线性规划单纯形法小结.ppt（18页珍藏版）》请在三一办公上搜索。

1、线 性 规 划(Linear Programming),单纯形法小结,一、无穷多最优解例1、用单纯形法表求解下面的线性规划问题。,几种特殊情况,解：用单纯形表来求解。,填入单纯形表计算得：,非基变量s3的检验数等于零，这样我们可以断定此线性规划问题有无穷多最优解。求得另一个基本可行解，如下表所示：,不妨用向量Z1，Z2表示上述两个最优解即Z1=（50，250，0，50，0）t，Z2=（100，200，0，0，50）t，则无穷多最优解可表示为Z1+（1-）Z2，其中01。,二、无界解,例2、用单纯形表求解下面线性规划问题。,几种特殊情况,填入单纯形表计算得：,解：在上述问题的约束条件中加入松驰变

2、量，得标准型如下：,三、无可行解 例3、用单纯形表求解下列线性规划问题,解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：,填入单纯形表计算得：,几种特殊情况,只要最优解有人工变量大于零，则原线性规划无可行解。,有初始可行基的情况下：唯一最优解、无穷多最优解、无界解；无初始可行基的情况下会怎样？,标准化后列出初始单纯形表 A,线性规划问题单纯型方法求解的第一步是标准化,A,四、退化问题 如果一个基本可行解的基变量中至少有一个为0，则称此基本可行解为退化的基本可行解。例4.用单纯形表，求解下列线性规划问题。,几种特殊情况,几种特殊情况,解：加上松驰变量s1,s2,s3化为标准形式，

3、填入单纯形表计算：,在以上的计算中可以看出在0次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量s2=0。又由于在第1次迭代出现了退化，导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。当本题继续计算下去最后得到了最优解（1，0，2，1，0，0）T，其最优值为5。,但有些特殊情况下当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解 为了避免这种现象，我们介绍勃兰特法则。首先我们把松弛变量（剩余变量）、人工变量都用xj表示，一般松弛变量（剩余变量）的下标号列在决策变量之后，人工变量的下标号列在松弛变量（剩余变量）之后，在计算中，遵守以下两个规则：（1）在所有检验数大于零的非基变量中，选一个下标最小的作为进基变量。（2）在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。这样就一定能避免出现循环。,