运筹学

　　运筹学（Operations Research，又译为作业研究），一门新兴的应用科学。应用数学和形式科学的跨领域研究，利用统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率。　　“运筹”一词，本指运用算筹，后引伸为谋略之意。“运筹”最早出自于汉高祖刘邦对张良的评价：“运筹帷幄之中，决胜千里之外。”二次大战时，英军首次邀请科学家参与军事行动研究（operations research, 在英国又称operational research或OR/MS, management science），战后这些研究结果用于其他用途，这是现代“运筹学”的起源。中国在1956年曾用过“运用学”的名字，于1957年正式定名为“运筹学”，于1980年成立中国运筹学会（ORSC），并于1982年加入国际运筹学联合会（IFORS）。  　　由于它所研究的对象极其广泛，有着许多不同的定义。　　　　1976年美国运筹学会定义“运筹学是研究用科学方法来决定在资源不充分的情况下如何最好地设计人－机系统，并使之最好地运行的一门学科。”1978年联邦德国的科学辞典上定义“运筹学是从事决策模型的数字解法的一门学科”。前者着重于处理实际问题，而对“科学方法”则未加说明。后者强调数字解，而注重数学方法。　　　　英国运筹学杂志认为“运筹学是运用科学方法（特别是数学方法）来解决那些在工业、商业、政府部门、国防部门中有关人力、机器、物资、金钱等的大型系统的指挥和管理方面所出现的问题，其目的是帮助管理者科学地决定其策略和行动”。有人则认为运筹学是近代应用数学的一个分支，主要是将生产、管理等实际中出现的一些带普遍性的运筹问题加以提炼，然后利用数学方法去解决。前者提供模型，后者提供理论和方法。前者是后者发展的基础，后者是前者进行工作的科学依据。其实，运筹学是这两者有机结合而成的。英文oper ations research（运筹学）一词的原意是作战研究。早在1938年英国空军就有了飞机定位和控制系统，并在沿海有几个雷达站，可以用来发现敌机。但在一次空防大演习中发现，由这些雷达送来的（常常是相互矛盾的）信息，需要加以协调和关联，以改进作战效能。这一任务的提出即产生“运筹学”一词。英国空军成立了运筹学小组，主要从事警报和控制系统的研究。在1939年和1940年，这个小组的任务扩大到包含防卫战斗机的布置，并对某些未来的战斗结果进行预测，以供决策之用。运筹学工作者在第二次世界大战中研究并解决了许多战争的课题，例如通过适当配备护航舰队减少了船只受到潜艇攻击的损失；通过改进深水炸弹投放的深度，使德国潜艇的死亡率提高；以及根据飞机出动架次作出维修安排，提高了飞机的作战效率等等。在战争结束时，估计英国、美国和加拿大等三国的军队中，运筹学工作者已超过七百人。战后，一些原在军队的运筹学工作者，在英国成立了一个民间组织“运筹学俱乐部”，定期讨论如何将运筹学转入民用工业，并取得了一些进展。第一份运筹学杂志和英国的运筹学会分别于1950年和1953年出现了。世界上第一个运筹学会“美国运筹学会”于1952年成立。1959年成立了国际运筹学会联盟，到1986年已有35个会员国和6个兄弟学会会员3万余人，大多数会员国都办有自己的杂志。中国的运筹学会“中国数学会运筹学会”于1980年成立，于1982年加入国际运筹学会联盟并创刊《运筹学杂志》。

运筹学的分支学科

　　运筹学包含有以下一些分支:数学规划(它又包含有线性规划；非线性规划；整数规划、混合整数规划、0-1规划；组合规划（组合最优化）；参数规划；随机规划；多目标规划；几何规划；动态规划;等等)；图论、网络流；决策分析；排队论、可靠性数学理论；库存论；对策论；搜索论；模拟。　　

·数学规划

　　数学规划可以表示成求函数 ƒ(x1，x2，…，xn)，(目标函数)在规定（x1，x2，…，xn）必须满足（x1，x2，…，xn）∈A（约束条件）的要求之下的极小(或极大)值，即тinƒ(x)，x∈A，A吇Rn。简记为(P)。数学规划与古典的极值问题有本质上的不同，古典方法只能处理ƒ(x)和A都具有简单的表达式的情况，而现在的问题(P)的目标函数和约束条件一般都很复杂;古典方法只考虑n很小的情况，例如n=3、4、5，而问题(P)中的n可能很大，有的n甚至超过百万；古典方法在求解时往往满足某一表达式，即可利用公式进行求解，因此只能处理某些简单类型的问题，而问题(P)则要求给出某种精确度的数字解答，因此算法研究特别受到重视。由于这些本质差别，求解数学规划必须另辟途径。　　若，则称(P)为线性规划，否则称为非线性规划。若x1，x2，…，xn中有一部分（或全部）限制为只取整数值，则称(P)为整数规划。若ƒ(x)不只是一个函数，而是几个函数，则称(P)为多目标规划，当然，多目标规划的极值概念需要另加定义。　　　　线性规划及其解法单纯形法的出现，对运筹学的发展起了重大的推动作用。许许多多的实际问题都可化成线性规划问题来解，而单纯形法又是一个行之有效的算法。加上计算机的发展，使一些大型复杂的实际问题的解决成为现实，从而引起生产部门对数学方法的重视。有许多实际问题要求变量只取整数值。例如某工厂选址，若令xi=0表示第i处供选地址未被选中；xi=1表示该地址被选中。此时xi只能取0或1。对于这类问题，人们也许以为可用解一般的数学规划的方法，求出近似解并经过四舍五入的办法可以解决问题。但是有人举出了一个简单的线性规划问题，按单纯形法求出问题的解，然后经四舍五入求出整数解。如此进行了上万次的运算，却没有一次能得出可行解，当然更不可能是最优解。因此对于整数规划问题必须另寻新的解决方法。近年来，整数规划的算法虽然取得了不少进展，但是对于许多离散问题仍然无能为力。例如对于 4台机器10个零件的排序问题，若用数学规划来描述，则须引入40个连续变量、180个0-1变量、390个约束条件，而成为一个相当麻烦的混合整数规划问题。目前对它还不存在象单纯形法那样有效的算法。在一个有限集上求极值的问题是所谓组合最优化问题，这类问题在实际中大量存在，为解决这类问题，于是又形成了一门新的分支组合最优化。它的内容主要包括四个方面：a.设计出求解某些特定问题的算法；b.估计某些近似解与最优解的差距；c.研究哪些问题属于“难”题（计算的复杂性）；d.对于一些复杂的实际问题，设计求出可供实用的数字解的方法。随着组合最优化的发展，一些数学分支如组合数学、拟阵、广义拟阵、图论等也相应得到发展。　　　　非线性规划是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划范畴，要求发展新的方法。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本理论问题，使数学中的许多学科如凸分析、数值分析等也得到发展。　　　　多目标问题也常出现于实际问题之中。例如在工业生产中，往往既要求产量提高，同时又要求资源消耗尽量少，这两个指标是相互矛盾的。因此在这类问题上首先遇到的是“最优”概念如何定义。显然它不象单目标问题那样是惟一确定的。它牵涉到一个所谓偏序问题，即对可供选择的方案及其属性如何定义一种优劣“次序”，亦即如何描述目标对于可供选择的方案的依赖关系。多目标规划一般既涉及数学问题，也涉及到如何从外界(专家或决策人)得到一些信息以作出“偏序”。　　　　在数学规划的应用中有一些问题，它们所涉及的输入信息常随时间而作微小的变动，这些变动有时会引起目标函数发生大的变动。基于这种现象而产生了一个新的分支参数规划。它既要处理当有参数出现于目标函数和（或）约束条件时如何求解，同时也要处理解的性质对于参数的依赖性。　　

·图论

　　图论主要研究两类问题：其一，在给定的图中，具有某种性质的点和（或）线是否存在？若存在，有多少或至多（少）有多少？其二，如何构造一个具有某些给定性质的图或子图？就问题所讨论的性质大致可分为五方面：连通性、极值问题、嵌入、阵与拟阵、网络流。其中以极值问题和网络流与运筹学中的问题关系最为密切。极值问题主要是研究满足某种性质的点或边的最小个数。网络流理论研究的问题很多，其主要的有两类:一类是网络自身所固有的问题，如确定从甲地到乙地的最短路程、两地之间的最大流通量问题。一类是属于网络流的管理方面，如在军事中，当攻击手段受到某种限制时，如何确定一最优阻止策略以破坏敌人的通讯及(或)交通网络；在公用事业中，假若由于运输量的增加已发觉现有网络不能胜任，则应如何增加线路以使某种指标达到最优，等等。　　　　上述各种规划问题的共同特点是：问题的结果决定于最后的阶段，即问题本身是属于一次性的。但是，生产实际中有一些问题是属于多阶段性的，要求在每一阶段的开始必须作出某一决定，而整个问题的最终结果则与各阶段所作的决定有关。以一个简单的库存问题为例说明如下：设有一个工厂要在一年中储备某种元件，这种元件的购买都在每月月初进行。元件的单价决定于购买的月份和数量，即若第i个月月初买进μi个元件，设购买的单价为pi(μi)。设已知第i个月的消耗量为ri，每日的消耗量为常数。又设第i个月月末的储存量为xi，x0=x12=0。要求元件的储存量必须保证供应。问如何决定每月购买数量，使总的费用最省。显然，这一问题的最终结果取决于每月月初（阶段）所作的决策。这类问题在生产实际中出现很多，例如在控制问题、分配问题方面都会出现这类多阶段决策问题。动态规划方法就是用来处理这类问题的，它是在20世纪50年代由R.贝尔曼等人发展起来的，是数学规划的主要组成部分之一。　　

·排队论

　　排队论的研究目的是要回答如何改进服务机构或组织被服务的对象使得某种指标达到最优的问题。例如一个港口应有多少码头，一个工厂应有多少维修人员等等。排队论最初是在20世纪初由丹麦工程师A.K.埃尔朗关于电话交换机的效率研究开始的，只是在第二次世界大战中为了对飞机场跑道的容纳量进行估计，它才被纳入运筹学的范畴。与排队论问题较接近的有工厂设备的维修问题、元件的更换问题和可靠性问题等，其相应的学科更新论、可靠性理论等都已发展起来。　　　　运筹学中还有一大类问题是在有的场合它以确定性问题的面貌出现，有的场合则以随机性问题的面貌出现。如库存问题、对策问题等等。

·对策论

　　对策论也叫博弈论，前面讲的田忌赛马就是典型的博弈论问题。作为运筹学的一个分支，博弈论的发展也只有几十年的历史。系统地创建这门学科的数学家，现在一般公认为是美籍匈牙利数学家、计算机之父——冯·诺依曼。    最初用数学方法研究博弈论是在国际象棋中开始的——如何确定取胜的着法。由于是研究双方冲突、制胜对策的问题，所以这门学科在军事方面有着十分重要的应用。近年来，数学家还对水雷和舰艇、歼击机和轰炸机之间的作战、追踪等问题进行了研究，提出了追逃双方都能自主决策的数学理论。近年来，随着人工智能研究的进一步发展，对博弈论提出了更多新的要求。　　

·库存论

　　库存论是研究所需项目的生产时间、数量、运输、需要量(消耗量)的概率分布、维修、变质等等问题，以制定某些库存策略使得某种指标达到最优。根据生产时间、运输、消费量等等因素出现情况的不同，库存问题可以分成许多不同的类型。若其中的某些因素（例如消费量）是随机的，则为随机性模型。关于库存论问题的研究早在20世纪20年代就出现了一些结果，到了40年代以后才得到深入研究和广泛应用。　　　　对策论是通过抽象出一些共同的策略特征，从理论“模型”上来研究斗争中平衡状态的性质、斗争各方的平衡策略的性质以及设计出确定这种状态和策略的方法。对策论虽然在20世纪20年代初(F.-é.-J.-) é.波莱尔已着手研究，但只是在J.冯·诺伊曼等人将它用于竞争中的经济行为之后才受到广泛的注意。这门学科在理论上已经有了深入发展，但在应用上仍处于定性阶段。　　

·搜索论

　　搜索论也是由于第二次世界大战中战争的需要而出现的运筹学的一分支。所研究的是：在资源和探测手段受到限制的情况下如何设计寻找某种目标的方案，并如何加以实施的理论和方法，目的是以最大的可能或(和)最短的时间找到所说的目标。它是以搜索大西洋中袭击盟军商船的德国潜艇的研究而开始的。搜索论在实际应用中已取得不少成效，例如在20世纪60年代美国寻找在大西洋失踪的核潜艇打谷者号和蝎子号以及在地中海丢失的氢弹，都是依据搜索论获得成功的。　　

·决策分析

　　决策分析是运筹学中发展较晚的一个分支。它的研究目的在于提供一种合理的论证或方法，使得人们能够利用所有可资利用的信息，从可供选择的方案之中选出那种按决策者的标准来说是“最优的”方案。假若问题所涉及的因素都是确定性的，这问题就属于普通的最优化问题。通常所说的决策问题都包含有不确定因素，最终的结果并不完全能从所作出的选择预先知道。例如，农田作物的选择，虽然按照某种判断选种了某类作物，但并不能保证一定会得到预期的收成。决策论所作的是要根据可资利用的信息以做出可能最好的合乎逻辑的决策。　　　　以上所述是运筹学目前所包含的各个相对独立的分支，具有独自的理论和方法。在生产实际中所出现的问题并不一定属于单独的某一分支，但往往可以把它分解成若干子问题，使得每一子问题属于某一分支。当然，对于一些结构复杂的问题，并不常能作出这种分解。它们有时可以用模拟方法来解决。所谓模拟方法，通常是指使用数字计算机，特别是统计抽样于数学模型以得出某种反应出现的可能性大小的估计等一类的结果。