5章单纯形法课件.ppt

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

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

3、向量pi相应的变量xi叫基变量，基变量有m个。1 单纯形法的基本思路和原理100100101200111),(54321pppppA.3管管 理理 运运 筹筹 学学非基变量：非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有nm个。由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。在此例中我们不妨找到了 为A的一个基，令这个基的 非基变量x，s2为零。这时约束方程就变为基变量的约束方程：1010010113B1 单纯形法的基本思路和原理.4管管 理理 运运 筹筹 学学

4、x2+s1300，x2=400，x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=100，s2=0，s3=150 由于在这个基本解中s1=100，s3=150，不满足该线性规划s10，s30的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。1 单纯形法的基本思路和原理.5管管 理理 运运 筹筹 学学 一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解

5、是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。0100011001 单纯形法的基本思路和原理.6管管 理理 运运 筹筹 学学 在本例题中我们就找到了一个基是单位矩阵。在第一次找可行基时，所找

6、到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。1000100012B1 单纯形法的基本思路和原理.7管管 理理 运运 筹筹 学学二、二、最优性检验最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。1.最优性检验的依据检验数j 一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变

7、量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。显然所有基变量的检验数必为零。在本例题中目标函数为50 x1+100 x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知1=50，2=100，3=0，4=0，5=0。1 单纯形法的基本思路和原理.8管管 理理 运运 筹筹 学学1 单纯形法的基本思路和原理 2.最优解判别定理 对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 0，则这个基本可行解是最优解。下面我们用通俗的

8、说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式 由于所有的xj的取值范围为大于等于零，当所有的 都小 于等于零时，可知 是一个小于等于零的数，要使z 的值最大，显然 只有为零。我们把这些xj取为非基 变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。*对于求目标函数最小值的情况，只需把 0改为 0j0jjj Jzzxjjjj Jxjjj Jxjj.9管管 理理 运运 筹筹 学学1 单纯形法的基本思路和原理三、三、基变换基变换 通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到

9、一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。为了换基就要确定换入变量与换出变量。1.入基变量的确定 从最优解判别定理知道，当某个j0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j最大者的非基变量为入基变量，在本例题中2=100是检验数中最大的正数，故选x2为入基变量。.10管管 理理 运运 筹筹 学学1 单纯形法的基本思路和原理2.出基变量的确定 在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，

10、也就是确定哪一个基变量变成非基变量呢？如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0，我们也可以从下式：x2+s1=300，x2+s2=400，x2=250，求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因为此解满足非负条件，是基本可行解，故s3可以确定为出基变量。能否在求出基本解以前来确定出基变量呢？以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？.11管管 理理 运运 筹筹 学学1 单纯形法的基本思路和原理 我们把确定出基变量的方法概括如下：把已确定的入基

11、变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。在本例题中约束方程为 在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得12112223300,2400,250.xxsxxsxs312122232300400250300,400,250.111bbbaaa.12管管 理理 运运 筹筹 学学1 单纯形法的基本思路和原理 其中 的值最小，所以可以知道在原基变量中系数向量为 的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x

12、1，s3为非基变量。令非基变量为零，得 x2+s1=300,x2+s2=400,x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.这时目标函数值为 50 x1+100 x2=500+100250=25000。显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好得多。下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。332ba30,0,1Te.13管管 理理 运运 筹筹 学学2 单纯形法的表格形式 在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数 的

13、表达式。可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：以下用 表示基变量，用 表示非基变量。j112211,111,122,112,2,11,max.,0.1,2,nnmmnnmmnnmm mmm nnmjzc xc xc xxaxaxbxaxaxbxaxaxbxjn1,2,ix im1,2,jxjmmn.14管管 理理 运运 筹筹 学学2 单纯形法的表格形式 把第i个约束方程移项，就可以用非基变量来表示基变量xi，把以上的表达式带入目标函数，就有 其中：,11,22,1.1,2,iii mmi mmi nnniijjj mxbaxaxa xba xim1 122

14、110011mnnniijjij mnnjjjjjj mj mzc xc xc xc xc xzcz xzx01,;miijjjizcbcz121 12212112,jmjjiijjjmmjmimjmjaazc ac ac ac ac ccac ccp.15管管 理理 运运 筹筹 学学2 单纯形法的表格形式 上面假设x1,x2,xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为 则 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数

15、依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。max 50 x1+100 x2+0s1+0s2+0s3.x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，x1,x2,s1,s2,s30.把上面的数据填入如下的单纯形表格1,2,jpjn1,jBBmjBjzccpcp.16管管 理理 运运 筹筹 学学2 单纯形法的表格形式按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的

16、单位矩阵，对应的基变量为s1,s2,s3；在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；在 行中填入cj-zj所得的值，如 ；z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此确定s3为出基变量；由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。jjjcz迭代次数基变量 cB x1 x2 s3 s4 s5 b比值Bi/ai2 50 1

17、00 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=0jjjcz150050210.17管管 理理 运运 筹筹 学学2 单纯形法的表格形式以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是 也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。在上表中第3个基变量s1已被x2代

18、替，故基变量列中的第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.30,0,1Te jjjcz迭代次数基变量 cB x1 x2 s3 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

19、0 0 0 -10025000.18管管 理理 运运 筹筹 学学2 单纯形法的表格形式从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50,s3=0,这时z=27500。由于检验数都0，因此所求得的基本可行解为最优解，z=27500为最优目标函数值。实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。1500jjjcz迭代次数基变量 cB x1 x2 s3 s4 s5 b 比值 bi/a

20、ij 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.19管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划的问题的单纯形表解法一、大M法以第二章的例2来讲解如何用单纯形表的方法求解目标函数值最小的线性规划问题。目标函数：约束条件：加入松弛变量和剩余变量变为标准型，得到新的约束条件如下：12min23.fxx1211212350,125,2600,0.xxxxxx x1211212312123350,125,260

21、0,0.xxsxsxxsx x s s s.20管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划的问题的单纯形表解法 至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问题化成求目标函数最大值的问题。具体做法只要把目标函数乘以（1）。要注意到人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。为了竭尽全力地要求人工变量为零，我们规定人工变量在目标函数中的

22、系数为M，这里M为任意大的数。这样只要人工变量M0，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，则该问题无可行解。.21管管 理理 运运 筹筹 学学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叫做罚因子。.22管管 理理 运运 筹筹 学学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 M 0 -M -M-2+2M -3+M

24、-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 1/2M-2 -M 0 -1/2M+1 0

25、-M-50M-600jjjczjjjczjjjcz.23管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划的问题的单纯形表解法 从上表中可知检验数都小于零。已求得最优解为：x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最优值为 f=-z=-(-800)=800。jjjcz迭代迭代次数次数基变基变量量 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 125 z

26、j -2 -3 4 0 1 -4 0 0 0 -4 0 -1 -M+4 -M-800.24管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划的问题的单纯形表解法二、两阶段法 两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划划分两阶段求解，仍以上面的例题为例，阐述两阶段法的求解过程。第一阶段：要判断原线性规划是否有基可行解，方法是先求解下列线性规划问题：目标函数：约束条件：12max;zaa 12111221231212312350,125,2600,0.xxsaxsaxxsx x s s s a a.25管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划

27、的问题的单纯形表解法 注意：此线性规划的约束条件与原线性规划一样，而目标函数是求人工变量的相反数之和的最大值。如果此值大于零，则不存在使所有人工变量都为零的可行解，停止计算。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。第二阶段：将第一阶段的最终单纯形表中的人工变量取消，将目标函数换成原问题的目标函数，把此可行解作为初始可行解进行计算。.26管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划的问题的单纯形表解法迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3 a1 a2b比值比值 -2 -3 0 0 0 -1 -10a1a2s3-1-10 1 1 -1 0

28、 0 1 0 1 0 0 -1 0 0 1 2 1 0 0 1 0 0350125600350/1125/1600/2 zj-2 -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 -

29、10.27管管 理理 运运 筹筹 学学3 求目标函数值最小的线性规划的问题的单纯形表解法迭代迭代次数次数基变基变量量cB x1 x2 s1 s2 s3b比值比值 -2 -3 0 0 0 0 x2x1s3-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=

30、0,s2=125,s3=0是本例的最优解，其最优值为z=-(-800)=800。.28管管 理理 运运 筹筹 学学4 几种特殊情况.0,40,30,1501033020max212112121xxxxxxxxxz约束条件目标函数一、无可行解一、无可行解 例例1、用单纯形表求解下列线性规划问题、用单纯形表求解下列线性规划问题解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：解：在上述问题的约束条件中加入松驰变量、剩余变量、人工变量得到：121121121231121231max2030310150,30,40,0.zxxMaxxsxsxxsax x s s s a目标函数约束条件

31、填入单纯形表计算得：填入单纯形表计算得：.29管管 理理 运运 筹筹 学学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-

32、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.30管管 理理 运运 筹筹 学学4 几种特殊情况 从第二次迭代的检验数都小于零来看，可知第从第二次迭代的检验数都小于零来看，可知第2次迭代所得的基本可次迭代所得的基本可行解已经是最优解了，其最大的目标函数值为行解已经是最优解

33、了，其最大的目标函数值为780-4M。我们把最优解。我们把最优解x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三个约束方程得代入第三个约束方程得x1+x2-0+4=40,即有：即有：x1+x2=3640.并不满足原来的约束条件并不满足原来的约束条件3，可知原线性规划问题无可行解，或者说，可知原线性规划问题无可行解，或者说其可行解域为空集，当然更不可能有最优解了。其可行解域为空集，当然更不可能有最优解了。像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划像这样只要求线性规划的最优解里有人工变量大于零，则此线性规划无可行解。无可行解。二、无界解二、无界解 在求目标函

34、数最大值的问题中，所谓无在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取界解是指在约束条件下目标函数值可以取任意的大。下面我们用单纯形表来求第二任意的大。下面我们用单纯形表来求第二章中的例子。章中的例子。例例2 2、用单纯形表求解下面线性、用单纯形表求解下面线性规划问题。规划问题。12121212max1,326,0.zxxxxxxx x目标函数约束条件.31管管 理理 运运 筹筹 学学4 几种特殊情况 迭迭代代次次数数基基变变量量CBx1 x2 s1 s2b比比值值1 1 0 00s1s2001 -1 1 0-3 2 0 1161zjcj-zj0 0 0 0 1 1 0

35、 001x1s2101 -1 1 0 0 -1 3 119zjcj-zj1 -1 1 00 2 -1 01填入单纯形表计算得：填入单纯形表计算得：解：在上述问题的约束条件中加入松驰变量，得标准型如下：解：在上述问题的约束条件中加入松驰变量，得标准型如下：121211221212max1,326,0.zxxxxsxxsx x s s目标函数约束条件.32管管 理理 运运 筹筹 学学4 几种特殊情况 12a 从单纯形表中，从第一次迭代的检验数等于从单纯形表中，从第一次迭代的检验数等于2，可知所得的基本可行解，可知所得的基本可行解x1=1,x2=0,s1=0,s2=9不是最优解。同时我们也知道如果进

36、行第不是最优解。同时我们也知道如果进行第2次迭代，那么次迭代，那么就选就选x2为入基变量，但是在选择出基变量时遇到了问题：为入基变量，但是在选择出基变量时遇到了问题：=-1,=-1,找不找不到大于零的到大于零的 来确定出基变量。事实上如果我们碰到这种情况就可以断定来确定出基变量。事实上如果我们碰到这种情况就可以断定这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目这个线性规划问题是无界的，也就是说在此线性规划的约束条件下，此目标函数值可以取得无限大。从标函数值可以取得无限大。从1次迭代的单纯形表中，得到约束方程：次迭代的单纯形表中，得到约束方程：22a22a 移项可得：移项可得：

37、1212121,39.xxsxss121221211212121,39.,0,1,0,9.121.xxssxsxM sxMxMssMzxxMMM 不妨设可得一组解：显然这是线性规划的可行解，此时目标函数.33管管 理理 运运 筹筹 学学4 几种特殊情况 ij 由于由于M可以是任意大的正数，可知此目标函数值无界。可以是任意大的正数，可知此目标函数值无界。上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：上述的例子告诉了我们在单纯形表中识别线性规划问题是无界的方法：在某次迭代的单纯形表中，如果存在着一个大于零的检验数在某次迭代的单纯形表中，如果存在着一个大于零的检验数 ，并且该列，并且

38、该列的系数向量的每个元素的系数向量的每个元素aij(i=1,2,m)都小于或等于零，则此线性规划问题都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。是无界的，一般地说此类问题的出现是由于建模的错误所引起的。三、无穷多最优解三、无穷多最优解例例3、用单纯形法表求解下面的线性规划问题。、用单纯形法表求解下面的线性规划问题。121212212max5050300,2400,250,0.zxxxxxxxx x目标函数约束条件.34管管 理理 运运 筹筹 学学4 几种特殊情况 解：此题我们用图解法已求了解，现在用单纯形表来求解。解：此题我们用图解法已求了解，现在

39、用单纯形表来求解。123121211222312123,max5050300,2400,250,0.s sszxxxxsxxsxsx xs ss加入松弛变量，我们得到标准形：目标函数约束条件填入单纯形表计算得：填入单纯形表计算得：.35管管 理理 运运 筹筹 学学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

40、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 015000.36管管 理理 运运 筹筹 学学4 几种特殊情况 124,这样我们求得了最优解为这样我们求得了最优解为x1=50,x2=250,s1=0,s2=50,s3=0,此线性规划的此线性规划的最优值为最优值为15000。这个最优解是否是惟一的呢？由于在第。这个最优解是否是惟一的呢？由于在第2

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

42、050200zjcj-zj50 50 50 0 00 0 -50 0 015000.37管管 理理 运运 筹筹 学学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），则此线段上的任一点，即可表示为），则此线段上的任一点，即可

43、表示为Z1+（1-）Z2，其中，其中01。如图。如图5-1所示：所示：100100200200300300100100200200300300250250Z Z1Z Z2图图5-1.38管管 理理 运运 筹筹 学学4 几种特殊情况 s 在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数 为零，为什么我们把这个非基变量为零，为什么我们把这个非基变量xs作为入基变量进行迭代时，得到的最作为入基变量进行迭代时，得到的最优解仍为最优解呢？优解仍为最优解呢？不妨设出基变量为不妨设出基变量为xk，则原最优单纯形表可表示如下：，则原最优单

44、纯形表可表示如下：111111,111,1122100100000,0ksksskkkskkk skkksmmm sjjjmsssmmsssiisixxccxcaxcaxcaxcaxcaczc ac ac accc a从此表可知即有，也就是。.39管管 理理 运运 筹筹 学学4 几种特殊情况 通过迭代，我们得到了新的单纯形表，其中通过迭代，我们得到了新的单纯形表，其中xs为基变量了，而为基变量了，而xk为非为非基变量了。我们可得到下表。基变量了。我们可得到下表。111111111111101101111000ksksskskmkiisiissiikksksksmkkksiiskkssiksks

45、sskskskkksmsmmksjksjjjkxxccaxcazc ac acaaaxcac ac acaaxcacaxcaaxcazzcczcz 在此表中把111.0.msiisikskksskksksjkjkc azcc accaaczcz，代入上式得：即又可得到：.40管管 理理 运运 筹筹 学学4 几种特殊情况 又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证又显然在新的单纯形表中，基变量的检验数为零，用同样的方法可证明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基明其他的非基变量的检验数不变，仍然小于零，这样就证明了新得到的基本可行解仍然是最优解。本可行解

46、仍然是最优解。这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优这样我们得到了判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无穷多最优解。有无穷多最优解。四、退化问题四、退化问题 在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的在单纯形法计算过程中，确定出基变量时有时存在两个以上的相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。为退化。例例4.用单纯形

47、表，求解下列线性规划问题。用单纯形表，求解下列线性规划问题。解：加上松驰变量解：加上松驰变量s1,s2,s3化为标准形式后，化为标准形式后，填入单纯形表计算得：填入单纯形表计算得：1312131231233max222,24,3,0.zxxxxxxxxxx x x目标函数约束条件.41管管 理理 运运 筹筹 学学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

48、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 04.42管管 理理 运运 筹筹 学学4 几种特殊情况 在以上的计算中可以看出在在以上的计算中可以看出在0次迭代中，由于比次迭代中，由于比值值b1/a11=b2/a21=2为最小比值，导致在第为最小比值，导致

49、在第1次迭代中出次迭代中出现了退化，基变量现了退化，基变量s2=0。又由于在第。又由于在第1次迭代出现了次迭代出现了退化，基变量退化，基变量s2=0，又导致第，又导致第2次迭代所取得的目标次迭代所取得的目标函数值并没有得到改善，仍然与第函数值并没有得到改善，仍然与第1次迭代的一样都次迭代的一样都等于等于4。像这样继续迭代而得不到目标函数的改善，。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：以得到最优解的。像本题继续计算如下：.43管管 理理 运运 筹筹 学学4 几种特殊情况迭迭

50、代代次次数数基基变变量量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 -15.44管管 理理 运运 筹筹 学学4 几种特殊情况 得到了最优解得到了最优解x x1 1=1=1，x x2 2=0=0，x