运筹学基础及应用第五版胡运权绪论讲述.ppt

运 筹 学 (O.R.) §0.1 运筹学简述 运筹学（Operations Research）是系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”，故有人称之为最优化技术。 我国朴素的运筹学思想：田忌赛马、丁渭修皇宫 1938年英国最早出现了军事运筹学，命名为“Operational Research”,1942年，美国从事这方面工作的科学家命其名为“Operations Research”这个名字一直延用至今。 §0.1 运筹学简述 美国运筹学的早期著名工作之一是研究深水炸弹起爆深度问题。当飞机发现潜艇后，飞机何时投掷炸弹及炸弹的引爆引度是多少？运筹学工作者对大量统计数字进行认真分析后，提出如下决策：1.仅当潜艇浮出水面或刚下沉时，方投掷深水炸弹。2.炸弹的起爆深度为离水面25英尺（这是当时深水炸弹所容许的最浅起爆点）。空军采用上述决策后，所击沉潜艇成倍增加，从而为反法西斯战争的胜利做出了贡献，为运筹学增添了荣誉。 §0.1 运筹学简述 运筹学是研究从众多方案（甚至无限多个方案）中选佳的优化技术，那么在当代计算机技术迅速发展的今天，这种优化技术是否会丧失其重要性？事实正相反，新型计算机的出现，恰为运筹学的应用开辟了新天地。 假设有70艘油轮向70个港口运货，已知每艘油轮驶向每个港口的费用，油轮公司需制订出最优运输方案。采用全枚举法（穷举法）需计算方案数为70!(大于10100 ）；IBM公司当时生产的大计算机1秒种大约可算出109（即10亿）个方案。若要逐个算出全部方案，则需调用占有空间为1050个地球一样大的IBM公司生产的众多大计算机同时计算几百亿年以上。而在这种大机器上用线性规划的单纯形法计算只需几秒钟（这是整数规划问题）。 可见，将运筹学与计算机科学及其它科学结合应用，将会产生更好的效果。 §0.1 运筹学简述 《史记-高祖本纪》记载： 夫运筹策帷帐之中，决胜於千里之外，吾不如子房。 镇国家，抚百姓，给馈饷，不绝粮道，吾不如萧何。 连百万之军，战必胜，攻必取，吾不如韩信。 此三者，皆人杰也，吾能用之，此吾所以取天下也。 1957年，我国将O.R.正式译为“运筹学” §0.2 运筹学的发展 战后运筹学的活动扩展到工业和政府部门，发展大致可分为三个阶段： 1. 1945年到50年代初——创建时期 人数少，范围小，出版物学会寥寥无几。 1948年，英国 “运筹学俱乐部”，美国麻省理工 介绍该课程；1950年，英国伯明翰大学正式开设课程，第一本《运筹学季刊》在英国创刊； 1952年美国喀斯工业大学设运筹学硕士和博士学位； 美国运筹学会成立 §0.2 运筹学的发展 2. 20世纪50年代初期到50年代末期——成长时期 电子计算机技术的迅速发展促进运筹学的推广； 美国的约半数的大公司经营管理中融入运筹学； 大批的国家成立运筹学会，各种运筹学刊物相继问世 ； 1957年，牛津大学，第一次国际运筹学会议 1959年，国际运筹学会 成立 §0.2 运筹学的发展 3. 20世纪60年代后——迅速发展和开始普及时期 运筹学进一步细分为各个分支； 更多团队，更多期刊，更多书籍，更多学校开设课程； 开始研究一些大的复杂系统，如城市交通、环境污染、国民经济计划 §0.2 运筹学的发展 我国的运筹学发展： 1956年 第一个运筹学小组于中国科学院力学研究所成立 1958年 成立运筹学研究室 1960年 山东济南召开全国应用运筹学经验交流会 1962年和1978年 先后在北京和成都召开全国运筹学专业学术会议 1980年4月 中国运筹学会 正式成立 §0.3 运筹学的主要内容 规划理论 线性规划 非线性规划 运输问题 整数规划 动态规划 目标规划 图与网络理论 排队论 存储论 决策论 对策论 §0.4 运筹学方法解决问题的思路 ☆ 提出问题：从实际问题中提出需运作、决策的 问题。 ☆ 建立模型：抽象归纳形成表达式。 ☆ 求解：运用运筹学方法求出问题的解。 ☆ 结果分析与调整：分析解是否合理，如果需要，修 改模型后在求解。 ☆ 实施：