《第三章线性规划的单纯形算法2》由会员分享，可在线阅读，更多相关《第三章线性规划的单纯形算法2（23页珍藏版）》请在金锄头文库上搜索。
1、 定理定理8 （Bland规则规则）对（SLP），在进行单纯形法迭代时，如果按照上面的规则和选取入基 变量和出基变量，就不会出现循环。 此定理的证明见管梅谷、郑汉鼎线性规划P69-72。注意注意，Bland 方法理论上很重要，但实际上迭代次数不一定比摄动法少。由于实际问题中出现循环，可在设计程序是安置一条打印目标函数值的命令，如果目标出数值长久不变，则表明出现循环，此时再采用一些简单补救措施就可以了，这样做程序简单，工作量也小。则选 为出基变量。规则规则 若有几个 同时达到最小那么选取其中下标最小的基变量作为出基变量，即若 原问题有一个退化可行基，基变量是 退化基可行解（0，0，0，0，0，0
2、，1），首先改变变量下标，使 是基变量，得到问题的形式如下：现在我们用-摄动法求解Beale 的例子。相应的摄动问题为：（0充分小）st st max 怎样列单纯形表怎样列单纯形表？是否与以前一样要列出 的取值列？ 易见摄动问题的约束条件Ax=b(）中右端 的系数与左边 系数相同，这是由b(）的构造决定的。 当足够小时，退化问题有非退化初始可行基（P1，P2，P3）对应基可行解： 其中 的取值分别是上面约束等式右端项。没有必要没有必要！ 因为除去 即常数项系数外 ， 的系数与 的系数相同，都在单纯形表上给出。这样，只须加一行顺序 为 分别与 对应即可。u（注XB处只列出 的系数，XB的取值为对
3、应的 系数及 行与该行中元素积之和。）这里，0次项： （如1次项比值相等，再比 2次项，3次项），0足够小时，由单纯形法迭代公式知，应从下面两式中找，即：足够小，多项式取值主要取决于的较低次幂。 取枢轴 作枢轴运算， 出基， 入基，得下表 故此时，判别数全部非负，得到摄动问题的最优解： 再按开始的方式，将变量下标还原，即得Beale问题的最优基可行解：其中基变量取值即为列的系数 我们已经知道，某些线性规则问题不止一个最优解，而是某一个凸子集上都达到最优，即最优解的个数不唯一时，最优解的个数就有无穷多个。因此，要求出全部最优解是不可能，也是无意义的。但基本可行解个数是有限的，因而最优基本可行解个
4、数也是有限的。这样，求出全部最优基本可行解是可能的。 而在实际问题中，一个最优基本可行解就是一个实施方案，如果有若干个方案都能达到最优，便能为决策者提供多种选择方式，因而求出全部最优基本可行解是重要的。 如何求出全部最优基本可行解？3.6 求全部最优基本可行解 求全部最优基本解，要从最优单纯形表出发，若已得到一个最优基本可行解，由目标函数迭代公式： 若=0,或 =0, 则迭代后目标函数值保持不变，我们正是利用这一性质来求出线性规则全部最优基本可行解的。 如果 即迭代后目标函数值非最优，这是我们不希望的迭代，不必进行。下面分几种情形讨论： 1）若最优基本可行解非退化，且所有非基变量的判别数 ,
5、则最优基本可行解是唯一的。 如果进行迭代, 因为非退化,则0,又 因此 即表明目标值下降，因而不可能产生其他最优基本可行解，只可能有唯一最优基本可行解。 2）若最优基本可行解非退化，且有非基变量 的判别数 , 并存在 就可将 换作基变量，求l使下式成立，并以 作为出基变量。 3 若某个最优基本可行解是退化的，例如 则可将任何满足 的非基变量 代替 为基变量 ，因=0，所以无论 是否为0，这样得到的仍是同一退化极点的不同表示。设当前最优基本可行解为这时，对应非基变量4 若对某个非基变量 这时，或者得到一个不同的最优基本可行解，或者得 不到新的基本最优解，而只是同一个退化极点的不同表示而已。 由上
6、面这些说明，我们看到可以这样求出全部基本最优解：从最优单纯形表出发，构造一系列新表可，每个新表或者是 由这个最优表旋入一个 而得到：或者是将一个取零值的基变量旋出而得到。 虽然有时得不到不同的最优解，但仍然把它写出来。因为在下一个步骤中，它可能导出一个新的基本最优解。 上述过程作完之后，在对新表重复这样的步骤，这时又可能得到一些新的基本最优解。其中有些是已经得到过的，就把它去掉。而对那些第一次得到的新表，再继续作下去，直到再不能得到新表为止。（这总可以在有限步内终止的，因为极点个数有限。） 解：由表1看到，非基变量 的判别数为0，故可以分别将 换入基内，可得表3。 另一方面，表1中是一个退化的
7、最优基本可行解，基变量 ，因此可以将 换入基代替 ，从而得表4。 例：求出线性规划问题的全部最优解。设线性规划的最优单纯形表，如下表1 表4与表1对应了同一个退化极点 但对应不同可行基，即表4与表1以不同基表示同一退化极点， 表4中， ，因而所得的是最优基本可行解，但非基变量X3的检验数 不符合最优判别定理。 现在再考虑表2、3、4。 表2中，非基变量的检验数 若 入基，则 出基，又回到了表1，因此去掉此种情形。若 入基，则得表5。 表2中的最优基本可行解是退化的，基 入基 出基得表6。u表4中，非基变量检验数 入基，则回到表1，表4中，非基变量检验数 若 入基，则 出基，仍得表6，不产生新表
8、，若 入基， 出基，仍得表7，因而表4不产生新表。u 表3中基变量的检验数 若 入基，又回到了表1，因此去掉此种情形。若 入基得表与表5同，不产生新表。u 表3中基变量 入基， 出基，得表7。 表5中，非基变量检验数 若 入基，则 出基，又回到表2，若 入基，则 出基，又回到表3，均不产生新表。但表5中，基变量 ，若 入基， 出基，则得表8。表6中，基变量 ，若 出基，则 入基，又得表2。表6中，非基变量检验数 若 入基，则 出基，仍得表4：若 入基，则 出基，又得表8，因此表6不产生新表。 下面再考虑表5、6、7： 这样便结束了求全部最优基本可行解的过程，共得四个基本最优解：u小结与复习提要：u1 如何建立线性规划的数学模型u2 怎样将一般线性规划问题标准化u3 线性规划的几何性质（基可行解对应极点，相邻极点搜索u4 线性规划的基本概念 （可行解域，基凸性，多面凸集，极点，极射问题）u5 线性规划的基本定理（极点 基可行解P40定理2P49无最优解判定定理可行解表示定理P51u6单纯形方法
