运筹学基础-线性规划(3).ppt

《运筹学基础-线性规划(3).ppt》由会员分享，可在线阅读，更多相关《运筹学基础-线性规划(3).ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上节小结：利用大上节小结：利用大M法和两阶段法求解线性规划法和两阶段法求解线性规划试用：试用：(一一)大大M法、法、(二二)两阶段法求解上述线性规划模型两阶段法求解上述线性规划模型线性规划1 1（一）大（一）大（一）大（一）大MM法求解线性规划模型法求解线性规划模型法求解线性规划模型法求解线性规划模型n 化线性规划模型为标准型化线性规划模型为标准型线性规划minZ=10 x1+8x2+7 x3 2x1+x2 6 x1 +x2+x3 4 x1,x2,x30maxZ=10 x1 8x2 7x32x1+x2 x4+x5=6+0 x4Mx5x1 +x2+x3 x6+x7=4+0 x6Mx7x1,x2,

2、x3,x4,x5,x6,x7 02 2n n 试用大试用大试用大试用大MM法求解法求解法求解法求解00-7-8-10401116-1012 -M010-10-M 1 010M-M -7+M -8+2M-10+3M401116-1012001-M-100 1 01/2M-5 -7+M -3+1/2M 011/211/203-1/201/21 5-3/2M-1/21/2-M-100 1 0M+30线性规划3 3 -3/2 0 1/2 011/211/203-1/201/21 3/2-M-1/21/2-7-107-M 1 037-2 -1 0 0212102-1-1012-M-11-6-216-M

3、2-136令令令令 x x3 3=x=x4 4=x=x5 5=x=x6 6=x=x7 7=0=0得得得得 x x1 1=2,x=2,x2 2=2,=2,即即即即 X X0 0=(2,2,0,0,0,0,0)=(2,2,0,0,0,0,0)T T j j00此解最优此解最优此解最优此解最优 maxmax（-Z-Z）=36=36，从而得从而得从而得从而得 minZminZ=36=36线性规划4 4（二）两阶段法（二）两阶段法（二）两阶段法（二）两阶段法 这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。第一阶段是先求以人工变量等于0为目标的线性规划问题第二阶段利用已求出的初始基

4、可行解来求原问题最优解。线性规划5 5试用两阶段法求解如下线性规划问题试用两阶段法求解如下线性规划问题试用两阶段法求解如下线性规划问题试用两阶段法求解如下线性规划问题 解：先划线性规划模型为标准型 线性规划6 6初等变换初等变换初等变换初等变换0-10000-W11010-2030021-4011011-21000-10-101040031-6-W11010-2030021-4011011-210-10-100010-Z x1 x2 x3 x4 x5 x6 x7 b线性规划7 7 0-10000-W 11010-20 1-200100 12-51003000-1-2-10121-30010-W

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

6、开始第二阶段的计算。-Z-Z线性规划8 8 0-10000-W 11010-20 1-200100 12-51003000-1-2-10121-30010-W11010-201-20010010-110-230-10-100010进行第二阶段的计算进行第二阶段的计算将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。3 -1 -1 0 0 3 0 -1 0 -1 1 1 0 0 0 -1 2此时求解不是最优，继续迭代此时求解不是最优，继续迭代 令令x5=x6=x7=0，得最优解，得最优解X=(0,1

7、,1,12,0)T，minW=0。因人工变。因人工变量量 x6=x7=0,所以是原问题的基可行解。于是可以开始第二阶段的计算。所以是原问题的基可行解。于是可以开始第二阶段的计算。-Z-Z线性规划9 9 2-30001-Z11010-201-20010012-110030-10-1-20010接上表接上表接上表接上表-2-3-1/3000-Z912/310001-2001004-11/30010-1/3-4/3-1-2/30010 j j00，x x4 4=0,x=0,x5 5=0,x=0,x1 1=4,x=4,x2 2=1,x=1,x3 3=9,=9,即即即即X X0 0=(4,1,9,0,0

8、)=(4,1,9,0,0)T T，此时最优解此时最优解此时最优解此时最优解 ZZ=-2=-2而而而而 maxZmaxZ=2=2则则则则 minZminZ=-2=-2线性规划1010【另例另例另例另例】试用两阶段法求解试用两阶段法求解试用两阶段法求解试用两阶段法求解MinZ=10 x1+8x2+7 x3 2x1+x2 6 x1+x2+x3 4 x1,x2,x3 0maxZ=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线性规划111100000-Z4011106-10120 -1010

9、-10-1 1 010-1 1 2 3-Z4011106-10120001-1-100 1 01/2 1 1/2 0-Z11/211/2003-1/201/210-3/2-1/21/2-1-100 1 01第一阶段规划求解第一阶段规划求解线性规划 1212 0 00 0-Z11/211/2003-1/201/210-1-1/21/20-10-1 1 00令令令令 x x3 3=x=x4 4=x=x6 6=0=0得得得得 x x1 1=2,x=2,x2 2=2,=2,此解最优此解最优此解最优此解最优 max-Z=36max-Z=36 j j00-Z -10 -8 -7 0 -3/2 0 1/2

10、0 -Z11/211/2003-1/201/2101/2-1/21/2-7-10-1 1 037-2-1 0 0 -Z2121002-11-10101/2-1/21/2-6-21-1 1 036从而得从而得从而得从而得 minZminZ=36=36 j j00第二阶段规划求解第二阶段规划求解第一阶段规划最优第一阶段规划最优线性规划1313四、单纯形法补遗四、单纯形法补遗四、单纯形法补遗四、单纯形法补遗进基变量相持：进基变量相持：进基变量相持：进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取下下下下标标标标最小的非基变量最小的

11、非基变量最小的非基变量最小的非基变量为换入变量；离基变量相持：离基变量相持：离基变量相持：离基变量相持：单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为0，称这种情况为退化解退化解。选取其中下标最大的基变量最大的基变量最大的基变量最大的基变量做为换出变量。多重最优解：多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：无界解：在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解。无无可行解：可行解：最终表中存在人工变量是基变量。线性规划1414 解的判别：情况解的判别：情况1无穷最优解无穷最优解Cj

12、比值CBXBb检验数j0 x1x2x3x4x5x6240000221000120100X3X4X5X6000040001064-3Max 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,x600400012400001281612线性规划1515 迭代结果迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-200.5

13、 1 0 0 1 0-0.5X3X1X5X20204000-4124-432010000.25000-2002288j0令令令令 x x4 4=0 0，x x6 6=0=0，得，得，得，得x x1 1=2=2，x x2 2=8=8，x x3 3=2=2，x x5 5=8=8即即即即 X X0 0=(2,8,2,0,8,0)=(2,8,2,0,8,0)T T 此时此时此时此时Z Z 2 22+482+48=36=36 是最优解是最优解是最优解是最优解线性规划1616 再次迭代结果再次迭代结果Cj比值CBXBb检验数j-36x1x2x3x4x5x6240000001-1-0.25 0 1 0000

14、.25 0X3X1X6X20204000-20.5 1 0 100.5-0.125 0000-1.50 00447j0令令令令 x x4 4=0 0，x x5 5=0=0，得，得，得，得x x1 1=4=4，x x2 2=7=7，x x3 3=0=0，x x6 6=4=4即即即即 X X0 0=(4,7,0,0,0,4)=(4,7,0,0,0,4)T T 此时此时此时此时Z Z2 24+474+47=36=36 也是最优解也是最优解也是最优解也是最优解结论：非基变量检验数有为结论：非基变量检验数有为结论：非基变量检验数有为结论：非基变量检验数有为0 0的，此线性规划有无穷多个解的，此线性规划有

15、无穷多个解的，此线性规划有无穷多个解的，此线性规划有无穷多个解 两两两两最优解对应可行域两顶点，两点间连线上的点都是最优解最优解对应可行域两顶点，两点间连线上的点都是最优解最优解对应可行域两顶点，两点间连线上的点都是最优解最优解对应可行域两顶点，两点间连线上的点都是最优解线性规划1717 解的判别：情况解的判别：情况2 解无界解无界maxZ=2x1+3x2+0 x3 4x1 +x3 =16 x1,x2,x30Cj比值CBXBb检验数jx1x2x323016401230 x30确定x2进基，但x2所在列的系数为0，x2可以任意增大，解无界Max z=2x1+3x2 4x1 16 x1,x2 0说

16、明此线性规划解无界说明此线性规划解无界说明此线性规划解无界说明此线性规划解无界 线性规划1818 另例另例maxZ=5x1+6x2+0 x3 Mx4+0 x5 2x1-x2-x3+x4 =2 -2x1+3x2 +x5=2 x1,x2,x3,x4,x50Cj比值CBXBb检验数jx1x2x3x4x5560-M022-1-1102-23001X4X5-M0Max z=5x1+6x2 2x1-x2 2-2x1+3x2 2 x1,x2 0560-M0检验数j5+2M6-M-M0011-1/2-1/21/20402-11 1-5017/25/2-M+5/20线性规划1919Cj比值CBXBb检验数jx1

17、x2x3x4x5560-M0210-3/4 3/41/42 01-0.50.50.5X1X256560-M00 0 27/4-M+27/4-17/4确定x3进基，但x3所在列的系数为负，此时解无界结论：入基变量系数均结论：入基变量系数均结论：入基变量系数均结论：入基变量系数均 0 0的，该问题目标函数无界的，该问题目标函数无界的，该问题目标函数无界的，该问题目标函数无界线性规划 2020 解的判别：情况解的判别：情况3无解无解maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0标准化标准化 maxZ=3x1+2 x2-M x5-M x6-2x1+x2-x3 +x5

18、=2 x1-3 x2 -x4+x6=3 x1,x2,x3,x4 0Cj比值CBXBb检验数j3200-M-Mx5x6-M-M 此时检验数j00计算计算q qi i=b=bi i/a aikik令令q q=min(min(q qi i)所有所有s sj j0 0是是否否2 2、对目标函数求、对目标函数求、对目标函数求、对目标函数求maxmax的线性规划，用单纯形法计算步骤如下的线性规划，用单纯形法计算步骤如下的线性规划，用单纯形法计算步骤如下的线性规划，用单纯形法计算步骤如下计算非基变量计算非基变量各列的检验数各列的检验数s sj j否否某非基变量某非基变量检验数为零检验数为零否否唯一唯一最优解

19、最优解对任一对任一s sj j00有有P Pj j0是是无界解无界解无可行解无可行解是是是是无穷多最优解无穷多最优解是是迭代运算迭代运算线性规划2525六、用计算机软件求解线性规划问题 关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。其中简便易行的求解软件是Excel，下面介绍其使用方法。（1）建立Excsl工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为

20、可变单元格，建立约束条件。（3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。线性规划2626 利用EXCEL求线性规划的步骤1 1、激活、激活、激活、激活“工具栏工具栏工具栏工具栏”中的中的中的中的“规划求解规划求解规划求解规划求解”线性规划2727 利用EXCEL求线性规划的步骤2 2、根据线性规划模型建立计算模板、根据线性规划模型建立计算模板、根据线性规划模型建立计算模板、根据线性规划模型建立计算模板 maxZ=3x1+5x2 x1 8 2x2 12 3x1+4 x2 36 x1、x2 0线性规划2828 利用EXCEL求线性规划的步骤3 3、定义决策变

21、量及目标函数、约束条件、定义决策变量及目标函数、约束条件、定义决策变量及目标函数、约束条件、定义决策变量及目标函数、约束条件注：注：sumproductsumproduct表示对应乘积之和表示对应乘积之和调用函数调用函数sumproductsumproduct定义实际值定义实际值 （E2E2：E5E5）线性规划2929 利用EXCEL求线性规划的步骤4 4、利用、利用、利用、利用“工具栏工具栏工具栏工具栏”之之之之“规划求解规划求解规划求解规划求解”求解求解求解求解线性规划3030 利用EXCEL求线性规划的步骤线性规划3131 利用EXCEL求线性规划的步骤最优解为：最优解为：x x1 1=

22、4,x=4,x2 2=6=6 maxZmaxZ=42=42线性规划3232练习：练习：练习：练习：由下表数据，列出使总利润最大的生产计划模型，并求利润最大的生产方案maxZ=12 x1+8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0令产品甲的产量为x1,产品甲的产量为x2,得如下线性规划模型线性规划3333参考答案：参考答案：参考答案：参考答案：maxZ=12 x1+8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0maxZ=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上模拟单纯形法的迭代过程上模拟单纯形法的迭代过程线性规划3434练习：利用练习：利用EXCEL求解线性规划求解线性规划线性规划3535