资源描述：
《第章单纯形法的几种特殊情况学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§4 几种特殊情况一、无可行解例1、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：填入单纯形表计算得：1§4 几种特殊情况迭代次数基变量CBx1x2s1s2s3a1b比值2030000-M0s1s2a100-M31010001001001100-111503040150/10—40/1zjcj-zj-M-M00M-M20+M30+M00-M0-40M1x2s2a1300-M3/1011/100001001007/100-1/100-1115302515/(3/10)30/125/(7/10)zjcj-zj9-7/1
2、0M303+M/100M-M11+7/10M0-3-M/100-M0450-25M2x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304zjcj-zj20303+M/1011+7M/10M-M00-3-M/10-11-7M/10-M0780-4M2§4 几种特殊情况迭代次数基变量CBx1x2s1s2b比值11000s1s2001-110-3201161—zjcj-zj0000110001x1s2101-1100-13119zjcj-zj1-11002-101填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量
3、，得标准型如下：4§4 几种特殊情况从单纯形表中，从第一次迭代x2的检验数等于2，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进行第2次迭代，那么就选x2为入基变量，但是在选择出基变量时遇到了问题：=-1,=-1,找不到大于零的比值来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：移项可得：5§4 几种特殊情况由于M可以是任意大的正数，可知此目标函数值无界。上述的例子告诉了我们在单纯形表中识别
4、线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数，并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。三、无穷多最优解例3、用单纯形法表求解下面的线性规划问题。6§4 几种特殊情况解：此题我们用图解法已求了解，现在用单纯形表来求解。填入单纯形表计算得：7§4 几种特殊情况迭代次数基变量CBx1x2s1s2s3b比值50500000s1s2s3000111002101001001300400250300/1400/1250/1zjcj-zj0
5、0000505000001s1s2x200501010-12001-1010015015025050/1150/2—zjcj-zj0500050500000125002x1s2x2500501010-100-211010015050250—50/1250/1zjcj-zj5050500000-5000150008§4 几种特殊情况这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的最优值为15000。这个最优解是否是惟一的呢？由于在第2次迭代的检验数中除了基变量的检验数等于零外，非基变量s3的检验数也等于零，这样我们可以断
6、定此线性规划问题有无穷多最优解。不妨我们把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解，如下表所示：迭代次数基变量CBx1x2s1s2s3b50500003x1s3x25005010-11000-211012-1010050200zjcj-zj5050500000-500015000从检验数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最优解9§4 几种特殊情况四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化
7、。例4.用单纯形表，求解下列线性规划问题。解：加上松驰变量s1,s2,s3化为标准形式后，填入单纯形表计算得：10§4 几种特殊情况迭代次数基变量CBx1x2x3s1s2s3b比值203/20000s1s2s30001-101002010101110012432/14/23/1zjcj-zj000000203/200001x1s2s32001-10100021-210021-101201—0/21/2zjcj-zj2-20000023/2-20042x1x2s3200101/201/20011/2-11/200001-112012/(1/2)0/(1/2)—zj
8、cj-zj2010100
