运筹学 绪论.ppt

北京物资学院教学课件 运筹学 主讲教师 李珍萍信息学院数学教研室 绪论 运筹学的产生与发展运筹学研究的基本特点运筹学解决问题的基本步骤运筹学的主要内容几个典型的运筹学案例教学计划和教学方法主要参考书 一 运筹学的产生与发展 1 运筹学名称的由来 operationsresearch operationalreasearch直译为 运用研究 或 作业研究 许国志等根据史记中 运筹于帷幄之中 决胜于千里之外 将其翻译成 运筹学 运筹学是运用科学的数量方法 主要是数学模型 研究对人力 物力进行合理筹划和运用 寻找管理及决策最优方案的综合性学科 2 运筹学的发展历程 萌芽 产生 发展 成熟 案例1 田忌赛马的故事 1 运筹学的萌芽时期 古代朴素的运筹思想 比赛规则 每人分别出上中下三个等次的马各一匹参加比赛 三赛二胜制 在双方条件相当时 对策得当可以战胜对方 在双方条件相差很远时 对策得当也可将损失减低到最低程度 第一次比赛 第二次比赛 距今1000年前 北宋皇城因大火毁于一旦 宋真宗任命大臣丁渭主持重建全部宫室殿宇 有三难 取土之难 运输之难 清场之难 丁渭采取的措施 将宫前大街开挖成河 取土烧砖 引汴水入宫 水运建材 宫修复 以废砖烂瓦填平河沟 修复宫前大街 挖河一举解决取土之难 运输之难 清场之难 可谓 一石三鸟 使重建皇城事半功倍 案例2 丁渭修皇宫 2 运筹学的产生 最早的运筹学工作 1 以英国生理学家希尔为首的英国国防部防空试验小组在第一次世界大战期间进行的高射炮系统利用研究 2 英国人莫尔斯建立的分析美国海军横跨大西洋护航队损失的数学模型 1938年 英国成立了专门小组 研究如何利用雷达系统送来的信息改进作战效能的问题 这个专门小组就是空军运筹学小组 当时主要从事警报和控制系统的研究 在1939年到1940年 这个小组的任务扩大到 防卫战斗机的布置 对未来的战斗的预测等 小组的工作对后来的不列颠空战的胜利起了积极的作用 二战期间 美国 加拿大等国也成立了军事运筹小组 研究并解决战争提出的运筹学课题 例如 组织适当的护航编队使运输船队损失最小 改进搜索方法 及时发现敌军潜艇 改进深水炸弹的起爆深度 提高了毁伤率 合理安排飞机维修 提高了飞机的利用率等 这些运筹学成果对盟军大西洋海战的胜利起了十分重要的作用 对许多战斗的胜利也起了积极的作用 战争结束时 英美及加拿大军队中工作的运筹学工作者已超过了700人 正是由于战争的需要 运筹学有了长足的发展 并且形成为科学 3 运筹学的发展 二次世界大战结束以后 运筹学研究应用于和平时期的工商业 出现了应用研究和理论研究相互促进的局面 应用方面 在工商业管理中的应用是最主要的 特别是在美国 管理科学方面的主要内容便是运筹学 理论方面 1947年 dantzing提出了求解线性规划问题的单纯形方法 使得运筹学的主要分支线性规划的理论逐渐完善起来 4 运筹学的成熟 应用范围扩大 60年代以后 随着电子计算机的出现 使得运筹学中的一些方法可以用来解决一些大规模问题 运筹学得以用来研究一些大的复杂的系统 如城市交通 环境污染 国民经济计划等 理论完善 专门从事运筹学研究的人员也越来越多 运筹学的各个分支的理论都逐渐成熟起来 二 运筹学研究的基本特点 1 系统的整体优化 2 引入模型解决实际问题 运用系统的观点 定量化的方法 将多门学科相结合 寻求解决问题的最佳方案 3 交叉学科 三 运筹学解决问题的步骤 1 分析与表述问题 2 建立模型 3 对问题求解 4 对模型和由模型导出的解进行检验 5 建立起对解的有效控制 6 方案的实施 四 运筹学的主要内容 五 几个典型的运筹学案例 设要从甲地调出物资2000吨 从乙地调出物资600吨 从丙地调出物资500吨 分别供应给a地1700吨 b地1100吨 c地200吨 d地100吨 已知每吨运费如下表所示 假定运费与运量成正比例 问怎样才能找到一个总运费最省的调拨计划 丙 17 26 38 43 15 37 51 51 乙 15 7 25 21 甲 d c b a 销地产地 单位 元 吨 1 运输问题 2 下料问题工厂要制作100套专用钢架 每套钢架需要用长为2 9m 2 1m和1 5m的圆钢各一根 已知原料每根长7 4米 每根原料的成本是80元 问如何下料才能使购买原料的成本最低 3 人员安排问题 某个中型百货商场对售货人员 周工资200元 的需求经统计如下表 每个人的休息时间为连续的两天时间 每天安排的人员数不得低于需求量 但可以超过需求量 为了保证销售人员充分休息 销售人员每周工作5天 休息2天 问应如何安排销售人员的工作时间 使得所配售货人员的总费用最小 4 最短路问题 已知如图所示交通网络图 边旁的数字表示通过这段路所需要的费用 现某人要从v1出发到v8去 问他该走哪条路线才能花费最少 5 指派问题 设某工程有b1 b2 b3 b4四项任务 需由四个工人a1 a2 a3 a4去完成 由于任务性质和每个工人的技术水平不相同 他们完成各项任务所需的时间也不一样 见下表 问应当如何分配 即哪个人去完成哪项任务 才能使完成四项任务的总时间最少 6 决策分析某电视机厂 2008年产品更新方案 a1 彻底改型 a2 只改机芯 不改外壳 a3 只改外壳 不改机芯 可能遇到的市场销售情况有三种 销量高 s1 中 s2 低 s3 三种状态下的收益 单位 万元 如下表 问 如何决策 六 教学计划和方法 教学计划线性规划 运输问题 整数规划与分配问题 目标规教学方法以课堂讲授为主 讲课中主要培养用最优化方法解决实际问题的能力 考核方式 期末闭卷考试 平时成绩平时成绩包括 考勤 课堂表现 作业 学期论文 大作业 七 主要参考书 1 吴祈宗编管理运筹学机械工业出版社 2004