1.3 主要分支简介

按照所使用模型的特征，可以将运筹学的主要内容分为不同的分支，当然运筹学也在不断形成新的分支，对于一些较新的、理论上还有待完善的分支，本书不做介绍。下面分别介绍理论较成熟的运筹学经典分支。

1.数学规划（Mathematical Programming，MP）

各类决策活动中都会涉及资源的分配问题，往往要求在预定的目标下，寻求资源使用效益最大或总成本最低的方案。对这类问题进行量化分析和模型构建，会得到一个带有目标函数的不等式（或等式）方程组，一般称为数学规划模型。

当目标函数和所有约束方程都是线性表达式时，称为线性规划（Linear Programming，IP）。由于IP建模相对简单，理论成熟完善，有通用的求解算法和求解软件，其已经成为运筹学中应用最广泛的分支。其内容一般包括线性规划模型和单纯形算法、对偶理论、灵敏度分析、运输问题、线性目标规划等方面。

如果模型中存在非线性表达式，则相应的数学规划模型称为非线性规划（NonLinear Programming，NLP）模型。NLP问题广泛存在，对NLP模型的求解可以有效解决很多应用领域的复杂优化问题，但一般而言，NLP模型的求解非常困难，目前只有部分NLP问题得到了很好的解决，如二次规划、凸规划等。实践中需要尽量构建线性规划模型，如果误差太大，也要积极考虑利用分段线性化等方法将模型的复杂性降低，直到其能够求解或能够近似求解。

特别地，当数学规划模型中要求全部或者部分变量取整数时，称为整数规划（Integer Programming），如果除了整数约束外，模型中的其他部分均为线性表达式，则称为线性整数规划，否则称为一般整数规划。由于变量的离散化，整数规划的求解往往比变量连续的规划问题求解更为困难。不同领域对整数规划有着不同的称呼，如离散优化问题、组合最优化问题等。

2.图与网络分析（Graph Theory and Network Analysis，GT&NA）

生产生活中经常遇到有关最短路线选择或者网络布局优化这方面的问题，这一问题在运筹学中往往在“图与网络分析”这一分支中讨论。运筹学中把一些具体对象用“顶点”来表示，对象之间的关系用“边”来表示（根据需要，还可以在“边”上赋予一个或多个数字表示一定的定量关系，如距离、费用等，称之为网络图，简称网络），对象及对象之间的关系可用一个“图模型”来刻画，则研究图的结构和性质、对图中要素进行量化优化，就成为非常有实用价值的工作。

按照研究对象是否侧重于数量上的优化，可将这一分支大致分为“图”分析和“网络流”分析，前者更多考察图的结构和不同类型图的性质，也称为图论（Graph Theory）；后者更多强调图中宏观方面的定量优化，如最短路径、最大流量等。有趣的是，网络流的大部分问题可以转化为数学规划模型，甚至是线性规划模型。

3.动态规划（Dynamic Programming，DP）

动态规划是运筹学中专门研究多阶段决策问题的分支，它针对的是这样的问题：一个大的决策可以由多个相互影响的决策阶段组成，每个阶段依次进行决策，上一阶段的输出就是下一阶段的输入，决策者需要在每个阶段都做出决策，使得大的决策全过程达成某种总体优化目标。其中决策变量可以是连续的也可以是离散的，目标可以用方程形式来表达，也可以不用，只要满足一定条件（主要是可分离性），就可以用动态规划的求解方法求解。现实生活中多阶段决策问题的普遍性决定了动态规划有着重要的应用价值，很多复杂的决策问题都需要使用动态规划来解决。

4.排队论（Queuing Theory，QT）

人们生活中存在大量的排队现象（有形的或无形的），运筹学提供了一个专门研究排队问题的分支——排队论，它把排队区分为顾客、服务机构以及排队机制等要素，通过分析顾客到达的特征和概率分布、服务机构的串并联关系及服务时间的概率分布、不同排队规则等方面的具体情况来量化分析和优化增强系统的服务效率，为设计新的排队系统或改进现有系统的性能提供量化依据。

5.存储论（Inventory Theory，IT）

在生产经营活动中，往往需要通过库存来协调生产和需求之间在时间与空间上的矛盾，这时就存在对何时订货、订多少货、以什么策略订货进行优化的问题。运筹学中专门研究库存优化问题的分支称为存储论，它通过订货时间、订货费用、是否允许缺货、需求是确定的还是随机的等要素的分类形成不同的存储模型，通过求解模型优化订货策略，使得包括订货、生产、库存、缺货等方面的费用总体最少，为订货策略的优化设计提供量化依据。

6.决策论（Decision Theory，DT）

运筹学的研究目的是为决策优化提供量化依据，而作为一个分支的决策论则直接针对人们的决策活动，要对整个决策活动中涉及方案进行目标选取和度量、概率估计、效用计算，并形成优化方案，其核心问题是如何运用定性定量分析的相关方法，支持决策者实现由直观经验型决策到科学精细型决策的转变，包括科学决策所需遵循的原则、规则、程序、方法和技术等方面。由于社会发展的需要，实际上，这方面已经形成了一个庞大的科学门类，称为决策科学，其按照不同的维度可分为确定性决策和不确定性决策理论方法、单目标决策和多目标决策理论方法、单人决策和群决策理论方法等。作为运筹学分支的决策论一般侧重于决策中定量模型的研究和应用。

7.对策论（Game Theory，GT）

对策论是专门研究具有竞争和对抗问题的运筹学分支。在对策模型中，参与对抗的各方常称为局中人，每个局中人均有若干策略可供选择，当各局中人采取一定的策略时，对应的每个局中人都会在对抗情况下获取一定的收益（或承担一定的损失）。对策论研究的核心问题是各局中人应该如何选取策略才能保证在竞争情况下个人利益最大化。竞争（有时同时伴有合作）现象的普遍性决定了对策论是具有重要意义的运筹学分支，其在军事、经济、社会甚至国际关系等领域都有广泛的应用。经济学中的对策研究也常称为博弈论，其已经成为经济学中的研究热点，已经有十多位学者因为博弈论及其在经济领域的应用获得了诺贝尔经济学奖。

作为基础性教材，本书只介绍数学规划中的线性规划模型、整数规划模型以及图与网络分析，它们均为确定性优化模型。其中线性规划包括单纯形算法、对偶理论、灵敏度分析、运输问题和线性目标规划，整数规划介绍整数线性规划，图与网络分析介绍图的基本理论、树的理论和算法、最短路径问题、最大流量问题及最小费用流问题。