搜索
运筹学OperationsResearch安徽财经大学统计与应用数学学院page28February2020安徽财经大学统计与应用数学学院参考书目：2、《管理运筹学》韩大卫著大连理工大学出版社1、《运筹学(修订版)》运筹学教材编写组清华大学出版社3、《运筹学教程》胡运权、郭耀煌著清华大学出版社4、《运筹学及其应用》朱求长编著武汉大学出版社5、《运筹学》刘强主编石油工业出版社6、《运筹学》程理民、张亚光著科学技术文献出版社page38February2020安徽财经大学统计与应用数学学院Contents第1章绪论1第2章线性规划2第3章线性规划的对偶理论和灵敏度分析3第4章运输问题4第5章整数规划5第6章动态规划6第7章图与网络模型7第一章绪论Ch1Introductionpage58February2020安徽财经大学统计与应用数学学院运筹学的应用§1.3§1.2§1.1运筹学发展简史运筹学的定义运筹学的分支第一章绪论§1.4page68February2020安徽财经大学统计与应用数学学院§1.1运筹学其发展简史朴素的运筹学思想早在两千多年前就被人们应用着，田忌赛马即为一个典型的运用对策论思想解决问题的范例。欧拉早在1736年便用图论思想成功解决了哥尼斯堡七桥问题。运筹一词最早出现在《汉书·高帝纪》中记载“上（刘邦）曰：夫运筹帷幄之中，决胜于千里之外，吾不如子房（张良）。”丁渭修皇宫沈括运军粮page78February2020安徽财经大学统计与应用数学学院连通网络可一笔画的充要条件：它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2返回page88February2020安徽财经大学统计与应用数学学院§1.1运筹学其发展简史运筹学作为一门学科是近60年才发展起来的。运筹学的早期工作可以追溯到1914年，军事运筹学中的兰彻斯特（Lanchester）战斗方程式的提出。1916年英国工程师F.W.Lanchester在《战斗中的飞机》一文中，首先提出用常微分方程组描述敌对双方消灭过程，定性地说明了集中兵力的原理。Erlang在20世纪初期发展了排队论，提出了一些著名的公式，并将之应用于哥本哈根电话交换机的效率研究。英国人莫尔斯(Morse)建立的分析海军护航舰队损失的数学模型，也是最早进行的OR工作。第一次世界大战前后所做出的努力、积累的经验和探索的结果为OR日后的发展奠定了基础。但是这一时期OR的发展处于摸索之中，理论思想尚在萌芽阶段，未能获得较快发展。page98February2020安徽财经大学统计与应用数学学院§1.1运筹学其发展简史运筹学作为一门新兴学科是在第二次世界大战中兴起。1935年，英国为防御德国战机袭击，在英国东海岸的奥福德纳斯(Orfordness)装备了雷达。使用中发现所传送的信号间常常相互矛盾。为此，1938年在波德塞(Bowdsey)，由A.P.Rowe负责组建了一个研究机构，其职责是让军事领导人学会用雷达定位敌方飞机。Rowe和R.W.Watt爵士主持了最早的两个雷达研究，并将之命名为OperationalResearch。波德塞被称为OR的诞生地。该研究机构的建立标志着现代OR的开端。page108February2020安徽财经大学统计与应用数学学院1939年9月，英国空军为了延长雷达首次预警与敌机袭击之间的时间间隔，将波德塞OR小组领导人之一的E.C.Williams调至皇家空军作战指挥部的新工作组。之后，皇家空军轰炸指挥部、海岸指挥部和英军防空指挥部均建立了OR工作组。1940年秋，由于德国战机对英国的夜间空袭，物理学家P.M.S.Blackett加入防空指挥部，组建了运筹工作组—著名的“Blackett马戏团”，它就是由2个生理学家、2个物理学家、1个军官、1个前线测量员组成，之后又有1个普通物理学家、2个数学家加入和第3个生理学家加入。1941年12月，Blackett被咨询有无可能为海军建立运筹工作组。次年1月，他转到海军从事OR创建工作。防空指挥部的OR工作组遂成为英国OR工作组的核心。page118February2020安徽财经大学统计与应用数学学院二战后，从事这项工作的许多专家转到经济、企业和大学、研究所，继续从事决策的数量方法研究，运筹学逐步形成并迅速发展起来。形成了运筹学的许多分支。如数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存储论、对策论、决策论、设备维修更新理论、可靠论和质量管理等。1947年美国人丹捷格（GeorgeDantzig）提出的求解线性规划问题的单纯形法是运筹学发展史上最重大的进展之一。page128February2020安徽财经大学统计与应用数学学院运筹学的真正发展是在二十世纪五十和六十年代，其标志是1949年线性规划理论的建立。然后，于1951年创立了非线性规划理论；1954年建立了网络流理论；1955年创立随机规划以及1958年创立了整数规划理论。其他方面，如排队论，存储论和马氏决策理论也在同期得到了迅速的发展。与此同时，运筹学的应用也遍及经济和社会生活的各个部门与领域。page138February2020安徽财经大学统计与应用数学学院国际运筹学会联合会(IFORS)成立于1959年，现在已有44个成员国，包括了世界各主要发达国家和有影响的发展中国家。三年一次的世界范围的IFORS大会已举行了10余次。运筹学方面的期刊己超过百种。这些事实说明，运筹学作为一门独立的新兴科学，早己为国际社会所公认。page148February2020安徽财经大学统计与应用数学学院50年代中期，钱学森等教授将运筹学由西方引入我国，并结合我国的特点在国内推广应用。在经济数学方面，特别是投入产出表的研究和应用开展较早，1958年为了解决粮食的合理调运问题，我国科学家提出了“图上作业法”，有效地解决了线性规划中的运输问题。在解决邮递员合理投递线路时，管梅谷教授提出了国外称之为“中国邮路问题”的解法。近年来运筹学的应用已趋向研究规模大和复杂的问题，如部门计划、区域经济规划等，并已与系统工程难以分解。page158February2020安徽财经大学统计与应用数学学院运筹学的应用§1.3§1.2§1.1运筹学发展简史运筹学的定义运筹学的分支第一章绪论§1.4page168February2020安徽财经大学统计与应用数学学院运筹学是一门应用于管理有组织系统的学科”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具”——《大英百科全书》运筹学是一门诞生于20世纪30年代的新兴的学科，运筹学是用数学方法研究各种系统最优化问题的学科，应用运筹学解决问题的动机是为决策者提供科学决策的依据，目的是求解系统最优化问题，即制定合理的运用人力、物力、财力的最优方案。——《现代科学综述大辞典》主要研究经济活动与军事活动中能用数量来表达的有关应用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，做出综合性的合理安排，以达到较经济较有效地使用人力和物力。——《辞海》（1979年版）page178February2020安徽财经大学统计与应用数学学院运筹学的应用§1.3§1.2§1.1运筹学发展简史运筹学的定义运筹学的分支第一章绪论§1.4page188February2020安徽财经大学统计与应用数学学院运筹学经过60多年的发展，已经形成了自己相对完善的学科理论体系，包含有众多的分支，每一个分支都有丰富的内容。本书的内容涉及到运筹学的主要分支，具体包括线性规划、整数规划、非线性规划、动态规划、图与网络、排队论、存贮论、决策论、对策论、预测等。下面对运筹学的主要分支作简要介绍。page198February2020安徽财经大学统计与应用数学学院（1）线性规划(LinearProgramming)。线性规划解决的主要问题是在给定线性约束条件下，求线性目标函数的极大极小值问题。G.B.Danzig等人提出了求解线性规划问题的单纯形方法，这为线性规划的理论与计算奠定了基础，同时对运筹学的发展起了重大的推动作用。许多工业、农业、商业、交通运输业等部门的实际问题都可以化成线性规划来解决，特别是电子计算机的出现和日益完善，含有成千上万个约束条件和变量的大规模的复杂实际问题可用电子计算机来求解。典型线性规划问题有生产计划问题、混合配料问题、下料问题、运输问题等。page208February2020安徽财经大学统计与应用数学学院例如：用两种原料，生产、、三种产品，产品对原料的消耗系数、现有原料数、以及单位产品的利润如下表：B1B2B3现有原料数A1123100A2314200单位产品利润437产品原料应如何安排生产，才能使得总利润最大？这就是一个较简单的线性规划问题。page218February2020安徽财经大学统计与应用数学学院设：B1、B2、B3产品的计划产量分别为x1、x2、x3，则当目标函数是线性函数，且约束条件都是线性等式或线性不等式时，就称它为线性规划问题。否则，就称为非线性规划问题。321734maxxxxS求：目标函数0,0,02004310032..321321321xxxxxxxxxts约束条件page228February2020安徽财经大学统计与应用数学学院（2）整数规划（IntegerProgramming）。在许多实际问题中，某些变量必须具有整数要求才有意义，因此整数规划是数学规划一个重要的分支。特别地，当线性规划的变量只能取整数0或1时，整数规划称为0-1整数规划，简称0-1规划。0-1规划的一个典型应用是任务指派问题。page238February2020安徽财经大学统计与应用数学学院例：（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些最有用的东西，但他最多只能携带b公斤的物品。而每件物品都只能整件携带，于是他给每件物品规定了一定的“价值”，以表示其有用程度。如果共有m件物品，第i件物品重公斤，价值为。问题变成：在携带物品总重量不超过b公斤的条件下，携带哪些物品，可使总价值最大？iciapage248February2020安徽财经大学统计与应用数学学院首先引进ix规定：件物品不携带第件物品携带第iixi01ni,,2,1该背包问题的数学模型为：miiixcS1max10.1或imiiixbxats这是一个0—1规划问题。page258February2020安徽财经大学统计与应用数学学院（3）非线性规划(NonlinearProgramming)。如果规划问题的目标函数或约束方程为非线性函数，则规划问题称为非线性规划。非线性规划是线性规划的进一步发展和继续。许多如工程设计等实际问题中，其物理变量的表达式是非线性的。非线性规划扩大了数学规划的应用范围，是优化设计的有力工具。同时非线性规划提出了许多基本理论问题，数学中的凸分析、数值分析等也得到了发展。page268February2020安徽财经大学统计与应用数学学院（4）动态规划(DynamicProgramming)。动态规划是一种解决多阶段决策问题的优化方法。动态规划是20世纪50年代初由美国数学家贝尔曼(R.Bellman)等人提出的，该方法根据多阶段决策问题的特点，提出了决策多阶段决策问题的最优化原理。利用动态规划的最优性原理，可以解决生产管理和工程技术等领域的许多实际问题，如最优路径、资源分配、生产计划和库存等。近年来在工程控制、技术物理和通讯中的最佳控制问题中，已经成为经常使用的重要工具。page278February2020安徽财经大学统计与应用数学学院(5)图与网络(ChartTheoryandNetwork)。图论是一个古老的但又十分活跃的分支，它是网络技术的基础。图论的创始人是数学家欧拉，他解决了著名的哥尼斯堡七桥问题。网络规划主要是研究解决生产组织、计划管理中诸如最小生成树、最短路径、最小费用流等