第三章线性规划的单纯形算法-1.ppt

第三章 单纯形法,§3.1 单纯形法原理,求解线性规划的单纯形方法（Simplex Method）是美国G·D·Dantzig在1947年提出来的。是一种有效的实用算法。 单纯形法是根据线性规划的基本原理，在基可行解上进行迭代的一种算法。此方法的特点是：将线性规划化为标准形，从一个初始基可行解开始迭代，使之改进得到另一个基可行解。每迭代一次，目标函数值绝不会变小，如果非退化，目标函数值就严格增大。若有最优解，经有限次迭代就得到基本最优解。 标准形式线性规划问题求解的主要途径是通过枢轴运算把约束方程组变为典范型来进行的。这个过程实质上就是古典的高斯-约当消去法求解线性规划的过程。,下列运算可以将一组线性方程变换为另一组等价的线性方程。 将一个方程 乘上一个常数k（k0） 将方程 用 替换 这样的运算称为线性方程组的初等变换，或称为基本行运算。下面分别说明枢轴运算（Pivot Operation）和典范型（Canonical form）,一 枢轴运算 枢轴运算就是通过一系列的基本行运算，使某一选定的变量在方程组的某一方程中系数是1，而这个变量在其他方程中的系数均为0 具体步骤是：,例：在下列方程组 中对变量 进行枢轴运算： 解： 选 中2 为枢轴项,在方程Er的s列中选取arsxs作为枢轴元素，条件是 枢轴元素所在的行称为枢轴行，枢轴元素所在的列称为枢轴列。 将方程Er除以 ，使枢轴元素系数为1。 对方程 以外的方程 ，用 来代替 。,将 除以2化为： 对 进行基本运算：即以 代替 得： 对 进行基本运算：即以 代替 得：,二 典范型线性方程组：,对n个变量m个方程的线性方程组可以通过对各个基变量逐一进行枢轴运算，将这m 个基变量的系数距阵变换成mxm单位阵。这样的等价线性方程组就是典范型线性方程组。,这样就可以直接求出一个基本解： 如果常数项均非负，则得到的就是基本可行解。 用矩阵符号表示就是： 约束方程为：Ax=b 变量分成基变量 和非基变量 两部分 系数距阵中相应分成B和N两块。即A=（B;N） 则约束方程组可以写成： 左乘以 得： 即 当非基变量取0时，则基变量的解为,由于基本解最多有 个，因而基可行解也不超过 个。 如果全部的基可行解找出来了，就有可能求出最优基本解。但这样做是不能实现的。单纯形法（Simplex Method）就是沿一个初始基可行解出发，找出下一个更优的基可行解，而不找所有的基可行解。,三 单纯形法的一般步骤, 如果线性规划问题存在可行解，就可以找出一个基可行解，作为初始可行解。 为寻找基可行解，约束方程组以典范型方程组表示。 如果线性规划问题不存在可行解（约束条件有矛盾）则由找基可行解的过程可以得知问题无解。, 以中找到的基可行解为起点，找出具有较佳目标值的另一基可行解。这一步骤称为迭代。 重复。直到目标函数再也不能改善，就得到问题最优解。 若问题的最优解是无界的，在迭代过程中就可以知道问题有无穷解，终止迭代。,解：这是一个标准形线性规划问题，可以化为等价的典范型方程组：,令 ，由上述典范型方程组直接得到一个基本解 。显然这个基本解是可行解。相应目标函数值为 现在要判断一下这个目标函数的值是否能改进，故换基变量就可能获得另一个基本可行解和相应的目标函数值。这样可用 或 来取代 或 成为基变量，因此目前的基本可行解有许多相邻的基本可行解。,单纯形法就是在得到一个基本可行解后，在它的相邻基可行解中选取能使目标函数值最大程度改进的基本可行解。,例如，现在考虑非基变量 ，假定 增加一个单位，而其余的非基变量暂不考虑，仍为0。则约束方程可表示为： 由第一个方程可见， 由01，则 由108。 由第二个方程可见， 由01，则 由63。 因此在满足上述方程组的条件下， 增加1得到新可行解为：,选取的原则是看哪一个非基变量改为基变量后能够使目标函数有更多的改进。具体地，可以在满足方程组的情况下，分别将各非基变量增加一个单位。比较目标值由此发生的变化，从而选取能使目标函数值有最大增加的非基变量作为新的基变量。,相应的目标值为： z=25 所以 x 3 增加1个单位，目标函数z的变化值为： z的旧值 - z的新值=22-（25）= -3 称这个值为非基变量x 3 的检验值（判别数）。因为可以用它来判别把x 3 改为基变量后，能否改进目标值。 这个检验数的绝对值有时也称为相对收益系数。 由于检验数为负，增加x 3可以增加目标函数值。这证明目前的基可行解不是最优解，如将x 3改为基变量就可以改进目标值。 类似的可以算 x 4, x 5 的检验数。 比较所得到的几个检验数，决定把哪个非基变量换为基变量对目标函数的改进有利。 检验数也可以用消去目标函数z中x 1, x 2的代入法来得,由此可知当取x 1和x 2为基变量时， x 3, x 4, x 5的检验数分别为-3，0和-2。目标值为22。 x 3, x 4或x 5每增加一个单位，z的值就相应增加3，0， 个单位，所以把x 3作为新基变量对改进目标函数最有利。 现在的问题是x 3增加多少仍能满足约束条件，仍然以 x 4, x 5 作非基变量。这时约束条件为：,从第一个方程看， 最多增到 ，若再大， 成为负值。,从第一个方程看， 最多增到 ，若再大， 成为负值。,因此为保证 最大增加值由这两个值中较小的一个来决定。即：,当 由02后， 新的目标值为z=28 。,这个目标值的改进是通过将非基变量 改为基变量，而基变量 改为非基变量得到的。,新引进的非基变量称为进基变量。 换出的基变量则称为出基变量。 选择进基变量的原则一般可以按负检验数绝对值大的先进基。 选择出基变量的原则是最小比值原则。 一般先决定进基变量，再决定出基变量。,当前得到的基可行解是否已最优还要重复上述算法，重新计算在目前的基可行解中所有非基变量的检验数。如果检验数中至少有一个负数，那么就可以得到另一个相邻基本可行解能使目标函数值进一步有所改进。 重复这一过程，直到所有检验数都不为负值。则此时的基可行解就是最优解。 用 来表示非基变量 的检验数，以 表示检验数组成的向量。注意一般在线性规划中，检验数取下面形式：,定义1：对于基B，称 为基B的判别数。,四 判别数，最优判别定理,设 是（SLP）的一个基变量，对应C中的系数 构成m维向量,判别数也可以用向量及距阵表示。因为,(注意：有些教科书书定义 。则下面表中计算时作相应变化。) 下面我们来用表格形式说明如何计算判别数。 作形如下面的表格。,定理1：设B是（SLP）的一个基，若满足 且 CBB-1A-C =0, 则对应基B的基可行解就是最优解。（称为基本最优解，基B称为最优基）,证明：因 。表明基变量取非负值。则基B对应的基本解为基本可行解。记为 ，其目标值记为 又设 是（SLP）的任意可行解，即 则目标值 要证 是基本最优解，只须证明 。 用基B的单纯形乘子 乘 两边得：,_,是最优基本解。,解：第一步，将（LP）问题化为（SLP）问题。 第二步，作下面形式的单纯形表（开始只能写出左上部表格）,§3.2 表格单纯形方法,我们先举个实例说明怎样用表格形式单纯形法解线性规划问题。 例：,第三步,第六步，对选定的入基变量 xj ，考虑 取 ，对应的变量 x2 作为出基变量,第七步，这样得到一组新基x1, x 3 ,对应的单纯形表如下(利用枢轴运算得下表粗线以上部分),（每迭代一次要计算一次 ）,由上例我们可以归纳出单纯形算法的步骤如下： 1 用标准形式表示问题 2 从含有初始基可行解的典范型方程组开始建立初始单纯形表示(注:对不易找到初始基的问题,将专门讨论) 3 应用内积规则求检验数,反复进行上述步骤，直到各检验数均非负值，即可得到基本最优解，上面得到原问题最优解为：,4 在某次迭代中如果所有j均非负值，则原基可行解即为最优解，算法终止。,5 如有j为负值，选取j绝对值最大的一列为枢轴列，使这一列对应的变量为进基变量。 6 应用最小比值规则,决定枢轴行,使这一行的基变量出基。最小比值原则就是指,若进基变量为xr 。r列的系数为,7 进行枢轴运算, 获得新的单纯行表. 返回第三步. 以上算法是针对极大化问题而言的,如在化标准型时不将极小化问题转化为极大化问题， 同样可以利用上述单纯行表形式求解，只要将检验数的判别准则改变一下符号就可以。,解:利用单纯形表迭代得,例2.求解线性规划,解:对后面两个约束方程引进松弛变量x5, x6化为：,例3,列出初始单纯形表并进行迭代得：,解:列单纯形表迭代过程如下:,例4.,作业:,这个结论说明了我们为什么可以只考虑非基变量的检验数,关于判别数的讨论,1. 如果所有判别数 。则由定理1（最优性判别定理）知当前的初始基本可行解是最优解，计算步骤终止。 2. 如果 可构造新的可行解. 先证明一个结论: 基变量对应的检验数：,下面再分两种情形讨论：,定理2.设B是(SLP)的一个可行基，若某非基变量 的判别数 且 。则此(SLP)问题的目标函数无上界无最优解 .(定理中的判别数 不一定是最小判别数, ） . 这个定理我们已经在上面作过讨论,下面再进行一次证明.,（SLP）的目标函数无上界，因而问题无最优解。,的其他坐标对应于非基变量坐标时：,解:引进松弛变量x4, x5化为,列出初始单纯形表并进行迭代过程如下:,例2. 解线性规划,其中：1=-9的这一列元素均为负数，因此原问题不存在有界最优解。,关于单纯行的迭代公式： 先回顾单纯形表格形式（SLP）,单纯形表实际上就是基B典则形式的一种表格表示方式,由此表立刻可以写出关于基B的典则形式来:,单纯形表就是把非基变量看作参数，表示出基变量和目标函数时的系数矩阵。 下面我们说明为什么上面典则形式中目标函数可以表示成:,若对所有非基变量的检验数 ，则无论将哪个非基变量换为基变量都不可能将目标函数值增加，因而此时的基可行解即为最优。,由上式我们再次看到算法终止准则的正确性.,根据前面有关讨论，在单纯形法每一步迭代中，都要作下面三种判断之一，以确定算法是终止还是继续。,1. 如果所有判别数 （j=1n）由最优判别定理1知B是最优基，则求出了最优基本解，步骤终止。,2. 如果存在 且 。由定理2知问题的目标函数无上界，无最优解，步骤终止。,3. 如果有 且 有正分量，这时进行枢轴运算，寻找新的基可行解。,如果以 为极轴， 出基 入基，我们已经证明了B=（ ）是新基，它与B只有一列不同。下面来给出枢轴运算公式：（说明以下公式对于计算机编程的实用性）,这样对于新基B， 是非基变量， 是基变量。记B的非基变量下标集合为J 它与J只有一个元不同(以 代替J中k就得J ) 由于 在基B下是基变量，因此在典则约数方程 中 的系数是单位向量 在第i 方程中 的系数为 .而在第i方程中为,为使 右端非负，即,这再次说明了极轴元 的选取必然是 中正元且行标l的选取由（ ）最小比值准则决定。否则做枢轴运算后基变量可能为负值，从而不能保证新的基本解就是基本可行解。,下面进一步导出迭代前后可行基B以及B对应各值之间迭代关系式。 是基B的单纯形表中各值。 用 表示基B的单纯形表中各值，则B的典则形式的m个等式约束应为： （） 将（）与（）（）对比可得去：,对于目标函数值：,再看判别数变换：因 其中,则上面变换公式（1）（2）（3）可以统一成下面的枢 轴运算公式：,现在我们将单纯形表中所有数据统一成 的符号。,记基变量取值 记判别数 记目标函数值,这个公式可采用下面的直观记忆方法：,注意到基变量所在各列是单位向量，除对应于该基变量的行的元素为1外，其余元素为0，那么计算将更简便，特别在计算机中往往可以不写基变量各列以节省内存。,那么当 的k不止一个时，怎样确定入基变量呢？理论上讲任选一个k就行了，但人们往往希望越大越好而目标函数增大值为： 因此我们希望选取 k 使（5）使右端极大，但是 :,综上所述，假定基B对应了非退化的基可行解，即 若存在 及 ，则可产生一个新的基本可行解使目标函数值增大。,这样寻找k需要进行很大量的额外计算是不值得的。通常用求 最小的办法来代替（5）式极大，即取,（前面公式）,经验表明，这样选取的 k 效果良好，能用较少的迭代次数求得最优解。 我们前面曾经指出单纯形算法是在极点上进行迭代的过程。下面将不加证明地给出一个定理说明对于非退化的基本可行解，迭代是沿着可行域的相邻极点进行迭代。 为此先给出相邻极点的概念。 定义3：设 是n维欧氏空间中多面凸集R的不同两点，Z是以 为端点的线段上的任一点，当它能表成R中异于Z的两点的出组合 即,则 都在以 为端点的线段上。那么称 是R的相邻极点。,我们再来综述一下前面所讲的内容： 如果有一个（LP）问题，且非退化，当能找到它的一个可行基B后，就一定可以解决这个（LP）问题了。因为可行基B必属于下述情况之一： （1）可行基B满足最优性判别条件，即判别数均非负， 则终止迭代。 （2）可行基的判别中有 ，且 则目标函数无上界，无最优解。,定理3：在单纯形迭代中，如果从极点 迭代到下极点 ，且 非退化，则 是相邻极点。,由于假定每次迭代得到的基本可行解都是非退化的，故每迭代一次目标函数值增大了（因为：基可行解非退化）则,（3）可行基B的判别数中有 且 中有正分量，这时由单纯形法可得出新的可行基 （B与 对应的基可行解是相邻极点）,因此，当我们得到了线性规划问题的一个可行基B之后，首先要检查是否属于情形（1）或（2）。是（1）则找到了一个最优解，是（2）断定此（LP）无最优解。这时问题都已解决了。如果是情形（3），作枢轴运算，再检查 B1是否情形（1），（2）。否则再作枢轴运算可行基B2 B3 . . . ， 等。,定理4：对于（SLP）如果从一个非退化的基可行解开始迭代，且假定每次迭代中出现的基可行解均是非退化的，则单纯形算法必在有限次迭带后终止于下列两种情形之一：或者判断线性规划目标函数无上界而无最优解；或者得到了一个基本最优解。,则 即目标函数值在相邻迭代点上严格增大）。 这样前面出现过的可行基后面将不再出现，而基的个数及基本可行解的个数是有限的，因而经过有限次迭代后必然得到一个可行基 满足（1）或（2），也就是说，经有限次迭代后就解决了这个线性规划问题。 这样我们就得出了单纯形法的收敛定理：,则 而,步骤1：（检查最优性条件是否成立）若判别数 则已求得最优解，其基变量取值为： 否则，转入步骤2。,下面我们再次归纳一下单纯形算法的步骤，并举例说明。,当找到（SLP）的一个可行基B及其对应的单纯形表后，可按下面步骤进行迭代：,步骤3：若 则终止迭代，目标函数无上界，无最优解。否则转入步骤4。,步骤2：求k使：,步骤4：求l使,计算出新的单纯形表，返回步骤1。,步骤5：以 为主元进行枢轴运算。由公式,例：用表格形式单纯形法求解,解：首先引进松弛变量,取初始可行基 得初始基可行解,初始单纯形表列如下：,解：首先将（LP）标准化引进松弛变量 剩余变量,例1：解下面的（LP）,再化为典范型时， 可作为变量，再在后面两个方程分 别加入人工变量 和 ，得出一个典范型如下：,(*) x1-2x2+x3+x4=11 -4x1+x2+2x3-x5+x6=3 -2x1+x3+x7=1 x1,x2,x70 如果选取x4 x6 x7 为基变量 x1 x2 x3 x5 为非基变量.则得基可行解x1=x2=x3=x5=0 x4=11 x6=3 x7=1 但它不是原来问题的基本可行解 .只有当x6和x7两人工变量取0值时 则（*）的基本可行解才成为原来的基本可行解. 使用人工变量的单纯形法中有两种解法可以尽快地把人工变量减小到零-大M法和两阶段单纯形法。 （）大M单纯形法：大M单纯形法要求将目标函数中的人工变量被指定一个很大的目标函数系数（人工变量与松弛剩余变量不同之处）,用大M法处理极小化时，当目标函数中人工变量具有一个很大系数M之后，在改进目标函数过程中，人工变量会迅速地减少，很快出基. 用大M法处理极大化问题时，则用一个绝对值很大的数-M作为人工变量的目标函数系数。同样也可使人工变量出基. 注意具体做时，M不必要用具体的数值，只要用M代表一个很大的正数就行了. 下面用大M法求解上述例中极大化问题. 目标函数为：max z=3x1-x2-x3-Mx6-Mx7 约束条件为上面的（*） 列出初始单纯形表如下，其余计算步骤与上节介绍的一致。 具体过程如下：,初始表,第一表,第二表,第三表,人工变量X6和X7分别在一次和二次选代之后迅速被其他变量取代.在计算时人工变量一旦出基，就可以不再考虑之.因此上面表中被框住部分完全可以省少操作.第三表中检验数已均非负，说明得到最优解X1=4 X2=1 X3=9Z最优解为Z=2,例2 .用人工变量大M法解下列线性规则； max z=(3 X1+ 2 X2) s.t. 2x1+x22 3x1+4x212 x10， x20,2x1+x2+x3=2 3x1+4x2-x4+x5=12 xi0 i=15,解: 将约束条件加上松弛变量X3.剩余变量x4和人工变量x5后则到一个具有基可行解的典则型方程如下:,相应的目标函数为 max z=(3x1+2x2)-Mx5 列出初始单纯形表，并进行迭代得；,这时的检验数已全部非负.得最优解x1=x3=x4=0 x2=2 x5=4 最优值Z=4-4M 此时的最优基中包含了人工变量.因此是不可行的.从而原问题无解.这类情况有时称为伪最优解（Pseudo Optimal Solution) （二） 两阶段单纯形法 仍以上面的例子来说明.在加入人工变量x6和x7以后.还可以将线性规划问题分成两个阶段求解 第一阶段的目的是为原问题求初始基可行解。第二阶段再在此基可行解基础上对原目标函数进行优化。 在第一阶段中先不考虑原来的目标函数.而是另外建立一数个人工目标函.因在例1中.第一阶段的目的是要使x6和x7为零.所以本例中目标函数及约束问题列为；,min=x6+x7 s.t. x1-2x2+x3+x4=11 -4x1+x2+2x3-x5+x6=3 -2x1+x3+x7=1 xi0 i=17,用单纯形法来解这个新的线形规划问题（也可以先化为极大化问题再解）（用MIN时注意判别数改变符号！）,上面最后一表中检验数均非正值。因此得到第一阶段的最优解x1=0 x2=1 x3=1 x4=12 x5=0 x6=0 x7=0.最小值=0.由于人工变量x6和x7均为0.所以这个最优解就是原来问题的初始基本可行解.有了这个初始基本可行解后.就可以进入第二阶段用单纯形法求远问题的最优解了。,第二阶段的表格如下:,此时检验数已全部非负.得到了最优解：x1=4,x2=1,x3=9, x4=x5=0此时最优解z=2.这与前面用大M法得出的结果是一样的. 这两种方法的第一目的都是为了尽快地使人工变量为零，从而得到原问题的初始基本可行解。由于大M法在计算机求解时出现非常大的数字.容易产生误差.这是大M法的缺点。因此后来又提出了两阶段法。 两阶段法的第一阶段的目的是找出原问题的一个初始基本可行解，或者明确缘问题无解。第二阶段的目的是找出原问题的最优解，或者明确有无解。,下面再利用二阶段法来求解前面的例2,第一阶段的问题可列为（因只有一个人工变量） min =x5 s.t. 2x1+x2+x3=2 3x1+4x2-x4+x5=12 xi0 （i=15),用单纯形法求解。得出第一阶段表格如下：（注意是极小化问题，判别数都不大于0时即为最优表！）,由此时检验数已全部非正，符合求最小解的要求。但注意到此时的基变量中有人工变量x5=4。没有达到人工变量为零的预期要求。因此在第一阶段找不到可行解.当然更谈不上第二阶段的求解了。 因而原问题无解.（与前面用大M法得出一致结论）。 下面我们从理论上证明上面介绍的第二阶段法的正确性. 设有一个 （SLP）:max z=cx s.t. Ax=b x0 称为原问题 或 第二问题,现构造一个与之相应的第一阶段问题与之对应。记为（ SLP ）* 如下： SLP* max =-(y1+y2+ym) s.t. a11x1+a12x2+a1nxn+y1=b1 am1x1+am2x2+amnx0+y m=b yi0 xj0 bi0（i=1m，j=1n),引进第一阶段的目的是为了求解原问题（ SLP ） 首先看看它们两者之间可行解、基本可行解之间的关系. 显然 ：若x是（SLP）的一个可行解。则（X，0）T 必是(SLP)*的一个可行解。若x 是(SLP)*的一个基本可行解，则(X 0)T 必是(SLP)*的一个基本可行解。反之若（X，Y）T 是(SLP)*的一个可行解，并且Y=0时，X必是（SLP）的一个可行解。若（X，Y）T 是(SLP)*的一个基本可行解，且Y=0时，X必是（SLP）的一个基本可行解. 现在(SLP)*有一个明显的单位矩阵可取作初始可行解.y1ym是基变量。对应的基本可行解为：x1=x n=0， y1=b1ym=bm现在找到了第一阶段的一个可行解。 若第一阶段是非退化的那么由单纯形法收敛性定理知：,经过有限次迭代必终止于下面两种情形之一：或者判断第一阶段有无界解。或者求得了一个基本最优解。 但第一阶段不可能有无界解，因为第一阶段的目标函数 =-（y1 +y m)0有上界，因此必有最优解。 设用单纯形法迭代得到第一阶段的最优解为（x1 y1)T 时。它与原问题的关系，有下述定理. 定理5 设（x*，y*)T 为第一阶段的基本最优解，则原问题有可行解的充分必要条件是 y* =0 。 证明： 充分性 若y*=0.则x*满足Ax* =b x* 0因而x*是原问题的可行解.由于（x*， y*)T 是第一阶段的基本可行解。所以它也是原问题的基本可行解. 必要性 设原问题有可行解。要证y*=0。 利用反证法。,若y*0不妨设y*的第t分量y*t 0因（x*，y*)T 是第一阶段最优解,代入其目标函数得 * =-(y*1+ y*2+ y*t+y*m)-y*t0 . 又假定了原问题有可行解，设为x，那么(x,0)T 是第一阶段的可行解，它对应的目标值记为则： =-（0+0+.+0）=0但此目标值不应超过最优值*. 即0=* 0矛盾， 故y*=0 。 定理证毕。,现在来进一步分析第一阶段结束时与原问题的关系。 设第一阶段的最优基B*对应基本最优解为 （x*，y*)T=(x*1 x*n , y*1 y*m )T 第一 若y*1 y*m全是非基变量。因为非基变量取值为零.则y* =0，那么x*就是原（SLP）的一个基本可行解。 这是一种重要情形.这样可求得原问题的一个初始基本可行解x*及初始基B=B*，于是就可以求解原问题了。,第二 某些yj是基变量，且y*0。则由定理5知原问题无可行解。 第三 某些yj是基变量，且y* =0。这时（x*，y*)T 是第一阶段的退化的基本可行解，由于已假定第一阶段的是非退化的，所以不会出现这种情况。 但在实际问题中，第三种情况中的退化情形是可能出现的。这时又如何得到原问题的基本可行解呢？ 设在第一阶段的的基本最优解中第t个基本变量是y的某分量.无妨设为yt(1tm)，且yt= b*t=0那么在第一阶段最优单纯形表的第t行。对应的约束方程为：,这时原问题中的约束方程Ax=b的第t个方程是多余的，但若假定原问题的约束方程系数阵A的秩是m,就不会有多余的方程（否则可以去掉这个方程）。因此这种情形可不考虑. 2） 若有kJ， .则以 为枢轴进行枢轴运算，旋出基变量yt，旋入基变量xk，从而把y中分量yt排出基外。若还有y中分量留在基内，则同样办法，可在有限步内将y的分量全部排出基外，于是就化为yj全为非基变量的情形了。,其中yt为基变量。J， J”分别为x，y中非基变量的下标集合。 1） 若所有jJ， ，即有：,（LP）中退化的基本可行解是指基可行解中有取零值的基变量的情形。 我们以前的计算都是假设在非退化的情形下进行的，并证明了单纯形法收敛性。但实际上，往往会出现退化的基可行解，这时单纯法会出现循环。 先看一个有退化基的例子，来说明一个基可能重复出现，从而出现循环迭代。,Beale 的例： max f=(3/4)x1-150x2+(1/50)x3-6x4 (1/4)x1-60x2-(1/25)x3+9x4+x5=0 (1/2)x1-90x2-(1/50)x3+x4+x6=0 x3+x7=1 xi0 i=17 利用前面的 单纯形法求解:,3.4 退化与克服循环的 方法,此处的l不唯一，若选 l 1则有下表:,此处的l也不唯一，若选l 1则可继续得出下表:,此处的l又不唯一，若选l 1则继续可得：,此最后一表与最开始一表 完全一致。 如果继续同样迭代下去，运算将会循环不止，造成循环的原因是迭代过程中=0目标函数值始终不变。 这是一个人造例子。实际中，退化的情形很多，但循环情形极少。但从数学理论的完整性考虑，研究避免发生循环的方法是必要的。下面介绍克服循环的-摄动法。,二 避免循环的摄动法 如果（SLP）有一个退化的基本可行解，即B0b0中有0分量。于是就不满足单纯形法迭代收敛定理的条件，不能保证有限次迭代内解决此问题。 上面的Beale 例即说明了此种情况。 摄动法的基本思想就是： 将向量b作一微小的变动，变为b（）。使得 B0-1b（）0。从而对于摄动问题B0对应了非退化的基本可行解。如果能进一步证明：在的某一取值范围内摄动问题是一个非退化的（LP），那么它满足单纯形法迭代收敛条件，经过有限次迭代就能解决此问题。如果摄动问题有最优解，再把b（）b，就得到原问题的最优解。 下面来具体构造摄动问题。,设B0是（SLP）的一个可行基，或者B0退化，或者在单纯形迭代时，由 l决定的出基变量标号jl时l不唯一。 引进摄动问题的目的就是为了在单纯形迭代中能确定唯一的l, 并能使原问题避免循环。 为方便起见，不妨假设（SLP）的基变量标号调换为1，2，m的顺序，即调换后的基变量为x1 ,x2，xm调换后的规划问题仍记为： （SLP） max f=cx s.t. Ax=b, x0 已知A的前m列组成基B0=（P1P2Pm），在单纯形迭代时确定不了唯一的l，或者B0是退化的可行基。,构造摄动问题: max f=cx s.t. Ax= b()， x0 其中b()=b+1p1+2 p2 + n pn =b+,或写成 因 ，则 又当0足够小时，总可以使,若 则任0均可，若 0则,（当 时 ） 于是有x i()0，(i=1m)，即 所以当正数足够小时，B。是摄动问题的非退化可行基。下面进一步证明当0足够小时，摄动问题是非退化的。,定理6 对摄动问题 max f=cx s.t. Ax=b()，x0, 存在00, 使得对任何满足 00, 此摄动问题是非退化的。,对这m个方程求根，每个方程最多有n个实根。 对每个基B，有m个这样的多项式方程，而在A中可以取作基矩阵的数目也是有限的，设为P个，于是多项式方程总个数为mp个。,其中J为非基变量下标集合。令xj=0(jJ)得基变量取值为,下面证明：存在0 0，对任意：00 ，(*)给出的基变量取值不为0。 因(*)式右端是系数不全为0的的n次多项式，令其为0,使所有这些多项式中任一个为等于0的的个数最多nmp 个，从而这些根中取正值的也只有有限个。 取一个0 0，使0比所有这些正根还要小。则当：00，任意：00，摄动问题任何一个基变量不可能为0。由于多项式是的连续函数，而区间 (0, 0 )又没有这些多项式的根， 故每一多项式在（0，0 ）内或者恒大于零，或者恒小于零，二者必居其一。,如果某一多项式在（0， 0 ）内恒大于零，则对于任意的，00 ，由（*）确定的对应此多项式的基变量也 恒大于零。 如果某基B的m个基变均取正值，那么当 （ 0 ， 0 ）时，B就是摄动问题的非退化可行基。 而摄动问题非退化可行基是存在的。（前面的叙述，对B0基）。 现在要证摄动问题在（0，0 ）内是非退化的，即只须证摄动问题的任一可行基B是非退化的。 因在（0， 0 ）内，摄动问题的基变量取值非零。,若B是摄动问题的可行基，则基变量取值非负。 故知基变量取值为正值。 即若B是摄动问题的可行基，则B一定是摄动问题的非退化可行基。 定理7：当0足够小， （1）若 是摄动问题的基可行解，令=0，则 是原问题的一个基可行解。 （2）若x*（）是摄动问题的基本最优解。则x*（0）也是原问题的基本最优解。 证明：（1）设X0（）是摄动问题的一个基可行解，对应基B。并设 的分量为 (i=1m),由（*）式知X0（）的基变量取值为：,上式中令=0，则X0（0）的基变量取值 ，(i=1m） 因此，要证（1）只须证 0，(=1m) （用反证法）若不然，存在 ，则对于充分小的0，必有：,（2）现在取充分小后，用单纯形法解摄动问题，在迭代 过程中得到一系列的基本可行解 因定理6已证明摄动问题是非退化的，则由单纯形法收敛定理知若摄动问题有最优解，必在有限步迭代得到基本最优解X*（），令=0，由上面（1）的结论知：相应得到一系列原问题的基可行解：,（这与前面一开始的证明方法一样可证），但这与 X0 （）是摄动问题的基可行解矛盾。因而问题得证。并且这两个问题的基本可行解X0（）与X0（0）对应同一可行基B。,下面证明： X* （0）是原问题的基本最优解。 因X*（） X* （0）对应同一个基B，判别数向量 与向量b, b(）无关，而由于摄动问题和原问题有相同的A，B，C，所以对于同一个基B，两者的判别数也相同，因此，如果X* （）是摄动问题的基本最优解，则X* （0）也是原问题的基本最优解。 因为摄动问题是非退化的（00）且有了一个可行基B0，因而可通过有限次单纯形法迭代，或求出基本最优解X* （）, 那么也求得了原问题的基本最优解X*（0），或判断摄动问题有无界解，则原问题也有无界解）。,求摄动问题时，不必先求出的范围只须让正充分小就可以了。用单纯形法求解摄动问题的过程基本上与原来的单纯形放一致。,