单纯行法例题解析PPT课件

1、教案要点教案要点文文 件件 名：名：051or11.ppt051or11.ppt；第五章；第五章.xls.xls授课时间：第十一讲授课时间：第十一讲授课内容：授课内容：lplp问题的单纯形法大问题的单纯形法大m m法法, ,无解无解. .预备知识：凸集合，预备知识：凸集合，excelexcel复习可行解、基可行解，基及非基变量。复习可行解、基可行解，基及非基变量。难难 点：引入人工变量点：引入人工变量, ,解的各种情况解的各种情况. .重重 点：单纯形法的步骤：引入人工变量点：单纯形法的步骤：引入人工变量, ,初初始表，检验数，判优，进基、比值、出基、迭代，始表，检验数，判优，进基、比值、出基

2、、迭代，无解、无穷界的情况表上操作；利用无解、无穷界的情况表上操作；利用excelexcel。下节预习：教材第六章下节预习：教材第六章2 2 对偶理论。对偶理论。运筹学单纯形法练习用图解法和单纯形法求如下线性规划问题的最优解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0 x1+3x2=7经过点(_,0)与(1,_)724x1+2x2=9经过点(2,_)与(0,_)0.54.5可行域在x1+3x2=7与4x1+2x2=9之_0123456712345(2.25,0)4x1+x2=9填入第一个约束的数据.13107填入第二个约束的数

3、据.420191310742019基基?填目标函数系数,填基变量列填基变量列,填cb列, 计算计算zj,计算检验数j,4 1 0 0 x3x4000 0 0 0 04 1 0 013107420194 1 0 0 x3x4000 0 0 0 04 1 0 0最优吗？查什么？ 不是！ 谁进基？检验数最大的x1进基, 谁出基？x1的系数有正的吗？求比值？79/49/4413107420194 1 0 0 x3x4000 0 0 0 04 1 0 09/47基变量列中_换为_,x4x1改cb列,_换为_.04excelx3x44100001 3 1 0 74 2 0 1 9迭代次数基变量cbx1x2

4、x3x4bi比 迭代次数基变量cbx1x2x3x4bi比 0zjj=cj- zj1zjj=cj- zj0 0 0 0 04 1 0 079/44 1 0 0 x3x1041 0.5 0 0.25 2.250 2.5 1 -0.25 4.754 2 0 1 90 -1 0 -1练习用图解法和单纯形法求如下线性规划问题的最优解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0可行域在直线 x1+3x2=7之_可行域在直线4x1+2x2=9之_0123456712345(7,0)4x1+x2=28最优解是x1=7,x2=0,此时max z

5、=28标准化为:max z =4 x1+x2+0 x3+0 x4 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4 =9 x1 , x2 , x3 , x4 0基是谁?这个“-”如何处理?再引进一个“人工变量”x5+x5-mx5m是一个大的正数, x5max z =4x1+x2+0 x3+0 x4-mx5 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4+x5 =9 x1, x2 , x3 , x4 , x5 0基是谁?x3,x5x5的检验数为0请它出基,逼它取值为0.两行，几列? 少一列?填入第一个约束的数据.填入第二个约束的数据.基基?填目标函数

6、系数,填基变量列填基变量列,填cb列, 计算计算zj,计算检验数j,最优吗？查什么？ 不是！ 谁进基?检验数最大的x1进基,谁出基?x1的系数有正的吗?求比值?79/4基变量列中_换为_,x5x1改cb列,_换为_.-m4excel练习用图解法和单纯形法求如下线性规划问题的最优解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0可行域在直线 x1+3x2=7之_可行域在直线4x1+2x2=9之_0123456712345有可行解,但无有限的最优解,z+.标准化为:max z=4x1+x2+0 x3+0 x4 x1 + 3x2 - x

7、3 =7 s.t. 4x1 + 2x2 -x4 =9 x1 ,x2 ,x3 ,x4 0基是谁?这里“-”如何处理?引进两个“人工变量” x5 ,x6+x5-mx5 -mx6m是一个大的正数(大m法),x5 ,x6+x6max z=4x1+x2+0 x3+0 x4 -mx5 mx6 x1+3x2-x3 +x5 =7 s.t. 4x1+2x2 -x4 +x6=9 x1,x2,x3,x4 ,x5,x6 0基是谁?x5,x6它们的检验数为0请它们出基,逼它们取值为0.excel不能全出基,就无可行解.vlp问题解的几种可能：问题解的几种可能：vlp问题解的几种可能：问题解的几种可能： axb s.t. x0vlp问题解的几种可能：问题解的几种可能：v第五章第五章(p.99-100)： 7a,b,c,d练习一个一个lp问题