第三节 运筹学的主要分支

运筹学的主要分支包括：规划论(包括线性规划、非线性规划、整数规划和动态规划)、图论、决策论、对策论、排队论、存储论等。

(1)规划论

规划论又称为数学规划，是运筹学的一个重要分支，包括了线性规划、非线性规划和动态规划。1939年，苏联的利奥尼德·康托洛维奇(L.V.Kantorovich)和美国的希奇柯克(F.L.Hitchcock)等人就在生产组织管理和制定交通运输方案方面首先研究和应用——线性规划方法。非线性规划的基础性工作则是在1951年由库恩(H.W.Kuhn)和达克(A.W.Tucker)等人完成的。数学规划的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成在满足约束条件下的求函数极大极小值问题。数学规划和古典的求极值的问题有本质上的不同，古典方法只能处理具有简单表达式，和简单约束条件的情况。而现代的数学规划中的问题目标函数和约束条件都很复杂，而且要求给出某种精确度的数字解答，因此算法的研究特别受到重视。

数学规划中最简单的一种问题就是线性规划。如果约束条件和目标函数都是呈线性关系的就叫线性规划。线性规划及其解法—单纯形法的出现，对运筹学的发展起了重大的推动作用。许多实际问题都可以化成线性规划来解决，而单纯形法有是一个行之有效的算法，加上计算机的出现，使一些大型复杂的实际问题的解决成为现实。

如果线性规划模型中目标函数或约束条件不全是线性的，对这类模型的研究构成非线性规划分支。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本理论问题，使数学中的如凸分析、数值分析等也得到了发展。

动态规则是解决多阶段决策过程最优化的运筹学分支。大约产生于20世纪50年代。1951年美国数学家贝尔曼(R.Bellman)等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。动态规划近年来在工程控制、技术物理和通讯中的最佳控制问题中，已经成为经常使用的重要工具。

(2)图论

图论是研究由节点和边所组成的图形的数学理论和方法。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论的创始人是数学家欧拉。1736年他发表了图论方面的第一篇论文，解决了著名的哥尼斯堡七桥难题。相隔一百年后，在1847年基尔霍夫第一次应用图论的原理分析电网，从而把图论引进到工程技术领域。20世纪50年代以来，图论的理论得到了进一步发展，将复杂庞大的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题，例如，完成工程任务的时间最少，距离最短，费用最省等等。图论受到数学、工程技术及经营管理等各方面越来越广泛的重视。

(3)存贮论

存贮论又称库存理论，是一种研究物资最优存储及存储控制的理论和方法，是运筹学中发展较早的分支。早在1915年，哈李斯(F.Harris)针对银行货币的储备问题进行了详细的研究，建立了一个确定性的存贮费用模型，并求得了最佳批量公式。1934年威尔逊(R.H.Wilson)重新得出了这个公式，后来人们称这个公式为经济订购批量公式(简称为EOQ公式)。这是属于存贮论的早期工作。存贮论真正作为一门理论发展起来还是在本世纪50年代的事。1958年威汀(T.M.Whitin)发表了《存贮管理的理论》一书，随后阿罗(K.J.Arrow)等发表了〈存贮和生产的数学理论研究〉，毛恩(P.A.Moran)在1959年写了《存贮理论》。此后，存贮论成了运筹学中的一个独立的分支，并陆续对随机或非平稳需求的存贮模型进行了广泛深入的研究。

(4)排队论

排队论又叫随机服务系统理论，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法。它的研究目的是要回答如何改进服务机构或组织被服务的对象，使得某种指标达到最优的问题。比如一个港口应该有多少个码头，一个工厂应该有多少维修人员等。最初是在二十世纪初由丹麦工程师艾尔郎关于电话交换机的效率研究开始的，在第二次世界大战中为了对飞机场跑道的容纳量进行估算，它得到了进一步的发展，其相应的学科更新论、可靠性理论等也都发展起来。因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具。此外，还有微分和微分方程。排队论在日常生活中的应用是相当广泛的，比如水库水量的调节、生产流水线的安排，铁路分成场的调度、电网的设计等等。

(5)决策论

决策论是研究各种环境条件下的决策的理论和方法。所谓决策为最优地达到目标，依据一定准则，对若干备选行动的方案进行的抉择。决策问题是由决策者和决策域构成的，而决策域又由决策空间、状态空间和结果函数构成。研究决策理论与方法的科学就是决策科学。决策科学是在研究决策活动基本规律的基础上，总结出一套进行决策必须遵循的原则、规则、程序、方法和技术。决策的基本步骤为：确定问题，提出决策的目标；发现、探索和拟定各种可行方案；从多种可行方案中，选出最满意的方案；决策的执行与反馈，以寻求决策的动态最优。

(6)对策论

一种处理竞争与合作问题的数学决策方法，属应用数学的一个分支，对策论已经成为经济学的标准分析工具之一。目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。