LinearProgramming第三章线性规划的单纯形算法2章节幻灯片.pptVIP

规则I 若有几个判别数 , 则选取其中下标数小的标号作为k，（即选表上判别数小于0的最左边一个），即若k=min ,则选 为入基变量。 四 Bland的避免循环的方法 1976，R.G.Bland提出并证明了一种新的方法，避免单纯形迭代出现循环。当时在国际上引起了很多人重视，并认为是线性规划的一项很好成果。在方法上，比前面的都要简单些，只须按下面规则选取入基和出基变量，就不会产生循环 。 定理8 （Bland规则）对（SLP），在进行单纯形法迭代时，如果按照上面的规则Ⅰ和Ⅱ选取入基 变量和出基变量，就不会出现循环。 此定理的证明见管梅谷、郑汉鼎《线性规划》P69-72。 注意，Bland 方法理论上很重要，但实际上迭代次数不一定比摄动法少。由于实际问题中出现循环，可在设计程序是安置一条打印目标函数值的命令，如果目标出数值长久不变，则表明出现循环，此时再采用一些简单补救措施就可以了，这样做程序简单，工作量也小。 则选 为出基变量。 规则Ⅱ 若有几个 同时达到最小 那么选取其中下标最小的基变量作为出基变量，即若  原问题有一个退化可行基，基变量是 退化基可行解（0，0，0，0，0，0，1），首先改变 变量下标，使 是基变量，得到问题的形式如下： 现在我们用ε-摄动法求解Beale 的例子。 相应的摄动问题为：（ε0充分小） st st max 怎样列单纯形表？是否与以前一样要列出 的取值列？ 易见摄动问题的约束条件Ax=b(ε）中右端 的系数与左边 系数相同，这是由b(ε）的构造决定的。 当ε足够小时，退化问题有非退化初始可行基（P1，P2，P3）对应基可行解： 其中 的取值分别是上面约束等式右端项。 没有必要！ 因为除去 即常数项系数外 ， 的系数与 的 系数相同，都在单纯形表上给出。这样，只须加一行顺序 为 分别与 对应即可。 （注XB处只列出 的系数，XB的取值为对应的 系数及 行与该行中元素积之和。） 这里，0次项： （如1次项比值相等，再比 2次项，3次项……） ，ε0足够小时，由单纯形法迭 代公式知，应从下面两式中找θ，即： ε足够小，多项式取值主要取决于ε的较低次幂。 取枢轴 作枢轴运算， 出基， 入基，得下表 故 此时，判别数全部非负，得到摄动问题的最优解： 再按开始的方式，将变量下标还原，即得Beale问题的最优基可行解： 其中基变量取值即为ε列的系数 我们已经知道，某些线性规则问题不止一个最优解，而是某一个凸子集上都达到最优，即最优解的个数不唯一时，最优解的个数就有无穷多个。因此，要求出全部最优解是不可能，也是无意义的。但基本可行解个数是有限的，因而最优基本可行解个数也是有限的。这样，求出全部最优基本可行解是可能的。 而在实际问题中，一个最优基本可行解就是一个实施方案，如果有若干个方案都能达到最优，便能为决策者提供多种选择方式，因而求出全部最优基本可行解是重要的。 如何求出全部最优基本可行解？ 3.6 求全部最优基本可行解 求全部最优基本解，要从最优单纯形表出发，若已得到一个最优基本可行解，由目标函数迭代公式： 若θ=0,或 =0, 则迭代后目标函数值 保持不变，我们正是利用这一性质来求出线性规则全部最优基本可行解的。 如果 即迭代后目标函数值非最优，这是我们不希望的迭代，不必进行。 下面分几种情形讨论： 1）若最优基本可行解非退化，且所有非基变量的判别数 , 则最优基本可行解是唯一的。 如果进行迭代, 因为非退化,则θ0,又 因此 即表明目标值