运筹学线性规划02资料讲解.ppt

《运筹学线性规划02资料讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学线性规划02相应的摄动问题为：（ε>0充分小）ststmax怎样列单纯形表？是否与以前一样要列出的取值列？易见摄动问题的约束条件Ax=b(ε）中右端的系数与左边系数相同，这是由b(ε）的构造决定的。当ε足够小时，退化问题有非退化初始可行基（P1，P2，P3）对应基可行解：其中的取值分别是上面约束等式右端项。没有必要！因为除去即常数项系数外，的系数与的系数相同，都在单纯形表上给出。这样，只须加一行顺序为分别与对应即可。（注XB处只列出的系数，XB的取值为对应的系数及行与该行中元素积之和。）这里，0次项：（如

2、1次项比值相等，再比2次项，3次项……），ε>0足够小时，由单纯形法迭代公式知，应从下面两式中找θ，即：ε足够小，多项式取值主要取决于ε的较低次幂。取枢轴作枢轴运算，出基，入基，得下表故此时，判别数全部非负，得到摄动问题的最优解：再按开始的方式，将变量下标还原，即得Beale问题的最优基可行解：其中基变量取值即为ε列的系数我们已经知道，某些线性规则问题不止一个最优解，而是某一个凸子集上都达到最优，即最优解的个数不唯一时，最优解的个数就有无穷多个。因此，要求出全部最优解是不可能，也是无意义的。但基本可行解个数是有

3、限的，因而最优基本可行解个数也是有限的。这样，求出全部最优基本可行解是可能的。而在实际问题中，一个最优基本可行解就是一个实施方案，如果有若干个方案都能达到最优，便能为决策者提供多种选择方式，因而求出全部最优基本可行解是重要的。如何求出全部最优基本可行解？3.6求全部最优基本可行解求全部最优基本解，要从最优单纯形表出发，若已得到一个最优基本可行解，由目标函数迭代公式：若θ=0,或=0,则迭代后目标函数值保持不变，我们正是利用这一性质来求出线性规则全部最优基本可行解的。如果即迭代后目标函数值非最优，这是我们不希望的

4、迭代，不必进行。下面分几种情形讨论：1）若最优基本可行解非退化，且所有非基变量的判别数,则最优基本可行解是唯一的。如果进行迭代,因为非退化,则θ>0,又因此即表明目标值下降，因而不可能产生其他最优基本可行解，只可能有唯一最优基本可行解。2）若最优基本可行解非退化，且有非基变量的判别数,并存在就可将换作基变量，求l使下式成立，并以作为出基变量。3若某个最优基本可行解是退化的，例如则可将任何满足的非基变量代替为基变量，因θ=0，所以无论是否为0，这样得到的仍是同一退化极点的不同表示。设当前最优基本可行解为这时，对应

5、非基变量4若对某个非基变量这时，或者得到一个不同的最优基本可行解，或者得不到新的基本最优解，而只是同一个退化极点的不同表示而已。由上面这些说明，我们看到可以这样求出全部基本最优解：从最优单纯形表出发，构造一系列新表可，每个新表或者是由这个最优表旋入一个而得到：或者是将一个取零值的基变量旋出而得到。虽然有时得不到不同的最优解，但仍然把它写出来。因为在下一个步骤中，它可能导出一个新的基本最优解。上述过程作完之后，在对新表重复这样的步骤，这时又可能得到一些新的基本最优解。其中有些是已经得到过的，就把它去掉。而对那些第

6、一次得到的新表，再继续作下去，直到再不能得到新表为止。（这总可以在有限步内终止的，因为极点个数有限。）解：由表1看到，非基变量的判别数为0，故可以分别将换入基内，可得表3。另一方面，表1中是一个退化的最优基本可行解，基变量，因此可以将换入基代替，从而得表4。例：求出线性规划问题的全部最优解。设线性规划的最优单纯形表，如下表1表4与表1对应了同一个退化极点但对应不同可行基，即表4与表1以不同基表示同一退化极点，表4中，，因而所得的是最优基本可行解，但非基变量X3的检验数不符合最优判别定理。现在再考虑表2、3、4。

7、表2中，非基变量的检验数若入基，则出基，又回到了表1，因此去掉此种情形。若入基，则得表5。表2中的最优基本可行解是退化的，基入基出基得表6。表4中，非基变量检验数入基，则回到表1，表4中，非基变量检验数若入基，则出基，仍得表6，不产生新表，若入基，出基，仍得表7，因而表4不产生新表。表3中基变量的检验数若入基，又回到了表1，因此去掉此种情形。若入基得表与表5同，不产生新表。表3中基变量入基，出基，得表7。表5中，非基变量检验数若入基，则出基，又回到表2，若入基，则出基，又回到表3，均不产生新表。但表5中，基变量

8、，若入基，出基，则得表8。表6中，基变量，若出基，则入基，又得表2。表6中，非基变量检验数若入基，则出基，仍得表4：若入基，则出基，又得表8，因此表6不产生新表。下面再考虑表5、6、7：这样便结束了求全部最优基本可行解的过程，共得四个基本最优解：小结与复习提要：1如何建立线性规划的数学模型2怎样将一般线性规划问题标准化3线性规划的几何性质（基可行解对应极点，相邻极点搜索4线性规划的基本