运筹学完整版ppt课件.ppt

《运筹学完整版ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学完整版ppt课件.ppt（575页珍藏版）》请在金锄头文库上搜索。

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 他很快看到了线性规划在经济中应用的意义 并呼吁年轻的经济 学家要关注线性

5、规划 其中阿罗 萨谬尔逊 西蒙 多夫曼和胡尔 威茨等都获得了诺贝尔奖 绪绪 论论 20世纪50年代中期 钱学森 许国志等教授在国内全面介 绍和推广运筹学知识 1956年 中国科学院成立第一个运筹学研 究室 1957年运筹学运用到建筑和纺织业中 1958年提出了图上 作业法 山东大学的管梅谷教授提出了 中国邮递员问题 1970年 在华罗庚教授的直接指导下 在全国范围内推广统筹方 法和优选法 1978年11月 在成都召开了全国数学年会 对运筹学的理论 与应用研究进行了一次检阅 1980年4月在山东济南正式成立了 中国数学会运筹学会 1984年在上海召开了 中国数学会运 筹学会第二届代表大会暨学术交

6、流会 并将学会改名为 中国 运筹学会 绪绪 论论 成熟的学科分支向纵深发展 新的研究领域产生 与新的技术结合 与其他学科的结合加强 传统优化观念不断变化 运筹学的发展趋势 运筹学的主要内容运筹学的主要内容 数学规划 线性规划 整数规划 目标规划 动态 规划等 图论 存储论 排队论 对策论 排序与统筹方法 决策分析 运筹学的主要内容运筹学的主要内容 1 线性规划 Linear Program 是一个成熟的分支 它有 效的算法 单纯形法 主要解决生产计划问题 合理下料 问题 最优投资问题 2 整数规划 Integrate Program 在线性规划的基础上 变 量加上整数约束 3 非线性规划 No

7、nlinear Program 目标函数和约束条件 是非线性函数 如证券投资组合优化 如何合理投资使风险 最小 4 动态规划 Dynamic Program 多阶段决策问题 是美国 贝尔曼于1951年提出的 运筹学的主要内容运筹学的主要内容 5 图与网络 Graph Theory and Network 中国邮递员问 题 哥尼斯堡城问题 最短路 最大流问题 6 存储论 Inventory Theory 主要解决生产中的库存问 题 订货周期和订货量等问题 7 排队论 Queue Theory 主要研究排队系统中的系统排 队和系统拥挤现象 从而评估系统的服务质量 8 对策论 Game Theory

8、 主要研究具有斗争性质的优化问 题 9 决策分析 Decision Analysis 主要研究定量化决策 本课程的教材及参考书本课程的教材及参考书 选用教材 运筹学教程 胡运权主编 第3版 清华出版社 参考教材 运筹学基础及应用 胡运权主编 哈工大出版社 管理运筹学 韩伯棠主编 第2版 高等教育出版社 运筹学 修订版 钱颂迪主编 清华出版社 本课程的特点和要求本课程的特点和要求 先修课 高等数学 基础概率 线性代数 特点 系统整体优化 多学科的配合 模型方法的应用 运筹学的研究的主要步骤 真实系统 系统分析 问题描述 模型建立 与修改 模型求解 与检验 结果分析与 实施 数据准备 本课程授课方

9、式与考核本课程授课方式与考核 学科总成绩 平时成绩 40 课堂考勤 50 平时作业 50 期末成绩 60 讲授为主 结合习题作业 运筹学在经济管理中的应用运筹学在经济管理中的应用 运筹学在经济管理中的应用涉及的方面 1 生产计划 2 运输问题 3 人事管理 4 库存管理 5 市场营销 6 财务和会计 7 物流配送 另外 还应用于设备维修 更新和可靠性分析 项目的选择 与评价 工程优化设计等 管理运筹学管理运筹学 软件介绍软件介绍 管理运筹学 2 0版包括 线性规划 运输问题 整数规划 0 1整数 规划 纯整数规划和混合整数规划 目标规划 对策论 最短路径 最小生成树 最大流量 最小费用最大流

10、关键路径 存储论 排队论 决策分析 预测问题和层次分析法 共15个子模块 运 筹 帷 幄 之 中 决 胜 千 里 之 外 线 性 规 划及单纯形法 Linear Programming 第一章 Chapter1 线性规划 Linear Programming LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论 人工变量法 LP模型的应用 本章主要内容 本章主要内容 线性规划问题的数学模型线性规划问题的数学模型 1 规划问题 生产和经营管理中经常提出如何合理安排 使人力 物力等各种资源得到充分利用 获得最大的效益 这就是规划问题 线性规划通常解决下列两类问题 线性规划通常解决下列两类问题 1

11、 当任务或目标确定后 如何统筹兼顾 合理安排 用 最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 2 在一定的资源条件限制下 如何组织安排生产获得最 好的经济效益 如产品量最多 利润最大 线性规划问题的数学模型线性规划问题的数学模型 例1 1 如图所示 如何截取x使铁皮所围成的容积最 大 x a 线性规划问题的数学模型线性规划问题的数学模型 例1 2 某厂生产两种产品 下表给出了单位产品所需资 源及单位产品利润 问 应如何安排生产计划 才 能使总利润最大 解 1 决策变量 设产品I II的产量 分别为 x1 x2 2 目标函数 设总利润为z 则有 max z 2 x1

12、 x2 3 约束条件 5x2 15 6x1 2x2 24 x1 x2 5 x1 x2 0 线性规划问题的数学模型线性规划问题的数学模型 例1 3 已知资料如下表所示 问如何安排生产才能使利润 最大 或如何考虑利润大 产品好销 设 备 产 品 A B C D 利润 元 2 1 4 0 2 2 2 0 4 3 有 效 台 时 12 8 16 12 解 1 决策变量 设产品I II的产量 分别为 x1 x2 2 目标函数 设总利润为z 则 有 max z 2 x1 x2 3 约束条件 x1 0 x2 0 2x1 2x2 12 x1 2x2 8 4x1 16 4x2 12 线性规划问题的数学模型线性规

13、划问题的数学模型 例1 4 某厂生产三种药物 这些药物可以从四种不同的 原料中提取 下表给出了单 位原料可提取的药物量 解 要求 生产A种药物至少160 单位 B种药物恰好200单位 C种药物不超过180单位 且使原料总成本最小 1 决策变量 设四种原料的使用 量分别为 x1 x2 x3 x4 2 目标函数 设总成本为z min z 5 x1 6 x2 7 x3 8 x4 3 约束条件 x1 2x2 x3 x4 160 2x1 4 x3 2 x4 200 3x1 x2 x3 2 x4 180 x1 x2 x3 x4 0 例1 5 某航运局现有船只种类 数量以及计划期内各条航 线的货运量 货运成

14、本如下表所示 航线线号船队队 类类型 编队编队 形式 货货运成本 千元 队队 货货运量 千吨 拖轮 A型 驳驳船 B型 驳驳船 1 112 3625 21 43620 2 32247240 41 42720 船只种类类船只数 拖 轮轮 30 A型驳驳船 34 B型驳驳船 52 航线线号合同货货运量 1200 2400 问 应如何编队 才能既完成合同任务 又使总货运成本为最小 线性规划问题的数学模型线性规划问题的数学模型 解 设 xj为第j号类型船队的队数 j 1 2 3 4 z 为总货运成本 则 min z 36x1 36x2 72x3 27x4 x1 x2 2x3 x4 30 2x1 2x3

15、 34 4x2 4x3 4x4 52 25x1 20 x2 200 40 x3 20 x4 400 xj 0 j 1 2 3 4 线性规划问题的数学模型线性规划问题的数学模型 线性规划问题的数学模型线性规划问题的数学模型 2 2 线性规划的数学模型由三个要素构成线性规划的数学模型由三个要素构成 决策变量决策变量 Decision variables Decision variables 目标函数目标函数 Objective functionObjective function 约束条件约束条件 ConstraintsConstraints 其特征是 其特征是 1 1 问题的目标函数是多个决策变

16、量的 问题的目标函数是多个决策变量的线性线性函数 函数 通常是求最大值或最小值 通常是求最大值或最小值 2 2 问题的约束条件是一组多个决策变量的 问题的约束条件是一组多个决策变量的线性线性不不 等式或等式 等式或等式 怎样辨别一个模型是线性规划模型 怎样辨别一个模型是线性规划模型 线性规划问题的数学模型线性规划问题的数学模型 3 3 建模条件建模条件 1 1 优化条件优化条件 问题所要达到的目标能用线型函数描述 且 问题所要达到的目标能用线型函数描述 且 能够用极值能够用极值 max max 或或 minmin 来表示 来表示 2 2 限定条件限定条件 达到目标受到一定的限制 且这些限制能够 达到目标受到一定的限制 且这些限制能够 用决策变量的用决策变量的 线性等式或线性不等式表示 线性等式或线性不等式表示 3 3 选择条件选择条件 有多种可选择的方案供决策者选择 以便找 有多种可选择的方案供决策者选择 以便找 出最优方案 出最优方案 线性规划问题的数学模型线性规划问题的数学模型 4 4 建模步骤建模步骤 1 1 确定决策变量确定决策变量 即需要我们作出决策或选择的量 一般 即需要我