第0章绪论 0.1运筹学的起源和发展过程 运筹学在英国称为operational research，在美国称为operation research（缩写为O.R.）。Operation Research 原意是操作研究、作业研究、运用研究、作战研究，译作运筹学，是借用了《史记》“运筹于帷幄之中，决胜于千里之外”一语中“运筹”二字，既显示其军事的起源，也表明它在我国已早有萌芽。 运筹学是在第二次世界大战期间发展起来的一门新兴学科。在第二次世界大战期间，英国空军为了应用雷达探测德国飞机的空袭，成立了一个由物理学家、数学家、天文学家和军人组成的作战研究小组，称为空军运筹学小组，专门研究作战防空问题。其主要任务包括防卫战斗机的合理布置等。由于空军运筹学小组的出色工作和成效显著，英国海军也成立了类似的作战研究小组，专门研究运输船队护航问题，反潜深水炸弹的合理爆炸深度等问题，结果均取得良好的效果。如研究反潜深水炸弹的合理爆炸深度后，使德国潜艇被摧毁的数量增加到400%。 第二次世界大战以后，英、美等国在军队中成立了更加正式的运筹研究组织，继续研究战略、战术及武器运用等问题。此外，运筹学也开始在工业、农业和经济社会等其他领域得到广泛应用。随着运筹学应用范围不断扩大和深入，一些专家、学者也对运筹学理论进行了更加深入的研究。美国运筹学家P.M.Morse与G.E.Kimball于1952年出版了《运筹学方法》一书，并把运筹学定义为： “运筹学是在管理领域，运用数学方法，对需要管理的问题统筹规划，作出决策的一门应用科学。” 从20世纪40年代后期开始，一些国家先后成立了运筹学专门学会。1948年，英国首先成立了运筹学会，美国于1952年成立了运筹学会，法国于1956年成立了运筹学会，日本和印度于1957年成立了运筹学会。到1986年为止，世界上已有38个国家和地区成立了运筹学会或类似组织。1959年，英、美、法三国发起成立了国际运筹学联合协会（IFORS），以后各国的运筹学会纷纷加入。此外，还有一些其他地区性运筹学会组织，如欧洲运筹学协会（EURO）成立于1976年，亚太运筹学协会（APORS）成立于1985年。 早在20世纪50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。1956年在中国科学院力学研究所成立了运筹学小组，1958年成立了运筹学研究室。1960年在山东济南召开了全国应用运筹学的经验交流和推广会议； 1962年和1978年先后在北京和成都召开了全国运筹学专业学术会议； 1980年4月，中国数学会运筹学分会成立。这对运筹学在我国的发展，无疑起到很大的推动作用。1982年中国运筹学会加入IFORS，1991年中国运筹学会成立。1999年8月组织了第15届IFORS大会。著名数学家华罗庚教授任运筹学会第一届理事会理事长，此后，著名数学家越民义、徐光辉、章祥荪、袁亚湘教授先后任运筹学会理事会理事长。目前，运筹学已在我国各个部门得到广泛应用。 中国运筹学会现有专业委员会 11 个、地方分会 9 个，团体会员 68 个，个人会员 1200 多人，集中了全国运筹学最优秀的科研人员。同时，中国运筹学会还主办《运筹学学报》和《运筹与管理》两份杂志。 运筹学的快速发展还要归功于另外两个关键因素。一是第二次世界大战之后，运筹学的技术得到实质性的进展，主要的贡献之一为： 1947年George Dantzig给出了线性规划的单纯型解法。 第二个因素是计算机革命。由于计算机的出现，原来依靠手工计算而限制了运筹学发展的运算规模得到革命性的突破。计算机的超强计算能力大大激发了运筹学在建模和算法方面的研究； 同时，大量标准的运筹学工具被制作成通用软件（如LINGO等），或编入企业管理软件，如MRPII、ERP等。 随着科学技术和生产的发展，运筹学本身也在不断发展。目前，运筹学已发展成为具有许多分支的研究学科，如线性规划、动态规划、图与网络分析、排队论、存储论等。下面简单介绍一些运筹学的分支学科。 0.1.1线性规划 在生产和经营管理工作中，如何有效地利用有限的人力和物力取得最优的经济效果，或在预定的目标条件下，如何花费最少的人力和物力去实现目标，这类问题统称为规划问题。规划问题用数学语言描述为： 根据研究问题的目标选取适当的一组变量，问题的目标用变量的函数形式表示，该函数称为目标函数，问题的约束条件用一组由选定变量组成的等式或不等式表达，这些等式或不等式称为约束方程。即规划问题由一个或几个目标函数和一组约束方程构成。 最简单的规划问题是线性规划。线性规划只有一个目标函数，且目标函数和约束方程都是线性函数。线性规划建模相对简单，有通用的算法和计算机软件，是运筹学应用最为广泛的一个分支。用线性规划求解的典型问题有生产计划问题、混合配料问题、下料问题、运输问题等。 当线性规划的变量只能取整数时，线性规划转变为整数线性规划，简称整数规划。特别地，当线性规划的变量只能取0或1整数时，整数规划称为01整数规划，简称01规划。01规划的一个典型应用是任务分配问题。 如果规划问题的目标函数或约束方程为非线性函数，则规划问题称为非线性规划。非线性规划是线性规划的进一步发展和继续。由于大多数工程物理量的表达式是非线性的，所以，非线性规划在各类工程中的优化设计有广泛的应用，是优化设计的有力工具。 0.1.2动态规划 动态规划本质上也是一个规划问题，因为动态规划也有目标函数和约束方程。但是，由于动态规划是一种解决多阶段决策问题的优化方法。多阶段决策有“动态”含义，所以，通常把处理多阶段问题的方法称为动态规划。动态规划是20世纪50年代初由美国数学家贝尔曼（R.Bellman）等人提出的，该方法根据多阶段决策问题的特点，提出了决策多阶段决策问题的最优化原理。利用动态规划的最优性原理，可以解决生产管理和工程技术等领域的许多实际问题，如最优路径、资源分配、生产计划和库存等。由于动态规划的解题思路独特，所以，它在处理某些最优化问题时，比线性规划或非线性规划更有效。 0.1.3图与网络分析 在日常生活中，我们可见到各种各样的图，如道路交通图、电话网络图等。这些图的共同特征是由一些节点和节点之间的连线组成。当然，对于不同图，节点与节点之间的连线含义不同。在道路交通图中，节点表示道路交叉点，节点之间的连线表示道路； 而在电话网络图中，节点表示交换局，节点之间的连线表示中继线。另外，根据研究的具体图与网络对象，节点之间的连线可赋予特定含义的一个或若干个权值，如两点之间的距离、两点之间的流量等。图与网络分析的重要内容有： 任意两点之间的最短路径、给定网络的最大通过流量等。图与网络分析在研究各类网络结构和流量优化等领域有重要的应用。 0.1.4随机服务系统理论 随机服务系统理论是研究随机服务系统的数学理论和方法。在日常生活中，我们经常可见到各种各样的随机服务系统，如在银行办理存、取款业务，在商店购买商品，电话局对电话用户的服务，等等。在这些系统服务中，经常出现排队现象，所以随机服务系统理论又称排队论。 随机服务系统早已存在，但对随机服务系统的理论研究直到电话发明后才有了进展。丹麦科学家爱尔朗（A.k.Erlang）于1909—1920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础。 一般来说，一个随机服务系统存在如下两个方面的要求： （1） 顾客希望服务质量好，如排队等待时间短、损失率低等； （2） 系统运营方希望设备利用率高。 显然，上述两个方面的要求是相互矛盾的。因此，随机服务系统理论研究的第一个任务是在给用户一个经济上能够承受的满意的质量条件下，系统的设备要配备多少？这实际上是一个系统设计问题。随机服务系统理论研究的第二个任务是计算给定一个随机服务系统的有关参数和指标，如顾客的平均等待时间、顾客的平均排队队长等。 随机服务系统理论在通信网、道路交通网的设计、流量分析以及性能评价等领域有重要的应用。 0.1.5存储论 存储是常见的社会现象。如为了保证企业生产的正常进行，需要存储一定数量的原材料和配件； 商店为了确保销售，需要存储一定数量的商品。存储论主要研究最优的存储策略，即确定什么时间进货以及每次进货量等于多少时，才能使系统的总费用最小。 0.2运筹学的基本特点和研究对象 运筹学是一门应用科学，它广泛应用于现代科学技术知识和数学方法，解决生产和经济活动过程中提出的实际问题，为决策者选择最优决策提供定量的依据。 运筹学的主要特点之一是优化。它是以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法。 运筹学的另一个特点是定量。它为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案。 运筹学研究的主要对象是来自生产管理过程中的具体问题，如资源分配、物资调度、生产计划与控制等。 0.3运筹学研究解决问题的方法步骤 运筹学在研究解决实际问题时，主要方法步骤有： （1）理清问题、明确目标； （2）建立模型； （3）求解模型； （4）结果分析。 1. 理清问题、明确目标 理清问题、明确目标是解决问题的首要步骤，因为运筹学所解决的问题一般都是生产管理过程中的具体问题，涉及的因素很多，事情发展的后果难以预计，所以要通过调查研究，把问题的实质、影响因素、约束条件以及可能导致的后果理出头绪。明确目标是解决问题的关键。同样的问题，目标不同可能引出不同的方案和结论。 2. 建立模型 建立模型就是把要解决的问题的参数、变量和目标等之间的关系用模型表示。如形象模型、数学模型、模拟模型等。为了易于定量解决问题，运筹学中的模型多半是数学模型。由于社会活动的复杂性，很难总结出一套规范的方法来建立模型。所以建立模型是一项创造性的劳动，要依靠运筹工作者发挥其聪明才智及其经验来完成。 3. 求解模型 建立模型之后，对它求解才能得到所要求的答案。对运筹学中现有的各种模型已经研究出多种解法，由于运算量一般都很大，通常需要用计算机计算。所以运筹学的广泛应用是与计算机的发展密切相系。 4. 结果分析 因模型中有许多实际因素需要考虑进去，如社会因素、政策因素等，因此对求解出的结果要从其他方面进行评价和研究。 0.4运筹学与其他学科的关系 运筹学建模和求解等过程都需要利用很多数学知识，所以学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因。有人甚至认为运筹学是一门应用数学。但是运筹学所解决的问题本身并非数学问题，而是生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要涉及管理科学的有关理论，因此，运筹学的发展与管理科学的发展有密切的关系。此外，由于运筹学所研究的实际问题通常都比较复杂，而且规模较大，在求解这些问题时，必须借助计算机来完成，所以运筹学的发展还与计算机科学的发展有很大关系。 第一章线性规划 线性规划（linear programming）是运筹学的一个重要分支，它是研究在满足一组线性约束条件下，使某一线性目标函数达到最优的问题。1947年G．Ｂ．Dantzig提出了求解一般线性规划的方法——单纯形法以后，线性规划的理论趋向成熟，实际应用领域日益广泛和深入。随着计算机能够处理成千上万个约束条件和决策变量的线性规划之后，线性规划的应用领域更加广泛了。目前，线性规划已成为现代科学管理的重要手段之一，并在国防、科技、工业、农业、商业、交通运输、环境工程、经济计划、管理决策和教育等领域得到了广泛应用。 1.1线性规划模型 1.1.1问题的提出 本部分我们将以线性规划问题为小麻雀，解剖运筹学解决问题4个步骤的前两步（理清问题、明确目标和建立数学模型）的基本思路和过程，并展示运筹学的两个基本特点（优化和定量）与研究对象（生产管理中的一个个具体问题）。 在生产和经营管理工作中，经常需要进行合理的计划或规划。计划或规划的共同特点是，在人力、财力和物力等资源有限的条件下，如何确定方案，使总收入或总利润达到最大； 或在规定的任务或指标的前提下，如何确定方案，使总成本或总消耗最小。 例1.1多产品生产计划问题 某工厂计划用现有的铜、铅两种资源生产甲、乙两种电缆，已知甲、乙两种电缆的单位售价分别为6万元和4万元。生产单位产品甲、乙电缆对铜、铅资源的消耗量及可利用的铜、铅资源量如表1.1所示。 表1.1铜、铅资源的消耗量及可利用量 甲电缆乙电缆资源量 铜/t2110 铅/t118 单位售价/万元64 另外，市场对乙电缆的最大需求量为7单位，而对甲电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大？ 解根据题意，上述问题是一个典型的多产品生产计划问题，其目标是使工厂的总收入最大。为建立该问题的数学模型，我们设x1，x2 分别代表甲、乙两种电缆的生产量，f（x）为工厂的总收入，则上述问题可用如下数学模型来表示。 OBJ： maxf（x）=6x1+4x2 s.t.2x1+x2≤10铜资源约束 x1+x2≤8铅资源约束 x2≤7产量约束 x1,x2≥0产量不允许为负值 （1.1） 式（1.1）就是上述问题的线性规划数学模型。其中，OBJ（objective）表示目标，s.t.（subject to）表示满足于。该数学模型表示，在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大。 利用后面将要探讨的线性规划数学模型图解法等方法，我们可以很容易求得（1.1）线性规划数学模型的最优解为 x1=2,x2=6,maxf（x）=36。 即甲电缆生产2单位，乙电缆生产6单位时，工厂的总收入达到最大，为36万元。 显然，多产品生产计划问题是生产管理中的一个重要问题，（1.1）线性规划数学模型的最优解体现了优化和定量两个基本特点。 例1.2配料问题 某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对VA、VB1、VB2和VD的最低含量有一定的要求。已知单位甲、乙两种原料VA、VB1、VB2和VD的含量，单位混合饲料对VA、VB1、VB2和VD的最低含量以及甲、乙两种原料的单位价格如表1.2所示。 表1.2原料含量和单位价格表 原料甲原料乙混合饲料最低含量 VA含量0.50.52 VB1含量1.00.33 VB2含量0.20.61.2 VD含量0.50.22 原料单价0.30.5 问该加工厂应如何搭配使用甲、乙两种原料，才能使混合饲料在满足VA、VB1、VB2和VD的最低含量要求条件下，总成本最小？ 解根据题意，上述问题是一个典型的配料生产问题，其目标是使混合饲料的总成本最小。为建立该问题的线性规划数学模型，我们设 x1，x2分别代表混合单位饲料对甲、乙两种原料的用量，f（x）表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下。 minf（x）=0.3x1+0.5x2 s.t.0.5x1+0.5x2≥2 1.0x1+0.3x2≥3 0.2x1+0.6x2≥1.2 0.5x1+0.2x2≥2 x1,x2≥0（1.2） 式（1.2）就是上述问题的线性规划数学模型。该数学模型表示，在满足VA、VB1、VB2和VD的最低含量等要求条件下，确定原料甲和乙的购买量，使生产出来的混合饲料总成本最小。 利用后面将要探讨的线性规划数学模型求解方法，我们可以求得（1.2）线性规划数学模型的最优解，即该问题的最优解为 x1=3.69，x2=0.77，minf（x）=1.49。 即单位混合饲料对甲、乙两种原料的用量分别为3.69单位和0.77单位时，单位混合饲料所需要的总成本最小，为1.49单位。 显然，混合饲料生产问题也是生产管理中的一个重要问题，（1.2）线性规划数学模型的最优解体现了优化和定量两个基本特点。 例1.3下料问题 某工厂要制作100套钢筋架，每套需用2.9m、2.1m和1.5m的钢筋各一根。这些钢筋均用长7.4m的原材料切割而成。问如何切割原材料才能使原材料的使用最节省？ 解该问题属于如何合理下料问题。要解决这一问题，应先列出若干种可能的切割方案，表1.3列出了8种可能的切割方案。 表1.3各种下料方案 方案2.9m2.1m1.5m合计余料 12017.30.1 21207.10.3 31116.50.9 41037.40 50306.31.1 60227.20.2 70136.60.8 800461.4 解根据题意，上述问题是一个典型的下料生产问题，其目标是使总剩余的废料最小。为建立该问题的线性规划数学模型，我们设x1，x2，…，x8分别代表采用切割方案1~8的套数，f（x）表示总剩余的废料，则上述问题的线性规划数学模型如下。 minf（x）=0.1x1+0.3x2+0.9x3+0x4+1.1x5+0.2x6+0.8x7+1.4x8 s.t.2x1+x2+x3+x4≥100 2x2+x3+3x5+2x6+x7≥100 x1+x3+3x4+2x6+3x7+4x8≥100 x1,x2,x3,x4,x5,x6,x7,x8≥0（1.3） 式（1.3）就是上述问题的线性规划数学模型。该数学模型表示在完成规定的规格和数量的钢筋架的要求条件下，如何切割原材料，才能使总剩余的废料最少。 同样利用后面将要探讨的线性规划数学模型的求解方法，我们可以求得（1.3）线性规划数学模型的最优解为 x1=10，x2=50，x4=30，其他为0，minf（x）=16m。 即只需要90根原材料，其中，方案1需要10根，方案2需要50根，方案4需要30根，可得到规定的100套钢筋架。此时，总剩余的废料最小，为16m。 显然，下料生产问题的属性及其线性规划数学模型（1.3）的最优解也体现了运筹学的两个基本特点（优化与定量）和研究对象（生产管理中具体问题）。 通过上述三个实例的讨论，我们展示了线性规划问题的基本特征和建立其数学模型的基本思路和过程。 进一步仔细观察和分析上述三个例子的线性规划数学模型，我们可以看出，三个线性规划数学模型都具有如下共同特征。 （1） 有一组决策变量（x1，x2，…，xn）表示某一方案。这一组决策变量的具体值就代表一个具体方案。 （2） 有一个目标函数，该目标函数根据其具体性质取最大值或最小值。当目标为成本型时取最小，而当目标为效益型时取最大。 （3） 有一组约束方程，包括决策变量的非负约束。 （4） 目标函数和约束方程都是线性的。 根据以上分析，我们可以推出如下线性规划数学模型的定义。 定义1.1有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。 为了帮助大家进一步加深理解和掌握线性规划的基本概念及其应用，我们把例1.1的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下： 用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大。 希望大家记住该背景模型，记住了该背景模型，也就基本理解和掌握了线性规划数学模型的基本特征。后面我们会反复提及和用到该背景模型。 这里所指的背景模型是： 能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型。如高等数学中二维积分的背景模型可认为是平面的面积。如果我们想到二维积分就想到它就是一曲线底下的面积，这样二维积分的基本特征和原理就很容易理解和记住了。 利用一些相对比较简单的问题来阐述运筹学中一些相对复杂和抽象的基本概念和原理是作者力求在本书中体现的第一个特点，如果读者用心体会，相信将会感到运筹学比一般人想象的要容易得多。 1.1.2线性规划数学模型的一般表示 在1.1.1小节中，我们讨论了三个典型的线性规划问题及其数学模型。对于不同的规划问题，其线性规划数学模型的形式也不同。但是各种形式的线性规划问题的数学模型，均可用如下一般形式来表示。 max（min）f（x）=c1x1+c2x2+…+cnxn s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1 a21x1+a22x2+…+a2nxn≤（=,≥）b2  am1x1+am2x2+…+amnxn≤（=,≥）bm x1,x2,…,xn≥0 （1.4） 其中，xj（j=1，2，…，n）称为决策变量，共有n个，是线性规划问题中要求解的变量。约束条件共有（m+n）个，即线性规划问题的规模为（m+n）。在（m+n）个约束条件中，前m个约束条件称为约束行，简称为线性规划的m个约束； 后n个约束条件称为决策变量的非负约束。 系数cj（j=1，2，…，n）称为价值系数，bi（i=1，2，…，m）称为右端系数，aij称为技术系数。这三个系数建议大家先利用线性规划的背景模型来理解和记忆。在线性规划背景模型中，cj表示第j种产品的单位价格，bi表示第i种资源的拥有量，aij表示生产单位第j种产品对第i种资源的消耗量。 在不同的场合，我们可能会用到不同形式的线性规划数学模型。以下我们给出和式、向量式和矩阵式的线性规划数学模型（为了书写方便，我们只给出背景模型的相应线性规划数学模型）。