《运筹学的研究对象及研究方法》运筹学分支简介

​运筹学的研究对象及研究方法

在本书开头就曾提出:什么是运筹学?现在

可以简要地回答这一问题了。按英国运筹学会的说法，运筹学是“运用科学方法来解决工业、商业、政府、国防等部门里，有关人力、机器、物资、金钱等大型系统的指挥或管理中出现的复杂问题的一门学科”。

关于运筹学的这个定义，并不是唯一的，在这个定义出现的年代，就有了几十种不同的定义方法。现在，它的定义已是数以百计了。我们不妨再向读者介绍两个定义，一个是说“运筹学是研究经济活动与军事活动中，能用数量来表达的有关运用、筹划和管理等方面的问题。它根据问题的要求。通过数学方法的分析与运算，作出综合性的合理安排，以达到较经济、较有效地使用人力和物力。”另一个是说“运筹学是一门新兴的边缘科学，它使用数学方法，利用电子计算机等现代化工具，把复杂的研究对象当作综合系统，进行定量分析。从整体最优出发，进行有目的的分析，提出一个最优的可行方案，提供给执行机构作为决策的参考。”

尽管运筹学有不同的定义方法，但我们可以从这些叙述中得到运筹学所具有的特点。

1.运筹学的研究对象是一类有目的性的、可控制的过程或行动。换句话说，它是研究可受人的控制而产生不同影响的系统。说得更通俗些就是，不论哪一个行业，凡属于安排、调度、筹划、控制等问题都是运筹学研究的对象。

2.运筹学是从量的方面，对上述体系进行研究。

过去，在一些小商店或小工厂中,有一把算盘，一个帐本就可以进行经营管理了。但在今天的大企业中，要对十分复杂的系统进行安排、筹划或控制，用那种落后的方式进行管理，或者凭经验作些定性分析就远远不够了。我们必须从量的方面给出较满意的结果。

要实现在量的方面的研究，必须建立反映这一事物本质的教学模型，这个数学模型一般是以优化的形式出现的。

在建立数学模型时，必须用科学的态度弄清楚实际问题，以及它所涉及的系统。在实际问题中，

作者来说，要解决实际问题，最困难的步骤一个是如何将实际问题转化为数学模型，另一个是如何收集到比较准确的原始数据。

运筹学分支简介

运筹学的研究特点是将许多具有典型性的问

题，抽象成具有共性的数学模型。对模型求解后，再将结果用于这类问题。在运筹学中，将处理方法相近的问题归为一类，这种归类就形成了运筹学中许多相对独立的分支。由于运筹学的分支很多，限于篇幅，我们只能选择其中一部分做些简单介绍。

(一)线性规划

先举一个例子。

某工厂要制造A、B两种产品，每件A产品要消耗甲原料2公斤，乙原料2公斤,其产值20元;每件B产品消耗甲原料3公斤，乙原料1公斤，其产值15元。现该厂有甲原料600公斤，乙原料400

问题，但是由于这些问题的规模不同(表现在决策变量个数和约束条件个数不同),因此在计算时所用的时间也不同。为了判断问题规模的大小，可以把这个问题输入计算机时必须的数据，转化成一个二进制的代码序列(即由0和1组成的序列)。我们把这个序列中所包含的0与1的个数L叫做这个具体问题的输入长度，显然可以用L表示这一问题规模的大小。

给定一个算法，对于输入长度为L的具体问题来说，如果它的计算步数是关于L的一个多项式，则称这个算法是多项式算法。用多项式算法解具体问题时，可有效地利用计算机求得解答。因此，可以认为多项式算法是一种好算法。然而，单纯形方法却不是多项式算法，而是一种指数算法。

近十年来，许多数学家为解决这一问题，都在研究线性规划是否有多项式算法。苏联数学家哈奇扬(XayugH)在1979年提出了《线性规划的多项式算法》，也称作线性规划的椭球算法，从理论上证明了，线性规划问题存在着多项式算法。1984年，印度数学家Karmakar又提出了不同于椭球算法的线性规划的多项式算法，引起了轰动。目前还在对这一方法进行深入的探讨。

为了不涉及过多的数学知识，我们用方程组的知识来介绍一下单纯形法。用第一个例子加以说明。

不能超过200，如果取x=200，则目标函数值S=20x200=4000

这个S值是不是目标函数的最大值呢?用什么标准判断目标函数已取得了最大值?我们给出一个判断方法:当表格中的最下面一行的所有元素全部变为非负数时，就求得了S的最大值。这是因为这些元素为非负时，意味着目标函数S中变量的系数是负值或为零，因而当变量再取大于零的值时，只会使目标函数S的值下降。

所谓单纯形方法，就是采用表格化计算，将它最下面一行元素全部变为非负。这样，就求出了目标函数的最大值。

下面是采用单纯形法求目标函数最大值的一般步骤:

1.格的最下面一行中找出一个负数(如果同时有几个负数，可选下标号最小的变量对应的负数);

2°.在1°中确定的元素所对应的列中，找出大于零的元素，分别去除表格中最右一列中的对应元素，求得商值;

3°.比较2°中的商值，对应最小商值的那个列元素作为表格变化的中心，称为主元素，并用方框“口”框起来;

其一，整数规划的可行方案往往是有限的，是否能将这些方案一一比较后，得出最优方案呢?我们说这一想法是难于实现的。以分配问题为例，4个人的分配方案共有4!=24种，要一一比较方案的优劣，是相当费时间的。而20人的分配方案就有20!=2433x10种，如果一一比较的话，即使用高速计算机也得计算几万年，可见用一一列举的方法(数学上称为穷举法或枚举法)解整数规划是不行的。

其二，整数规划的数学模型与线性规划的数学模型很相近，能否先不考虑“取整”的约束，而用单纯形方法求出非整数的最优解，再用四舍五入法“取整”而获得整数最优解呢?这种办法一般来说是不会成功的。原因是这样“凑”出来的整数解或者不是整数规划的最优解，或者根本不是整数规划的可行解(满足所有约束条件的解)。

基于以上两点，我们有必要对整数规划的算法进行研究。

关于整数规划的算法概括起来有两个分支，一个是搜索法(包括隐枚举法和分枝定界法)，另一个是割平面法。搜索法就是把整数解看作是一个确定的点阵，如果全部搜索这些点阵，就是穷举法，如果只枚举一部分而扬弃无希望的点，被扬弃的点可

(6)的后继问题的最优值不会超过307，而问题(7)得不到可行解。于是问题(1)解完，最优解为x=4，xz=2且MaxS=340。

割平面法的思想是利用线性规划的解法，然后附加新的约束条件，割去非整数解的范围，但不会割去整数解部分，继续下去，可得到整数最优解。

割平面的算法是1958年由柯莫瑞(RE.Gomo ry)提出的。从理论上说这个算法可以解任意规模的整数规划问题，但由于计算能力的限制以及方法本身的缺陷，实际上只能解小规模的整数规划问题。1960年ALand和A.G.Doig提出分枝定界原理，由于概念简单，方法灵活，适应性强，容易在计算机上实现，因而成为大多数整数规划问题算法的基础。目前关于整数规划算法的研究还是很活跃的。

下面我们向读者介绍解决分配问题的匈牙利法。

分配问题是特殊的运输问题，当然可以用运输模型的解法求解，但由于它具有变量只取0、1两个数值的特点，因此可以用所谓匈牙利法求解，这个方法是由匈牙利数学家克尼格(Konig)在1955年提出的。

例4某教研组有四门课要开出，准备派四位教员去承担，因各人专长不同，备课时间如下表所

要选择一个最优策略，对于这一策略其效果在预定的标准下是最好的。这种处理优化问题的方法称为动态规划。

动态规划的创始人是美国数学家贝尔曼(R.B- ellman)。他在四十年代的后期和五十年代初期曾在美国兰德公司工作，他针对一些多阶段的决策问题，提出了解决这类问题的最优化原理，并在1957年发表了《动态规划》一书，这是关于动态规划理论和方法的第一本著作。动态规划在存贮控制理论、网络流、车间作业安排、生产控制以及整数规划中都得到了应用。

动态规划不象线性规划那样，有一个标准化的数学模型，然后对这个模型配合相应的解法。动态规划是为决策人取得最佳效果提供合理的思维方法。人们根据最优化原理得出所谓函数方程以后，还要结合问题的性质以及数学技巧来求解，而并非有统一的数学解法。从某种意义上说，这也正是它的一个缺点。另外，在动态规划中还存在着一个“维数障碍”，就是说，当变量的个数太多时，计算量过大，往往使问题无法解决。

但是，动态规划毕竟还是解决离散性问题的一种较好的工具。

我们用一个简单的例子，说明动态规划的基本思想。

用动态规划解决这类问题有许多优点。

其一，减少了计算量。可能有的读者会想，用穷举法不是也可找出一条最短路线吗?对于一个大型问题，这是不可能的。例如,当问题有10个阶段，而每个阶段又有10项可能的决策时，穷举法必须考虑101°种方案，而利用动态规划所计算的方案不会超过103个。

其二，利用动态规划求出的不仅仅是从A到E的最短路线，而且得到了从所有各中间点出发到终点的最短路线和最短距离，这就是说，求出的是一族最优策略，这对于解决实际问题是非常有利的。

(四)对策论

在日常生活中，我们经常碰到一些带有竞争、比赛性质的现象，如下棋、打扑克、体育比赛等。参加竞争的各方都希望能发挥自己的特长，抑制对方的长处而取得胜利。

在经济领域内，各国之间的贸易谈判;各公司企业之间的加工订货谈判;各企业争夺国际或国内市场等都是竞争现象。

在农业生产中，人们为了获得丰收，要研究合理施肥以及如何战胜水、旱、虫等灾害。这可以看成是以人为一方，以自然为一方的竞争现象。

在军事斗争中，更明显地表现为敌我双方你死我活的竞争。

以上这些带有竞争性质的现象，称为对策现象或博弈现象。

有一些竞赛活动，某一方的胜利是纯粹依赖于机缘的。如两人轮流掷骰子，谁的点大谁的得分就多，这种比赛完全听其自然，人们无法事先作出选择。这种竞赛活动不是对策论研究的对象。两人下棋这种竞赛活动与前者不同，当一方下了一着棋后，对方有许多不同的着法，或者说有许多不同的对策。对策不同，结果也不同，很可能是一 着 妙棋,奠定了胜利的基础,也可能一着棋错,满盘皆输,这完全依靠有理智的人去选择。对策论就是研究这种富于策略性的竞赛或斗争活动。一般来说，在一些对策现象中，都存在着决策者如何选择一个最优策略，用以对付另一方，从而使自己获得胜利的问题。对策论就是研究对策现象的数学理论和方法的科学。

最初用数学方法研究对策问题的数学家是策墨洛(Zemelo)，他在1921年用数学方法研究过国际象棋的对弈法。但真正为当前对策论奠定理论基础的，是美籍匈牙利数学家冯·诺曼(John·Von Neumann)和美国经济学家摩根斯坦(0·Morgen-人都有六个策略，这就是

(上、中、下) (上、下、中)

(中、上、下) (中、下、上)

(下、中、上) (下、上、中)

我们将这些策略的全体称为一个策略集合，如果在一局对策中，局中人的策略只有有限个，称为“有限策略”，否则称为“无限策略”。

3.一局对策的得失:在一局对策之后，对每个局中人来说，不外乎是胜利或失败，排名的先后或物质上的收益、支出等等。事实上，每一局的得失，与局中人所取定的策略有关。在齐王与田忌赛马中，齐王出策略(上、中、下)，田忌出(下、上、中)与之相对，则田忌可得一千金，若田忌这时也出策略(上、中、下),那么他肯定要输掉三千金了。在一局对策中，从每个局中人的策略集合中，各取出一个策略进行配对，组成一个策略组，称为“局势”。显然“得失”是“局势”的函数。如果在任一局势中，全体局中人的得失相加总和等于零，这个对策称为“零和对策”，如下棋、打桥牌、齐王与田忌赛马等都是所谓“二人零和对策”。也有“非零和对策”。如两个企业在市场争夺的对策问题中，最后结果无非是一个获利多些，另一个少些。

“二人零和对策”是对策论中一种最简单的情

甲。这样，甲最后获胜，收入是2，而乙失败，付出也恰好为2。

值得注意的是，我们所研究的是有理智的局中人在每一局势下采取的行动，因此进行对策时，要考虑到最坏的后果，在选择任何策略时，都要想到对方总是可能采取最不利于这个策略的行动方式来对抗。基于这一原则，最优策略不是冒险性结果，而是审慎的，留有余地的周密安排。

在上例中，甲如果不存在冒险心理，为了尽可能达到最佳结局，他必须计算每个策略与乙方的策略对策的结果，从而求得使用每个策略带来的最坏收入，再从这些最坏收入的数字中，选出一个收入最大的数字来，对应这个数字的行策略就是甲的最优策略。同样，可以求得乙的最优策略。但应注意，局中人乙的每个策略的最大损失是甲方支付表中各列中最大的正数，为了尽可能减少损失，乙应从这些数字中选出一个最小数，与这个数字对应的列策略，就是乙的最优策略。

在表14中，每行的最小数字分别是-8、2、 -12、-3，在这些最坏收入中，2是最大收入，因此甲的最优策略是这个数字2对应的策略a2。同理，在各列中最大正数分别是19、2、6，它们表示乙的损失，从这些数字中挑选一个最小数字也是2，于是乙应使用策略β2,才会使其损失最小。我们称策略对(az，βz)为纯策略下的对策解，其中 a2、β₂分别为局中人甲、乙的最优策略。

在支付表中，az与β₂交叉点上的元素az2=2，称为它的一个鞍点数，简称鞍点。这个数值在支付表中是所在行中的最小数，同时又是所在列中的最大数。这个数值2称为对策值，记为v=2。它表明甲的收入恰等于乙的支出。这是二人零和对策的基本原理。

顺便指出，如果甲选取策略a2，而乙具有冒险心理，不采取策略Bz而是别的策略，那么甲的收入就会是3或6，这都超过了甲的预期值v=2。

一般来说，u≥0时，甲可以有处于不败之地的策略;u<0时，乙有处于不败之地的策略。

上面所谈的最优策略，实际上是保守策略。换句话说，就是在双方都不愿意承担任何风险的情况下的稳妥保守策略。因此，在有鞍点的对策中，如果双方都很“明智”的话，那么完全可以事先告诉对方，自己将采取的最优策略是什么，这并不影响竞争的结果。这种对策的最优策略的选择以及各自的所得，都是完全确定的，这称为确定型决策。

读者还应当知道，有的二人零和对策的鞍点不止一个。

例如给定一个二人零和对策的支付表(如表15)它的各行最小元素分别为0、0、-2，其中最大

了减少损失将采取策略β1。由于不存在鞍点，因此甲方估计到乙方采取策略B时，他将认为采用a:比 az更好些。然而，如果乙具有远见，预测到甲的作法，则乙方认为采取策略Bz更好些，这时他的损失是3而不是6。这一循环过程说明，对于甲和乙来说，都不存在最优策略。也就是说，他们在对策过程中不是只使用一个策略,而是应当以适当的概率，随机地交替使用各个策略，这在对策论中称之为混合策略。

混合策略下的对策解，是一对最优混合策略(P*，Q*)，相应于这个解的赢得叫做对策值v。

对于只有两个局中人，每个局中人各有两个策略的所谓2x2型对策，可用画图方法求得对策解和对策值。

我们以上例说明画图方法。

对于甲方来说，在横轴上截取长度为1的线段，其左端点为x=0，右端点为x=1，为了画图方便，在x=0及x=1处各画一个纵坐标，如图9所示。

在左侧纵坐标上截取4个单位和8个单位，分别表示甲方采取策略az时的赢得，并记作β1、2。

在右侧纵坐标上截取3个单位和6个单位，分别表示甲方采取策略a时的赢得，并记作Bz、β。

对策论的研究要联系社会心理学、政治学、军事学、管理科学等。它是一门较为复杂的边缘科学。目前它的内容已从有限对策发展到无限对策，由矩阵对策发展到微分对策。虽然它的理论成果大部分还是定性的，但它还是广泛地应用于军事部署、自动控制、基本建设、地质勘探、海洋捕捞、工农业生产安排、商品经营、贸易谈判以及各种体育竞赛方面。因此它是一门十分有发展前途的学科。

(五)决策论

决策是在人们生活和工作中普遍存在的一种

活动。比如一个卖冰棍的小贩,每卖出一根赚2分，若卖不出去，每根赔1分。当他听到天气预报说今天有雨时，就面临一个决策问题:到底取货还是不取货?因为天气预报不会是百分之百的准确。小贩如果去取货，因下雨卖不出去冰棍要受损失，如果不取货，可能也因没下雨而没赚到钱，这也是一种损失。又如一个企业，分析市场对某种新产品的需求，情况是好、中、坏三种可能，情况好能获利，情况坏要赔钱，而中等情况不赔不赚。该工厂对这种新产品到底投产不投产，需要企业的决策人作出抉择。简单地说，决策就是决定干或者不干。决策是行为的选择，行为是决策的执行。从管理的角度来说，决策贯彻管理的全过程，管理就是决策。

决策论就是研究抉择结构和选择决策方式及标准的一门科学，它是指导人们用科学方法进行分析、比较，以便作出正确决策的有用工具。

决策活动是随着人类有意识的活动的产生而开始的。我们中华民族的历史上，有许多优秀决策的实例。如三国时期,诸葛亮借东风火烧战船，与东吴孙权共同消灭曹军二十万雄兵，取得赤壁大战的胜利，就是古代军事家运用决策方法的典型事例。

但是，作为决策理论的提出，还是第二次世界大战以后的事。以美国的赫伯特·西蒙(HA Simon)和詹姆士·马奇(J.G.March)为代表，他们吸收了行为科学、系统理论、运筹学和计算机科学的内容，对决策的过程、决策准则、程序化决策和非程序化决策以及计算机在决策中的应用进行了研究，创立了决策理论。

在运筹学中所介绍的决策理论，主要是用来解决确定型决策、不确定型决策和风险型决策的决策分析方法。用下面的例子加以说明。

例如，有一个工地，施工负责人决定下周是否开工。如果天气好，开工后可按期完工，获利10万元，如果开工后天气不好，造成损失为4万元，如果不开工，则不论天气好坏都造成窝工，损失2万

4.道自然状态出现的可能性大小(用概率表示)。在上例中要依靠天气预报的准确性程度;

5.对于各种不同决策下的益损值作出估计。根据决策者掌握的信息量的不同，将决策问题分为三个类型。

①确定型决策。是指条件4的信息掌握得完全充分，即决策系统所处的状态是肯定的。那么决策者只要算出在这种状态下不同决策的益损情况，然后加以比较，就可以选出最优决策。在上例中，如果天气预报在未来一段时间内都是好天气，那么这个决策问题就变为确定型决策，这时表17中右边一列就不存在了。施工负责人的最优决策当然是开工。

看起来确定型决策很简单，但对于许多实际问题来说，计算量是相当大的，因此在具体解题时，还要借助线性规划、非线性规划、动态规划等方法才能解决。

②风险型决策。是指条件4的信息掌握得不很充分，即我们不能确切地知道哪种自然状态将要发生，但是每种自然状态发生的可能性是可以预先估计或从历史资料中得到。

在处理这种类型的决策时，决策者要承担一定的风险。这是因为对于哪种自然状态的出现，一般要由决策者自己作出判断。另外，决策者对于益损值重视程度会因人而异的。对于这种不同的价值观念，如果绘出一个数量标志去衡量，这就是效用函数。决策者根据自己的主观估计，用自己的效用函数去决策，当然要有一定的风险。

在具体解决风险型决策时，要用到许多概率论知识，这里就不再介绍了。

③不确定型决策。是指条件4的任何信息都不掌握，也就是说，对状态出现的可能性大小都无法预测。对这种类型的决策只能根据不同的决则，得出不同的决策。

现在我们用一个简单例子说明在不确定情况下的决策方法。

假定一个卖冰棍的小贩有五种取货方案:取0根、100根、200根、300根和400根冰棍。但由于对取回的冰棍全部卖出的可能性大小一无所知，因此小贩不知按哪种方案取货。试帮助他作出决策。

首先列出决策表(益损原则仍按本节引例中提到的条件)，见表18。表18中的状态是指卖出情况。

其次，根据不同的决策准则，可以得到不同的决策。

1.悲观准则 这种方法的思路是,对客观情况总是抱悲观态度，为了保险起见，总把事情的结果估计得很不利，因而也是一种保守方法。具体作法

先取决策表中各行的平均值，它们分别是0、1.4

2.2、2.4、2.0，再取它们的最大值为2.4，它所对应的方案 A为最优决策。

4.最小机会损失准则 当决策者掌握了各状态的完全信息时，就可在每种状态下按最大收益来确定方案，结果会百发百中，取得胜利,不会后悔。但是如果决策者不掌握各状态的任何信息，那么他作出的决策，一般会使收益减少，其减少量就是该方案的后悔值，产生了后悔值,决策者会感到遗憾。最小机会损失准则也称为遗憾准则，这个方法是在所有方案的最大后悔值中选择一个最小数值，它所对应的方案作为最优决策。

在本例中，状态E下的理想值为0，各方案的后悔值分别为0-0=0，0-(-1)=1，0-(-2)=2，0-(-3)=3，0-(-4)=4，在E₂状态下的理想值为2，各方案的后悔值分别为2-0=2，2-2=0，2-1=1，2-0=2，2-(-1)=3，……。依此类推，可求得在各状态下，各方案的后悔值，同时求出各方案的最大后悔值，列成下表，再从这些最大后悔值中求出最小值为3，它所对应的方案是A，也就是说小贩应取300根冰棍。

对于这种不确定型决策问题，选用不同的决策准则，会得到不同意义下的最优决策。至于哪种决

(六)排队论

排队现象在日常生活中大量存在，到公共汽

车站候车，到理发馆去理发，到食堂去买饭，到剧场或球场去买票，一般都要排队，这些都是有形的排队现象。在生活中还有一些看不见的排队现象，如打电话时因占线需要等候，这是一种无形的排队现象。

排队现象在工农业、交通运输以及社会服务系统中也广泛存在着。

让我们再举一些排队的实例。

在工业生产中，等待机床加工的零件，等待检验的产品，等待检修的机床等，都是一种排队现象。

在运输系统中，等待装卸的船舶，等待降落的飞机也是排队现象。

这些排队现象虽然千差万别,但结构是相同的。它们都有客源、输入过程、排队规则和服务机构几部分。

1.客源是指参加排队的个体的来源是有限的还是无限的。例如某工厂有20名维修工，那么可能排队领取零件的人数是有限的，而排队等待公共汽车的乘客则认为是无限的(实际上它是一个很大的数目)。在数学处理上,这两种情况是很不同的，

一般来说客源无限比客源有限更容易些。

2.输入过程是指顾客到达服务站的速度和方式。有的是间隔固定地到达，例如机器加工零件的速度是均匀的，预约挂号也是为了使病人均匀到达。而大多数顾客是随机到达，例如打电话的人，到公共汽车站候车的人都是随机到达的。经研究表明，在许多实际问题中，顾客的到达是遵从概率论中的泊松(Poisson)分布的，这种情况用数学处理起来比较方便。

3.排队规则分为损失制和等待制两种,损失制是指队伍排到一定长度时，顾客再来到时就不排了。例如某辆汽车看到加油站等待加油的车辆较多，就会转到另一个加油站去加油，或者根本不去加油了。等待制是指必须排队等候。例如汽车通过某检查站，就不得不排队。

对于排队的顾客到达服务台时，他是按照什么方式被服务的，又可分为下面几种情形:

①先到先服务。这是一种基本方式:

②优先权服务。例如对于急诊病人实行优先服务;

③后到先服务。例如后到的军事情报因其重要性而作了优先处理;

④随机服务。

4.服务机构 主要包括服务能力和服务时间两方面。服务能力是指同时可以进行服务的服务员的数目，他们的服务方式可以是单台服务(有一条服务线路)，也可以是有几个平行的服务线路。对顾客的服务可以一个一个地进行,如工人维修机器。也可以是成批服务，如公共汽车一次运载几十名乘客。服务时间可以是固定的，也可以是随机的，例如在戏院售票处买票的平均时间是相当短的，但这种时间也因人而异，要取决于找零钱和需要回答问题的多少。经过统计分析证明，许多实际问题的服务时间是服从负指数分布(在这里就不详细介绍了)。

排队论要解决的是什么问题呢?我们知道，一个服务系统的服务能力如果不能满足顾客的需要时，就会出现排队现象，而排队会给顾客个人和社会带来损失。如果顾客因排队过长而不来排队，或已经排队又中途走掉，这会对服务机构造成损失。为了解决排队现象，可以增加服务设施，然而这会增加成本，况且服务设施的服务能力超过了实际需要，又会出现窝工现象造成经济损失。排队论就是用数学方法，研究顾客在某种情形下，排队所需的平均时间，队伍的平均长度，以及在什么情况下，应增加服务设施,使排队者花去的时间不至于过多，而服务机构的成本支出又减到最少。

前面曾经提到，排队论是由爱尔朗在研究电话

一笔画出)的问题。

要想一笔画成这个图形，从起点开始到某一点终止，中间经过的每一点,必须有一条画进去的线，同时又有一条画出来的线。如果要起点与终点重合。那么图上的每一点都必须是偶数条线相连。然而图10中，B、C、D有三条线相连，A点处有五条线相连，它们都是奇数条线，因此不能一笔画出这个图形。经过这种分析，欧拉断定:这个问题，不论是否要求回到出发点，不重复地一次走遍七座桥，都是不可能的。

欧拉就是通过对图的分析，得出了满意的结果。

所谓图就是由一组给定的点(称为节点)和一组给定的连接这些点的线(称为弧)所组成的整体。图论就是研究图的理论的一门学科。哥尼斯堡七桥问题，可以看成是最古老的图论问题，然而作为一门独立的学科，那还是五十年代以后的事。目前图论已成为运筹学、计算机科学不可缺少的数学工具，它的应用范围还在不断扩大。因此这是一门很有发展前途的学科。

网络可以看成是一个赋值的图，也就是说，图的各条边具有给定的流通量、长度以及运费等数值，这种图可称为网络。

网络可分为有向网络(各条边都有方向)、无向网络和混合网络(一部分边有方向)。

用网络分析的方法可以解决许多实际问题，这些问题大体可以分为两种类型。第一类型的特点是实物的外形就表现为网络的形式。例如，一个国家的交通线可以看成一个网络;一组电路看成是一个网络;一个通讯系统看成是一个网络;地下自来水、煤气管道系统也是网络。对于这些网络要研究的问题常常是，在某一个网络中，从甲地到乙地的最短路线是什么?如果把自来水管道系统看成网络，那么要把水从几个抽水站分配到各用户那里，当管子的容量为已知时，从抽水站分配到各用户的最大流量是多少?抽象地说，是研究最短路问题，或者最大流问题等等。第二类型的特点是，该问题并不涉及实际网络，但可将它设计成网络，利用网络方法求解。这就是网络方法在计划工作中的应用。

1956年美国杜邦公司在制定协调企业不同业务部门的规划时，借助网络表示各项工作和完成工作所需时间，以及各项工作之间的相互联系。利用网络分析的方法，找出编制与执行计划的关键部分，因此称为关键路线法(简称CPM)。如果将关键路线法用于某一建设项目，那么关键路线就是指完成各道工序需要时间最长的路，在这条路上的各工序都是关键工序，它们的提前或延误，会影响整个工

1958年，美国海军部门为加速“北极星”导弹的研制工作，他们利用网络分析方法，注重对各项任务安排的评价和审查，在分析过程中，找出哪些活动可能拖整个计划的后腿，造成脱期。因此在开工之前，项目的负责人就知道应在什么地方采取措施，防止或减少可能产生的延误,得以顺利实施计划。这种方法称为计划评审法(简称PERT)。

1965年以来，在我国著名数学家华罗庚教授的带领下，推广了网络分析方法，并根据它的主要特点--统筹安排，把它称为统筹方法。它在我国国民经济各部门得到了广泛应用，并取得了显著效果。

总之，上述这些方法在处理问题时，能使计划工作作到统筹兼顾，全面安排，并能抓住编制与执行计划的关键，从而有效地解决生产中的实际问题。