Page 1 1 1 运运 筹筹 学学 (OperationsResearch)(OperationsResearch) Page 2 2 2 绪绪 论论 （1）运筹学简述 （2）运筹学的主要内容 （3）本课程的教材及参考书 （4）本课程的特点和要求 （5）本课程授课方式与考核 （6）运筹学在工商管理中的应用 本章主要内容： Page 3 3 3 运筹学简述运筹学简述 uu运筹学（运筹学（Operations ResearchOperations Research） uu系统工程的最重要的理论基础之一，在美系统工程的最重要的理论基础之一，在美 国有人把运筹学称之为管理科学国有人把运筹学称之为管理科学 (Management Science)(Management Science)。运筹学所研究。运筹学所研究 的问题，可简单地归结为一句话：的问题，可简单地归结为一句话： uu“ “依照给定条件和目标，从众多方案中选择依照给定条件和目标，从众多方案中选择 最佳方案最佳方案” ” uu故有人称之为最优化技术。故有人称之为最优化技术。 Page 4 4 4 运筹学简述运筹学简述 uu运筹学的历史运筹学的历史 “运作研究(Operational Research)小组”:解决复 杂的战略和战术问题。例如： 1. 如何合理运用雷达有效地对付德军德空袭 2. 对商船如何进行编队护航，使船队遭受德国潜 艇攻击时损失最少； 3. 在各种情况下如何调整反潜深水炸弹的爆炸深 度，才能增加对德国潜艇的杀伤力等。 Page 5 5 5 运筹学的主要内容运筹学的主要内容 数学规划（数学规划（线性规划、整数规划、目标线性规划、整数规划、目标 规划规划、动态规划等）、动态规划等） 图论图论 存储论存储论 排队论排队论 对策论对策论 排序与统筹方法排序与统筹方法 决策分析决策分析 Page 6 6 6 本课程的教材及参考书本课程的教材及参考书 vv选用教材选用教材 运筹学基础及应用胡运权主编 哈工大出版社 vv参考教材参考教材 运筹学教程胡运权主编 （第2版）清华出版社 管理运筹学韩伯棠主编 （第2版）高等教育出 版社 运筹学(修订版) 钱颂迪主编 清华出版社 Page 7 7 7 本课程的特点和要求本课程的特点和要求 先修课：高等数学，基础概率、线性代数 特点：系统整体优化；多学科的配合；模型方法的应用 运筹学的研究的主要步骤： 真实系统 系统分析 问题描述 模型建立 与修改 模型求解 与检验 结果分析与 实施 数据准备 Page 8 8 8 本课程授课方式与考核本课程授课方式与考核 学科总成绩 平时成绩 （40） 课堂考勤 （50） 平时作业 （50） 期末成绩 （60） 讲授为主，结合习题作业 Page 9 9 9 运筹学在工商管理中的应用运筹学在工商管理中的应用 uu运筹学在工商管理中的应用涉及几个方面运筹学在工商管理中的应用涉及几个方面 ： 1. 生产计划 2. 运输问题 3. 人事管理 4. 库存管理 5. 市场营销 6. 财务和会计 uu另外，还应用于设备维修、更新和可靠性另外，还应用于设备维修、更新和可靠性 分析，项目的选择与评价，工程优化设计分析，项目的选择与评价，工程优化设计 等。等。 Page 10 1010 运筹学在工商管理中的应用运筹学在工商管理中的应用 uuInterfaceInterface上发表的部分获奖上发表的部分获奖 项目项目 组织组织应用应用效果效果 联合航空公司联合航空公司在满足乘客需求的前提下，以最在满足乘客需求的前提下，以最 低成本进行订票及机场工作班低成本进行订票及机场工作班 次安排次安排 每年节约成本每年节约成本600600万美万美 元元 CitgoCitgo石油公司石油公司优化炼油程序及产品供应、配送优化炼油程序及产品供应、配送 和营销和营销 每年节约成本每年节约成本70007000万万 AT Page 26 2626 线性规划问题的数学模型线性规划问题的数学模型 标准形式如下： Page 27 2727 线性规划问题的数学模型线性规划问题的数学模型 uu4. 4. 线性规划问题的解线性规划问题的解 线性规划问题 求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。 Page 28 2828 线性规划问题的数学模型线性规划问题的数学模型 可行解：满足约束条件、的解为可行解。所有可行解 的集合为可行域。 最优解：使目标函数达到最大值的可行解。 基：设A为约束条件的mn阶系数矩阵(m0 40 10 换 出 行 将3化为1 5/3 1 180 1/301/310 11/330 30 05/304/3 乘 以 1/3 后 得 到 103/5 1/5 18 011/52/54 00 11 Page 48 4848 单纯形法的计算步骤单纯形法的计算步骤 uu例例1.9 1.9 用单纯形法求解用单纯形法求解 解：将数学模型化为标准形式： 不难看出x4、x5可作为初始基变量，列单纯形表计算。 Page 49 4949 单纯形法的计算步骤单纯形法的计算步骤 c c j j 1 1 2 2 1 1 0 0 0 0 i i c cB B 基变基变 量量 b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 0 0 x x4 4 1515 2 2 -3-3 2 2 1 1 0 0 0 0 x x5 5 20201/1/ 3 3 1 1 5 5 0 0 1 1 1 1 2 2 1 1 0 0 0 0 0 0 x x4 4 2 2 x x2 2 20 x x2 2 2 2 1/3150120 75301713 1/30902 25 60 x x1 1 11017/31/3125 0128/9-1/92/3 35/3 00-98/9 -1/9 -7/3 Page 50 5050 单纯形法的计算步骤单纯形法的计算步骤 学习要点： 1. 线性规划解的概念以及3个基本定理 2. 熟练掌握单纯形法的解题思路及求解步骤 Page 51 5151 单纯形法的进一步讨论人工变单纯形法的进一步讨论人工变 量法量法 uu人工变量法：人工变量法： uu前面讨论了在标准型中系数矩阵有单位前面讨论了在标准型中系数矩阵有单位 矩阵，很容易确定一组基可行解。在实际矩阵，很容易确定一组基可行解。在实际 问题中有些模型并不含有单位矩阵，为了问题中有些模型并不含有单位矩阵，为了 得到一组基向量和初基可行解，在约束条得到一组基向量和初基可行解，在约束条 件的等式左端加一组虚拟变量，得到一组件的等式左端加一组虚拟变量，得到一组 基变量。这种人为加的变量称为人工变量基变量。这种人为加的变量称为人工变量 ，构成的可行基称为人工基，用大，构成的可行基称为人工基，用大MM法或法或 两阶段法求解，这种用人工变量作桥梁的两阶段法求解，这种用人工变量作桥梁的 求解方法称为人工变量法。求解方法称为人工变量法。 Page 52 5252 单纯形法的进一步讨论人工变单纯形法的进一步讨论人工变 量法量法 uu例例1.10 1.10 用大用大MM法解下列线性规划法解下列线性规划 解：首先将数学模型化为标准形式 系数矩阵中不存在 单位矩阵，无法建 立初始单纯形表。 Page 53 5353 单纯形法的进一步讨论人工变单纯形法的进一步讨论人工变 量法量法 uu故人为添加两个单位向量，得到人工变量单故人为添加两个单位向量，得到人工变量单 纯形法数学模型：纯形法数学模型： 其中：M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；再用前面介 绍的单纯形法求解该模型，计算结果见下表。 Page 54 5454 单纯形法的进一步讨论人工变单纯形法的进一步讨论人工变 量法量法 c c j j 3 3 2 2 -1-1 0 0 0 0 -M-M-M-M C CB B X XB B b b x x1 1 x x2 2 x x3 3 x x4 4 x x5 5 x x6 6 x x7 7 i i -M-M x x6 6 4 4 -4-4 3 3 1 1 -1-1 0 0 1 1 0 0 4 4 0 0 x x5 5 1010 1 1 -1-1 2 2 0 0 1 1 0 0 0 0 5 5 -M-M x x7 7 1 1 2 2 -2-2 1 1 0 0 0 0 0 0 1 1 1 1 3-3- 2 2 MM 2+M2+M - - 1+21+2 MM -M-M 0 0 x x6 6 3 3 -6-6 5 5 0 0 -1-1 0 0 1 1 3/53/5 -M-M x x5 5 8 8 -3-3 3 3 0 0 0 0 1 1 0 0 8/38/3 -1-1 x x3 3 1 1 2 2 -2-2 1 1 0 0 0 0 0 0 5-5- 6 6 MM 5M5M 0 0 -M-M 0 0 0 0 2 2 x x2 2 3/53/5 6 6 / / 5 5 1 1 0 0 1/1/ 5 5 0 0 -M-M x x5 5 31/31/ 5 5 3/53/5 0 0 0 0 3/53/5 1 1 31/31/ 3 3 -1-1 x x3 3 11/11/ 5 5 2 2 / / 5 5 0 0 1 1 2/2/ 5 5 0 0 5 5 0 0 0 0 0 0 0 0 2 2 x x2 2 1313 0 0 1 1 0 0 1 1 2 2 3 3 x x1 1 31/31/ 3 3 1 1 0 0 0 0 1 1 5/35/3 -1-1 x x3 3 19/19/ 3 3 0 0 0 0 1 1 0 0 2/32/3 0 0 0 0 0 0 -5-5 - - 2 2 5 5 / / 3 3 Page 55 5555 单纯形法的进一步讨论人工变单纯形法的进一步讨论人工变 量法量法 解的判别： 1）唯一最优解判别：最优表中所有非基变量的检验数非零, 则线 规划具有唯一最优解。 2）多重最优解判别：最优表中存在非基变量的检验数为零, 则线则性规划具有多重最优解（或无穷多最优解）。 3）无界解判别：某个k0且aik（i=1，2,m）则线性 规划具有无界解。 4）无可行解的判断：当用大M单纯形法计算得到最优解并 且存在Ri0时，则表明原线性规划无可行解。 5）退化解的判别：存在某个基变量为零的基本可行解。 Page 56 5656 单纯形法的进一步讨论人工变单纯形法的进一步讨论人工变 量法量法 uu单纯性法小结单纯性法小结: : 建建 立立 模模 型型 个个 数数取取 值值右右 端端 项项 等式或等式或 不等式不等式 极大或极小极大或极小 新加变新加变 量量 系系 数数 两两 个个 三个三个 以上以上 x x j j 0 0 x x j j 无无 约束约束 x xj j 0 0 b b i i 0 0 b bi i mi 时，企业愿意 购进这种资源，单位纯利为yi*mi ，则有利可图；如果yi* mi 则购进资源i，可获单位纯利yi*mi 若yi* mi则转让资源i ，可获单位纯利miyi Page 99 9999 对偶问题的经济解释影子价格对偶问题的经济解释影子价格 uu3 3）影子价格在资源利用中的应用）影子价格在资源利用中的应用 uu根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理: : uu Y Y* *X Xs s =0 , Y=0 , Y s sX X * * =0=0 uu表明生产过程中如果某种资源表明生产过程中如果某种资源bibi未得到充未得到充 分利用时，该种资源的影子价格为分利用时，该种资源的影子价格为0 0；若当；若当 资源资源的影子价格不为资源资源的影子价格不为0 0时，表明该种资时，表明该种资 源在生产中已耗费完。源在生产中已耗费完。 Page 100 100100 对偶问题的经济解释影子价格对偶问题的经济解释影子价格 uu4 4）影子价格对单纯形表计算的解释）影子价格对单纯