管管 理理 运运 筹筹 学学4几种特殊情况 一、无可行解一、无可行解 例例1、用、用单纯单纯形表求解下列形表求解下列线线性性规规划划问题问题解：在上述解：在上述问题问题的的约约束条件中加入松束条件中加入松驰变驰变量、剩余量、剩余变变量、人工量、人工变变量得到：量得到： 填入填入单纯单纯形表形表计计算得：算得：1精选ppt管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 s1 s2 s3 a1b比比值值20 30 0 0 0 -M0s1s2a100-M3 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040150/1040/1zjcj-zj-M -M 0 0 M -M20+M 30+M 0 0 -M 0-40M1x2s2a1300-M3/10 1 1/10 0 0 0 1 0 0 1 0 07/10 0 -1/10 0 -1 115302515/(3/10)30/125/(7/10)zjcj-zj9-7/10M 30 3+M/10 0 M -M11+7/10M 0 -3-M/10 0 -M 0 450-25M2x2x1a13020-M0 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6304zjcj-zj20 30 3+M/10 11+7M/10 M -M0 0 -3-M/10 -11-7M/10 -M 0780-4M2精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 从第二次迭代的从第二次迭代的检验检验数都小于零来看，可知第数都小于零来看，可知第2次迭代所得的基本可次迭代所得的基本可行解已行解已经经是最是最优优解了，其最大的目解了，其最大的目标标函数函数值为值为780-4M。我。我们们把最把最优优解解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个代入第三个约约束方程得束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640. 并不并不满满足原来的足原来的约约束条件束条件3，可知原，可知原线线性性规规划划问题问题无可行解，或者无可行解，或者说说其可行解域其可行解域为为空集，当然更不可能有最空集，当然更不可能有最优优解了。解了。 像像这样这样只要求只要求线线性性规规划的划的最最优优解里有人工解里有人工变变量大于零量大于零，则则此此线线性性规规划划无可行解无可行解。二、无界解二、无界解 在求目在求目标标函数最大函数最大值值的的问题问题中，所中，所谓谓无无界解是指在界解是指在约约束条件下目束条件下目标标函数函数值值可以取可以取任意的大。下面我任意的大。下面我们们用用单纯单纯形表来求第二形表来求第二章中的例子。章中的例子。例例2 2、用、用单纯单纯形表求解下面形表求解下面线线性性规规划划问题问题。 3精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比比值值1 1 0 00s1s2001 -1 1 0-3 2 0 1161zjcj-zj0 0 0 0 1 1 0 001x1s2101 -1 1 0 0 -1 3 119zjcj-zj1 -1 1 00 2 -1 01填入填入单纯单纯形表形表计计算得：算得：解：在上述解：在上述问题问题的的约约束条件中加入松束条件中加入松驰变驰变量，得量，得标标准型如下：准型如下：4精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 从从单纯单纯形表中，从第一次迭代形表中，从第一次迭代x2的的检验检验数等于数等于2，可知所得的基本可行，可知所得的基本可行解解x1=1,x2=0,s1=0,s2=9不是最不是最优优解。同解。同时时我我们们也知道如果也知道如果进进行第行第2次迭代，那次迭代，那么就么就选选x2为为入基入基变变量，但是在量，但是在选择选择出基出基变变量量时时遇到了遇到了问题问题： =-1, =-1,找找不到大于零的比不到大于零的比值值来确定出基来确定出基变变量量。事。事实实上如果我上如果我们们碰到碰到这这种情况就可以种情况就可以断定断定这这个个线线性性规规划划问题问题是无界是无界的，也就是的，也就是说说在此在此线线性性规规划的划的约约束条件下，束条件下，此目此目标标函数函数值值可以取得无限大。从可以取得无限大。从1次迭代的次迭代的单纯单纯形表中，得到形表中，得到约约束方程：束方程： 移移项项可得：可得：5精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 由于由于M可以是任意大的正数，可知此目可以是任意大的正数，可知此目标标函数函数值值无界。无界。 上述的例子告上述的例子告诉诉了我了我们们在在单纯单纯形表中形表中识别线识别线性性规规划划问题问题是无界的方法：是无界的方法：在某次迭代的在某次迭代的单纯单纯形表中，如果形表中，如果存在着一个大于零的存在着一个大于零的检验检验数数 ，并且，并且该该列列的系数向量的每个元素的系数向量的每个元素aij(i=1,2,m)都小于或等于零都小于或等于零，则则此此线线性性规规划划问题问题是无界是无界的，一般地的，一般地说说此此类问题类问题的出的出现现是由于建模的是由于建模的错误错误所引起的。所引起的。三、无三、无穷穷多最多最优优解解例例3、用、用单纯单纯形法表求解下面的形法表求解下面的线线性性规规划划问题问题。6精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 解：此解：此题题我我们们用用图图解法已求了解，解法已求了解，现现在用在用单纯单纯形表来求解。形表来求解。填入填入单纯单纯形表形表计计算得：算得：7精选ppt管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 s1 s2 s3b比比值值50 50 0 0 00s1s2s30001 1 1 0 02 1 0 1 00 1 0 0 1300400250300/1400/1250/1zjcj-zj0 0 0 0 050 50 0 0 001s1s2x200501 0 1 0 -12 0 0 1 -10 1 0 0 15015025050/1150/2zjcj-zj0 50 0 0 5050 0 0 0 0125002x1s2x2500501 0 1 0 -10 0 -2 1 10 1 0 0 1505025050/1250/1zjcj-zj50 50 50 0 00 0 -50 0 0150008精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 这样这样我我们们求得了最求得了最优优解解为为x1=50,x2=250,s1=0,s2=50,s3=0,此此线线性性规规划的最划的最优值为优值为15000。这这个最个最优优解是否是惟一的呢？由于在第解是否是惟一的呢？由于在第2次迭代的次迭代的检验检验数中数中除了基除了基变变量的量的检验检验数数 等于零外，等于零外，非基非基变变量量s3的的检验检验数也等于数也等于零零，这样这样我我们们可以断定此可以断定此线线性性规规划划问题问题有无有无穷穷多最多最优优解。不妨我解。不妨我们们把把检验检验数也数也为为零的非基零的非基变变量量选为选为入基入基变变量量进进行第行第3次迭代。可求得另一个基本可次迭代。可求得另一个基本可行解，如下表所示：行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50 50 50 0 00 0 -50 0 015000 从从检验检验数可知此基本可行解数可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最也是最优优解解9精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 四、退化四、退化问题问题 在在单纯单纯形法形法计计算算过过程中，确定出基程中，确定出基变变量量时时有有时时存在两个以上的相同的存在两个以上的相同的最小比最小比值值，这样这样在下一次迭代中就有了一个或几个基在下一次迭代中就有了一个或几个基变变量等于零，量等于零，这这称之称之为为退化。退化。例例4.用用单纯单纯形表，求解下列形表，求解下列线线性性规规划划问题问题。解：加上松解：加上松驰变驰变量量s1,s2,s3化化为标为标准形式后，准形式后，填入填入单纯单纯形表形表计计算得：算得：10精选ppt管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 x3 s1 s2 s3b比比值值2 0 3/2 0 0 00s1s2s30001 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 12432/14/23/1zjcj-zj0 0 0 0 0 02 0 3/2 0 0 001x1s2s32001 -1 0 1 0 0 0 2 1 -2 1 00 2 1 -1 0 12010/21/2zjcj-zj2 -2 0 0 0 00 2 3/2 -2 0 042x1x2s32001 0 1/2 0 1/2 00 1 1/2 - 1 1/2 00 0 0 1 -1 1 2012/(1/2)0/(1/2)zjcj-zj2 0 1 0 1 00 0 1/2 0 -1 0411精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 在以上的在以上的计计算中可以看出在算中可以看出在0次迭代中，由于比次迭代中，由于比值值b1/a11=b2/a21=2为为最小比最小比值值，导导致在第致在第1次迭代中出次迭代中出现现了退化，基了退化，基变变量量s2=0。又由于在第。又由于在第1次迭代出次迭代出现现了了退化，基退化，基变变量量s2=0，又，又导导致第致第2次迭代所取得的目次迭代所取得的目标标函数函数值值并没有得到改善，仍然与第并没有得到改善，仍然与第1次迭代的一次迭代的一样样都都等于等于4。像。像这样继续这样继续迭代而得不到目迭代而得不到目标标函数的改善，函数的改善，当然减低了当然减低了单纯单纯形算法的效率，但一般来形算法的效率，但一般来说还说还是可以是可以得到最得到最优优解的。像本解的。像本题继续计题继续计算如下：算如下：12精选ppt管管 理理 运运 筹筹 学学4几种特殊情况迭迭代代次次数数基基变变量量CBx1 x2 x3 s1 s2 s3b比比值值2 0 3/2 0 0 03x1x3s323/201 -1 0 1 0 00 2 1 - 2 1 00 0 0 1 -1 1 2012/11/1zjcj-zj2 1 3/2 -1 3/2 00 -1 0 1 -3/2 044x1x3s123/201 -1 0 0 1 -10 2 1 0 -1 20 0 0 1 -1 1 221zjcj-zj2 1 3/2 0 1/2 10 -1 0 0 -1/2 -1513精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 得到了最得到了最优优解解x x1 1=1=1，x x2 2=0=0，x x3 3=2=2，s s1 1=1=1，s s2 2=0=0，s s3 3=0=0，其最，其最优值为优值为5 5。 但有但有时时候当出候当出现现退化退化时时，即使存在最，即使存在最优优解，而迭代解，而迭代过过程程总总是重复解的是重复解的某一部分迭代某一部分迭代过过程，出程，出现现了了计计算算过过程的循程的循环环，目，目标标函数函数值总值总是不是不变变，永，永远远达不到最达不到最优优解。解。 下面一个是由下面一个是由E.Beale给给出的循出的循环环的例子。的例子。例例5 5 目目标标函数函数 ：min f =min f =（3/43/4）x x4 4+20x+20x5 5（1 12 2）x x6 6+6x+6x7 7. . 约约束条件：束条件：x x1 1+ +（1 14 4）x x4 48x8x5 5x x6 6+9x+9x7 7=0=0， x x2 2+ +（1 12 2）x x4 412x12x5 5（1 12 2）x x6 6+3x+3x7 7=0=0， x x3 3+x+x6 6=1=1， x x1 1，x x2 2，x x3 3，x x4 4，x x5 5，x x6 6，x x7 70.0.14精选ppt管管 理理 运运 筹筹 学学4几种特殊情况 这这个例个例题题的确存在最的确存在最优优解，但用一般解，但用一般单纯单纯形表法，形表法，经过经过6 6次迭代后得到的次迭代后得到的单纯单纯形表与第形表与第0 0次次单纯单纯形表一形表一样样，而目，而目标标函数函数都是零，没有任何都是零，没有任何变变化，化，这样这样迭代下去，永迭代下去，永远远达不到最达不到最优优解。解。为为了避免了避免这这种种现现象，我象，我们们介介绍绍勃勃兰兰特法特法则则。 首先我首先我们们把松弛把松弛变变量（剩余量（剩余变变量）、人工量）、人工变变量都用量都用x xj j表示，表示，一般松弛一般松弛变变量（剩余量（剩余变变量）的下量）的下标标号列在决策号列在决策变变量之后，人量之后，人工工变变量的下量的下标标号列在松弛号列在松弛变变量（剩余量（剩余变变量）之后，在量）之后，在计计算中，算中，遵守以下两个遵守以下两个规则规则：（1 1）在所有）在所有检验检验数大于零的非基数大于零的非基变变量中，量中，选选一个下一个下标标最小的最小的作作为为入基入基变变量。量。（2 2）在存在两个和两个以上最小比）在存在两个和两个以上最小比值时值时，选选一个下一个下标标最小的最小的基基变变量量为为出基出基变变量。量。 这样这样就一定能避免出就一定能避免出现现循循环环。 15精选ppt管管 理理 运运 筹筹 学学单纯性法小结化标准性:建立模型个 数取 值右 端 项等式或不等式极大或极小新加变量系数两个三个以上xj0xj无约束xj 0 bi 0bi 0且aik（i=1，2,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。17精选ppt