运筹绪论ppt课件.ppt

运筹学 授课老师 张林刚办公电话 60873611联系手机公地点 文科楼A212室Email lgzhang 教学要求 平时成绩占30 期末考试成绩占70 其中 平时成绩由三部分组成 考勤 上课出勤情况 课堂表现 上课参与情况 课后作业 习题 案例策划等完成情况 2 答疑如何安排 时间 地点 绪论 运筹学释义运筹学的来源运筹学的发展运筹学研究的基本特征运筹学研究的基本步骤运筹学主要分支简介 运筹学释义 大英百科全书 运筹学是一门应用于管理有组织系统的科学 运筹学为掌管这类系统的人提供决策目标和数量分析的工具 辞海 用数学方法研究经济 民政和国防等部门在内外环境的约束条件下合理分配人力 物力 财力等资源 使实际系统有效运行的技术科学 它可以用来预测发展趋势 制定行动规划或优选可行方案 中国企业百科全书 应用分析 试验 量化的方法 对经济管理系统中人 财 物等有限资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 P M Morse与G E Kimball在他们的奠基作中给运筹学下的定义是 运筹学是在实行管理的领域 运用数学方法 对需要进行管理的问题统筹规划 作出决策的一门应用科学 运筹学的来源 名称来源运筹学一词在英国称为Operationa1research 在美国称为operationsresearch 缩写为O R 可直译为 运用研究 或 作业研究 1957年我国从 夫运筹帷幄之中 决胜千里之外 见 史记 高祖本纪 这句古语中抽取 运筹 二字 将O R 正式译作运筹学 包含运用筹划 以策略取胜等意义 比较恰当地反映了这门学科的性质和内涵 夫运筹帷幄之中 决胜千里之外 吾不如子房 镇国家 抚百姓 给馈饷 不绝粮道 吾不如萧何 连百万之军 战必胜 攻必取 吾不如韩信 1 运筹学的历史 中国古代朴素的运筹思想 都江堰水利工程战国时期 大约公元前250年 川西太守李冰父子主持修建 其目标是 利用岷江上游的水资源灌溉川西平原 另外 还考虑防洪 灌溉 水运社会经济效益问题 其总体构思是系统思想的杰出运用 都江堰水利工程示意图 都江堰水利工程由三大工程及120多项配套工程组成 1 鱼嘴 岷江分水工程 将岷江水有控制地引入内江 2 飞沙堰 分洪排沙工程 将泥沙排入外江 3 宝瓶口 引水工程 除沙后的江水引入水网干道 它们巧妙结合 完整而严密 相得益彰 两千多年来 这项工程一直发挥着巨大的效益 是我国最成功的水利工程 丁谓的皇宫修复工程北宋年间 一场大火烧掉了皇宫 真宗皇帝命令大臣丁渭修复皇宫 他面临烧砖无土 大型建筑材料无法运输 清墟无处排放等重重困难 丁渭第一件事是将皇宫周围的大街小巷挖成河道 与河流相通 挖出来的土烧砖制瓦 解决了取土问题 这是短期目标 为修皇宫服务 全国各地建筑材料水运到京城 由开挖的河道直接运到工地 省去二次运输 节约了一大笔资金 解决了运输问题 几年以后 皇宫修复了 建筑垃圾成山 他又叫人将垃圾填到挖的河道中去 恢复了原来的大街小巷 结果 皇宫修成了 街道恢复了 资金节省了 可谓 一石三鸟 田忌赛马齐王要与大臣田忌赛马 双方各出上 中 下马各一匹 对局三次 每次胜负1000金 田忌接受孙膑的建议 做如下安排 齐王上中下田忌下上中最终净胜一局 赢得1000金 一 运筹学在西方的起源Lanchester 1914 兰彻斯特战斗方程的提出 应用数学方法研究敌对双方在战斗中的武器 兵力消灭过程的运筹学分支 兰彻斯特方程证明 相同战斗力和战斗条件下 1000对2000人作战 几轮战斗下来 人数较多一方只要伤亡268人就能全歼1000人的队伍 兰切斯特方程特别适用于现代战争中分散化军队和远程火炮配置发生的战斗 远距离战斗比如炮战 空战 舰队海战很可能出现兰切斯特方程的理想情况 Erlang 1910 电话交换机排队系统 Von Neumann与对策论 对策论与经济行为 将经济中的冲突 协调和平衡问题用量化的方式来解决 正式使用 二十世纪三十年代后期的二战期间英美运筹学小组的建立 通过科学方法的运用成功地解决了许多非常复杂的战略和战术问题 例如如何合理运用雷达有效地对付德国空袭 对商船队如何进行编队护航 在船队遭受德国潜艇攻击时使船队损失最少 反潜深水炸弹在各种情况下如何调整其爆炸深度 才能增加对德国潜潜艇的杀伤力等 英国第一个运筹小组 领导人 著名的物理学家M s Blackett 后来因在宇宙射线方面的研究成果而获得诺贝尔物理学奖 组员 2位数学家 2位普通物理学家 1位理论物理学家 1位天体物理学家 l位测量员 3位生理学家 1位军官组成 Blackett马戏团 研究的问题是 设计将雷达信息传送到指挥系统和武器系统的最佳方式 指挥系统与作战系统的协调 防空系统的改进等问题 这个项目是运筹学的典范 整体化的思想 明确的目标 多学科的协同 数量化的分析 最优化的结果 巨大的使用价值及简明的表述 都展现了运筹学的本色 Blackett马戏团 在秘密报告中使用了 OperationalResearch 即 运筹学 美国也成立一个运筹小组 领导人 物理学家PhilipW Morse 美国运筹学会第一届主席 组员与英国相仿 大多为自然科学家 包括数学家 物理学家 其中还有一位象棋大师 运筹学在军事领域中的应用取得了显著效果 例如 在第二次世界大战中 德国潜艇严重威胁盟军运输船队 反潜战的一个重要问题是 当侦察飞机发现潜艇后 飞机投掷深水炸弹的最佳时间以及炸弹引爆的最佳深度应是多少 运筹工作者对大量统计数字进行认真分析后 提出 1 应在潜艇浮出水面或刚下沉时 投掷深水炸弹 2 炸弹起爆的最佳深度为离水面25英尺 当时深水炸弹所容许的最低起爆点 空军采用上述建议后 使德国潜艇被摧毁数增加到40 船只受敌机攻击时中弹数由47 降到29 运筹学的发展 值得注意的是 当时许多实际问题的解决 仅应用了初等概率和统计 第二次世界大战以后 运筹学得到了很大的发展 一方面 运筹学得到了广泛应用 它几乎涉及经济管理的所有领域 另一方面 理论成果大量涌现 发展了许多数学分支 例如数学规划 应用概率 应用组合论 博弈论 数理经济学 系统科学等 一 从l945年到50年代初 运筹学理论的创建时期 第一本运筹学杂志 运筹学季刊 O R Quarterly 1950年于英国创刊 第一个运筹学会英国运筹学会于1948年成立 MIT 1948 首开 运筹学 课 G B Dantzig提出的线性规划单纯形法 1947年 二 50年代初期到50年代末期 运筹学的成长时期最早建立运筹学会的国家是英国 1948 接着是美国 1952 法国 1956 日本和印度 1957 我国的运筹学会建立在1980年 三 自60年代以来 运筹学迅速发展和普及时期运筹学进一步细分为各个分支 专业学术团体迅速增多 更多期刊创办 运筹学书籍大量出版 更多学校将运筹学课程纳入教学计划 目前国际上著名的运筹学刊物有 ManagementScience OperationsResearch Interfaces JournalofOperationalReseachSociety EuropeanJournalofOperationsResearch 国内比较著名的运筹学刊物 系统工程学报 管理科学学报 中国管理科学 运筹与管理 系统工程等 运筹学在中国的发展引入 中国第一个运筹学小组在钱学森 许国志先生的推动下于1956年在中国科学院力学研究所成立 1959年 第二个运筹学研究小组在中国科学院数学研究所成立 力学所小组与数学所的小组于1960年合并成为数学研究所的一个研究室 当时的主要研究方向为排队论 非线性规划和图论 五十年代后期 运筹学在中国的应用集中在运输问题和图论上 如 选址问题 中国邮路问题 管梅谷 中国运筹学早期应用的亮点由华罗庚教授点燃的 中国运筹学会于1980年成立 作为中国数学会的一个分会 1982年成为国际运筹学联合会 IFORS 的成员 1992年中国运筹学会从中国数学会独立出来成为国家一级学会是学会发展史上的一个重要事件 近二十年来 中国运筹学工作者在信息科学 生命科学等现代高科技都作出了突出的贡献 例如 将全局最优化 图论 神经网络等运筹学理论及方法应用于分子生物信息学中的DNA与蛋白质序列比较 芯片测试 生物进化分析 蛋白质结构预测等问题的研究 在金融管理方面 将优化及决策分析方法 应用于金融风险控制与管理 资产评估与定价分析模型等 在网络管理上 利用随机过程方法 研究排队网络的数量指标分析 在供应链管理问题中 利用随机动态规划模型 研究多重决策最优策略的计算方法 运筹学研究的基本特征 系统的整体观念多学科的综合模型方法的应用 制定决策是运筹学应用的核心 而建立模型则是运筹学方法的精髓 运筹学研究的基本步骤 一 分析和表述问题二 建立模型三 求解模型和优化方案四 对模型和由模型导出的解进行检验五 建立起对解的有效控制六 方案的实施 运筹学的主要分支 一 线性规划 Linearprogramming 二 非线性规划 nonlinearprogramming 三 动态规划 dynamicprogramming 四 图与网络分析 graphtheoryandnetworkanalysis 五 存贮论 inventorytheory 六 排队论 queueingtheory orwaitingline 七 对策论 gametheory 八 决策论 decisiontheory 线性规划 数学规划 非线性规划 整数规划 动态规划 学科内容 多目标规划 双层规划 组合优化 最优计数问题 网络优化 排序问题 统筹图 随机优化 对策论 排队论 库存论 决策分析 可靠性分析 线性规划问题 某医院护士值班班次 每班工作时间及各班所需护士数如表所示 每班护士值班开始时向病房报到 并连续工作8小时 试决定该医院最少需多少名护士 以满足轮班需要 动态规划问题 某公司打算在3个不同地区设置4个销售点 根据市场预测部门估计 在不同地区设备不同数量的销售站 每月可得利润如表所示 试问应如何在各地区设置销售站 可使每月总利润最大 格尼斯堡七桥问题 一个散步者能否走过七座桥 且每座桥只走过一次 最后回到出发点 图与网络分析 一笔画问题 欧拉 1736 存储论 对某种电子元件每月需求量为4000件 每件成本为150元 每年的存贮费为成本的10 每次订购费为500元 求 1 不允许缺货条件下的最优存贮策略 2 允许缺货 缺货费为每件每年100元 条件下的最优存贮策略 排队论 某店仅有一个修理工人 顾客到达过程为Poisson流 平均每小时3人 修理时间服从负指数分布 平均需10分钟 求 1 店内空闲的概率 2 有4个顾客的概率 3 至少有1个顾客的概率 4 店内顾客的平均数 5 等待服务的顾客的平均数 6 平均等待修理时间 对策论 二指莫拉问题 甲 乙二人游戏 每人出一个或两个手指 同时又把猜测对方所出的指数叫出来 如果只有一个人猜测正确 则他的赢得分数为二人所出指数之和 否则重新开始 试写出该对策中各局中人的策略集及甲的赢得矩阵 并说明是否存在某一种策略比其它策略更有利 再如 囚徒困境 决策论 根据以往的资料 一家面包店每天所需面包数 当天市场需求量 可能是下列当中的某一个 100 150 200 250 300 但其概率分布不知道 如果一个面包当天没有卖掉 则可在当天结束时每个0 15元处理掉 新鲜面包每个售价为o 49元 成本为0 25元 假设进货量限制在需求量中的某一个 要求 1 做出面包进货问题的决策矩阵 2 用处理不确定性决策问题的方法确定最优进货量 运筹学在科技体系中的地位 一门科学只有成功地应用数学时 才算达到了完善的地步 马克思 钱学森 著名物理学家 世界著名火箭专家 被誉为 中国导弹之父 1934年毕业于交通大学 1934年在美国麻省理工学院和加利福尼亚理工大学学习 1938年获博士学位 后留任美国并从事火箭研究 1950年开始争取回归祖国 当时美国海军的一位高级将领金布尔说 钱学森无论走到哪里 都抵得上5个师的兵力 我宁可把他击毙在美国也不能让他离开 因此钱学森受到美国政府控制 失去自由 历经5