运筹学—线性规划第3章02.ppt

《运筹学—线性规划第3章02.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、规则I若有几个判别数,则选取其中下标数小的标号作为k，（即选表上判别数小于0的最左边一个），即若k=min,则选为入基变量。四Bland的避免循环的方法1976，R.G.Bland提出并证明了一种新的方法，避免单纯形迭代出现循环。当时在国际上引起了很多人重视，并认为是线性规划的一项很好成果。在方法上，比前面的都要简单些，只须按下面规则选取入基和出基变量，就不会产生循环。定理8（Bland规则）对（SLP），在进行单纯形法迭代时，如果按照上面的规则Ⅰ和Ⅱ选取入基变量和出基变量，就不会出现循环。此定理的证明见管梅谷、郑汉鼎《线性规划》P69-72。注意，Bland方法理论上很

2、重要，但实际上迭代次数不一定比摄动法少。由于实际问题中出现循环可能性小，可在设计程序是安置一条打印目标函数值的命令，如果目标出数值长久不变，则表明出现循环，此时再采用一些简单补救措施就可以了，这样做程序简单，工作量也小。则选为出基变量。规则Ⅱ若有几个同时达到最小那么选取其中下标最小的基变量作为出基变量，即若原问题有一个退化可行基，基变量是退化基可行解（0，0，0，0，0，0，1），首先改变变量下标，使是基变量，得到问题的形式如下：现在我们用ε-摄动法求解Beale的例子。相应的摄动问题为：（ε>0充分小）ststmax怎样列单纯形表？是否与以前一样要列出的取值列？易见摄动

3、问题的约束条件Ax=b(ε）中右端的系数与左边系数相同，这是由b(ε）的构造决定的。当ε足够小时，退化问题有非退化初始可行基（P1，P2，P3）对应基可行解：其中的取值分别是上面约束等式右端项。没有必要！因为除去即常数项系数外，的系数与的系数相同，都在单纯形表上给出。这样，只须加一行顺序为分别与对应即可。（注XB处只列出的系数，XB的取值为对应的系数及行与该行中元素积之和。）这里，0次项：（如1次项比值相等，再比2次项，3次项……），ε>0足够小时，由单纯形法迭代公式知，应从下面两式中找θ，即：ε足够小，多项式取值主要取决于ε的较低次幂。取枢轴作枢轴运算，出基，入基，得下

4、表故此时，判别数全部非负，得到摄动问题的最优解：再按开始的方式，将变量下标还原，即得Beale问题的最优基可行解：其中基变量取值即为ε列的系数我们已经知道，某些线性规则问题不止一个最优解，而是某一个凸子集上都达到最优，即最优解的个数不唯一时，最优解的个数就有无穷多个。因此，要求出全部最优解是不可能，也是无意义的。但基本可行解个数是有限的，因而最优基本可行解个数也是有限的。这样，求出全部最优基本可行解是可能的。而在实际问题中，一个最优基本可行解就是一个实施方案，如果有若干个方案都能达到最优，便能为决策者提供多种选择方式，因而求出全部最优基本可行解是重要的。如何求出全部最优基

5、本可行解？3.6求全部最优基本可行解求全部最优基本解，要从最优单纯形表出发，若已得到一个最优基本可行解，由目标函数迭代公式：若θ=0,或=0,则迭代后目标函数值保持不变，我们正是利用这一性质来求出线性规则全部最优基本可行解的。如果即迭代后目标函数值非最优，这是我们不希望的迭代，不必进行。下面分几种情形讨论：1）若最优基本可行解非退化，且所有非基变量的判别数,则最优基本可行解是唯一的。如果进行迭代,因为非退化,则θ>0,又因此即表明目标值下降，因而不可能产生其他最优基本可行解，只可能有唯一最优基本可行解。2）若最优基本可行解非退化，且有非基变量的判别数,并存在就可将换作基变

6、量，求l使下式成立，并以作为出基变量。3若某个最优基本可行解是退化的，例如则可将任何满足的非基变量代替为基变量，因θ=0，所以无论是否为0，这样得到的仍是同一退化极点的不同表示。设当前最优基本可行解为这时，对应非基变量4若对某个非基变量这时，或者得到一个不同的最优基本可行解，或者得不到新的基本最优解，而只是同一个退化极点的不同表示而已。由上面这些说明，我们看到可以这样求出全部基本最优解：从最优单纯形表出发，构造一系列新表可，每个新表或者是由这个最优表旋入一个而得到：或者是将一个取零值的基变量旋出而得到。虽然有时得不到不同的最优解，但仍然把它写出来。因为在下一个步骤中，它可

7、能导出一个新的基本最优解。上述过程作完之后，在对新表重复这样的步骤，这时又可能得到一些新的基本最优解。其中有些是已经得到过的，就把它去掉。而对那些第一次得到的新表，再继续作下去，直到再不能得到新表为止。（这总可以在有限步内终止的，因为极点个数有限。）解：由表1看到，非基变量的判别数为0，故可以分别将换入基内，可得表3。另一方面，表1中是一个退化的最优基本可行解，基变量，因此可以将换入基代替，从而得表4。例：求出线性规划问题的全部最优解。设线性规划的最优单纯形表，如下表1表4与表1对应了同一个退化极点但对应不同可行基，即表4与表