运筹学基础线性规划ppt课件.ppt

上传人:小飞机 文档编号:1445077 上传时间:2022-11-25 格式:PPT 页数:35 大小:1.48MB
返回 下载 相关 举报
运筹学基础线性规划ppt课件.ppt_第1页
第1页 / 共35页
运筹学基础线性规划ppt课件.ppt_第2页
第2页 / 共35页
运筹学基础线性规划ppt课件.ppt_第3页
第3页 / 共35页
运筹学基础线性规划ppt课件.ppt_第4页
第4页 / 共35页
运筹学基础线性规划ppt课件.ppt_第5页
第5页 / 共35页
点击查看更多>>
资源描述

《运筹学基础线性规划ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学基础线性规划ppt课件.ppt(35页珍藏版)》请在三一办公上搜索。

1、1,上节小结:利用大M法和两阶段法求解线性规划,试用:(一)大M法、(二)两阶段法求解上述线性规划模型,线性规划,2,(一)大M法求解线性规划模型,化线性规划模型为标准型,线性规划,maxZ= 10 x1 8x2 7x3,2x1 + x2 x4 + x5 = 6,+0 x4Mx5,x1 + x2 + x3 x6 + x7= 4,+0 x6Mx7,x1 , x2 , x3 , x4 , x5 , x6 , x7 0,3,试用大M法求解,线性规划,4,令 x3= x4=x5=x6=x7=0得 x1=2, x2=2, 即 X0=(2,2,0,0,0,0,0)T,j0,此解最优 max(-Z)= 36

2、,从而得 minZ=36,线性规划,5,(二)两阶段法,这种方法是在约束条件中加入人工变量,将线性规划问题分为两阶段进行求解。,第一阶段是先求以人工变量等于0为目标的线性规划问题,第二阶段利用已求出的初始基可行解来求原问题最优解。,线性规划,6,试用两阶段法求解如下线性规划问题,解:先划线性规划模型为标准型,线性规划,7,初等变换,-Z x1 x2 x3 x4 x5 x6 x7 b,线性规划,8,进行第二阶段的计算,将第一阶段的人工变量列取消, 并将目标函数系数换成原问题的目标函数系数, 重新计算检验数行, 可得如下第二阶段的初始单纯形表;应用单纯形算法求解得最终表。,此时求解不是最优,继续迭

3、代,令x5= x6= x7=0,得最优解X= ( 0, 1, 1 ,12, 0 )T, minW= 0。因人工变量 x6=x7= 0, 所以是原问题的基可行解。于是可以开始第二阶段的计算。,-Z,线性规划,9,进行第二阶段的计算,将第一阶段的人工变量列取消, 并将目标函数系数换成原问题的目标函数系数, 重新计算检验数行, 可得如下第二阶段的初始单纯形表;应用单纯形算法求解得最终表。,此时求解不是最优,继续迭代,令x5= x6= x7=0,得最优解X= ( 0, 1, 1 ,12, 0 )T, minW= 0。因人工变量 x6=x7= 0, 所以是原问题的基可行解。于是可以开始第二阶段的计算。,

4、-Z,线性规划,10,接上表,j0, x4=0, x5=0, x1=4, x2=1, x3=9 ,即X0=(4,1,9,0,0)T,此时最优解 Z= -2而 maxZ=2,则 minZ= -2,线性规划,11,【另例】试用两阶段法求解,maxZ=10 x1 8x2 7 x3 M x5 M x7 2x1 + x2 x4 + x5 = 6 x1 + x2 + x3 x6 + x7 =4 x1 , x2 , x3 , x4 , x5 , x6 , x7 0,线性规划,12,第一阶段规划求解,线性规划,13,令 x3= x4=x6=0得 x1=2, x2=2, 此解最优 max-Z=36,j0,-Z

5、-10 -8 -7 0,从而得 minZ=36,第二阶段规划求解,第一阶段规划最优,线性规划,14,四、单纯形法补遗,进基变量相持:单纯形法运算过程中,同时出现多个相同的j最大。在符合要求的j(目标为max:j0,min:j0)中,选取下标最小的非基变量为换入变量;,离基变量相持:单纯形法运算过程中,同时出现多个相同的最小值。继续迭代,便有基变量为0,称这种情况为退化解。选取其中下标最大的基变量做为换出变量。,多重最优解:最优单纯形表中,存在非基变量的检验数j=0。让这个非基变量进基,继续迭代,得另一个最优解。,无界解:在大于0的检验数中,若某个k所对应的系数列向量Pk0,则此问题是无界解。,

6、无可行解:最终表中存在人工变量是基变量。,线性规划,15,解的判别:情况1无穷最优解,Max z=2x1+4x2 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1, x2, x3 0,标准化,Max z=2x1+4x2+ 0 x3+ 0 x4+ 0 x5+ 0 x6 2x1+2x2 + x3 =12 x1+2x2+ x4 =8 4x1 +x5 =16 4x2 +x6=12 x1, , x60,线性规划,16,迭代结果,j0,令 x4=0,x6=0,得x1=2,x2=8,x3=2, x5=8即 X0=(2, 8, 2 ,0 , 8, 0) T 此时Z 22+48=36 是

7、最优解,线性规划,17,再次迭代结果,j0,令 x4=0,x5=0,得x1=4,x2=7,x3=0, x6=4即 X0=(4, 7, 0 ,0 , 0,4) T 此时Z24+47=36 也是最优解,结论:非基变量检验数有为0的,此线性规划有无穷多个解,两最优解对应可行域两顶点,两点间连线上的点都是最优解,线性规划,18,解的判别:情况2 解无界,maxZ= 2x1+3x2 +0 x3 4x1 + x3 =16 x1 , x2 , x30,确定x2进基,但x2所在列的系数为0, x2可以任意增大,解无界,Max z=2x1+3x2 4x1 16 x1, x2 0,说明此线性规划解无界,线性规划,

8、19,另例,maxZ= 5x1+6x2 +0 x3 Mx4 +0 x5 2x1-x2- x3+x4 = 2 -2x1+3x2 +x5=2 x1,x2,x3, x4, x50,Max z=5x1+6x2 2x1- x2 2-2x1+3x2 2 x1, x2 0,线性规划,20,确定x3进基,但x3所在列的系数为负, 此时解无界,结论:入基变量系数均0的,该问题目标函数无界,线性规划,21,解的判别:情况3无解,标准化 maxZ= 3x1 +2 x2-M x5-M x6 -2x1 + x2 - x3 + x5 =2 x1 -3 x2 - x4 + x6 =3 x1 , x2 , x3, x4 0,

9、此时检验数j 0,无进基变量,但x5, x6还没有替换出去。Z不能达到最优,说明此线性规划无解,结论:人工变量仍为基变量的,该问题无解,线性规划,22,图示:无解,说明此线性规划无解,线性规划,23,五、单纯形法的矩阵计算求解,用矩阵描述的线性规划的标准形式为:,求解,问题:B和B-1是什么?,待后讨论,线性规划,24,单纯形法小结,1、由实际问题给出数学模型,列出初始单纯形表,进行标准化,线性规划,25,是,否,2、对目标函数求max的线性规划,用单纯形法计算步骤如下,否,否,是,无界解,无可行解,是,是,无穷多最优解,是,线性规划,26,六、用计算机软件求解线性规划问题,关于线性规划问题的

10、求解,有许多好的专业软件和商务软件,通过计算机可十分方便地完成求解过程。其中简便易行的求解软件是Excel,下面介绍其使用方法。,(1)建立Excsl工作表。用 一组单元格表示变量,作为可变单元格(空);用几组单元格分别表示各约束条件和目标函数的系数;用一些单元格输入公式表示各组系数和变量的关系。,(2)打开工具栏中的“规划求解”对话框,指定存有目标函数的单元格为目标单元格,指定表示变量的单元格为可变单元格,建立约束条件。,(3)在规划求解对话框中按下“求解”按钮,即可求出最优解和最优值。推出规划求解对话框。,线性规划,27,利用EXCEL求线性规划的步骤,1、激活“工具栏”中的“规划求解”,

11、线性规划,28,利用EXCEL求线性规划的步骤,2、根据线性规划模型建立计算模板,maxZ=3x1 +5x2 x1 8 2x2 12 3x1 +4 x2 36 x1、x2 0,线性规划,29,利用EXCEL求线性规划的步骤,3、定义决策变量及目标函数、约束条件,注:sumproduct表示对应乘积之和,调用函数sumproduct定义实际值 (E2:E5),线性规划,30,利用EXCEL求线性规划的步骤,4、利用“工具栏”之“规划求解”求解,线性规划,31,利用EXCEL求线性规划的步骤,线性规划,32,利用EXCEL求线性规划的步骤,最优解为:x1=4,x2=6 maxZ=42,线性规划,3

12、3,练习:,由下表数据,列出使总利润最大的生产计划模型,并求利润最大的生产方案,maxZ= 12 x1 + 8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1, x2 0,令产品甲的产量为x1,产品甲的产量为x2,得如下线性规划模型,线性规划,34,参考答案:,maxZ= 12 x1 + 8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1, x2 0,maxZ= 12 x1 + 8 x2 5x1+2 x2 + x3 = 150 2 x1+3 x2 + x4 = 100 4x1+2 x2 + x5 =80 x1, x2 , x3, x4 , x50,答案: x1 =5, x2 = 30,max z=300,提示:可在EXCEL上模拟单纯形法的迭代过程,线性规划,35,练习:利用EXCEL求解线性规划,线性规划,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号