《第十三章 线性规划的单纯形算法.doc》由会员分享，可在线阅读，更多相关《第十三章 线性规划的单纯形算法.doc（37页珍藏版）》请在金锄头文库上搜索。
1、第十三章 单纯形法13.1 单纯形法原理求解线性规划的单纯形方法（Simplex Method）是美国GDDantzig在1947年提出来的，是一种有效的实用算法。单纯形法是根据线性规划的基本原理，在基可行解上进行迭代的一种算法。此方法的特点是：将线性规划化为标准形，从一个初始基可行解开始迭代，使之改进得到另一个基可行解。每迭代一次，目标函数值绝不会变小（对 max 问题），如果非退化，目标函数值就严格增大。若有最优解，经有限次迭代就得到基本最优解。标准形式线性规划问题求解的主要途径是通过枢轴运算把约束方程组变为典范型来进行的。这个过程实质上就是古典的高斯-约当消去法求解线性规划的过程。 下列
2、运算可以将一组线性方程变换为另一组等价的线性方程。将一个方程乘上一个常数k（k0）将方程用替换这样的运算称为线性方程组的初等变换，或称为基本行运算。下面分别说明枢轴运算（Pivot Operation）和典范型（Canonical form）13.1.1 枢轴运算枢轴运算就是通过一系列的基本行运算，使某一选定的变量在方程组的某一方程中系数是1，而这个变量在其他方程中的系数均为0.具体步骤是：在方程Er的s列中选取arsxs作为枢轴元素，条件是枢轴元素所在的行称为枢轴行，枢轴元素所在的列称为枢轴列。将方程Er除以 ，使枢轴元素系数为1。对方程以外的方程，用来代替 。例13.1.1：在下列方程组中
3、对变量进行枢轴运算：解： 选中2,为枢轴项将除以2化为：对进行基本运算：即以代替 得： 对进行基本运算：即以代替得：13.1.2 典范型线性方程组对n个变量m个方程的线性方程组可以通过对各个基变量逐一进行枢轴运算，将这m 个基变量的系数距阵变换成m m单位阵。这样的等价线性方程组就是典范型线性方程组。这样就可以直接求出一个基本解：如果常数项均非负，则得到的就是基本可行解。用矩阵符号表示就是：约束方程为： 变量分成基变量和非基变量两部分,系数距阵中相应分成B和N两块。即A=（B;N）则约束方程组可以写成：左乘以得： 即 当非基变量取0时，则基变量的解为 由于基本解最多有个，因而基可行解也不超过个
4、。如果全部的基可行解找出来了，就有可能求出最优基本解。但这样做是不能实现的。单纯形法（Simplex Method）就是沿一个初始基可行解出发，找出下一个更优的基可行解，而不找所有的基可行解。13.1.3 单纯形法的一般步骤 如果线性规划问题存在可行解，就可以找出一个基可行解，作为初始可行解。 为寻找基可行解，约束方程组以典范型方程组表示。 如果线性规划问题不存在可行解（约束条件有矛盾）则由找基可行解的过程可以得知问题无解。 以中找到的基可行解为起点，找出具有较佳目标值的另一基可行解。这一步骤称为迭代。 重复。直到目标函数再也不能改善，就得到问题最优解。 若问题的最优解是无界的，在迭代过程中就
5、可以知道问题有无穷解，终止迭代。例13.1.2： 求解 s.t 解：这是一个标准形线性规划问题，可以化为等价的典范型方程组：令，由上述典范型方程组直接得到一个基本解。显然这个基本解是可行解。相应目标函数值为现在要判断一下这个目标函数的值是否能改进，故换基变量就可能获得另一个基本可行解和相应的目标函数值。这样可用或来取代或成为基变量，因此目前的基本可行解有许多相邻的基本可行解。单纯形法就是在得到一个基本可行解后，在它的相邻基可行解中选取能使目标函数值最大程度改进的基本可行解。选取的原则是看哪一个非基变量改为基变量后能够使目标函数有更多的改进。具体地，可以在满足方程组的情况下，分别将各非基变量增加
6、一个单位。比较目标值由此发生的变化，从而选取能使目标函数值有最大增加的非基变量作为新的基变量。相应的目标值为：现在考虑非基变量，假定 增加一个单位，而其余的非基变量暂不考虑，仍为0。则约束方程可表示为：由第一个方程可见，由01，则由108。由第二个方程可见，由01，则由63。因此在满足上述方程组的条件下，增加1得到新可行解为：相应的目标值为： 所以 x3 增加1个单位，目标函数z的变化值为： z的旧值 - z的新值=22-（25）= -3称这个值为非基变量x3 的检验值（判别数）。因为可以用它来判别把x3 改为基变量后，能否改进目标值。这个检验数的绝对值有时也称为相对收益系数。由于检验数为负，
7、增加x3可以增加目标函数值。这证明目前的基可行解不是最优解，如将x3改为基变量就可以改进目标值。类似的可以算 4, 的检验数。比较所得到的几个检验数，决定把哪个非基变量换为基变量对目标函数的改进有利。检验数也可以用消去目标函数z中x1, x2的代入法来得到。将代入目标函数 的：由此可知当取x1和x2为基变量时， x3, x4, x5的检验数分别为-3，0和-2。目标值为22。x3, x4或x5每增加一个单位，z的值就相应增加3，0，个单位，所以把x3作为新基变量对改进目标函数最有利。 现在的问题是x3增加多少仍能满足约束条件，仍然以x4, x5 作非基变量。这时约束条件为：从第一个方程看， 最
8、多增到，若再大，成为负值。从第一个方程看，最多增到，若再大，成为负值。因此为保证最大增加值由这两个值中较小的一个来决定。即：当由02后，新的目标值为z=28 。这个目标值的改进是通过将非基变量 改为基变量，而基变量 改为非基变量得到的。 新引进的非基变量称为进基变量。换出的基变量则称为出基变量。选择进基变量的原则一般可以按负检验数绝对值大的先进基。选择出基变量的原则是最小比值原则。一般先决定进基变量，再决定出基变量。当前得到的基可行解是否已最优还要重复上述算法，重新计算在目前的基可行解中所有非基变量的检验数。如果检验数中至少有一个负数，那么就可以得到另一个相邻基本可行解能使目标函数值进一步有所
9、改进。重复这一过程，直到所有检验数都不为负值。则此时的基可行解就是最优解。用 来表示非基变量的检验数，以表示检验数组成的向量。注意一般在线性规划中，检验数取下面形式：13.1.4 判别数最优判别定理设是（SLP）的一个基变量，对应C中的系数构成m维向量 定义13.1.1：对于基B，称为基B的判别数。判别数也可以用向量及距阵表示。因为 从而 若令 则下面我们来用表格形式说明如何计算判别数。 作形如下面的表格。表13.1.1求 与 的内积。即上表中箭头所示两列对应元素乘积相加得：把与 下面的数 相减得： 由于 是基变量，因而对于基变量的判别数即基变量对应判别数等于0。因而只需计算非基变量的n-m个
10、判别数就可以了。n个判别数组成一个n维向量也可以用矩阵向量形式表出：下面导出矩阵形式的最优判别定理。为此先定义基B单纯形乘子。定义13.1.2 称为基B的单纯形乘子，记为可知单纯形乘子是一m维向量。记为定理13.1.1：设B是（SLP）的一个基，若满足且CBB-1A-C =0, 则对应基B的基可行解就是最优解。（称为基本最优解，基B称为最优基）证明： 因。表明基变量取非负值。则基B对应的基本解为基本可行解。记为，其目标值记为，又设是（SLP）的任意可行解，即 则目标值 要证是基本最优解，只须证明 。用基B的单纯形乘子乘两边得：此式与相减得： 根据定理条件 CBB-1A-C =0及x=0故对（C
11、BB-1A-C ）=0因此 对任意 ，= f * , 因此，是最优基本解。13.2 表格单纯形方法我们先举个实例说明怎样用表格形式单纯形法解线性规划问题。例13.2.1：解： 第一步，将（LP）问题化为（SLP）问题。第二步，作下面形式的单纯形表表13.2.1第三步 第四步 第五步 选取中最小的一个对应的变量作为入基变量。第六步，对选定的入基变量 xj ，考虑取 对应的变量 x2作为出基变量.第七步，这样得到一组新基x1, x 3,对应的单纯形表如下表13.2.2基变量CBXBx1x2x3x4x5121176x1161-2/30-14./3.x311201/3111/3z131110-5z=2
12、80103-1x569/23/4-1/20-3/41x3111/2-1/41/215/40z7/45/21137/46z=32.53/41/209/40反复进行上述步骤，直到各检验数均非负值，即可得到基本最优解，上面得到原问题最优解为：由上例我们可以归纳出单纯形算法的步骤如下：1） 用标准形式表示问题2） 从含有初始基可行解的典范型方程组开始建立初始单纯形表示(注:对不易找到初始基的问题,可专门讨论)。3） 应用内积规则求检验数 （每迭代一次要计算一次）4） 在某次迭代中如果所有j均非负值，则原基可行解即为最优解，算法终止。 5） 如有j为负值，选取j绝对值最大的一列为枢轴列，使这一列对应的变
13、量为进基变量。6） 应用最小比值规则,决定枢轴行,使这一行的基变量出基。最小比值原则就是指,若进基变量为xr .r列的系数为7）进行枢轴运算, 获得新的单纯行表。8）返回第三步。以上算法是针对极大化问题而言的,如在化标准型时不将极小化问题转化为极大化问题， 同样可以利用上述单纯行表形式求解，只要将检验数的判别准则改变一下符号就可以。例13.2.2.求解线性规划解: 利用单纯形表迭代得表13.2.3基变量CbXbx1x2x3x4321-2x1341-204x31501125/1z3-51140-7016x13141028x2250112z3282800730例13.2.3解: 对后面两个约束方程引进松弛变量x5, x6化为：列出初始单纯形表并进行迭代得：表13.2.4x1-161131006x5030-211103x6040-16-101z-1-1-3-1000-3-2-400x1-131320-101x4330-21110x6070-370111z-1-91
