运筹学1-教学讲解课件.ppt

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

2、案”故有人称之为最优化技术。运筹学简述 运筹学的历史“运作研究运作研究(Operational Research)小组小组”:解决复解决复杂的战略和战术问题。例如：杂的战略和战术问题。例如：如何合理运用雷达有效地对付德军德空袭如何合理运用雷达有效地对付德军德空袭对商船如何进行编队护航，使船队遭受德国潜对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；艇攻击时损失最少；1.在各种情况下如何调整反潜深水炸弹的爆炸深在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。度，才能增加对德国潜艇的杀伤力等。运筹学的主要内容 数学规划（线性规划、整数规划、目标规划、动态规划等）

3、图论 存储论 排队论 对策论 排序与统筹方法 决策分析本课程的教材及参考书v选用教材 运筹学基础及应用胡运权主编 哈工大出版社v参考教材 运筹学教程胡运权主编（第2版）清华出版社 管理运筹学韩伯棠主编（第2版）高等教育出版社 运筹学(修订版)钱颂迪主编 清华出版社 本课程的特点和要求先修课：先修课：高等数学，基础概率、线性代数高等数学，基础概率、线性代数特点：特点：系统整体优化；多学科的配合；模型方法的应用系统整体优化；多学科的配合；模型方法的应用运筹学的研究的主要步骤：运筹学的研究的主要步骤：真实系统真实系统系统分析系统分析问题描述问题描述模型建立模型建立与修改与修改模型求解模型求解与检验与

4、检验结果分析与结果分析与实施实施数据准备数据准备本课程授课方式与考核学科总成绩学科总成绩平时成绩平时成绩（4040）课堂考勤课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（6060）讲授为主，结合习题作业讲授为主，结合习题作业运筹学在工商管理中的应用运筹学在工商管理中的应用涉及几个方面：生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计1.另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。运筹学在工商管理中的应用 Interface上发表的部分获奖项目组织应用效果联合航空公司在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排每年节

5、约成本600万美元Citgo石油公司优化炼油程序及产品供应、配送和营销每年节约成本7000万AT&T优化商业用户的电话销售中心选址每年节约成本4.06亿美元，销售额大幅增加标准品牌公司控制成本库存（制定最优再定购点和定购量确保安全库存）每年节约成本380万美元法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量每年节约成本1500万美元，年收入大幅增加。Taco Bell优化员工安排，以最低成本服务客户每年节约成本1300万美元Delta航空公司优化配置上千个国内航线航班来实现利润最大化每年节约成本1亿美元“管理运筹学”软件介绍“管理运筹学”2.0版包括：线性规划、运输问题、整数规划（0-1整

6、数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。Chapter1 线性规划(Linear Programming)LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 LP模型的应用模型的应用线性规划问题的数学模型 1.规划问题生产和经营管理中经常提出如何合理安排，使人力、生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，物力等各种资源得到充分利用，获得最大的效益

7、，这就是规划问题。这就是规划问题。（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大.）线性规划问题的数学模型 例1.1 如图所示，如何截取x使铁皮所围成的容积最大？x xa a xxav 220 dxdv0)2()2()

8、2(22 xaxxa6ax 线性规划问题的数学模型例例1.2 某企业计划生产甲、乙两种产品。这些产品分某企业计划生产甲、乙两种产品。这些产品分别要在别要在A、B、C、D、四种不同的设备上加工。按工、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？企业总的利润最大？设 备产 品 A B C D利润（元）甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12线性规划问题的数学模型 解：设x1

9、、x2分别为甲、乙两种产品的产量，则数学模型为：线性规划问题的数学模型线性规划问题的数学模型00 )()(min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )(Z(min)max 11nxmbxaxcjnjijijnjjj简写为：简写为：线性规划问题的数学模型)(21ncccC nxxX1 mjjjaaP1 mbbB1 0)(min)maxXBxpCXzjj其中：其中：线性规划问题的数学模型 mnmnaaaaA1111 0)(min)maxXBAXCXZ其中：其中：)(21ncccC nxxX1 mb

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

11、到上式。，可得到上式。zz jjxczzmax即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx 0,jjxx 变量的变换变量的变换线性规划问题的数学模型 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0iniinjijxbxxa称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然0jxjjxx0 jx线性规划问题的数学模型例例1.3 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式 ,0,52324 7 532

12、min321321321321321无约束xxxxxxxxxxxxxxxZ用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以33xx 3x0,33 xx线性规划问题的数学模型(2)第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3)第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4)第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以

13、，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;线性规划问题的数学模型 0,5 )(252 )(7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：标准形式如下：线性规划问题的数学模型 4.线性规划问题的解 )3(,2,1,0)2(),2,1(.)1(max11njxmibxatsx

14、cZjnjijijnjjj线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。线性规划问题的数学模型 可行解可行解：满足约束条件：满足约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。最优解最优解：使目标函数达到最大值的可行解。：使目标函数达到最大值的可行解。基：基：设设A为约束条件为约束条件的的mn阶系数矩阵阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/330

15、3005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011单纯形法的计算步骤 例1.9 用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：解：将数学模型化为标准形式：5,2,1,02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。单纯形法的计算步骤cj12100icB基变量bx1x2x3x4x50 x4152-32100 x5201/315011210

16、00 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9-1/9-7/3j 单纯形法的计算步骤学习要点：学习要点：1.线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2.熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤单纯形法的进一步讨论人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变

17、量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论人工变量法 例1.10 用大M法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5,2,1,012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。单纯形法的进一步讨论人工变量法 故人为添加两个单位向量，得到人工

18、变量单纯形法数学模型：7,2,1,012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712

19、-21000113-2M2+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3j j j j 单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在

20、非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。单纯形法的进一步讨论人工变量法 单纯性法小结

21、:建立模型个 数取 值右 端 项等式或不等式极大或极小新加变量系数两个三个以上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；若当资源资源的影子

22、价格不为0时，表明该种资源在生产中已耗费完。对偶问题的经济解释影子价格 4）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j种产品的价格种产品的价格;表示生产该种产品所表示生产该种产品所消耗的各项资源的影子价格的总和消耗的各项资源的影子价格的总和,即产品的隐含成本。即产品的隐含成本。miiijya1当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产品有，表明生产该项产品有利，可在计划中安排；否则利，可在计划中安排；否则 ，用这些资源生产别的，用这些资源生产别的产品更有利，不在生产中安排该产品。产品更有利，不在生产中安排该产品。0 j 0 j