运筹学导论第八版--1绪论.ppt

1 名不正 则言不顺 言不顺 则事不成 事不成 则礼乐不兴 礼乐不兴 则刑罚不中 2 3 4 1942年 BarnesWallis巴恩斯 沃利森就设计出了专门用来炸毁混凝土拱形水坝的专用炸弹 起名为 跳跃炸弹 这种炸弹在水坝上游释放 投放前先在炸弹架上赋予它500转 分的自转速度 炸弹投下后会像小孩玩石头 打水漂 一样 在水面上多次跳跃前进 可以越过水坝前敷设的防弹网 在接触水坝时 炸弹利用自身的旋转 向水坝水线下深入 在水线下炸出大洞 拱形水坝一旦在支撑点上被炸毁 强大的水压将使水坝立即溃决 5 中文 运筹 夫运筹帷幄之中 决胜于千里之外 史记 高祖本纪 英文 OperationalResearch 英国 OperationsResearch 美国 直译为 作战研究 或 作业研究 运作研究 6 丁谓的皇宫修复工程 运筹学的起源 北宋年间 丁谓负责修复焚毁的开封皇宫 他的施工方案是 Step1 先将工程皇宫前的一条大街挖成一条大沟 将大沟与汴水相通 Step2 使用挖出的土就地制砖 令与汴水相连形成的河道承担繁重的运输任务 Step3 修复工程完成后 实施大沟排水 并将原废墟物回填 修复成原来的大街 丁谓将取材 生产 运输及废墟物的处理用 一沟三用 巧妙地解决了 7 田忌赛马 齐王与大臣田忌赛马 双方各出上 中 下马各一匹 对局三次 每次胜负1000金 著名的军事谋略家孙膑如何指导田忌的 齐王 上中下田忌 下上中最终净胜一局 赢得1000金 8 北宋科学家 军事家沈括 在率兵抗击西夏征途中利用各兵种背负粮食的基本数据 盘算后勤兵与战士在不同的行军天数中的差异比例关系 盘算了用种种牲口运粮与人力运粮之间的利弊 做出了从敌国就地征粮 保障前线提供的决策 优化后勤职员比例 增强了前线战斗力 这种军事运筹是运筹思想的典范 也是现代军事运筹的核心问题 沈括调整军队构成 9 运筹学真正的发展 起源于二次大战的一门新兴交叉学科与作战问题相关雷达设置 运输船队护航 反潜战中深水炸弹起爆深度 飞行员编组 军事物资存储等战后在经济 管理和机关学校及科研单位继续研究1948年英国首先成立运筹学会1952年 Morse和Kimball出版 运筹学方法 1952年美国成立运筹学会1959年成立国际运筹学联合会 IFORS 我国于1982年加入IFORS 并于1999年8月组织了第15届大会 10 PhilipM Morse 运筹学发展的主要推动者 WassilyW Leontief投入产出法 Dantzig 1914 2005单纯形法 VonNeumann MonteCarlo方法 JohnForbesNashJr博弈论 11 运筹学的内容丰富 分支众多 根据解决问题的主要特征可分两大类 确定型和概率型 其中确定型包含 线性规划 整数规划 动态规划 非线性规划 多目标决策及确定性存贮等 概率型中包含 回归分析 决策论 对策论 排队论 马尔可夫链 图论与网络 概率存贮及搜索技术等 本课将阐述运筹学中最基本的部分 规划论 即线性规划 对偶理论与灵敏度分析 整数规划 网络规划 排队论 运筹学分支及模型类型 12 运筹学的研究问题与对象 资源最佳利用问题方法 线性规划 整数规划 网络图 动态规划 目标规划等竞争现象如战争 投资 商品竞争方法 对策论 博弈论 拥挤现象如公共汽车排队 打电话 买东西 飞机着陆 船舶进港等方法 排队论 13 运筹学的关键在于模型的建立和使用 应用运筹学处理问题时 要从系统观点来分析问题 提出需要解决的问题和希望达到的目标 理清问题所处的环境和约束条件 包括 时间 地点 资金 原材料 设备 人力 能源 动力 信息 技术等 问题中的主要因素 各种环境和约束条件之间的逻辑关系 运筹学应用前提 14 运筹学的发展趋势 运筹学的危机脱离实际应用 陷入数学陷阱IT对运筹学的影响MIS MRP II CIMS ERPORDept Dept OfOR IS运筹学与行为科学结合群决策和谈判 对策理论 多层规划 合理性分析服务行业中的应用金融服务业 信息 电信服务业 医院管理 15 研究深水炸弹起爆深度问题 当飞机发现潜艇后 飞机何时投掷炸弹及炸弹的引爆引度是多少 运筹学工作者对大量统计数字进行认真分析后 提出如下决策 仅当潜艇浮出水面或刚下沉时 方投掷深水炸弹 炸弹的起爆深度为离水面25英尺 这是当时深水炸弹所容许的最浅起爆点 空军采用上述决策后 所击沉潜艇增加5倍 运筹学的研究意义 16 纽约消防车辆调度 都市求救电话是一个复杂的分布在不同地点的多个服务台的排队系统 涉及资源的空间配置 警车巡逻线路最优设计 警力配备 电话调度 部署在纽约 圣迭戈 萨克拉门托 达拉斯 波特兰 加拉加斯和鹿特丹 提高生产率10 15 特别是极大的降低了响应时间 运筹学的研究意义 17 假设有70艘油轮向70个港口运货 已知每艘油轮驶向每个港口的费用 油轮公司需制订出最优运输方案 采用全枚举法 穷举法 需计算方案数为70 大于10100 IBM公司生产的大计算机1秒种大约可算出1012 即1000亿 个方案 若要算出全部方案 则需调用占有空间为1050个地球一样大的计算机计算几百亿年以上 而在这种大机器上用线性规划的单纯形法计算只需几秒钟 这是整数规划问题 运筹学的研究意义 运筹学是研究从众多方案 甚至无限多方案 中选择最优方案的技术 那么在当代计算机技术迅速发展的今天 这种优化技术是否会丧失其重要性 18 运筹学的研究意义 新型计算机的出现 不能代替运筹学优化需求 运筹学与计算机科学及其它科学结合应用 可以将人解放出来 产生更好的实施效果 19 运筹学在工程和商业管理的应用 生产计划 生产作业的计划 日程表的编排 合理下料 配料问题 物料管理等 库存管理 多种物资库存量的管理 库存方式 库存量等 运输问题 确定最小成本的运输线路 物资的调拨 运输工具的调度以及建厂地址的选择等 人事管理 对人员的需求和使用的预测 确定人员编制 人员合理分配 建立人才评价体系等 市场营销 广告预算 媒介选择 定价 产品开发与销售计划制定等 财务会计 预测 贷款 成本分析 定价 证券管理 现金管理等 20 21 本课程课程背景 教材 参考书 先修课 高等数学 概率与统计 线性代数1 教材 HamdyA Taha 运筹学导论 第8版 邮电出版社 20072 参考书 希利尔 利伯曼 运筹学导论 第9版 清华大学出版社 2010运筹与管理 运筹学50周年纪念特刊 2004傅家良 运筹学方法与模型 复旦大学出版社 2006胡运权 运筹学教程 清华大学出版社出版 2007 22 国际著名运筹学刊物 Interfaces ManagementScience OperationsResearch EuropeanJournalofOperationsResearch TransportationScience MathematicsofOperationsResearch OperationsResearchLetters MathematicalProgramming 23 本课程特点及要求 目的 不仅掌握优化理论方法的专业知识 更重要的是提高分析问题和解决问题的能力 方法 强调思路 观点及弄清物理概念 掌握一定的理论推导能力 但不搞纯数学公式 避免2种倾向 只罗列方法 不讲本质 或只追求数学推导 掩盖物理概念 24 本课程授课方式与考核 本课程授课方式 对话式教学作业 计算机编程或者软件操作考核 课程设计 汇报24 报告36 期末考试成绩 40 25 绪论线性规划建模单纯形法与敏感性分析对偶与后最优分析运输模型网络模型整数线性规划排队论 本课程授课内容 26 第1章什么是运筹学 27 设想你需要完成一项工作任务 需要5周完成 期间需要往返于Fayetteville FYV 与Denver DEN 之间 每个星期一你都要乘飞机从Fayetteville出发 星期三返回 普通的往返机票是400美元 但是如果购买跨周末的往返机票 可以享受20 的折扣 如果是单程的机票则为往返票的75 那么如何购买这5周的机票 有哪些可能的决策方案 决策受到哪些限制条件 评价这些方案的标准是什么 1 1运筹学模型 28 购买5张普通的FYV DEN FYV往返机票 每周一出发 周三返回 购买1张FYV DEN单程机票 4张跨周末的DEN FYV DEN往返机票 再买1张DEN FYV单程 先购买1张第一周星期一出发 最后一周星期三返程的FYV DEN FYV往返机票 再买4张跨周末的DEN FYV DEN往返机票 该方案使得所有机票都至少跨越一个周末 所有方案的约束条件 必须周一从FYV出发 在本周的星期三返回 有哪些可能的决策方案 29 评价所提出的各种方案好坏标准是购买这些机票的总费用 花费最少的方案最佳 方案1的费用 5 400 2000方案2的费用 0 75 400 4 400 0 8 0 75 400 1880方案3的费用 5 400 0 8 1600所以 应该选择方案三 上例表明 运筹学模型的3个主要构成 备选方案目标评判标准约束条件 3个备选方案花费最少周一去周三回 30 考虑长度为L的电线围成一个矩形 要使得该矩形面积最大 长度和宽度如何选取 令w 矩形的长 h 矩形的宽 则限制条件可以叙述为 1 矩形长 矩形宽 电线长度一半 2 长宽不能为负值以数学形式表示为 1 2 w h L 2 w 0 h 0问题的目标 评判的标准 即矩形面积最大 令z为矩形的面积 模型变为Maxz whSt 2 w h L w h 0 w h L 4 对于可能的方案数是无限的情形 必须需要最优化模型 31 从上面的例子 可以归纳出一般的运筹学模型具有以下通用的格式 max或min目标函数St Subjectto 约束条件 一个模型的解若满足所有约束条件 则解是可行的 feasible 如果既是可行的 又取得了目标的最佳 最大或最小 值 则解是最优的 optimal 在购票的例子中3个方案是可行的 第三方案是最优的 构造矩形的例子中 可行方案要满足w h L 2 w和h非负 则有无穷多的可行解 32 虽然运筹学的模型是在一组约束条件下 使得某一具体的目标评判标准达到最优 但是它所得出的解的质量取决于模型对实际问题刻画的完全性 以购机票问题为例 假如我们不能找到所有的方案的话 那么所得到的解只相对于所选模型是最优的 例如方案3没有在模型中 则 最优 解就要用1880美元 这是一个次最优 suboptimal 解 因此 一个模型的 最优 解只是对这个模型是最好的 当模型完全的表达了实际问题时 他的解对实际才是最优的 33 1 2运筹学模型的求解 在OR中 没有一种万能的技术能求解出实践中所有的数学模型 在OR中 常用的技术有 线性规划 整数规划 动态规划 网络规划 非线性规划等 除此之外还有很多运筹学方法 运筹学的问题解通常不是某种解析式形式的 需要反复迭代 逐步向最优解靠近 每步迭代的计算规则是一致的 这需要计算机来计算 对于非常复杂的数学模型 可能必须放弃最优解 可能利用某些启发式算法或经验方法 找到较好的解 非最优的 34 1 3排队模型和模拟模型 排队模型和模拟模型用于研究等待队列 他们不属于最优化技术 而是用来度量等待队列的性能 例如队长 等待时间 设施利用率等 排队论基于各种概率分布采用概率论随机模型分析队列 而模拟可以分析任何排队情形 是观察实际系统最好的方法 建立模拟模型的过程非常费时费力 计算过程非常耗时 35 1 4建模的艺术 运筹学的建模过程实际上是对现实问题的抽象和近似 我们应该把研究的重点聚焦在控制实际系统行为的主要变量上 从现实世界中抽象出假定的实际系统 36 Tyko制造公司生产各种塑料容器制品 当生产订单到达生产部门的时候 必要的原材料要从公司库存或采购 完成生产后 销售部门负责向客户分销产品 问题 生产批量应该是多少 如何用模型来表达 许多变量都可以直接表示生产水平 下面是各部门的变量 生产部门 机器数 工人工作时间 半成品库存 质量控制标准表示的生产能力 原材料部门 原材料库存量 采购供货安排 库存限量销售部门 销售预测 分销网能力 广告促销能力 竞争水平 这些变量均影响生产量 建立上述所有因素的模型极为困难 37 第一个抽象水平需要定义出假定实际系统的边界 通过分析 可以用下面两个主要变量来近似描述实际系统 生产率 2 消费率计算生产率要用到生产能力 质量控制标准 现有原材料等变量 消费率则可以从与销售部门有关的变量计算 本质上 从现实世界到假定现实世界的简化 是通过多个现实世界变量 简化 成为单一的假定现实世界变量来实现的 利用生产率和消费率 就可以建立起库存剩余和不足的度量 建立起模型以平衡库存剩余或短缺所引起的冲突成本 使得库存费用最低 通过上述过程 比较容易对假定的现实世界建立模型 38 1 5仅有数学是不够的 运筹学模型是数学模型 数学是运筹学的基石 运筹学决策模型总是受到人的因素影响 运筹学的成败与心理因素密切相关 几个例子 电梯等待时间优化问题 机场柜台紧急插队问题 钢锭产量均衡问题 是否可能采用 突破常规的 思路解决问题 必须考虑人的因素 文化差异 国民习性 数学模型应该去适应现实问题 而不是反之 39 1 6运用运筹学的几个步骤 运用运筹学解决实际问题需要团队精神 需要OR人员的专业技能必须与客户的经验与合作相配合 必须面向客户的问题开展研究 运筹学是科学 也是艺术 科学性 体现数学的优点