单纯形方法ppt课件

《单纯形方法ppt课件》由会员分享，可在线阅读，更多相关《单纯形方法ppt课件（22页珍藏版）》请在装配图网上搜索。

1、2.3 单纯形方法单纯形方法典式典式根本定理根本定理单纯形方法单纯形方法单纯形表单纯形方法的实现单纯形表单纯形方法的实现1947年由年由Dantzig提出，被称为提出，被称为20世纪最好的十个算法之一，世纪最好的十个算法之一，是迄今为止处理线性规划问题的最成熟的方法。是迄今为止处理线性规划问题的最成熟的方法。定理定理2.2.6 一个规范的一个规范的LP问题假设有有限的最优值，问题假设有有限的最优值，那么一定存在一个根本可行解是最优解。那么一定存在一个根本可行解是最优解。主要思想：主要思想：1先找一个根本可行解先找一个根本可行解2判别能否为最优解判别能否为最优解3是，是，stop；不是，再找一个

2、更好的；不是，再找一个更好的已有初始解已有初始解min.0 Tzc xs tAxbx ,()|,0 nnmm nnxRcRbRARr AmnDxRAxb x 其其中中线性规划的规范方式：线性规划的规范方式：=m in.0 Tzcxs tAxbx min,.,0 BTTBNNBNBNxzccxxs tB Nbxxx 1 典式典式(定义定义)m in.,0 TTBBNNBNBNzcxcxs tBxNxbxx =1 典式定义典式定义0 011 000 10=m in.,0 TTBBNNBNBNzcxcxs tBxNxbxx 11m in.,0 TTBBNNBNBNzcxcxs tIxBNxBbxx

3、11()TTTBBNNzcBbcBNcx 0 0 01 典式定义典式定义1111m in().,0 TTTBBNNBNBNzc Bbc BNcxs tIxBNxBbxx 典式的特点：典式的特点：1 1、约束条件中含有一个单位矩阵；、约束条件中含有一个单位矩阵；2 2、目的函数中不含基变量。、目的函数中不含基变量。0 000 011 000 10=1 典式定义典式定义1111min().,0 TTTBBNNBNBNzc B bc B Ncxs tIxB NxB bxx 0 000 011 000 10=1 典式例典式例1231231425m in 23 s.t.28 416 412 0(1,2,

4、3,4,5)jzxxxxxxxxxxxj ,213543AANIAAAB TNTBxxxxxxx,21543 412416282514213xxxxxxx )5,4,3,2,1(0 12 4 16 4 8 2 s.t.538 min524132121jxxxxxxxxxxzj12(,)0,0,0,8,16,12TNTxxxx 令令得得 基基 本本 可可 行行 解解1 典式定义典式定义问题：如何判别一个根本可行解能否为最优解呢？问题：如何判别一个根本可行解能否为最优解呢？01min s.t.I 0TBNzzxxB Nxbx )5,4,3,2,1(0 12 4 16 4 8 2 s.t.538 m

5、in524132121jxxxxxxxxxxzj典那么方式的典那么方式的LP问题中，目的函数中的变量系数的符号，问题中，目的函数中的变量系数的符号，对于判别某一个根本可行解是不是最优解非常重要。对于判别某一个根本可行解是不是最优解非常重要。本例中本例中 是什么？是什么？典那么方式的典那么方式的LP问题中，目的函数系数向量的负向量。问题中，目的函数系数向量的负向量。称为检验数向量称为检验数向量.2 根本定理根本定理定理定理2.3.1 为为原原问问题题的的最最优优解解。，则则中中如如果果xxzzT00 例如：例如：)5,4,3,2,1(0 12 4 16 4 8 2 s.t.538 min5241

6、32121jxxxxxxxxxxzjT)12,16,8,0,0(xT)0,0,0,5,3(2 根本定理根本定理121231425min 835 s.t.2 8 4 16 4 12 0(1,2,3,4,5)jzxxxxxxxxxxj 例如：例如：Tx)12,16,8,0,0(010(m1)0,TkkkzzxknAB A 如如果果中中的的向向量量 中中，存存在在某某分分量量，而而向向量量定理定理2.3.2那么原问题无界。那么原问题无界。T)0,0,0,5,3(2 根本定理根本定理 )5,4,3,2,1(0 12 4 16 4 8 2 s.t.538 min524132121jxxxxxxxxxxz

7、j例如：例如：Tx)12,16,8,0,0(00.TkkTTxzzxAxc xc x 于于非非退退化化的的基基本本可可行行解解，若若式式中中的的向向量量有有，而而其其相相的的向向量量至至少少有有一一正正分分量量，能能找找到到一一新新的的基基本本可可行行解解，使使定理定理2.3.3对对应应那那么么T)0,0,0,5,3(2 根本定理根本定理定理定理2.3.4 对于任何非退化的线性规划问题，从任何根对于任何非退化的线性规划问题，从任何根本可行解开场，经过有限多次迭代，或者得到一个根本本可行解开场，经过有限多次迭代，或者得到一个根本可行的最优解，或者作出该线性规划问题无界的判别。可行的最优解，或者作

8、出该线性规划问题无界的判别。3 单纯形方法单纯形方法Step 1 Step 1 将线性规划问题化成典式将线性规划问题化成典式,求出各个非基变量的检验数。求出各个非基变量的检验数。Step 2 Step 2 判别一切非基变量的检验数能否非正判别一切非基变量的检验数能否非正,假设是假设是,那么终了；那么终了；否那么转否那么转step 3step 3。Step 3 Step 3 选取一个检验数大于零的非基变量为进基变量；选取一个检验数大于零的非基变量为进基变量；Step 4 Step 4 假设进基变量所对应的约束条件系数全为非正数假设进基变量所对应的约束条件系数全为非正数,那么原那么原问题无界问题无

9、界,终了；否那么终了；否那么,按最小比值原那么确定出基变量；按最小比值原那么确定出基变量；Step 5 Step 5 进展迭代进展迭代(用方程组的初等行变换法确定新的基对应的典用方程组的初等行变换法确定新的基对应的典式及检验数式及检验数),),转转step 2step 2。4 单纯形表单纯形表例例1 求解求解LP问题问题23123234235min2.223120,1,2,3,4,5jzxxs txxxxxxxxxxj Z 0 1 -2 0 0 0 x1 x4 x5 1 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1 2 Z 0 1 -2 0 0 0 x1 x4 x5 1

10、 -2 1 0 0 0 1 -3 1 0 0 1 -1 0 1 2 1 2 Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 1 Z 0 0 1 -1 0 -1 x1 x2 x5 1 0 -5 2 0 0 1 -3 1 0 0 0 2 -1 1 4 1 1 Z 0 0 0 -0.5 -0.5-1.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5例例2：23145245345min21513.2221352221112220,1,2,3,

11、4,5jzxxs txxxxxxxxxxj 4 单纯形表单纯形表 Z 0 1 2 0 0 0 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5 Z 0 0 0 1.5 -2.5 -3.5 x1 x2 x3 1 0 0 -0.5 2.5 0 1 0 -0.5 1.5 0 0 1 -0.5 0.5 6.5 2.5 0.5例例3：513345235min18.436313220,1,2,3,4,5jzxs txxxxxxxxxj 4 单纯形表单纯形表 Z 0 0 0 0 -1 18 x1 x4 x2 1 0 1 0 0 0 0 3 1 -1 0 1 -3/2 0 1/2 4 6 3 Z 0 0 0 0 -1 18 x1 x3 x2 1 0 0 -1/3 1/3 0 0 1 1/3 -1/3 0 1 0 1/2 0 2 2 6小结小结(一一).将规范线性规划模型转化为典式，了解根本定将规范线性规划模型转化为典式，了解根本定 理理.(二二).会用单纯形表解线性规划问题会用单纯形表解线性规划问题.(三三).作业作业 74页页 12 16(1)