运筹学单纯形法的例题

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

2、始表，检验数，判优，进基、比值、出基、迭代，无解、无穷界的情况表上操作；利用无解、无穷界的情况表上操作；利用excelexcel。下节预习：教材第六章下节预习：教材第六章2 2 对偶理论。对偶理论。10/24/2021运筹学单纯形法2运筹学单纯形法10/24/2021运筹学单纯形法3练习用图解法和单纯形法求如下线性规划问题的最优解： 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之_

3、10/24/2021运筹学单纯形法40123456712345(2.25,0)4x1+x2=910/24/2021运筹学单纯形法5填入第一个约束的数据.13107填入第二个约束的数据.4201910/24/2021运筹学单纯形法61310742019基基?填目标函数系数,填基变量列填基变量列,填cb列,计算计算zj,计算检验数j,4 1 0 0 x3x4000 0 0 0 04 1 0 010/24/2021运筹学单纯形法713107420194 1 0 0 x3x4000 0 0 0 04 1 0 0最优吗？查什么？ 不是！ 谁进基？检验数最大的x1进基, 谁出基？x1的系数有正的吗？求比值

4、？79/49/4410/24/2021运筹学单纯形法813107420194 1 0 0 x3x4000 0 0 0 04 1 0 09/47基变量列中_换为_,x4x1改cb列,_换为_.0410/24/2021运筹学单纯形法9x3x44100001 3 1 0 74 2 0 1 9迭代次数基变量cbx1x2x3x4bi比 迭代次数基变量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 -110/24/

5、2021运筹学单纯形法10练习用图解法和单纯形法求如下线性规划问题的最优解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0可行域在直线 x1+3x2=7之_可行域在直线4x1+2x2=9之_10/24/2021运筹学单纯形法110123456712345(7,0)4x1+x2=28最优解是x1=7,x2=0,此时max z=2810/24/2021运筹学单纯形法12标准化为:max z =4 x1+x2+0 x3+0 x4 x1 + 3x2 + x3 =7 s.t. 4x1 + 2x2 -x4 =9 x1 , x2 , x3 ,

6、x4 0基是谁?这个“-”如何处理?再引进一个“人工变量”x5+x5-mx5m是一个大的正数, x510/24/2021运筹学单纯形法13max 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.10/24/2021运筹学单纯形法14两行，几列? 少一列?填入第一个约束的数据.10/24/2021运筹学单纯形法15填入第二个约束的数据.基基?填目标函数系数,填基变量列填基变量列,填cb列,计算计算zj,计算检验

7、数j,10/24/2021运筹学单纯形法16最优吗？查什么？ 不是！ 谁进基?检验数最大的x1进基,谁出基?x1的系数有正的吗?求比值?79/410/24/2021运筹学单纯形法17基变量列中_换为_,x5x1改cb列,_换为_.-m410/24/2021运筹学单纯形法18练习用图解法和单纯形法求如下线性规划问题的最优解： max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0可行域在直线 x1+3x2=7之_可行域在直线4x1+2x2=9之_10/24/2021运筹学单纯形法190123456712345有可行解,但无有限的最优解,z+.

8、10/24/2021运筹学单纯形法20标准化为:max z=4x1+x2+0 x3+0 x4 x1 + 3x2 - x3 =7 s.t. 4x1 + 2x2 -x4 =9 x1 ,x2 ,x3 ,x4 0基是谁?这里“-”如何处理?引进两个“人工变量” x5 ,x6+x5-mx5 -mx6m是一个大的正数(大m法),x5 ,x6+x610/24/2021运筹学单纯形法21max 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.不能全出基,就无可行解.10/24/2021运筹学单纯形法22vlp问题解的几种可能：问题解的几种可能：10/24/2021运筹学单纯形法23vlp问题解的几种可能：问题解的几种可能： axb s.t. x010/24/2021运筹学单纯形法24vlp问题解的几种可能：问题解的几种可能：10/24/2021运筹学单纯形法25v第五章第五章(p.99-100)： 7a,b,c,d10/24