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

《运筹学基础线性规划精品文稿.ppt》由会员分享，可在线阅读，更多相关《运筹学基础线性规划精品文稿.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、运筹学基础线性规划第1 页，本讲稿共39 页另例：0 0 0-3-412-1 0 2 316 0-1 4 2x1 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.没有单位矩阵，不符合构造初始基的条件，需加入人工变量 需加入人工变量。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。v M 为无限大的正数，这是一个

3、惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量 将人工变量逐步从基变量中替换出 替换出去 去。v 如若到最终表中人工变量仍没有置换出去 最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解 无最优解。第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+x

4、3+x5=4 x1,x2,x3,x4,x5 0第5 页，本讲稿共39 页 初始单纯形表为：初始单纯形表为：0-M-2-1 34 1 1-2 16 0-3 2 3-M0110M 0-2-2M-1 3+4M4 1 1-2 16 0-3 2 30 0 1 3+3M-1+2M-2-3M 0-M 6M所以，此时求解不是最优解，需要换基。所以，此时求解不是最优解，需要换基。x1 x2 x3 x4 x5 b10M 0-2-2M-1 3+4M4 1 1-2 16 0-3 2 3001 3+4M-1-2-2M 0 0 10M第6 页，本讲稿共39 页 10M 0-2-2M-1 3+4M4 1 1-2 16 0-

5、3 2 3001-6+2M 0 1+2M-3-8M/3 02 1 2-8/3 02 0-1 2/3 1-1-4M/3-1/31/3-7-M-1/2 0-5/3 01 1/2 1-4/3 03 1/2 0-2/3 1-M-5/6-1/61/6xx22=0,x=0,x44=0,x=0,x55=0,x=0,x11=3,x=3,x33=1,=1,jj00，此时求解最优，此时求解最优即即X X0 0=(3,0,1,0,0)=(3,0,1,0,0)T T时，时，-Z=-7-Z=-7，最优解，最优解 maxZ=7maxZ=7第7 页，本讲稿共39 页试用大 试用大M M 法求解如下线性规划问题的最优解。法求

6、解如下线性规划问题的最优解。划为标准型，并按大M法引入人工变量x4,x5 的辅助问题如下：松驰变量剩余变量人工变量惩罚项第8 页，本讲稿共39 页解：解：0-M 0-1-1 31 1 0 1 0-23 0 0 2 1-411 0 1 1-2 100-10-M0104M 0 0-1+3M-1+M 3-6M1 1 0 1 0-23 0 0 2 1-411 0 1 1-2 1-M0-10 0010 x1 x2 x3 x4 x5 x6 x7 bx1 x2 x3 x4 x5 x6 x7 b第9 页，本讲稿共39 页M+1-3M+1 0 0-1+M 11 1 01 1 0-21-2 0 0 1 010-1

7、 1 0-2 3-M0-1000102-M-1 0 0 0 11 1 0 1 0-21-2 0 01 1 012-5 1 0 03 3-10-1-21-M012-2-M+23-1/3 0 0 09-7/3 2/3 1 0 01-2 0 0 1 04-5/3 1/3 0 0 1-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此时-ZZ=-2=-2 为最大,则则 最优解最优解 minZ=-2minZ=-2第10 页，本讲稿共39 页（二

8、）两阶段法（二）两阶段法 这种方法是在约束条件中加入人工变量，将线性规划问题分为两阶段进行求解。第一阶段是先求以人工变量等于0为目标的线性规划问题第二阶段利用已求出的初始基可行解来求原问题最优解。第11 页，本讲稿共39 页试用两阶段法求解如下线性规划问题 试用两阶段法求解如下线性规划问题 解：先划约束条件为标准型 第12 页，本讲稿共39 页初等变换 初等变换0-1 0 0 0 0-W1 1 0 1 0-2 03 0 0 2 1-4 011 0 1 1-2 1 000-10-10104 0 0 3 1-6-W1 1 0 1 0-2 03 0 0 2 1-4 011 0 1 1-2 1 0-1

9、0-100010-Z x1 x2 x3 x4 x5 x6 x7 b第13 页，本讲稿共39 页 0-1 0 0 0 0-W 1 1 0 1 0-2 0 1-2 0 0 1 0 0 12-5 1 0 0 3 000-1-2-10121-3 0 0 1 0-W1 1 0 1 0-2 01-2 0 0 1 0 010-1 1 0-2 3 0-10-100010进行第二阶段的计算 进行第二阶段的计算将第一阶段的人工变量列取消,并将目标函数系数换成原问题的目标函数系数,重新计算检验数行,可得如下第二阶段的初始单纯形表；应用单纯形算法求解得最终表。3-1-1 0 0 3 0-1 0-1 1 1 0 0 0

10、-1 2此时求解不是最优，继续迭代 此时求解不是最优，继续迭代 令x5=x6=x7=0，得最优解X=(0,1,1,12,0)T，minW=0。因人工变量 x6=x7=0,所以是原问题的基可行解。于是可以开始第二阶段的计算。-Z 第14 页，本讲稿共39 页 2-3 0 0 0 1-Z1 1 0 1 0-2 01-2 0 0 1 0 012-1 1 0 0 3 0-10-1-20010接上表 接上表-2-3-1/3 0 0 0-Z9 1 2/3 1 0 0 01-2 0 0 1 0 04-1 1/3 0 0 1 0-1/3-4/3-1-2/30010 j j0 0，x x4 4=0,x=0,x5

11、 5=0,x=0,x1 1=4,x=4,x2 2=1,x=1,x3 3=9,=9,即即XX00=(4,1,9,0,0)=(4,1,9,0,0)T T，此时最优解此时最优解 Z Z=-2=-2而而 maxZmaxZ=2=2则则 minZ=-2minZ=-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

12、0第16 页，本讲稿共39 页（二）试用两阶段法求解（二）试用两阶段法求解00 0 0 0-Z4 0 1 1 1 06-1 0 1 2 0-1010-10-1 1 010-1 1 2 3-Z4 0 1 1 1 06-1 0 1 2 0001-1-100 1 01/2 1 1/2 0-Z1 1/2 11/20 03-1/2 0 1/2 1 0-3/2-1/21/2-1-100 1 01第一阶段规划求解第17 页，本讲稿共39 页 0 00 0-Z1 1/2 11/20 03-1/2 0 1/2 1 0-1-1/21/20-10-1 1 00令令 x x3 3=x=x44=x=x66=0=0得得

13、xx11=2,x=2,x2 2=2,=2,此解最优此解最优 max-Z=36max-Z=36 j j0 0-Z-10-8-7 0-3/2 0 1/2 0-Z1 1/2 11/20 03-1/2 0 1/2 1 01/2-1/21/2-7-10-1 1 037-2-1 0 0-Z2 1 210 02-11-1 0 1 01/2-1/21/2-6-21-1 1 036从而得 从而得 minZ=36 minZ=36 j j0 0第二阶段规划求解第一阶段规划最优第18 页，本讲稿共39 页四、单纯形法补遗进基变量相持：进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在 符 合 要 求 的

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

15、检验数j0 x1x2x3x4x5x62 4 0 0 0 02 2 1 0 0 01 2 0 1 0 0X3X4X5X600004 0 0 0 1 064-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,x600 4 0 0 0 12 4 0 0 0 01281612第20 页，本讲稿共39 页 迭代结果Cj 比值CBXBb检验数j-36x1x2x3x4x

16、5x62 4 0 0 0 00 0 1-2 0 0.5 1 0 0 1 0-0.5X3X1X5X202040 0 0-4 1 24-4320 1 0 0 0 0.250 0 0-2 0 02288j0令 令 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+48 2+48=36=36 是最优解 是最优解第21 页，本讲稿共39 页 再次迭代结果Cj 比值CBXBb检验数j-36x1x2x3x4x5x

17、62 4 0 0 0 00 0 1-1-0.25 0 1 0 0 00.25 0X3X1X6X202040 0 0-20.5 1 0 1 0 0.5-0.125 00 0 0-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 Z 2 24+47 4+47=36=36 也是最优解 也是最优解结论：非基变量检验数有为 结论：非基变量检验数有为0 0的，此线性规划有无穷多个解 的，此线性

18、规划有无穷多个解 两最优解对应可行域两顶点，两点间连线上的点都是最优解 两最优解对应可行域两顶点，两点间连线上的点都是最优解第22 页，本讲稿共39 页 解的判别：情况2 解无界maxZ=2x1+3x2+0 x3 4x1+x3=16 x1,x2,x30Cj 比值CBXBb检验数jx1x2x32 3 016 4 0 12 3 0 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-

19、x3+x4=2-2x1+3x2+x5=2 x1,x2,x3,x4,x50Cj 比值CBXBb检验数jx1x2x3x4x55 6 0-M 02 2-1-1 1 02-2 3 0 0 1X4X5-M0Max z=5x1+6x2 2x1-x2 2-2x1+3x2 2 x1,x2 05 6 0-M 0检验数j5+2M 6-M-M0 01 1-1/2-1/2 1/2 04 0 2-1 1 1-5 017/2 5/2-M+5/20第24 页，本讲稿共39 页 另例Cj 比值CBXBb检验数jx1x2x3x4x55 6 0-M 02 1 0-3/4 3/4 1/42 0 1-0.5 0.5 0.5X1X25

20、65 6 0-M 00 0 27/4-M+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检验数 j3 2 0 0-M-Mx5x6-M-M 此时检验数j 0，无进基变量,但x5,x

21、6还没有替换出去。Z 不能达到最优说明此线性规划无解 说明此线性规划无解x1x2x3x4x5x62-2 1-1 0 1 03 1-3 0-1 0 13 2 0 0-M-M检验数 jx5x62-2 1-1 0 1 03 1-3 0-1 0 12M3-2M 3-2M 2+M 2+M-M-M 0 0 0 0-M-M5M3-M 3-M 2-2M 2-2M-M-M-M-M 0 0 0 000结论：人工变量仍为基变量的，该问题无解 结论：人工变量仍为基变量的，该问题无解第26 页，本讲稿共39 页图示：无解maxZ=3x1+2 x2-2x1+x2 2 x1-3 x2 3 x1,x2 0S.t.v 用图示法

22、x1x22462460 0说明此线性规划无解 说明此线性规划无解第27 页，本讲稿共39 页五、单纯形法的矩阵计算求解用矩阵描述的线性规划的标准形式为：求解问题：问题：B B和 和 B B-1-1是什么？，待后讨论 是什么？，待后讨论第28 页，本讲稿共39 页单纯形法小结单纯形法小结1.1.根据实际问题给出数学模型，列出初始单纯形表，进行标准化 根据实际问题给出数学模型，列出初始单纯形表，进行标准化第29 页，本讲稿共39 页 添加松驰变量、人工变量列出初始单纯形表基变量中有非零的人工变量sk=max(sj)对所有aik0计算 qi=bi/aik令q=min(qi)所有sj0是否2.2.对目

23、标函数求 对目标函数求max max 的线性规划，用单纯形法计算步骤如下 的线性规划，用单纯形法计算步骤如下计算非基变量各列的检验数sj否某非基变量检验数为零否唯一最优解对任一sj0有Pj0是无界解无可行解是是无穷多最优解是迭代运算第30 页，本讲稿共39 页六、用计算机软件求解线性规划问题 关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。其中简便易行的求解软件是Excel，下面介绍其使用方法。（1）建立Excsl 工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变

24、量的关系。（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。（3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。第31 页，本讲稿共39 页 利用EXCEL求线性规划的步骤1、激活“工具栏”中的“规划求解”第32 页，本讲稿共39 页 利用EXCEL求线性规划的步骤2、根据线性规划模型建立计算模板 maxZ=3x1+5x2 x1 8 2x2 12 3x1+4 x2 36 x1、x2 0第33 页，本讲稿共39 页 利用EXCEL求线性规划的步骤3、定义决策变量及目标函数、约束条件注：s

25、umproduct表示对应乘积之和调用函数sumproduct定义实际值（E2：E5）第34 页，本讲稿共39 页 利用EXCEL求线性规划的步骤4、利用“工具栏”之“规划求解”求解第35 页，本讲稿共39 页 利用EXCEL求线性规划的步骤第36 页，本讲稿共39 页 利用EXCEL求线性规划的步骤最优解为：x1=4,x2=6 maxZ=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 页