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

《运筹学基础线性规划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求解线性规划,线性规划,