运筹学简介要点课件.ppt

1,运 筹 学Operational Research,2,运筹学简介,一、运筹学发展简介,二、运筹学的定义,三、运筹学在管理中的应用,四、运筹学的工作步骤,五、运筹学内容介绍,3,战国时代，齐王常与他的大将田忌赛马，双方约定每场各出一匹马，分三场进行比赛。齐王的马有上、中、下三等，田忌的马也有上、中、下三等，但每一等都比不上齐王同等的马，于是田忌屡赛屡输。一日，田忌的宾客、对军事颇有研究的孙膑给田忌出了一个主意，结果以二比一赢了齐王。即要善于用局部的牺牲去换取全局的胜利,从而达到以弱胜强的目的典型的博弈问题.,1. 运筹学在国内 中国古代朴素的运筹学思想,田忌赛马,一、运筹学（OR）发展简介,4,第一是取土困难。即找不到适当的地方取土烧制大量的砖瓦 ；,第二是运输困难。因为除砖瓦外还有大量的建筑材料需要运到皇宫建筑工地，运输量很大。当时最好的运输方式是水路船运，可惜皇宫不位于汴水河岸，材料通过汴水运到汴京后还得卸货上岸，改由陆路用车马运到皇宫工地，既劳神费力又可能延误工期 ；,第三是清墟排放的困难。即大量的皇宫废墟垃圾及修建完皇宫后的建筑垃圾排放何处？,在我国北宋真宗年间，首都汴京（即今开封）发生大火灾，皇宫被烧为灰烬。大臣丁渭受命主持皇宫修复工程。那时，皇帝的命令是必须执行的，否则，即为抗旨。丁渭接到圣旨后，诚惶诚恐。但他并不是那种只知道之乎也者的呆儒，他立即对皇宫废墟进行了勘察。,丁渭主持修复皇宫,5,首先，沿着皇宫前门大道至最近的汴水河岸的方向挖道取土，并将大道挖成小河道直通汴水。挖出的土即用来烧砖瓦，解决“取土困难”;,第二步，挖成河道接通汴水后，建筑材料可由汴水通过挖出的小河道直运工地，解决“运输困难”；,最后，皇宫修复后，将建筑垃圾及废料充填到小河道中，恢复原来的大道，解决了“清墟排放”的困难 。,施工方案,丁渭在修复皇宫工程中，运用了整体的解决方案，统筹兼顾，使取土、运输、清墟三项繁重的任务协调起来，在总体上得到了最佳解决。,6,“运筹帷幄中,决胜千里外”,在公元前3世纪楚汉相争中,汉高祖刘邦的著名谋士张良为推翻秦朝,打败项羽,统一全国,立下大功,刘邦赞誉他运筹帷幄中,决胜千里外. 史记在高祖本纪 、留侯世家多处提及运筹帷幄中,决胜千里外. 这里的运筹,指张良在帷幄中制定作战谋略的过程.在西汉时代, 运筹已被当作制定谋略与决策职能分工的代名词. 我国学术界1955年开始研究运筹学时,正是从史记中摘取 “运筹”一词作为OR (Operations Research)的意译,就是运用筹划、以智取胜的含义.,7,2. 运筹学在国外 运筹学的产生,运筹学的早期历史可以追溯到19世纪中叶，特拉法加尔(Trafalgar)海战和纳尔森(Nelson)秘诀。法国拿破仑统帅大军要与英国争夺海上霸主地位。英国海军统帅、海军中将纳尔森亲自制定了周密的战术方案。1805年10月21日，这场海上大战爆发了。英国是纳尔森亲自统帅的地中海舰队，由27艘战舰组成；另外一方是由费伦钮夫(Villenuve)率领的法国-西班牙联合舰队，共有33艘战舰。在一场海战后，法国-西班牙联合舰队以惨败告终：联合舰队司令费伦钮夫连同12艘战舰被俘，8艘沉没，仅13艘逃走，人员伤亡7000人。而英国战舰没有沉没，人员伤亡1663人。,8,虽然作为统帅的纳尔森阵亡，但留下了秘密备忘录中的纳尔森秘诀。1914年英国人兰彻斯特(F.W.Lanchester)针对该秘诀进行研究，发布了关于人与火力的优势与胜利之间的理论文章，这就是军事运筹学中著名的“兰彻斯特战斗方程”。第一次世界大战期间，英国生理学教授希尔领导了一个防空实验小组，他们专门研究高射炮的利用，研究如何部署高射炮在阵地中的位置，从而使敌机受到的打击最大，而自己一方受到的损失最小。因此，后来的科学家、军事学家、工程师们认为希尔领导的防空实验小组是运筹组织的萌芽，希尔就被称为“运筹学之父”。,9,“运筹学”这一名词最早出现在第二次世界大战期间美、英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略、战术问题而提出的。例如：如何合理运用雷达有效地对付德国空袭；对商船队如何进行编队护航，在船队遭受德国潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况下 如何调整其爆炸深度，才能增加对德国潜潜艇的杀伤力等。1935年，英国科学家华生华特(Waston-Wart)发明了雷达，丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已经拥有一支强大的空军，起飞17分钟即可到达英国本土。雷达作为防空系统的一部分，从技术上是可行的，但是实际运用时却不理想。在如此短的时间里，如何预警和拦截德国飞机成为一大难题。,10,为此，一些科学家就如何合理运用雷达开始了研究。1939年，英国皇家空军指挥部组织了一个小组，即成立了英国第一个运筹小组，组长是曼彻斯特大学物理学家、英国战斗机司令部顾问P.M.S.Blackett（战后因在宇宙射线方面的研究成果而获得诺贝尔物理学奖）。组员：2位理论数学家，2位应用数学家，1位天文物理学家， 1位普通物理学家，3位心理学家，1位海军军官，1位陆军军官，l位测量员）。“Blackett杂技团”。他们研究的问题是：设计将雷达信息传递到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置。他们对探测、信息传递、作战指挥、战斗机与武器的协调等做了系统的研究，并获得成功。他们在秘密报告中使用了“Operational Research”一词，即“运筹学”。,11,1736年，欧拉(Euler)解决了著名的哥尼斯堡七桥问题。 1909年,丹麦电气工程师爱尔朗(A.K.Erlang)为解决自动电话交换系统的系统排队与系统拥挤现象，提出了有关排队论的理论与方法，标志着排队论的诞生。1915年，哈里斯(F.W.Harris)推导出了经济订货批量公式。1928年,冯.诺伊曼(John Von Neumann 1903-1957）以研究二人零和对策的一系列论文为对策论奠基.1939年,苏联的康托洛维奇(L.V.kantorovich,1912-1986)发表生产组织和计划中的数学方法一书是规划论的开始. 这些工作,仍是现在运筹学研究的领域.但作为一门学科, 运筹学诞生于20世纪第二次世界大战期间,运筹学起源于军事、管理、经济.,12,3. 运筹学的发展,运筹学的创建时期（1945-20世纪50年代初） 1947年，美国数学家丹捷格(G.B.Dantizg)发表了关于线性规划的研究成果，所解决的问题是美国空军军事规划时提出的，并给出了求解线性规划问题的单纯形算法。 1948年英国成立了运筹学俱乐部，定期讨论如何把运筹学用于民用事业，并取得了成果。 1952年世界上第一个运筹学会在美国成立，并出版期刊运筹学。运筹学的成长时期（20世纪50年代初到20世纪50年代末） 形成了比较完备的一套理论，如规划论、排队论、存贮论、决策论等。 1957年在英国牛津大学召开了第一届运筹学国际会议。 1959年成立了国际运筹学学会(International Federation of Operations Research Societies, IFORS).,13,3. 运筹学的发展,运筹学的普及和迅速发展时期（20世纪60年代以来） 计算机的普及和发展是推动运筹学迅速发展的巨大动力。 第三代电子数字计算机的出现，促使运筹学得以用来研究一些大型复杂的系统，如城市交通、环境污染、国民经济计划等。 运筹学细分为许多分支，很多内容出现在本科、硕士、博士研究生的教学课程中。 运筹学的学科划分没有统一的标准，在工科学院、商学院、经济学院和数理学院的教学中都可以发现它的存在。,14,国内： 1956年钱学森（系统工程专家）、许国志（数学家）从美国回来，刘源张（质量管理专家）从日本回来，周华章（经济学家、凯恩斯的学生）从英国回来。他们将运筹学由西方引入我国，最初译为“运用学”。1957年从“运筹帷幄之中，决胜千里之外”中摘取“运筹”二字，将O.R.正式命名为“运筹学”。1956年，我国第一个运筹学小组在中科院力学研究所成立。1958年分别在中国科学院力学研究所、数学研究所成立了二个运筹学研究室。1960年二个运筹学研究室合并。1978年以前（文革期间）钱学森在七机部负责我国“两弹一星”的研究工作。1978年以后钱学森认为应向社会推广，成立了中国军事运筹学会，1980年成立了中国运筹学会和中国系统工程学会。我国于1982年加入国际运筹学联合会，并于1999年8月组织了第15届大会。,15,运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法Morse和Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策英国运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为Management Science,二、运筹学的定义,16,三、运筹学在管理中的应用,生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。库存管理：多种物资库存量的管理，库存方式、库存量等。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及厂址的选择等。人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。其它：设备维修与更新，项目选择与评价，工程优化设计与管理等。,17,四、运筹学的工作步骤,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,满意？,Yes,No,No,结束,Yes,明确问题 建立模型 设计算法 整理数据 求解模型 评价结果,明确问题,18,五、运筹学内容介绍,线性规划与单纯形法（第1章） 对偶理论与灵敏度分析（第2章） 运输问题（第3章） 整数规划（第5章） 图论（第10,11章） 排队论 （第12章） 动态规划（第8,9章）,非线性规划存储论对策论决策论可靠性理论随机规划模糊规划,19,运筹学省级精品课程网站http:/ http:/,