线性规划的单纯形算法PPT学习教案

1、会计学1线性规划的单纯形算法线性规划的单纯形算法 原问题有一个退化可行基，基变量是 退化基可行解（0，0，0，0，0，0，1），首先改变变量下标，使 是基变量，得到问题的形式如下：321,xxx765,xxx现在我们用-摄动法求解Beale 的例子。第1页/共23页76546-50/1150-4/3maxxxxx)71(010350/1902/10925/1604/1637654276541jxxxxxxxxxxxxxjst )71(01350/1 902/1350/1902/1925/1604/1925/1604/163637654276542765476541jxxxxxxxxxxxxxj

2、st 7654650/11504/3xxxxmax第2页/共23页 怎样列单纯形表怎样列单纯形表？是否与以前一样要列出 的取值列？Bx 易见摄动问题的约束条件Ax=b(）中右端 的系数与左边 系数相同，这是由b(）的构造决定的。 当足够小时，退化问题有非退化初始可行基（P1，P2，P3）对应基可行解： 其中 的取值分别是上面约束等式右端项。jjx)(),(),(030201xxxjTxxxx)0 , 0 , 0 , 0),(),(),()(0302010没有必要没有必要！ 因为除去 即常数项系数外 ， 的系数与 的系数相同，都在单纯形表上给出。这样，只须加一行顺序 为 分别与 对应即可。j73

3、21,7321,xxxxjx0第3页/共23页1234567X1X2X3X4X5X6X7X1001001/4-60-1/259X2000101/2-90-1/503X3010010010000-3/4150-1/500CB。ju（注XB处只列出 的系数，XB的取值为对应的 系数及 行与该行中元素积之和。）00j第4页/共23页2/ 1350/ 1902/ 14/ 1925/ 1604/ 1min2/ 1)(4/ 1)(min7654276540201xx这里，0次项： （如1次项比值相等，再比 2次项，3次项）2/104/111 ,2/104/10次项： 02/104/1440min24144

4、，这一列，？在，如何找klkjk，0足够小时，由单纯形法迭代公式知，应从下面两式中找，即：足够小，多项式取值主要取决于的较低次幂。第5页/共23页1234567X1X2X3X4X5X6X7X1001-1/200-15-3/10015/2X23/400201-180-1/256X301001001003/20015-1/2021/2X103/1001-1/23/1000-15015/2X43/4 1/25021/251-18006X61/501001001003/21/20015021/2jjCB。 取枢轴 作枢轴运算， 出基， 入基，得下表, 02/1242x4x202/1)(022lxl 故

5、第6页/共23页此时，判别数全部非负，得到摄动问题的最优解：Txxxx)()(),(*7*2*1*（）（Tx)0 , 0 ,100/3 , 0 , 1 , 0 ,25/1 ()0(* 再按开始的方式，将变量下标还原，即得Beale问题的最优基可行解：Txxxx)0()0(),0()0(0*7*2*1*= ，得令Tx) 0 , 1 , 0 ,25/ 1 , 0 , 0 ,100/3 () 0 (*其中基变量取值即为列的系数第7页/共23页 我们已经知道，某些线性规则问题不止一个最优解，而是某一个凸子集上都达到最优，即最优解的个数不唯一时，最优解的个数就有无穷多个。因此，要求出全部最优解是不可能，

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

7、，这是我们不希望的迭代，不必进行。*,:, 0, 0ffk则下面分几种情形讨论：第9页/共23页 1）若最优基本可行解非退化，且所有非基变量的判别数 , 则最优基本可行解是唯一的。0j 如果进行迭代, 因为非退化,则0,又 因此 即表明目标值下降，因而不可能产生其他最优基本可行解，只可能有唯一最优基本可行解。 0k*fffk 2）若最优基本可行解非退化，且有非基变量 的判别数 , 并存在 就可将 换作基变量，求l使下式成立，并以 作为出基变量。kxkx0k)1 (0miiklklikikimilbb0|min1ljx第10页/共23页k0ib0ikkxjkx)0(,*kDxx则设当前最优基本可

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

9、3页XBX1X2X3X4X5X6X7X8X1210001012X2301002-310X3000100200X4100012202f*=190000010903675,xx75,xx03x6x3x 例：求出线性规划问题的全部最优解。设线性规划的最优单纯形表，如下表1第13页/共23页表2XBX1X2X3X4X5X6X7X8X13/2100-1/20-111X22010-10-51-2X3000100200X51/20001/21101表3f*=1900000109X7210001012X21-11001-30-2X3000100200X4100012202表4f*=1900000109X121

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

11、4x5x036第15页/共23页u表4中，非基变量检验数 入基，则回到表1，表4中，非基变量检验数 若 入基，则 出基，仍得表6，不产生新表，若 入基， 出基，仍得表7，因而表4不产生新表。33, 0 x0, 0755x4x7x1xu 表3中基变量的检验数 若 入基，又回到了表1，因此去掉此种情形。若 入基得表与表5同，不产生新表。0, 0511x5xu 表3中基变量 入基， 出基，得表7。63, 0 xx 3x第16页/共23页表5XBX1X2X3X4X5X6X7X8X73/2100-1/20-111X21/2-1101/20-40-3X3000100200X51/2001/21101表6f

12、*=1900000109X13/2101/2-1/20011X22015/2-1001-2X60001/200100X51/200-1/21/21001表7f*=1900-1/200009X7210001012X21-113/20100-2X60001/200100X4100-112002f*=1900-1/200009第17页/共23页表8XBX1X2X3X4X5X6X7X8X73/2101/2-1/20011X21/2-112-1/2000-3X60001/200100X51/200-1/21/21001f*=1900-1/200009第18页/共23页 表5中，非基变量检验数 若 入基，则 出基，又回到表2，若 入基，则 出基，又回到表3，均不产生新表。但表5中，基变量 ，若 入基， 出基，则得表8。表6中，基变量 ，若 出基，则 入基，又得表2。表6中，非基变量检验数 若 入基，则 出基，仍得表4：若 入基，则 出基，又得表8，因此表6不产生新表。 0, 0411x7x4x5x03x3x06x6x3x0, 0744x5x7x1x6x下面再