运筹学完整版课件.ppt

1、运 筹 学(Operations Research)梁 伟 河海大学商学院（常州）运 筹 帷 幄 之 中决 胜 千 里 之 外绪 论Introduction第一章绪 论（1）运筹学简述（2）运筹学的主要内容（3）本课程的教材及参考书（4）本课程的特点和要求（5）本课程授课方式与考核（6）运筹学在经济管理中的应用本章主要内容：绪 论绪 论运筹学简述 运筹学（Operations Research,简写OR）系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方

2、案”故有人称之为最优化技术。绪 论运筹学的历史与发展 “运筹学思想的出现可以追溯到很早“田忌赛马”。齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王 上中 下 田忌 下上 中绪 论丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。绪

3、 论 国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。运筹学简述“运作研究(Operational Research)小组”:解决复杂的战略和战术问题。例如：1.如何合理运用雷达有效地对付德军德空袭2.对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；3.在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。绪 论 在生产管理方面的应用，最

4、早是1939年前苏联的康特洛为奇提出了生产组织与计划中的线性规划问题，并给出解乘数法的求解方法，出版了第一部关于线性规划的著作生产组织与计划中的数学方法。但当时并没有引起重视，直到1960年康特洛为奇再次出版了最佳资源利用的经济计算，才受到国内外的一致重视，为此康特洛为奇获得了诺贝尔经济学奖。线性规划提出后很快受到经济学家的重视，如：二次世界大战中从事运输模型研究的美国经济学家库普曼斯（T.C.Koopmans），他很快看到了线性规划在经济中应用的意义，并呼吁年轻的经济学家要关注线性规划。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。绪 论 20世纪50年代中期，钱学森、许国志

5、等教授在国内全面介绍和推广运筹学知识，1956年，中国科学院成立第一个运筹学研究室，1957年运筹学运用到建筑和纺织业中，1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”，1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅，1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。绪 论成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优

6、化观念不断变化运筹学的发展趋势运筹学的主要内容数学规划（线性规划、整数规划、目标规划、动态规划等）图论存储论排队论对策论排序与统筹方法决策分析运筹学的主要内容 1.线性规划（Linear Program）是一个成熟的分支，它有效的算法单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。2.整数规划(Integrate Program)：在线性规划的基础上，变量加上整数约束。3.非线性规划(Nonlinear Program)：目标函数和约束条件是非线性函数，如证券投资组合优化:如何合理投资使风险最小。4.动态规划(Dynamic Program)：多阶段决策问题。是美国贝尔曼于1951

7、年提出的。运筹学的主要内容 5、图与网络(Graph Theory and Network)：中国邮递员问题、哥尼斯堡城问题、最短路、最大流问题。6、存储论（Inventory Theory)：主要解决生产中的库存问题，订货周期和订货量等问题。7、排队论(Queue Theory)：主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。8、对策论(Game Theory)：主要研究具有斗争性质的优化问题。9、决策分析(Decision Analysis)：主要研究定量化决策。本课程的教材及参考书选用教材 运筹学教程胡运权主编（第3版）清华出版社参考教材 运筹学基础及应用胡运权主编

8、 哈工大出版社 管理运筹学韩伯棠主编（第2版）高等教育出版社 运筹学(修订版)钱颂迪主编 清华出版社 本课程的特点和要求先修课：高等数学，基础概率、线性代数特点：系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：真实系统系统分析问题描述模型建立与修改模型求解与检验结果分析与实施数据准备本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（4040）课堂考勤课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（6060）讲授为主，结合习题作业运筹学在经济管理中的应用 运筹学在经济管理中的应用涉及的方面：1.生产计划2.运输问题3.人事管理4.库存管理5.市场营销6

9、.财务和会计7.物流配送 另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。“管理运筹学”软件介绍“管理运筹学”2.0版包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。运 筹 帷 幄 之 中决 胜 千 里 之 外线 性 规 划及单纯形法Linear Programming第一章Chapter1 线性规划(Linear Programming)LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论人工

10、变量法 LP模型的应用线性规划问题的数学模型 1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）线性规划问题的数学模型 例1.1 如图所示，如何截取x使铁皮所围成的容积最大？xa xxav 220 dxdv0)2()2()2(22 xaxxa6ax 线性规划问题的数学模型例1.2 某厂生产两种产品，下表给出了单位产

11、品所需资源及单位产品利润 问：应如何安排生产计划，才能使总利润最大？解：1.决策变量：设产品I、II的产量 分别为 x1、x22.目标函数：设总利润为z，则有：max z=2 x1+x23.约束条件：5x2 15 6x1+2x2 24 x1+x2 5 x1，x20线性规划问题的数学模型例1.3 已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。设 备产 品 A B C D利润（元）2 1 4 0 2 2 2 0 4 3 有 效 台 时12 8 16 12解：1.决策变量：设产品I、II的产量分别为 x1、x22.目标函数：设总利润为z，则有：max z=2 x1+x

12、23.约束条件：x1 0,x2 0 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12线性规划问题的数学模型例1.4 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量 解：要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。1.决策变量：设四种原料的使用 量分别为：x1、x2、x3、x42.目标函数：设总成本为z min z=5 x1+6 x2+7 x3+8 x43.约束条件：x1+2x2+x3+x4 160 2x1 +4 x3+2 x4 200 3x1 x2+x3+2 x4 180 x1

13、、x2、x3、x4 0 例1.5 某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：航线号航线号船队船队类型类型编队形式编队形式货运成本货运成本（千元队）（千元队）货运量货运量（千吨）（千吨）拖轮拖轮A型型驳船驳船B型型驳船驳船1112362521436202322472404142720船只种类船只种类船只数船只数拖拖 轮轮30A型驳船型驳船34B型驳船型驳船52航线号航线号合同货运量合同货运量12002400问：应如何编队，才能既完成合同任务，又使总货运成本为最小？解：设：xj为第j号类型船队的队数（j=1，2，3，4），z 为总货运成本则：min z=36x1+

14、36x2+72x3+27x4 x1+x2 +2x3+x4 30 2x1 +2x3 34 4x2+4x3+4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 （j=1,2,3,4）线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型00 )()(min)max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )(Z (min)max 11nxmbxaxcjnjijijnjjj 简写为：线性规划问题的数学模型)(21ncccC nxxX1 mjjja

15、aP1 mbbB1 0)(min)maxXBxpCXzjj其中：线性规划问题的数学模型 mnmnaaaaA1111 0)(min)maxXBAXCXZ其中：)(21ncccC nxxX1 mbbB1线性规划问题的数学模型 6.线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,2,1,2,1,0.max11 特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。线性规划问题的数学模型 目标函数的转换 如果是求极小值即 ，则可将目标函数乘以(-1)，可化为求极大值问题。jjxczmin也就是：令 ，可得

16、到上式。zz jjxczzmax即 若存在取值无约束的变量 ，可令 其中：jxjjjxxx 0,jjxx 变量的变换线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。ijijbxa0 iniinjijxbxxa称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量 常量 bi0 的变换:约束方程两边乘以（1）线性规划问题的数学模型例1.6 将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321无无约约束束xxxxxxxxxxxxxxxZ用 替换 ，且 解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所

17、以33xx 3x0,33 xx线性规划问题的数学模型(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然;线性规划问题的数学模型 0,5 )(252 )(7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：例1.7

18、 将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321xxxxxxxxxxxxxxxZ为无约束（无非负限制）解:用 替换 ，且 ，54xx 3x0,54 xx将第3个约束方程两边乘以（1）将极小值问题反号，变为求极大值标准形式如下：0,5 )(252 )(7 )(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ76,xx引入变量 无约束2121212,0435832xxxxxxx-xminZ10 x,x,x,x,xx)x(xxx)x(xx)x(xxZaxm111165436

19、4354343435832例1.8 将线性规划问题化为标准型解：例1.9 将线性规划问题化为标准型解：Min f=-3 x1+5 x2+8 x3 -7 x4s.t.2 x1 -3 x2+5 x3+6 x4 28 4 x1+2 x2+3 x3-9 x4 39 6 x2+2 x3+3 x4 -58 x1,x3 ,x4 0；x2无约束 Max z=3x15x2+5x2”8x3+7x4 s.t.2x13x2+3x2”+5x3+6x4+x5=28 4x1+2x2-2x2”+3x3-9x4-x6=39 -6x2+6x2”-2x3-3x4-x7=58 x1,x2,x2”,x3,x4,x5,x6,x7 0 线

20、性规划问题的数学模型 7.线性规划问题的解 )3(,2,1,0)2(),2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。线性规划问题的数学模型 可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件的mn阶系数矩阵(m04010换出行将3化为15/311801/301/31011/3303005/304/3乘以1/3后得到103/51/518011/52/540011单纯形法的计算步骤 例1.1

21、3 用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：5,2,1,02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出x4、x5可作为初始基变量，列单纯形表计算。单纯形法的计算步骤cj12100icB基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 2021/3150120753017131/30902j 256011017/31/31250128/9-1/9 2/335/300-98/9-1/9-7/3j 0,1

22、24 16 482122232max2121212121xxxxxxxxxxZ变成标准型 0,12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ单纯形法的计算步骤 例1.14 用单纯形法求解约束方程的系数矩阵 654321100040010004001021000122ppppppA IppppB100001000010000165436543 xxxx,21xx,为基变量为非基变量I 为单位矩阵且线性独立单纯形法的计算步骤cjcBxBb0000 x3x4x5x61281612 2x2 单纯形法的计

23、算步骤学习要点：1.线性规划解的概念以及3个基本定理2.熟练掌握线性规划问题的标准化 3.熟练掌握单纯形法的解题思路及求解步骤单纯形法的进一步讨论人工变量法 人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论人工变量法 例1.10 用大M法解下列线性规划 012210243423max32132132132

24、1321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式 5,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在单位矩阵，无法建立初始单纯形表。单纯形法的进一步讨论人工变量法 故人为添加两个单位向量，得到人工变量单纯形法数学模型：123671234612351237max3243 4 2 10 22 10,1,2,7jZxxxMxMxxxxxxxxxxxxxxxjL其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。单纯

25、形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j 单纯形法的进一步讨论人工变量法 例1.11 用大M法解

26、下列线性规划12312312313123max3 2114232 +10Zxxxxxxxxxxxxxx、解：首先将数学模型化为标准形式1231234123513max3 2114232 10,1,2,5jZxxxxxxxxxxxxxxjL系数矩阵中不存在单位矩阵，无法建立初始单纯形表。单纯形法的进一步讨论人工变量法 故人为添加两个单位向量，得到人工变量单纯形法数学模型：1234567123412356137max3 3 11-4 2 +3 2 10,1,2,7jZxxxxxMxMxxxxxxxxxxxxxxjL+0+0 其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定

27、的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。单纯形法的进一步讨论人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011Z-4M3-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x31-2010001Z-M-11-1+M00-M0-3M+1j 单纯形法的进一步讨论人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2

28、010001Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3单纯形法的进一步讨论两阶段法 用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。第一阶段：在原线性规划问题中加入人工变量，构造如下模型：1111 11111 1min00 nn mnnnnmmnnn mmxxxxa xa xxba xaxxbLLLMMOL1 0 n mxxL 对上述模型求解（单纯形法），若=0,说明问题存在基可行解，可以进行第二个阶段；

29、否则，原问题无可行解，停止运算。单纯形法的进一步讨论两阶段法第一阶段的线性规划问题可写为：67123412356137min 2 =11 42 3 2 1 xxxxxxxxxxxxxx127 ,0 x xx，第一阶段单纯形法迭代的过程见下表（注意：没有化为极大化问题）单纯形法的进一步讨论两阶段法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-2010001146-1-301000 x4103-20100-11x610100-11-210 x31-201000110-1001030 x4123001-22-

30、50 x210100-11-20 x31-201000000000011单纯形法的进一步讨论两阶段法 第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例：x,x,x x x x xx xxx xxx x xxxZmax 0123241123721731653214321321，单纯形法的进一步讨论两阶段法cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-

31、4/3Z2000-1/3-1/3第二阶段：54321003xxxxxZmax 最优解为（4 1 9 0 0），目标函数 Z=2单纯形法的进一步讨论 通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。无可行解 C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6/1-3/1 Z-7M

32、-6-4M-15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1-Z Z -3+M 0 -3-M 0 -M -2 0 2-M-3-M-2 x1x7x2 313 1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例运算到检验数全负为止，仍含有人工变量，无可行解。单纯形法的进一步讨论 无最优解与无可行解时两个不同的概念。无可行解是指原

33、规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解 无最优解C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z022001=20因 但 所以原问题无最优解1-1P=01-2

34、 退化 即计算出的（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是退化（会产生退化解）。为避免出现计算的循环，勃兰特(Bland)提出一个简便有效的规则（摄动法原理）：当存在多个 时，选下标最小的非基变量为换入变量；(2)当值出现两个以上相同的最小值时，选下标最小的基变量为换出变量。0j000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800Z1100 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-110

35、01001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。可得最优解maxZ=，X1,0,1,0,3T 无穷多最优解 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例：最优表：非基变量检验数，所以有无穷多最优解。C 1 2 0 0 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0

36、 -2 12/23/1-Z8 0 0 0 0 -14=0单纯形法的进一步讨论解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。单纯形法的进一步讨论 单纯性法小结:建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极

37、小极大或极小新加变新加变量系数量系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi mi 时，企业愿意购进这种资源，单位纯利为yi*mi，则有利可图；如果yi*mi 则购进资源i，可获单位纯利yi*mi 若yi*mi则转让资源i，可获单位纯利miyi对偶问题的经济解释影子价格 3）影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理:Y*Xs=0 ,YsX*=0 表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。对偶问题的经济解释影子价格 4）影子价格对单纯形表计算的解释单纯形表中的

38、检验数 miiijjjBjjyacPBCc11其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。miiijya1当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。0 j 0 j 对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB=b为非负），有最优解。否则，通过变换基解，直到找到原问

39、题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得。对偶单纯形法找出一个DP的可行基LP是否可行（XB 0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束对偶单纯形法例2.9 用对偶单纯形法求解：)3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解:（1）将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行（求max问题）。对偶单纯形法 014 5 12 3210 2215129max61632153214321321xxxxxxxxxxxxxxxxZcj-9-12-

40、15000bcBxBx1x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14j-9-12-150000i对偶单纯形法cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141

41、/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14ij j 对偶单纯形法cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3j 原问题的最优解为：X*=（2,2,2,0,0,0），Z*=72 由定理4，其对偶问题的最优解为：Y*=（1/3,3,7/3），W*=72对偶单纯形法 对偶单纯形法应注意的问题：用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解 初

42、始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则 最小比值中 的绝对值是使得比值非负，在极小化问题j0，分母aij0 这时必须取绝对值。在极大化问题中，j0，分母aij0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成ijja 这里j 0在求k时就可以不带绝对值符号。32134maxxxxz ijja 对偶单纯形法 对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是 0minikikiiaa

43、b其目的是保证下一个对偶问题的基本解可行 0|minljljjjaa 对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。0|min iilbbb灵敏度分析11mjjijijBjica xcC B P 1jjP=BP1bBb线性规划问题的标准形式11max.1,2,0,1,2,LLnjjjnijjijjZc xa xbs timxjnmax.0ZCXAXbs tX令：灵敏度分析一、价值系数cj的变化分析例1：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划 0,45 802903 45 max21212121

44、21xxxxxxxxxxZ问题：（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。灵敏度分析1212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 优 表如下：灵敏度分析4 =c25 05 =52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12j000c2-55-2c2

45、最优解X*=（35，10，25，0，0）保持不变。（1）灵敏度分析（2）Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2用对偶单纯形法是求解得。x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2灵敏度分析二、右端常数bi的变化分析XB=B1b例2：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55

46、，求出新的最优解。0,45 802903 45Z max2121212121xxxxxxxxxx灵敏度分析cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-32 1-01 1 05-2 1最优基：B=I=（P3，P1，P2）B1=最优解：X*=（35，10，25，0，0）灵敏度分析（1）XB=B1b=2 1-01 1 05-2 190803b80802333bb250 -5b90803b=0 B1解得40b350，即当b340，50 时，最优基B 不变z*=5（80b3）+4（80+2b3）=80+3b3333b2

47、80b805b-250*2*1*3xxx=灵敏度分析（2）当 b3=55 时 80802333250-5bbb 30 25 25=x2 x1x50-11/5-3/500j0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j-101030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045Cj最优解：X*=（30，20，0，0，5）灵敏度分析三、增加一个变量 的分析jx例3：（续例1）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6=。问它的价值系数c6符合什么条件才必须安排它的生产？

48、设c6=3，新的最优生产计划是什么？3/211/2 6=c6CBB1P6=c6（0，5，4）=c65/202/116P2 1-01 1 05-2 12/112/302/11=B1P6=灵敏度分析Cj540003CBXBbx1x2x3x4x5x60 x3250012-515x1351001-11/26 x2 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/20灵敏度分析四、增加新的约束条件的分析例4:假设在例1中，还要考虑一个新的资源约束：4x1+2x2150121212121212ma

49、x543902804215045,0 zxxxxxx x xxxxx12123124125122516346max54394028045,00215 zxxxxx xx x x x x x x xxx xxxx标准化灵敏度分析cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104x210010-1200 x6 150 420001j 000-1-300 x3250012-505

50、x1351001-104x210010-1200 x6-10 000-201j000-3-300 x3150010-515x1301000-11/24x21501002-1/20 x4 5 00010-1/2j0000-3-1/2灵敏度分析1.cj和bi同时变化的情况五、其它变化情况的分析例5:在例1中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？1212121212max5439028045,0 zxxxxxx x xx x2 1-01 1 05-2 1B1=B =5580902 1-01 1 05-2 1558090302525代替最优表的b列，并把c2改为6灵敏度分