运筹学基础线性规划精.ppt

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

1、运筹学基运筹学基础线性性规划划第1页，本讲稿共39页另例：000-3-412-1023160-142x1 x2 x3 x4 b问题：无标准的初始可行基，如何利用单纯形法求解问题：无标准的初始可行基，如何利用单纯形法求解问题：无标准的初始可行基，如何利用单纯形法求解问题：无标准的初始可行基，如何利用单纯形法求解化为标准形化为标准形不是标准的初始可行基不是标准的初始可行基不是标准的初始可行基不是标准的初始可行基第2页，本讲稿共39页三、人工变量问题三、人工变量问题用单纯形法解题时，需要有一个单位矩阵作为初始基初始基初始基初始基。当约束条件都是“”时，加入松弛变量就形成了初始基松弛变量就形成了初始基

2、松弛变量就形成了初始基松弛变量就形成了初始基。但如果存在“”或“”型的约束，就没有现成的单位矩就没有现成的单位矩就没有现成的单位矩就没有现成的单位矩阵阵阵阵。采用人造基的办法：采用人造基的办法：人为构造单位矩阵人为构造单位矩阵处理方法有两种：处理方法有两种：大大大大M M 法法法法两阶段法两阶段法第3页，本讲稿共39页（一）大（一）大（一）大（一）大MM法法法法maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 0S.t.没有单位矩阵，不符合构造初始基的条件，没有单位矩阵，不符合构造初始基的条件，需加入人工变量需加入人工变量需加入人工

3、变量需加入人工变量。maxZ=3x1 -x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0v人工变量最终必须等于0才能保持原问题性质不变。v为保证人工变量为0，在目标函数中令其系数为目标函数中令其系数为目标函数中令其系数为目标函数中令其系数为-M-M。vM为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量将人工变量将人工变量将人工变量逐步从基变量中替换出去替换出去替换出去替换出去。v如若到最终表中人工变量仍没有置换出去最终表中人工变量仍没有置换出去最

4、终表中人工变量仍没有置换出去最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解无最优解无最优解无最优解。第4页，本讲稿共39页大大MM法求解法求解按大按大M法构造人造基，引入人工变量法构造人造基，引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：v例如例如 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 0S.t.maxZ=3x1 -x2 -2 x3-M x4-M x5 3x1+2 x2-3 x3 +x4 =6 x1 -2 x2+x3 +x5=4 x1,x2,x3,x4,x5 0第5页，本讲稿共39页

5、初始单纯形表为：初始单纯形表为：初始单纯形表为：初始单纯形表为：0-M-2-13411-2160-323-M0110M0-2-2M-13+4M4 11-216 0-3230 0 1 3+3M -1+2M-2-3M 0 -M 6M所以，此时求解不是最优解，需要换基。所以，此时求解不是最优解，需要换基。所以，此时求解不是最优解，需要换基。所以，此时求解不是最优解，需要换基。x1 x2 x3 x4 x5 b10M0-2-2M-13+4M411-2160-323001 3+4M -1 -2-2M 0 0 10M第6页，本讲稿共39页 10M0-2-2M-13+4M411-2160-323001-6+2

6、M0 1+2M-3-8M/30212-8/3020-12/31-1-4M/3-1/31/3-7-M-1/20-5/3011/21-4/3031/20-2/31-M-5/6-1/61/6x x2 2=0,x=0,x4 4=0,x=0,x5 5=0,x=0,x1 1=3,x=3,x3 3=1,=1,j j00，此时求解最优，此时求解最优，此时求解最优，此时求解最优即即即即X X0 0=(3,0,1,0,0)=(3,0,1,0,0)T T时，时，时，时，-Z=-7-Z=-7，最优解，最优解，最优解，最优解 maxZ=7maxZ=7第7页，本讲稿共39页试用大试用大MM法求解如下线性规划问题的最优解。

7、法求解如下线性规划问题的最优解。划为标准型，并按大划为标准型，并按大M法引入人工变量法引入人工变量x4,x5 的辅助问题如下：的辅助问题如下：松驰变量松驰变量剩余变量剩余变量人工变量人工变量惩罚项惩罚项第8页，本讲稿共39页解：解：0-M0-1-1311010-230021-411011-2100-10-M0104M00-1+3M-1+M3-6M11010-230021-411011-21-M0-10 0010 x1 x2 x3 x4 x5 x6 x7 bx1 x2 x3 x4 x5 x6 x7 b第9页，本讲稿共39页M+1-3M+10 0-1+M11101 10-21-2001010-11

8、0-23-M0-1000102-M-10 00111010-21-2001 1012-51003 3-10-1-21-M012-2-M+23-1/3 0009-7/32/31001-200104-5/31/3001-1/3-4/3-1-2/31/3-M4/312/3令令x4=0,x5,=0,x6=0,x7,=0,得得x1=4,x2=1,x3=9即即X X0 0=(4,1,9,0,0,0,0)=(4,1,9,0,0,0,0)T T此时-Z Z =-2=-2为最大,则则则则 最优解最优解最优解最优解 minZ=-2minZ=-2第10页，本讲稿共39页（二）两阶段法（二）两阶段法 这这种种方方法法

9、是是在在约约束束条条件件中中加加入入人人工工变变量量，将将线线性性规规划划问题分为问题分为两阶段两阶段进行求解。进行求解。第一阶段第一阶段是先求以人工变量等于是先求以人工变量等于0为目标的线性规划问题为目标的线性规划问题第二阶段第二阶段利用已求出的初始基可行解来求原问题最优解。利用已求出的初始基可行解来求原问题最优解。第11页，本讲稿共39页试用两阶段法求解如下线性规划问题试用两阶段法求解如下线性规划问题 解：先划约束条件为标准型 第12页，本讲稿共39页初等变换初等变换0-10000-W11010-2030021-4011011-21000-10-101040031-6-W11010-203

10、0021-4011011-210-10-100010-Z x1 x2 x3 x4 x5 x6 x7 b第13页，本讲稿共39页 0 0-1-10 00 00 00 0-W-W 1 11 10 01 10 0-2-20 0 1 1-2-20 00 01 10 00 0 1212-5-51 10 00 03 30 00 00 0-1-1-2-2-1-10 01 12 21-30010-W11010-201-20010010-110-230-10-100010进行第二阶段的计算进行第二阶段的计算进行第二阶段的计算进行第二阶段的计算将第一阶段的人工变量列取消将第一阶段的人工变量列取消,并将目标函数系数

11、换成原问题的目标函数并将目标函数系数换成原问题的目标函数系数系数,重新计算检验数行重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。形算法求解得最终表。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,所以是原问题的基可行解。于是可以开始第二阶段的计算。所以是原问题的基

12、可行解。于是可以开始第二阶段的计算。-Z-Z第14页，本讲稿共39页 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)=(4,1,9,0,0)T T，此时最优解此时最优解此时最优解此时最优解 ZZ=-2=-2而而而而 maxZ=2=2则则则则 mi

13、nZ=-2第15页，本讲稿共39页（二）试用两阶段法求解（二）试用两阶段法求解MinZ=10 x1+8x2+7 x3 2x1+x2 6 x1+x2+x3 4 x1,x2,x3 0S.t.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第16页，本讲稿共39页（二）试用两阶段法求解（二）试用两阶段法求解00000-Z4011106-10120 -1010-10-1 1 010-1 1 2 3-Z4011106-10120001-1-100 1 01/2 1 1/2 0-Z11/

14、211/2003-1/201/210-3/2-1/21/2-1-100 1 01第一阶段规划求解第一阶段规划求解第17页，本讲稿共39页 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=36 j j00-Z -10 -8 -7 0 -3/2 0 1/2 0 -Z11/211/2003-1/201/2101/2-1/21/2-7-10-1 1 037-2-1 0 0 -Z2121002-1

15、1-10101/2-1/21/2-6-21-1 1 036从而得从而得从而得从而得 minZ=36minZ=36 j j00第二阶段规划求解第二阶段规划求解第一阶段规划最优第一阶段规划最优第18页，本讲稿共39页四、单纯形法补遗进基变量相持：进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取下下标标最最小小的的非基变量非基变量为换入变量；离基变量相持：离基变量相持：离基变量相持：离基变量相持：单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为0，称这种情况为退化解退化解。选取其中下标最大的基变量最大的基变量最

16、大的基变量最大的基变量做为换出变量。多重最优解：多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。无界解：无界解：在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解。无可行解：无可行解：最终表中存在人工变量是基变量。第19页，本讲稿共39页 解的判别：情况1无穷最优解Cj比比值值CBXBb检验数检验数 j0 x1x2x3x4x5x6240000221000120100X3X4X5X6000040001064-3Max z=2x1+4x2 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1,x2,x3

17、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第20页，本讲稿共39页 迭代结果Cj比比值值CBXBb检验数检验数 j-36x1x2x3x4x5x6240000001-200.5 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，

18、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 是最优解是最优解是最优解是最优解第21页，本讲稿共39页 再次迭代结果Cj比比值值CBXBb检验数检验数 j-36x1x2x3x4x5x6240000001-1-0.25 0 1 0000.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

19、=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的，此线性规划有无穷多个解的，此线性规划有无穷多个解的，此线性规划有无穷多个解的，此线性规划有无穷多个解 两最优解对应可行域两顶点，两点间连线上的点都是最优解两最优解对应可行域两顶点，两点间连线上的点都是最优解两最优解对应可行域两顶点，两点间连线上的点都是最优解两最

20、优解对应可行域两顶点，两点间连线上的点都是最优解第22页，本讲稿共39页 解的判别：情况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说明此线性规划解无界说明此线性规划解无界说明此线性规划解无界说明此线性规划解无界 第23页，本讲稿共39页 另例maxZ=5x1+6x2+0 x3 Mx4+0 x5 2x1-x2-

21、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第24页，本讲稿共39页 另例Cj比比值值CBXBb检验数检验数 jx1x2x3x4x5560-M0210-3/4 3/41/42 01-0.50.50.5X1X256560-M00 0 27/4-M

22、+27/4-17/4确定确定x3进基，但进基，但x3所在列的系数为负，所在列的系数为负，此时解无界此时解无界结论：入基变量系数均结论：入基变量系数均结论：入基变量系数均结论：入基变量系数均 0 0的，该问题目标函数无界的，该问题目标函数无界的，该问题目标函数无界的，该问题目标函数无界第25页，本讲稿共39页 解的判别：情况3无解maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0S.t.v标准化标准化 maxZ=3x1+2 x2-M x5-M x6-2x1+x2-x3 +x5=2 x1-3 x2 -x4+x6=3 x1,x2,x3,x4 0Cj比比值值CBXBb检

23、验数检验数 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否否某非基变量某非基变量检验数为零检验数为零否否唯一唯一最优解最优解对任一对任一s sj j00有有P Pj j0是是无界解无界解无可行解无可行解是是是是无穷多最优解无穷多最优解是是迭代运算迭代运算第30页，本讲稿共39页六、用计算机软

24、件求解线性规划问题六、用计算机软件求解线性规划问题 关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。其中简便易行的求解软件是Excel，下面介绍其使用方法。（1）建立Excsl工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。（3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。第31页，本讲稿共39

25、页 利用利用EXCEL求线性求线性规划的步骤规划的步骤1、激活“工具栏”中的“规划求解”第32页，本讲稿共39页 利用利用EXCEL求线性求线性规划的步骤规划的步骤2、根据线性规划模型建立计算模板 maxZ=3x1+5x2 x1 8 2x2 12 3x1+4 x2 36 x1、x2 0第33页，本讲稿共39页 利用利用EXCEL求线性求线性规划的步骤规划的步骤3、定义决策变量及目标函数、约束条件注：注：sumproductsumproduct表示对应乘积之和表示对应乘积之和调用函数调用函数sumproductsumproduct定义实际值定义实际值 （E2E2：E5E5）第34页，本讲稿共39

26、页 利用利用EXCEL求线性求线性规划的步骤规划的步骤4、利用“工具栏”之“规划求解”求解第35页，本讲稿共39页 利用利用EXCEL求线性求线性规划的步骤规划的步骤第36页，本讲稿共39页 利用利用EXCEL求线性求线性规划的步骤规划的步骤最优解为：最优解为：x x1 1=4,x=4,x2 2=6=6 maxZ=42maxZ=42第37页，本讲稿共39页练习：由下表数据，列出使总利润最大的生产计划模型，并求利润最大的生产方案maxZ=12 x1+8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80 x1,x2 0令产品甲的产量为x1,产品甲的产量为x2,得如下线性规划模型第38页，本讲稿共39页参考答案：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上模拟单纯形法的迭代过程上模拟单纯形法的迭代过程第39页，本讲稿共39页