管理运筹学第5章单纯形法ppt课件

《管理运筹学第5章单纯形法ppt课件》由会员分享，可在线阅读，更多相关《管理运筹学第5章单纯形法ppt课件（46页珍藏版）》请在金锄头文库上搜索。

1、管管 理理 运运 筹筹 学学第五章 单 纯 形 法1 单纯形法的根本思绪和原理2 单纯形法的表格方式3 求目的函数值最小的线性规划的问题的 单纯形表解法4 几种特殊情况管管 理理 运运 筹筹 学学1 单纯形法的根本思绪和原理 单纯形法的根本思绪：从可行域中某一个顶点开场，判别此顶点能否是最优解，如不是,那么再找另一个使得其目的函数值更优的顶点，称之为迭代，再判别此点能否是最优解。直到找到一个顶点为其最优解，就是使得其目的函数值最优的解，或者能判别出线性规划问题无最优解为止。 经过第二章例1的求解来引见单纯形法: 在加上松弛变量之后我们可得到规范型如下： 目的函数： max 50x1+100x2

2、 约束条件：x1+x2+s1300， 2x1+x2+s2400， x2+s3250. xj0 j=1，2,sj0 j=1，2,3管管 理理 运运 筹筹 学学它的系数矩阵 , 其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始根本可行解，先引见以下几个线性规划的根本概念。 基： 知A是约束条件的mn系数矩阵，其秩为m。假设B是A中mm阶非奇特子矩阵即可逆矩阵，那么称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列那么称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫

3、基变量，基变量有m个。1 单纯形法的根本思绪和原理管管 理理 运运 筹筹 学学非基变量：与非基向量非基变量：与非基向量pjpj相应的变量相应的变量xjxj叫非基变量，非基变量有叫非基变量，非基变量有n nm m个。个。 由线性代数的知识知道，假设我们在约束方程组系数矩阵中找到一个由线性代数的知识知道，假设我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个基，令这个基的非基变量为零，再求解这个m m元线性方程组就可得到独一元线性方程组就可得到独一的解了，这个解我们称之为线性规划的根本解。的解了，这个解我们称之为线性规划的根本解。 在此例中我们无妨找到了在此例中我们无妨找到了

4、 为为A A的一个基，令这个基的的一个基，令这个基的 非基变量非基变量x x，s2s2为零。这时约束方程就变为基变量的约束方程：为零。这时约束方程就变为基变量的约束方程： 1 单纯形法的根本思绪和原理管管 理理 运运 筹筹 学学 x2+s1300， x2=400， x2+s3=250. 求解得到此线性规划的一个根本解：x1=0，x2=400，s1=100，s2=0，s3=150 由于在这个根本解中s1=100，s3=150，不满足该线性规划s10，s30的约束条件，显然不是此线性规划的可行解，一个根本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其一切变量的解能否满足非负的条件。我们

5、把满足非负条件的一个根本解叫做根本可行解，并把这样的基叫做可行基。1 单纯形法的根本思绪和原理管管 理理 运运 筹筹 学学 普通来说判别一个基能否是可行基，只需在求出其根本解以后，当其根本解一切变量的解都是大于等于零，才干断定这个解是根本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是根本可行解呢？由于在线性规划的规范型中要求bj都大于等于零，假设我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成至于各列向量的前后顺序是无关紧要的事例如，那么显然所求得的根本解一定是根本可行解，这个单位矩阵或由单位矩阵各

6、列向量组成的基一定是可行基。实践上这个根本可行解中的各个变量或等于某个bj或等于零。 1 单纯形法的根本思绪和原理管管 理理 运运 筹筹 学学 在本例题中我们就找到了一个基是单位矩阵。 在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的根本可行解叫初始根本可行解。假设找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，详细做法在以后详细讲述。1 单纯形法的根本思绪和原理管管 理理 运运 筹筹 学学二、二、 最最优性性检验 所所谓最最优性性检验就是判就是判别已求得的根本可行解能否是最已求得的根本可行解能否是最优解。解

7、。1. 1. 最最优性性检验的根据的根据检验数数jj 普通来普通来说目的函数中既包括基目的函数中既包括基变量，又包括非基量，又包括非基变量。如今我量。如今我们要求要求只用非基只用非基变量来表示目的函数，量来表示目的函数，这只需在只需在约束等式中束等式中经过移移项等等处置就可置就可以用非基以用非基变量来表示基量来表示基变量，然后用非基量，然后用非基变量的表示式替代目的函数中基量的表示式替代目的函数中基变量，量，这样目的函数中只含有非基目的函数中只含有非基变量了，或者量了，或者说目的函数中基目的函数中基变量的系量的系数都数都为零了。此零了。此时目的函数中一切目的函数中一切变量的系数即量的系数即为各

8、各变量的量的检验数，把数，把变量量xixi的的检验数数记为ii。显然然一一切切基基变量量的的检验数数必必为零零。在在本本例例题中中目目的的函数函数为50x1+100x250x1+100x2。由于初始可行解中。由于初始可行解中x1x1，x2x2为非基非基变量，所以此目的函量，所以此目的函数曾数曾经用非基用非基变量表示了，不需求再代量表示了，不需求再代换出基出基变量了。量了。这样我我们可知可知1=501=50，2=1002=100，3=03=0，4=04=0，5=05=0。1 单纯形法的根本思绪和原理管管 理理 运运 筹筹 学学1 单纯形法的根本思绪和原理2.最优解判别定理 对于求最大目的函数的问

9、题中，对于某个根本可行解，假设一切检验数 0，那么这个根本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目的函数为如下方式 由于一切的xj的取值范围为大于等于零，当一切的 都小 于等于零时，可知 是一个小于等于零的数，要使z 的值最大，显然 只需为零。我们把这些xj取为非基 变量(即令这些xj的值为零)，所求得的根本可行解就使目的函数值最大为z0。*对于求目的函数最小值的情况，只需把 0改为 0管管 理理 运运 筹筹 学学1 单纯形法的根本思绪和原理三、三、 基基变换 经过检验，我，我们知道知道这个初始根本可行解不是最个初始根本可行解不是最优解。下面引解。下面引见

10、如何如何进行基行基变换找到一个新的可行基，找到一个新的可行基，详细的做法是从可行基中的做法是从可行基中换一个列向量，得一个列向量，得到一个新的可行基，使得求解得到的新的根本可行解，其目的函数到一个新的可行基，使得求解得到的新的根本可行解，其目的函数值更更优。为了了换基就要确定基就要确定换入入变量与量与换出出变量。量。1. 1. 入基入基变量确量确实定定 从最从最优解判解判别定理知道，当某个定理知道，当某个jj0 0时，非基，非基变量量xjxj变为基基变量不取量不取零零值可以使目的函数可以使目的函数值增大，故我增大，故我们要要选基基检验数大于数大于0 0的非基的非基变量量换到基到基变量量中中去去

11、称称之之为入入基基变量量。假假设有有两两个个以以上上的的jj0 0，那那么么为了了使使目目的的函数函数添加得更大些，普通添加得更大些，普通选其中的其中的jj最大者的非基最大者的非基变量量为入基入基变量，在本例量，在本例题中中2=1002=100是是检验数中最大的正数，数中最大的正数，应选x2x2为入基入基变量。量。管管 理理 运运 筹筹 学学1 单纯形法的根本思绪和原理2. 出基变量确实定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？ 假设把s3作为出基变量，那么新的基变量为x2，s1，s2，由于非基变量x1=s

12、3=0， 我们也可以从下式： x2 +s1=300， x2+s2=400， x2=250， 求出根本解：x1=0，x2=250，s1=50，s2=150，s3=0。由于此解满足非负条件，是根本可行解，故s3可以确定为出基变量。 能否在求出根本解以前来确定出基变量呢？ 以下就来看在找出了初始根本可行解和确定了入基变量之后，怎样样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？ 管管 理理 运运 筹筹 学学1 单纯形法的根本思绪和原理 我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量

13、确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。 在本例题中约束方程为 在第二步中曾经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得管管 理理 运运 筹筹 学学1 单纯形法的根本思绪和原理 其中 的值最小，所以可以知道在原基变量中系数向量为 的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。 令非基变量为零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的根本可行解x1=0,x2=250,s1=50,s2=150. 这时目的函数值为 50x1+100x2=500+100250=25

14、000。 显然比初始根本可行解x1=0,x2=0,s1=300,s3=250时的目的函数值为0要好得多。 下面我们再进展检验其最优性，假设不是最优解还要继续进展基变换，直至找到最优解，或者可以判别出线性规划无最优解为止。管管 理理 运运 筹筹 学学2 单纯形法的表格方式 在讲解单纯形法的表格方式之前，先从普通数学模型里推导出检验数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下假设其系数矩阵的前m列是单位矩阵： 以下用 表示基变量，用 表示非基变量。管管 理理 运运 筹筹 学学2 单纯形法的表格方式 把第i个约束方程移项，就可以用非基变量来表示基变量xi， 把以上的表达式带入目的函数，就有

15、 其中：管管 理理 运运 筹筹 学学2 单纯形法的表格方式 上面假设x1,x2,xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。假设迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目的函数系数为cBi，系数列向量为 那么 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目的函数依次组成的有序行向量。 单纯形法的表格方式是把用单纯形法求出根本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的方式有些像增广矩阵，而其计算的方法也大体上运用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。 max 50x

16、1+100x2+0s1+0s2+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的数据填入如下的单纯形表格管管 理理 运运 筹筹 学学2 单纯形法的表格方式按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；在 行中填入cj-zj所得的值，如 ；z表示把初始根本可行解代入目的函数求得的目的函数值，即b列*cB列；初始根本可

17、行解为s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此确定s3为出基变量；由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。迭代次数基变量 cB x1 x2 s3 s4 s5 b比值Bi/ai2 50 100 0 0 00 s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1300400250300/1400/1250/1 zj 0 0 0 0 0 50 100 0 0 0z=0管管 理理 运运 筹筹 学学2 单纯形法的表格方式以下进展第一次迭代，其变量为

18、x2,s1,s2,经过矩阵行的初等变换，求出一个新的根本可行解，详细的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是 也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。在上表中第3个基变量s1已被x2替代，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32曾经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。求得第1次迭代的根本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.迭代次数基变量 cB x1 x2 s3

19、s4 s5 b 比值 bi/aij 50 100 0 0 01 s1 s2 x2 0 0 100 1 0 1 0 -1 2 0 0 1 -1 0 1 0 0 1 50 150 250 50/1 150/2 zj 0 100 0 0 100 50 0 0 0 -10025000管管 理理 运运 筹筹 学学2 单纯形法的表格方式从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表中可知第二次迭代得到的根本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27

20、500。由于检验数都0，因此所求得的根本可行解为最优解， z=27500为最优目的函数值。实践上，我们可以延续地运用一个单纯形表，不用一次迭代重画一个表头。迭代次数基变量 cB x1 x2 s3 s4 s5 b 比值 bi/aij 50 100 0 0 02 x1 s2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50 250 zj 50 100 50 0 50 0 0 -50 0 -5027500管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法一、大M法以第二章的例2来讲解如何用单纯形表的方法求解目的函数值最小的

21、线性规划问题。目的函数：约束条件：参与松弛变量和剩余变量变为规范型，得到新的约束条件如下：管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法 至于目的函数，在规范型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个一致的解法，我们把一切求目的函数最小值的问题化成求目的函数最大值的问题。详细做法只需把目的函数乘以1。 要留意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。为了竭尽全力地要求人工

22、变量为零，我们规定人工变量在目的函数中的系数为M，这里M为恣意大的数。这样只需人工变量M0，所求的目的函数最大值就是一个恣意小的数。这样为了使目的函数实现最大就必需把人工变量从基变量中换出。假设不断到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，那么该问题无可行解。管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法 此例的数学模型如下所示： 目的函数： max z=2x13x2Ma1Ma2. 约束条件：x1+x2s1+a1=350， x1s2+a2=125， 2x1+x2+s3=600， x1，x2，s1，s2，s3，a1，a20. 像这样，为了构造

23、初始可行基得到初始可行解，把人工变量“强行地 加到原来的约束方程中去，又为了尽力地把人工变量从基变量中交换出来就令人工变量在求最大值的目的函数里的系数为M，这个方法叫做大M法，M叫做罚因子。管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法下面我们就用大M法来求解此题:迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 -2 -3 0 0 0 -M -M0a1a2a3-M-M0 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2M -M M

24、 M 0 -M -M-2+2M -3+M -M -M 0 0 0-475M1a1x2s3-M-20 0 1 -1 0 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -2225125350225-350/2 zj -2 -M M -M+2 0 -M -M-2 0 -3+M -M M-2 0 0 2-2M-225M-2502a1x1s2-M-20 0 1/2 -1 0 -1/2 1 0 1 1/2 0 0 1/2 0 0 0 1/2 0 1 1/2 0 -15030017550/1/2300/1/2175/1/2 zj -2 -1/2M-1 M 0 1/2M-1 -M 0 0

25、 1/2M-2 -M 0 - 1/2M+1 0 -M-50M-600管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法 从上表中可知检验数都小于零。已求得最优解为： x1=250,x2=100,s1=0, s2=125,s3=0,a1=0,a2=0，其最优值为 f=-z=-(-800)=800。迭代迭代次数次数基变基变量量 cB x1 x2 s1 s2 s3 a1 a2 b 比值比值 -2 -3 0 0 0 -M -M3 x2 x1 s2 -3 -2 0 0 1 -2 0 -1 2 0 1 0 1 0 1 -1 0 0 0 1 1 1 -1 -1 100 250 1

26、25 zj -2 -3 4 0 1 -4 0 0 0 -4 0 -1 -M+4 -M -800管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法二、两阶段法 两阶段法是处置人工变量的另一种方法，这种方法是将参与人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，论述两阶段法的求解过程。 第一阶段：要判别原线性规划能否有基可行解，方法是先求解以下线性规划问题： 目的函数： 约束条件：管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法 留意：此线性规划的约束条件与原线性规划一样，而目的函数是求人工变量的相反数之和的最大值。假设此值大于零，

27、那么不存在使一切人工变量都为零的可行解，停顿计算。假设此值为零，即阐明存在一个可行解，使得一切的人工变量都为零。 第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目的函数换成原问题的目的函数，把此可行解作为初始可行解进展计算。管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 -2 -3 0 0 0 -1 -10a1a2s3-1-10 1 1 -1 0 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2

28、 -1 1 1 0 -1 -1-2 1 -1 -1 0 0 0-4701a1x1s3-100 0 1 -1 1 0 1 -1 1 0 0 -1 0 0 1 0 1 0 2 1 0 -2225125350 zj 0 -1 1 -1 0 -1 1 0 1 -1 1 0 0 22252x2x1s3000 0 1 -1 1 0 1 0 1 0 0 -1 0 0 1 0 0 1 1 1 -1 -1225125125 zj 0 0 0 0 0 0 0 0 0 0 0 0 -1 -10管管 理理 运运 筹筹 学学3 求目的函数值最小的线性规划的问题的单纯形表解法迭代迭代次数次数基变基变量量cB x1 x2

29、s1 s2 s3b比值比值 -2 -3 0 0 0 0x2x1s3-3-20 0 1 -1 1 0 1 0 0 -1 0 0 1 0 2 1225125125225/1125/2 zj-2 -3 3 -1 0 0 0 -3 1 0-9251x2x1s2-3-20 0 1 -2 0 -1 1 0 1 0 1 0 0 1 1 1100250125 zj -2 -3 4 0 1 0 0 -4 0 -1-800 从表中可知其根本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。管管 理理 运运 筹筹 学学4 几种特殊情况 一、无可行

30、解一、无可行解 例例1、用单纯形表求解以下线性规划问题、用单纯形表求解以下线性规划问题解：在上述问题的约束条件中参与松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中参与松驰变量、剩余变量、人工变量得到： 填入单纯形表计算得：填入单纯形表计算得：管管 理理 运运 筹筹 学学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

31、-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-4M管管 理理 运运

32、 筹筹 学学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，可知原，可知原线性性规划划问题无可行解，或者无可行解，或者说其可行解域其可行解域为空集，当然更不能空集，当然更不能够有最有最优解了。解了。 像

33、像这样只需求只需求线性性规划的最划的最优解里有人工解里有人工变量大于零，那么此量大于零，那么此线性性规划无可行解。划无可行解。二、无界解二、无界解 在求目的函数最大在求目的函数最大值的的问题中，所中，所谓无无界解是指在界解是指在约束条件下目的函数束条件下目的函数值可以取可以取恣意的大。下面我恣意的大。下面我们用用单纯形表来求第二形表来求第二章中的例子。章中的例子。例例2 2、用单纯形表求解下面线性、用单纯形表求解下面线性规划问题。规划问题。 管管 理理 运运 筹筹 学学4 几种特殊情况 迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比值比值1 1 0 00s1s2001 -1 1 0

34、-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 几种特殊情况 从单纯形表中，从第一次迭代的检验数等于从单纯形表中，从第一次迭代的检验数等于2，可知所得的根本可行解，可知所得的根本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道假设进展第不是最优解。同时我们也知道假设进展第2次迭

35、代，那次迭代，那么就选么就选x2为入基变量，但是在选择出基变量时遇到了问题：为入基变量，但是在选择出基变量时遇到了问题： =-1, =-1,找找不到大于零的不到大于零的 来确定出基变量。现实上假设我们碰到这种情况就可以断来确定出基变量。现实上假设我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目的函数值可以获得无限大。从目的函数值可以获得无限大。从1次迭代的单纯形表中，得到约束方程：次迭代的单纯形表中，得到约束方程： 移项可得：移项可得：管管 理理 运运 筹筹 学学4 几种特殊情况 由于由于

36、M可以是恣意大的正数，可知此目的函数可以是恣意大的正数，可知此目的函数值无界。无界。 上述的例子通知了我上述的例子通知了我们在在单纯形表中形表中识别线性性规划划问题是无界的方法：是无界的方法：在某次迭代的在某次迭代的单纯形表中，假形表中，假设存在着一个大于零的存在着一个大于零的检验数数 ，并且，并且该列列的系数向量的每个元素的系数向量的每个元素aij(i=1,2,m)都小于或等于零，那么此都小于或等于零，那么此线性性规划划问题是无界的，普通地是无界的，普通地说此此类问题的出的出现是由于建模的是由于建模的错误所引起的。所引起的。三、无三、无穷多最多最优解解例例3、用、用单纯形法表求解下面的形法表

37、求解下面的线性性规划划问题。管管 理理 运运 筹筹 学学4 几种特殊情况 解：此题我们用图解法已求了解，如今用单纯形表来求解。解：此题我们用图解法已求了解，如今用单纯形表来求解。填入单纯形表计算得：填入单纯形表计算得：管管 理理 运运 筹筹 学学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

38、 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 015000管管 理理 运运 筹筹 学学4 几种特殊情况 这样我们求得了最优解为这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的此线性规划的最优值为最优值为15000。这个最优解能否是独一的呢？由于在第。这个最优解能否是独一的呢？由于在第2次迭代的检验数次迭代的检验数中除

39、了基变量的检验数中除了基变量的检验数 等于零外，非基变量等于零外，非基变量s3的检验数也等的检验数也等于零，这样我们可以断定此线性规划问题有无穷多最优解。无妨我们把检于零，这样我们可以断定此线性规划问题有无穷多最优解。无妨我们把检验数也为零的非基变量选为入基变量进展第验数也为零的非基变量选为入基变量进展第3次迭代。可求得另一个根本次迭代。可求得另一个根本可行解，如下表所示：可行解，如下表所示：迭代迭代次数次数基基变变量量CBx1 x2 s1 s2 s3b50 50 0 0 03x1s3x2500501 0 -1 1 00 0 -2 1 10 1 2 -1 010050200zjcj-zj50

40、50 50 0 00 0 -50 0 015000管管 理理 运运 筹筹 学学4 几种特殊情况 从从检验数可知此根本可行解数可知此根本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最也是最优解，从解，从图解法可知解法可知衔接接这两点的两点的线段上的任一点都是此段上的任一点都是此线性性规划的最划的最优解，解，无妨用向量无妨用向量Z1，Z2表示上述两个最表示上述两个最优解即解即Z1 =50，250，0，50，0， Z2 =100，200，0，0，50，那么此，那么此线段上的任一点，即可表示段上的任一点，即可表示为Z1+1- Z2，其中，其中01。如。如图5-1所示：所示：1

41、00100200200300300100100200200300300250250Z1Z1Z2Z2图图5-1管管 理理 运运 筹筹 学学4 几种特殊情况 在一个已得到最优解的单纯形表中，假设存在一个非基变量的检验数在一个已得到最优解的单纯形表中，假设存在一个非基变量的检验数 为零，为什么我们把这个非基变量为零，为什么我们把这个非基变量xs作为入基变量进展迭代时，得到的最作为入基变量进展迭代时，得到的最优解仍为最优解呢？优解仍为最优解呢？ 无妨设出基变量为无妨设出基变量为xk，那么原最优单纯形表可表示如下：，那么原最优单纯形表可表示如下：管管 理理 运运 筹筹 学学4 几种特殊情况 经过迭代，我

42、们得到了新的单纯形表，其中经过迭代，我们得到了新的单纯形表，其中xs为基变量了，而为基变量了，而xk为非为非基变量了。我们可得到下表。基变量了。我们可得到下表。管管 理理 运运 筹筹 学学4 几种特殊情况 又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，依然小于零，这样就证明了新得到的根明其他的非基变量的检验数不变，依然小于零，这样就证明了新得到的根本可行解依然是最优解。本可行解依然是最优解。 这样我们得到了判别线性规划有无穷多最优解的方法：对于某个最优这样我们得到了判别线性规划有无穷多最优解

43、的方法：对于某个最优的根本可行解，假设存在某个非基变量的检验数为零，那么此线性规划问的根本可行解，假设存在某个非基变量的检验数为零，那么此线性规划问题有无穷多最优解。题有无穷多最优解。四、退化问题四、退化问题 在单纯形法计算过程中，确定出基变量时有时存在两个以上的一样的在单纯形法计算过程中，确定出基变量时有时存在两个以上的一样的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。为退化。例例4.用单纯形表，求解以下线性规划问题。用单纯形表，求解以下线性规划问题。解：加上松驰变量解：加上松驰变量s1,s2,s3化

44、为规范方式后，化为规范方式后，填入单纯形表计算得：填入单纯形表计算得：管管 理理 运运 筹筹 学学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

45、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 04管管 理理 运运 筹筹 学学4 几种特殊情况 在以上的计算中可以看出在在以上的计算中可以看出在0次迭代中，由于比值次迭代中，由于比值b1/a11=b2/a21=2为最小比值，导致在第为最小比值，导致在第1次迭代中出现了退化，基变量次迭代中出现了退化，基变量s2=0。又由于在第。又由于在第1次迭代出现了退化，基变量次迭代出现了退化，基变量s2=0，又导致第，又导致第2次迭代所获得的目的函数值次迭代所获得的目的函数值并

46、没有得到改善，依然与第并没有得到改善，依然与第1次迭代的一样都等于次迭代的一样都等于4。像这样继续迭代而得。像这样继续迭代而得不到目的函数的改善，当然减低了单纯形算法的效率，但普通来说还是可不到目的函数的改善，当然减低了单纯形算法的效率，但普通来说还是可以得到最优解的。像此题继续计算如下：以得到最优解的。像此题继续计算如下：管管 理理 运运 筹筹 学学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-

47、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 -15管管 理理 运运 筹筹 学学4 几种特殊情况 得到了最得到了最优解解x1=1x1=1，x2=0x2=0，x3=2x3=2，s1=1s1=1，s2=0s2=0，s3=0s3=0，其最，其最优值为5 5。 但有但有时候当出候当出现退化退化时，即使存在最，即使存在最优解，而迭代解，而迭代过程程总是反复解的是反复解的某一部分迭代某一部分迭代过程，出程，出

48、现了了计算算过程的循程的循环，目的函数，目的函数值总是不是不变，永，永远达不到最达不到最优解。解。 下面一个是由下面一个是由E.BealeE.Beale给出的循出的循环的例子。的例子。例例5 5 目的函数目的函数 ：min f =min f =3/43/4x4+20x5x4+20x51 12 2x6+6x7.x6+6x7. 约束条件：束条件：x1+x1+1 14 4x4x48x58x5x6+9x7=0x6+9x7=0， x2+ x2+1 12 2x4x412x512x51 12 2x6+3x7=0x6+3x7=0， x3+x6=1 x3+x6=1， x1 x1，x2x2，x3x3，x4x4，x

49、5x5，x6x6，x70.x70.管管 理理 运运 筹筹 学学4 几种特殊情况 这个例题确实存在最优解，但用普通单纯形表法，经过这个例题确实存在最优解，但用普通单纯形表法，经过6 6次迭代后得次迭代后得到的单纯形表与第到的单纯形表与第0 0次单纯形表一样，而目的函数都是零，没有任何变化，次单纯形表一样，而目的函数都是零，没有任何变化，这样迭代下去，永远达不到最优解。为了防止这种景象，我们引见勃兰特这样迭代下去，永远达不到最优解。为了防止这种景象，我们引见勃兰特法那么。法那么。 首先我们把松弛变量剩余变量、人工变量都用首先我们把松弛变量剩余变量、人工变量都用xjxj表示，普通松弛表示，普通松弛变量剩余变量的下标号列在决策变量之后，人工变量的下标号列在松变量剩余变量的下标号列在决策变量之后，人工变量的下标号列在松弛变量剩余变量之后，在计算中，遵守以下两个规那么：弛变量剩余变量之后，在计算中，遵守以下两个规那么：1 1在一切检验数大于零的非基变量中，选一个下标最小的作为入基变在一切检验数大于零的非基变量中，选一个下标最小的作为入基变量。量。2 2在存在两个和两个以上最小比值时，选一个下标最小的基变量为出在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。基变量。 这样就一定能防止出现循环。这样就一定能防止出现循环。