运筹学线性规划02PPT学习教案

1、会计学1 运筹学线性规划运筹学线性规划02 原问题有一个退化可行基，基变量是 退化基可行解（0，0，0，0，0，0，1），首先改变 变量下标，使 是基变量，得到问题的形式如下： 321 ,xxx 765 ,xxx 现在我们用-摄动法求解Beale 的例子。 第1页/共25页 7654 6-50/1150-4/3maxxxxx )71(0 1 0350/1902/1 0925/1604/1 63 76542 76541 jx xx xxxxx xxxxx j st )71(0 1 350/1 902/1350/1902/1 925/1604/1925/1604/1 63 63 76542 765

2、42 7654 76541 jx xx xxxxx xxxxx j st 7654 650/11504/3xxxxmax 第2页/共25页 怎样列单纯形表怎样列单纯形表？是否与以前一样要列出 的取值列？ B x 易见摄动问题的约束条件Ax=b(）中右端 的系数与左边 系数相同，这是由b(）的构造决定的。 当足够小时，退化问题有非退化初始可行基（P1，P2，P3）对应基可行解： 其中 的取值分别是上面约束等式右端项。 j j x )(),(),( 0 3 0 2 0 1 xxx j T xxxx)0 , 0 , 0 , 0),(),(),()( 0 3 0 2 0 1 0 没有必要没有必要！ 因

3、为除去 即常数项系数外 ， 的系数与 的 系数相同，都在单纯形表上给出。这样，只须加一行顺序 为 分别与 对应即可。 j 7321 ,7321 ,xxxx j x 0 第3页/共25页 1 2 3 4 5 6 7 X1X2X3X4X5X6X7 X1001001/4-60-1/259 X2000101/2-90-1/503 X3010010010 000-3/4150-1/500 CB 。 j u（注XB处只列出 的系数，XB的取值为对应的 系数及 行与该行中元素积之和。） 0 0 j 第4页/共25页 2/ 1 350/ 1902/ 1 4/ 1 925/ 1604/ 1 min 2/ 1 )

4、( 4/ 1 )( min 765427654 0 2 0 1 xx 这里，0次项： （如1次项比值相等，再比 2次项，3次项） 2/1 0 4/1 1 1 , 2/1 0 4/1 0 次项： 02/104/1 440min 2414 4 ， 这一列，？在，如何找klk jk ，0足够小时，由单纯形法迭 代公式知，应从下面两式中找，即： 足够小，多项式取值主要取决于的较低次幂。 第5页/共25页 1234567 X1X2X3X4X5X6X7 X1001-1/200-15-3/10015/2 X23/400201-180-1/256 X3010010010 03/20015-1/2021/2 X

5、103/1001-1/23/1000-15015/2 X43/4 1/25021/251-18006 X61/5010010010 03/21/20015021/2 j j CB。 取枢轴 作枢轴运算， 出基， 入基，得下表 , 02/1 24 2 x 4 x 20 2/1 )( 0 2 2 l x l 故 第6页/共25页 此时，判别数全部非负，得到摄动问题的最优解： T xxxx)()(),( * 7 * 2 * 1 * （）（ T x)0 , 0 ,100/3 , 0 , 1 , 0 ,25/1 ()0( * 再按开始的方式，将变量下标还原，即得Beale问题的最优基可行解： T xxx

6、x)0()0(),0()0(0 * 7 * 2 * 1 * = ，得令 T x) 0 , 1 , 0 ,25/ 1 , 0 , 0 ,100/3 () 0 ( * 其中基变量取值即为列的系数 第7页/共25页 我们已经知道，某些线性规则问题不止一个最优解，而是某一个凸子集上都达到最优，即最优解的个数不唯一时，最优解的个数就有无穷多个。因此，要求出全部最优解是不可能，也是无意义的。但基本可行解个数是有限的，因而最优基本可行解个数也是有限的。这样，求出全部最优基本可行解是可能的。 而在实际问题中，一个最优基本可行解就是一个实施方案，如果有若干个方案都能达到最优，便能为决策者提供多种选择方式，因而求

7、出全部最优基本可行解是重要的。 如何求出全部最优基本可行解？ 3.6 求全部最优基本可行解 第8页/共25页 求全部最优基本解，要从最优单纯形表出发，若已得到一个最优基本可行解，由目标函数迭代公式： k ff * , 若=0,或 =0, 则迭代后目标函数值 * , ff 与迭代前最优解 k 保持不变，我们正是利用这一性质来求出线性规则全部最优基本可行解的。 如果 即迭代后目标函数值非最优，这是我们不希望的迭代，不必进行。 *, :, 0, 0ff k 则 下面分几种情形讨论： 第9页/共25页 1）若最优基本可行解非退化，且所有非基变量的判别数 , 则最优基本可行解是唯一的。 0 j 如果进行

8、迭代, 因为非退化,则0,又 因此 即表明目标值下降，因而不可能产生其他最优基本可行解，只可能有唯一最优基本可行解。 0 k * fff k 2）若最优基本可行解非退化，且有非基变量 的判别数 , 并存在 就可将 换作基变量，求l使下式成立，并以 作为出基变量。 k x k x 0 k )1 (0mi ik lk l ik ik i mi l bb 0|min 1 l j x 第10页/共25页 k 0 i b 0 ik k x jk x )0(, * k Dxx则 设当前最优基本可行解为 0, 0 k kKk k CDOADDx且的极方向 这时，对应非基变量 0, 0 ikkk ix有但对所

9、有的有 4 若对某个非基变量 这时，或者得到一个不同的最优基本可行解，或者得 不到新的基本最优解，而只是同一个退化极点的不同表示而已。 第11页/共25页 kk x的非基变量0 虽然有时得不到不同的最优解，但仍然把它写出来。因为在下一个步骤中，它可能导出一个新的基本最优解。 上述过程作完之后，在对新表重复这样的步骤，这时又可能得到一些新的基本最优解。其中有些是已经得到过的，就把它去掉。而对那些第一次得到的新表，再继续作下去，直到再不能得到新表为止。（这总可以在有限步内终止的，因为极点个数有限。） 第12页/共25页 XBX1X2X3X4X5X6X7X8 X1210001012 X2301002

10、-310 X3000100200 X4100012202 f*=1900000109 0 36 75,x x 75,x x 0 3 x 6 x 3 x 例：求出线性规划问题的全部最优解。设线性规划的最优单纯形表，如下表1 第13页/共25页 表2XBX1X2X3X4X5X6X7X8 X13/2100-1/20-111 X22010-10-51-2 X3000100200 X51/20001/21101 表3f*=1900000109 X7210001012 X21-11001-30-2 X3000100200 X4100012202 表4f*=1900000109 X1210001012 X2

11、3013/202010 X60001/200100 X4100-112002 f*=1900-1/200009 第14页/共25页 表4与表1对应了同一个退化极点 但对应不同可行基，即表4与表1以不同基表示同一退化极点， 表4中， ，因而所得的是最优基本可行解，但非基变量X3的检验数 不符合最优判别定理。 T )0 , 0 , 0 , 1 , 0 , 3 , 2( 0 23 y 19 * f 3 x 现在再考虑表2、3、4。 表2中，非基变量的检验数 若 入基，则 出基，又回到了表1，因此去掉此种情形。若 入基，则得表5。 表2中的最优基本可行解是退化的，基 入基 出基得表6。 0, 0 74

12、 6 x 7 x 0 3 x 4 x 5 x 0 36 第15页/共25页 u表4中，非基变量检验数 入基，则回到表1，表4中，非基变量检验数 若 入基，则 出基，仍得表6，不产生新表，若 入基， 出基，仍得表7，因而表4不产生新表。 33 , 0 x 0, 0 75 5 x 4 x 7 x 1 x u 表3中基变量的检验数 若 入基，又回到了表1，因此去掉此种情形。若 入基得表与表5同，不产生新表。 0, 0 51 1 x 5 x u 表3中基变量 入基， 出基，得表7。 63 , 0 xx 3 x 第16页/共25页 表5 XBX1X2X3X4X5 X6 X7X8 X7 3/2100-1/

13、20-111 X2 1/2-1101/20-40-3 X3 000100200 X5 1/2001/21101 表6f*=1900000109 X1 3/2101/2-1/20011 X2 2015/2-1001-2 X6 0001/200100 X5 1/200-1/21/21001 表7f*=1900-1/200009 X7 210001012 X2 1-113/20100-2 X6 0001/200100 X4 100-112002 f*=1900-1/200009 第17页/共25页 表8XBX1X2X3X4X5X6X7X8 X73/2101/2-1/20011 X21/2-112-1

14、/2000-3 X60001/200100 X51/200-1/21/21001 f*=1900-1/200009 第18页/共25页 表5中，非基变量检验数 若 入基，则 出基，又回到表2，若 入基，则 出基，又回到表3，均不产生新表。但表5中，基变量 ，若 入基， 出基，则得表8。表6中，基变量 ，若 出基，则 入基，又得表2。表6中，非基变量检验数 若 入基，则 出基，仍得表4：若 入基，则 出基，又得表8，因此表6不产生新表。 0, 0 41 1 x 7 x 4 x 5 x 0 3 x 3 x0 6 x 6 x 3 x 0, 0 74 4 x 5 x 7 x 1 x 6 x 下面再考虑表5、6、7： 第19页/共25页 T T T T ），的：（表 ），