《第三章线性规划的单纯形算法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单纯形方法