运筹学教程

第1章　筹学概论 1.1　筹学简史 20世纪30年代，德国使用战斗机对英美两国展开了猛烈的攻击，英美两国通过使用雷达和防空警报来抵御德国战机的空袭，这种方法虽然从理论与技术上可行，但使用的时候效果并不理想，英美两国的一些科学家为了研究如何能够更加合理地使用防空雷达而展开了一类新问题的研究.这类研究与传统的理论研究或技术研究不同，英国人在当时称之为“Operational Research”，也是运筹学作为一门科学出现的雏形.后来，美国人也给这一研究起了类似的名字“Operations Research”，尽管有细微的差别，但由于两国都以英语作为官方语言，这门“运用研究”学科都简写为OR.为了进一步开展运筹学的研究，当时的英美两国在军队中成立了一些专家小组，深入开展以下几个问题的研究：1护航舰队如何保护经商船队并降低其受攻击程度的海上编队问题;2当船队遭受德国潜艇攻击时，如何使船队的损失*少的问题;3为了提高反潜深水炸弹的威力，如何设置炸弹的合理爆炸深度的问题;4不同型号和大小的船只在受到敌机攻击时，如何选择逃避策略的问题等.尽管这些在战争中产生的研究所能解决的问题具有短期和战术性的特征，但都取得了非常好的效果.因此，在第二次世界大战结束后，英美两国的军队相继成立了正式的运筹学研究组织. 由于运筹学这门学科的诞生背景与战争有关，战时的研究内容一直处于保密状态，直到20世纪50年代才逐渐公开出来.1951年，莫尔斯(P.M.Morse)与金博尔(G.E.Kimball)出版了《运筹学方法》(Methods of Operations Research)，对当时的运筹学研究成果进行了深入的总结.而后，兰德(RAND)等公司和部门也重点开展一些战略性问题的研究，包括未来武器系统的设计以及其合理的运用方法、未来战争的战略、美军各种轰炸机系统的评估与评价、苏联的军事能力分析与预测、苏联政治局的行动原则和战术预测、各种洲际导弹的发展策略等.此外，兰德公司在此基础上还提出了系统分析(system analysis，SA)的名词及其相应的技术方法，开始更加注重战略方向的研究，如战略力量的构成和数量问题的研究等，并相继应用在国家的工业、农业、经济等各类问题上，后来也有研究人员把这两个名词放在一起叫作SA/OR. 运筹学在发展的过程中逐渐形成了许多分支，如数学规划(包括线性规划、非线性规则、整数规划、目标规划、动态规划、随机规划等)、图论与网络规划、排队论(随机服务系统理论)、存储论、对策论、决策论、维修更新理论、可靠性和质量管理等.1914年，军事运筹学中提出了著名的兰彻斯特(Lanchester)战斗方程;1917年，丹麦工程师埃尔朗(Erlang)在研究电话通信系统时提出了排队论的著名公式;20世纪20年代，存储论的*优批量公式被提出;20世纪30年代，商业界已开始通过运用运筹学研究和分析顾客心理来制定商业广告;1947年，丹齐格(G.B.Dantzig)在解决美国空军军事规划问题时提出了求解线性规划问性规划的模型以及给出的求解方法没有受到领导的重视，直至L.V.Kantorovich 1960年再次发表了能够解决工业生产组织和计划问题的《*佳资源利用的经济计算》后才受到国内外的重视，并因此获得了诺贝尔奖.后来，丹齐格认为其受到了里昂惕夫的投入产出模型(1932年)的影响，而里昂惕夫也是诺贝尔奖的获得者;其线性规划的理论则是受到了Von Neumann的影响.1944年，Von Neumann和O.Morgenstern发表的Theory of Game and conomic Behavior被认为是对策论研究的奠基之作.1948年，英国*早建立了运筹学会，紧接着美国(1952年)、法国(1956年)、日本和印度(1957年)等相继建立了各国的运筹学会. 我国在该领域的研究*早可追溯至1956年，当时使用“运用学”来命名该学科，1957年正式定名为“运筹学”.后来，钱学森、许国志等教授将运筹学由西方引入我国，并结合我国的特点在国内推广应用.1964年，华罗庚先生基于国外的运筹学研究理论与方法，提出了“优选法与统筹法”，并于1965年开始亲自带领学生去北京电子管厂开展运筹方法试点工作，让当时文化程度不高的人也能理解运筹思想和方法.1978年，华罗庚推广的“优选法与统筹法”工作在全国科学大会上被评为“全国重大科技成果奖”.我国的运筹学会在1980年成立.1982年，我国加入了由英、美、法三国的运筹学会发起成立的国际运筹学联合会(IFORS).此后，运筹学研究在我国迅速推广，为我国社会和经济的快速发展注入了新鲜的活力. 1.2　运筹学定义 运筹学是一门应用科学，很多学者曾尝试对其下定义.莫尔斯和金博尔对运筹学下的定义是：“为决策机构在对其控制的业务活动进行决策时，提供以数量化为基础的科学方法.”还有学者对其下的定义是：“运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择*优决策提供定量依据.”因此，运筹学研究*先强调的是科学方法，并且不是某种单一研究方法的独自或偶然的应用，而是适用于一类问题上，并能传授和有组织地活动，该方法同时还强调以量化为基础，能够为决策者提供可以量化的分析结果.另外，运筹学还具有多学科交叉的特点，如综合运用经济学、心理学、物理学、化学中的一些方法.运筹学虽然强调*优决策，但在实际的生产或生活中，“*”是一个目标和理想，通过权衡各方面的考虑，决策者往往也会用次优、满意等概念代替*优.因此，运筹学的又一定义是：“运筹学是一种给出问题的坏的答案的艺术，否则的话问题的结果会更坏.” 为了有效地应用运筹学，英国前运筹学学会会长托姆林森曾提出六条原则：1合伙原则，指运筹学工作者要和各方面人，尤其是同实际部门工作者合作;2催化原则，在多学科共同解决某个问题时，要引导人们改变一些常规的看法;3互相渗透原则，要求多部门彼此渗透地考虑问题，而不是只局限于本部门;4独立原则，在研究问题时不应仅受某人或某部门的特殊政策所左右，应独立从事工作;5宽容原则，解决问题的思路要宽，方法要多，而不是局限于某种特定的方法;6平衡原则，要考虑各种矛盾的平衡以及关系的平衡. 鉴于运筹学研究工作的实际特点，研究者们通过解决大量的实际问题后，总结并归纳形成了处理运筹学问题工作步骤：1提出和形成问题，即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料;2建立模型，即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来;3求解，即用各种手段(主要是数学方法，也可用其他方法)求得模型的解，解可以是*优解、次优解、满意解，复杂模型的求解需用计算机，解的精度要求可由决策者提出;4解的检验，即*先检查求解步骤和程序有无错误，然后检查解是否反映现实问题;5解的控制，即通过控制解的变化过程决定对解是否要做一定的改变;6解的实施，即将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改.然后反复进行以上过程，直至满意. 1.3　运筹学模型 运用运筹学解决实际问题时，按照实际问题和研究对象的不同可构造各种不同的模型.模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体描述所认识到的客观对象.阿可夫等对运筹学的模型分类和模型构建等有较完整的描述. 模型有三种基本形式：1形象模型;2模拟模型;3符号或数学模型.目前用得*多的是符号或数学模型.构模的方法和思路有以下五种. (1)直接分析法.即按研究者对实际问题内在机理的认识直接构造出模型.随着运筹学的不断发展，目前已经积累了很多经典的模型，如线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等.这些模型都已有较好的求解方法和求解软件，不过在使用这些已有的模型研究问题时，不能生搬硬套. (2)类比法.我们遇到的很多问题可以用不同的方法构造出模型，而这些模型的结构性质是类同的，可以通过互相类比找到解决问题的思路.如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路系统之间就有不少彼此类同的现象，甚至有些经济系统、社会系统也可以用物理系统来类比.在分析某些经济、社会问题时，不同国家之间有时也可以找出某些类比的现象. (3)数据分析法.有时候我们不清楚所面临问题的内在机理，但能搜集到与此问题密切相关的大量数据，或通过某些试验获得大量数据，这样就可以运用统计分析的方法分析、建模，从而求解问题. (4)试验分析法.有时候我们不仅不清楚所面临问题的内在机理，还不能通过做大量试验来获得与问题相关的数据，这时只能通过做局部试验获取部分数据，并综合运用各种分析方法来构造模型. (5)构想法.对有些问题来说，例如一些社会、经济、军事问题，研究者既不清楚问题的机理，又缺少问题的数据，也不能通过做试验来获得问题的数据，只能在现有的知识、经验和研究的基础上，对将来可能发生的情况给出合乎逻辑的设想和描述，然后运用已掌握的技术和方法构造模型，不断修正至满意为止.在研究社会问题时，国内外有研究者提出人工社会的构思，与这条建模思路十分类似，人们通过计算机在人工社会中进行大量的仿真试验，然后在真实社会中得到验证，或者通过人工社会获得在真实社会里尚未预知的方案和结果. 模型的一般数学形式可用下列表达式描述： 目标的评价准则; 约束条件 式中，xi为可控变量;yj为已知参数;为随机因素. 目标的评价准则一般要求达到*佳(*大或*小)、适中、满意等.目标准则可以有一个或多个.约束条件可以没有，也可有多个.当g是等式时，为平衡条件.当模型中无随机因素时，为确定模型，否则为随机模型.随机模型的评价准则可以用期望值、方差或某种概率分布来表示.当可控变量只取离散值时，为离散模型，否则为连续模型.另外，从数学工具的角度可以分为代数方程模型、微分方程模型、概率统计模型、逻辑模型等;从求解方法角度可以分为*优化模型、数字模拟模型、启发式模型等;从用途的角度可以分为分配模型、运输模型、更新模型、排队模型、存储模型等;从研究对象的角度可以分为能源模型、教育模型、军事对策模型、宏观经济模型等. 1.4　运筹学应用 运筹学的应用早期主要集中在军事领域，第二次世界大战后逐渐转向民用，在社会经济的发展和人民生活水平的提高过程中发挥了巨大的作用，可以分为以下几方面. (1)市场销售，主要应用在广告预算、媒介选择、竞争性定价、新产品开发、销售计划的制订等方面.例如，美国杜邦公司在20世纪50年代采用运筹学方法来制定广告、确定产品定价以及新产品研发等;通用电力公司对产品市场的模拟研究;京东商城对产品的动态定价等. (2)生产计划，主要应用在生产作业计划、日程表编排、劳动力匹配、合理下料、配料、存储以及物料管理等方面，通常使用线性规划和数值模拟等方法.例如，巴基斯坦某重型制造厂用线性规划安排生产计划，能够节省10％的生产费用. (3)库存管理，主要应用于多种物资库存量的管理，如确定某些设备的能力或容量、停车场的大小、新增发电设备的容量、电子计算机的内存量、合理的水库容量等方面.例如，美国某机器制造公司应用存储论的方法后费用节省了8％;美国西电公司通过建立“西电物资管理系统”使公司的物资存储费、运费和人员管理费用有了大幅度降低. (4)运输问题，主要应用于空运、水运、公路运输、铁路运输、管道运输、厂内运输等方面.空运运输问题主要涉及飞行航班和飞行机组人员及其服务时间的安排等;水运运输主要涉及船舶航运计划、港口装卸设备的配置和船到港后的运行安排等;公路运输主要涉及公路路网设计和分析、公共汽车路线的选择和发车时刻表的安排、市内出租汽车的调度、城市停车场的建设等. (