运筹学-绪论PPT课件.ppt

1 教材 胡运权等 运筹学基础及应用 第五版 高等教育出版社 课程说明 河南理工大学 运筹学 课件Page2 1 2先修课程微积分 线性代数 概率论3学习方式课堂听课 课下习题 案例分析 上机实验成绩 期末闭卷考试成绩 70 平时成绩 30 河南理工大学 运筹学 课件Page3 2 Cha1绪论 1 运筹学的产生2 运筹学在我国的发展3 运筹学的概念4 运筹学的主要内容5 运筹学研究问题的思路 河南理工大学 运筹学 课件Page4 3 运筹学的产生 运筹学 一词 最早于1938年出现于英国 英国人称之为OperationalResearch 简称OR 夫运筹帷幄之中 决胜于千里之外 吾不如子房 史记 古代运筹学思想 三个典故 田忌赛马 丁谓挖沟 沈括运粮 河南理工大学 运筹学 课件Page5 4 古代运筹学思想 田忌赛马 齐国的大将田忌 很喜欢赛马 有一回 他和齐威王约定要进行一场比赛 他们商量好 把各自的马分成上 中 下三等 比赛的时候 要上马对上马 中马对中马 下马对下马 由于齐威王每个等级的马都比田忌的马强得多 所以比赛了几次 田忌都失败了 田忌的好友孙膑给田忌出了这样一个策略 下马对上马 上马对中马 中马对下马 这样田忌就三局两胜取得了比赛的胜利 从这个典故我们可以得到什么启发 河南理工大学 运筹学 课件Page6 5 古代运筹学思想 丁谓挖沟 北宋真宗年间 皇宫失火被毁 主持重建工作的丁谓对这项既定任务进行统筹规划 他抓住取土 运材 除圾三个关键环节 有针对性的采取了一个有力措施 在宫址前的大街上挖一条长沟 这样 先挖沟取土就近烧制砖瓦 再将汴水引入沟内形成一条水上通道 使载运外地建筑材料的船只 排筏直抵宫址近前 待全部工程完毕 再将失火焚毁和施工中产生的破砖碎瓦等建筑垃圾就近填入沟内 修复大街 在这个典故中 一沟三用 一举数得 节省了大量人力 物力 财力和施工时间 这蕴涵着现代运筹学的重要方法之一 统筹法 的某些思想萌芽 河南理工大学 运筹学 课件Page7 6 古代运筹学思想 沈括运粮 沈括生于北宋时期 是我国历史上著名的科学家 还曾率兵抗击过西夏的侵扰 在他为后世留下的 梦溪笔谈 这一鸿著中 记有他用定量分析的方法研究军队的人数以及行军的天数所需粮数和运粮的民夫之间关系的具体事例 沈括认为 自运军粮所花费颇大而且难以运行 因此夺取敌人的粮食至关重要 沈括的结论与 孙子兵法 中 食敌一盅 当吾三十盅 的精辟论断一脉相承 显示出我国古典军事运筹学的卓越思想和悠久历史 河南理工大学 运筹学 课件Page8 7 运筹学在我国的发展 50年代中期 钱学森 许国志等教授将运筹学由西方引入我国 管梅谷 1962年 山东师范大学 中国邮递员问题 华罗庚 优选法 1970 和统筹法 1965 河南理工大学 运筹学 课件Page9 8 中国邮递员问题 一个邮递员 每次送信必须从邮局出发 走遍如图示的投递区域内的所有道路 最终回到邮局 图中路旁各数字分别表示对应路段的长度 单位 千米 他习惯按路线KHGFEDCBAIABJDEKJIHK投递 图中 为邮局 聪明的读者朋友 你知道他的路线是最短的吗 如果不是 请你帮助这位邮递员设计一条最短路线 并说明最短路线比他的路线少多少千米 A I H G B J K C E D F 河南理工大学 运筹学 课件Page10 9 优选法 优选法是华罗庚运用黄金分割法发明的一种可以尽可能减少做试验次数 尽快地找到最优方案的方法 例 比如我们要试制一种新型材料 需要加入某一种原料增强其强度 这就有加入多少的问题 加多了不行 加少了也不行 只有完全合适才行 比如我们估出每吨加入量在1克至1000克之间 这样我们就可以借用黄金分割规律来简化试验次数 而不必1克 2克 1000克这样逐一试验 我们用一个有刻度的纸条来表示1至1000克 在纸条上找到618 1000 0 618 克的地点画一条竖线 做一次试验 然后把纸条对折起来 找到618的对称点382 618 0 618 再做一次试验 如果382克为最好 则把618以外的纸条裁掉 然后再对折 找到382的对称点236 382 0 618 做试验 这样循环往复 就可以找到最佳的数值 请同学们回忆一下黄金分割点 请同学们找出一张白纸按例题进行操作 并思考优选法的原理 河南理工大学 运筹学 课件Page11 10 统筹法 被工商企业采用最多的运筹学方法 例 现在有一个部件 它有两个部分组成 由四个工序完成 为了节省时间 加工管子和加工盘子可以同时开始 加工管子30分钟 加工盘体20分钟 钻孔25分钟 焊接30分钟 如果用A表示加工管子 B表示加工盘子 C表示钻孔 D表示焊接 则每个工序之间的关系可以列表和绘图如下 河南理工大学 运筹学 课件Page12 11 统筹法 A表示加工管子B表示加工盘子C表示钻孔D表示焊接 关键路线 河南理工大学 运筹学 课件Page13 12 运筹学的定义 管理运筹学是一门应用科学 它广泛应用现有的科学技术和数学方法 解决管理中提出的专门问题 为决策者选择最优或较优的决策提供定量依据 运筹学是一门新兴的交叉学科 来源于军事 管理和经济 本课程主要介绍用于解决管理领域问题的运筹学 因此称为管理运筹学 北美称为管理科学 ManagemnetScience 河南理工大学 运筹学 课件Page14 13 运筹学的基本假设 1 假设决策者都是理性的 2 假设决策者都是风险中性的 3 针对实际的运筹学问题 一般情况下都存在最优解 河南理工大学 运筹学 课件Page15 14 理性的概念 个体理性 决策者都是从个人效用最大化出发 有关效用的两个基本原理 1 边际效用递减2 个人效用最大化原理完全理性 决策者是智能的 不会犯任何错误 效用是指对于消费者通过消费或者享受闲暇等使自己的需求 欲望等得到的满足的一个度量 河南理工大学 运筹学 课件Page16 15 理性 认识存在的问题 1 短期效用和长期效用的区别 例1 拣硬币游戏 现有1枚5分的硬币和1枚1毛的硬币 你会如何选择 例2 我们通常所说的 占小便宜吃大亏 与 吃亏是福 如何理解 2 理性 的结果不一定是最好的 例1 囚徒困境 例2 旅行者困境3 理性分析与现实的差距 例 分钱游戏 做 分钱游戏 的实验 甲捡到100元 被乙发现 乙提出和甲分钱 假如同学们为乙 问甲分给乙至少多少时乙才会同意 河南理工大学 运筹学 课件Page17 16 风险 1 何谓风险 风险是指在某一特定环境下 在某一特定时间段内 某种损失发生的可能性 风险是由风险因素 风险事故和风险损失组成 换句话来说 是指在一个特定时间段内 人们所期望达到的目标与实际出现的结果之间的距离称之为风险 例 在一个下雪天的晚上 一老头骑着一没闸 没铃的破自行车 去市内超市买一双皮鞋 在半路上发生了车祸 决策者对待风险的态度有哪些 风险偏好型 riskappetite 风险中立型 riskneutral 风险规避型 riskaverse 河南理工大学 运筹学 课件Page18 17 看下列一组决策问题 您会如何选择 A肯定得到1元 有1 10的可能得到10元 否则什么也得不到B肯定得到10元 有1 10的可能得到100元 否则什么也得不到C肯定得到1000元 有1 10的可能得到10000元 否则什么也得不到D肯定得到10000元 有1 10的可能得到100000元 否则什么也得不到E肯定得到10万元 有1 10的可能得到100万元 否则什么也得不到F肯定得到1000万元 有1 10的可能得到1亿元 否则什么也得不到 河南理工大学 运筹学 课件Page19 18 做如下的游戏 抛3枚相同的硬币 如果全部正面向上或反面向上我给你100元 否则你给我a元 问您能接受的最高的a值是多少 河南理工大学 运筹学 课件Page20 19 存在最优解 但很难求出的情形 例1 捡钻石游戏 某知名外企面试题 一栋大楼总共20层 在每一层的楼梯入口处分别放了一块大小不同的钻石 应聘者需要从一楼向上走 选择一块钻石 假设如下 1 不走回头路 2 不一定一直走到20层 问 应聘者应如何选择 例2 选夫问题假定你是个女性 决定要结婚 你身边社交圈里有100个合适的单身男子都有意追求你 你的任务就是 从他们当中挑选一个最好的作为结婚对象 但要从这100个里面选出最好的并非易事 你该怎么做才能争取到这个结果 条件如下 每个人只能约会一次 而且只能当场决定选择还是放弃 不能把他们冷冻起来作为后备 一旦你选择了其中一个 你就没有机会再约会别人了 河南理工大学 运筹学 课件Page21 20 运筹学解决问题的思路 提出问题 建立模型 模型求解 结果分析与调整 结果实施 优化问题max min 目标函数 决策变量 约束条件 求最优解 最优解是否可符合实际 是否需要增减约束条件 河南理工大学 运筹学 课件Page22 21 经典面试题之猴子运香蕉 课堂讨论题 一猴子从香蕉树上摘了100根香蕉 现需要把香蕉运至家中 已知从香蕉树到猴子家的距离是50m 假设 1 猴子最多可以拿起的香蕉数量是50颗 2 猴子在行走过程中 每走1m将吃掉一根香蕉 问 猴子最多可以带回家多少根香蕉 河南理工大学 运筹学 课件Page23 22 经典面试题之猴子运香蕉 假设 猴子走至x米处返回出发点再携带香蕉回家 x为决策变量 约束条件 1 x应满足0 x 502 猴子第一次和第二次在0处所能携带的香蕉数量不能超过50根50 2x 50 x 100 3x 503 为了保证猴子走1m吃一根香蕉 x为非负整数 目标函数 猴子运回家香蕉的数量用x表示为50 2x 该表达式的值越大越好 河南理工大学 运筹学 课件Page24 23 经典面试题之猴子运香蕉 河南理工大学 运筹学 课件Page25 24 运筹学的主要内容 线性规划 LinearProgramming整数规划 IntegerProgramming非线性规划 NonlinearProgramming多目标规划 Multi objectiveProgramming 动态规划 DynamicProgramming 博弈论 GameTheory 决策分析 DecisionAnalysis 存储论 InventoryTheory排队论 QueuingTheory图论 GraphTheory 统筹方法 programevaluationreviewtechnique 河南理工大学 运筹学 课件Page26 25 经典面试题之海盗分宝石 5个海盗抢到了100颗宝石 每一颗都一样的大小和价值连城 他们决定这分 1 抽签决定自己的号码 1 2 3 4 5 2 首先 由1号提出分配方案 然后大家5人进行表决 当且仅当超过半数的人同意时 按照他的提案进行分配 否则将被扔入大海喂鲨鱼 3 如果1号死后 再由2号提出分配方案 然后大家4人进行表决 当且仅当超过半数的人同意时 按照他的提案进行分配 否则将被扔入大海喂鲨鱼 4 以次类推 条件 每个海盗都是极其聪明的人 每个海盗都是非常残忍的人 每个海盗都能明确的判断得失然后作出明智的选择 问题 第一个海盗提出怎样的分配方