管理运筹学(21世纪高等院校教材)

作者简介

内容简介

第1章 绪论
　　1.1 运筹学简介
　　随着经济的发展，各类组织系统在运行中遇到越来越复杂的管理决策问题。从企业的内部管理到供应链企业之间的协调，从政府宏观决策的制定到大型工程的项目管理，随着组织系统复杂性增加，如何最有效地分配有用资源给不同部门或不同的环节将变得越来越困难。因此，这些问题就需要找到一个好的方法来解决。运筹学这一门学科就是在这样的需求下产生的。
　　人们一般认为运筹学作为一门学科首先在第二次世界大战期间英美两国发展起来的，然后随着在企业、政府部门等组织系统管理决策中的应用，其理论与方法得到丰富与发展，并逐步形成了一门包括众多分支的庞大学科。运筹学是人们为了获得关于系统运行的最优解而使用的一种科学方法，是为组织系统各种经营管理决策作出科学分析的手段。它使用许多数学工具（包括概率统计、数理分析、线性代数等)和逻辑判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题，以期发挥最大效益。运筹学是一门定量优化的决策科学，它可为管理决策提供数量分析与决策分析。它通过分析实际运行系统中的变量及其关系建立系统的数学模型，然后用各种数学方法进行定量分析和比较，求得合理运用人力、物力和财力的系统运行最优方案。
　　促进运筹学学科高速发展主要有两大因素：一方面是在运筹学方法研究上，从20世纪40、50年代以来取得一系列实质性成果。例如，早在20世纪40年代末，斯坦福大学管理科学教授乔治 丹茨格（George Dantzig)就系统地研究了线性规划问题，并发表了著名的单纯形法，他也因此被誉为“线性规划之父”。随后，线规划、动态规划、排队论等理论与方法均取得蓬勃发展；另一方面就是计算机发展对运筹学的巨大冲击。因为运筹学中很多复杂问题需要大量的计算，因此在很多情况下，这些计算用手工进行处理是根本不可能的。因此，能够快速处理大量计算任务的计算机的出现和发展对运筹学的发展提供了帮助，促进了运筹学的迅速成长和发展。
　　在我国，运筹学的研究和应用起步较晚，在20世纪50年代中期才由钱学森与许国志等老一辈科学家由西方引入。1957年正式定名为运筹学（从古语“夫运筹帷幄之中，决胜千里之外”摘取而来）。1958年运筹学在交通运输、工农业生产等方面都得到了应用，产生了具有独特风格的“图上作业法”。1970年后，在华罗庚教授的直接指导下，在全国范围内推广统筹法和优选法，并取得了卓著成效，同时也使运筹学的研究队伍迅速壮大。随后，中国运筹学会于1980年成立并立即申请加入国际运筹学会联合会（International Federation of Operational Research Soci-eties，IFORS)。1982年作为正式成员加人了IFORS。1984？1985年，中国运筹学会参与了亚太运筹学会联合会（Asian Pacific Operational Research Societies，APORS)的筹建工作，是八个创始国之一，这标志着我国在运筹学的研究领域内也跟上了当时的国际水平。
　　运筹学作为一门学科，是管理科学的基础。在国内外管理科学研究中，甚至将运筹学视为管理科学的基础。国际上最有影响力协会之一是运筹学和管理学研究协会（Institute for Operations Research and the Management Sciences，IN-FORMS)，该协会致力于促进、推动运筹学和管理学（OR/MS)领域里各学科的学术交流、推动学科发展。
　　随着科学技术和生产的发展，运筹学已渗入很多领域里，它也因此发挥了越来越重要的作用。
　　1.2 运筹学的主要内容
　　运筹学的具体内容包括规划论(包括线性规划、非线性规划、整数规划和动态规划）、图论与网络优化、排队论、博弈论等。下面简单介绍这几个主要理论。
　　1.规划论
　　线性规划及其解法——单纯形法的出现，对运筹学的发展起了重大的推动作用。许多实际问题都可以化成线性规划来解决，而单纯形法又是一个行之有效的算法，加上计算机的出现，使一些大型复杂的实际问题的解决成为现实。
　　非线性规划是线性规划的进一步发展和继续。许多实际问题例如设计问题经济平衡问题都属于非线性规划的范畴。非线性规划扩大了数学规划的应用范围，同时也给数学工作者提出了许多基本理论问题，使数学中的如凸分析、数值分析等也得到了进一步的发展。还有一种规划问题和时间有关，即“动态规划”。它在工程控制、技术物理和通信领域的最佳控制问题中，已经成为经常使用的重要工具。
　　2.图论与网络优化
　　图论与网络优化是一个古老的但又十分活跃的分支，它是网络技术的基础。图论的创始人是数学家欧拉。1736年他发表了图论方面的第一篇论文，解决了柯尼斯堡七桥难题，相隔一百年后，在1847年基尔霍夫第一次应用图论的原理分析电网，从而把图论引进到工程技术领域。20世纪50年代以来，图论的理论得到了进一步发展，将复杂庞大的工程系统和管理问题用图进行描述，可以解决很多工程设计和管理决策的最优化问题。例如，完成工程任务的时间最少、距离最短、费用最省等。图论受到数学、工程技术及经营管理等各方面越来越广泛的重视。
　　3.排队论
　　排队论又叫随机服务系统理论。最初是在20世纪初由丹麦工程师艾尔郎关于电话交换机的效率研究开始的。在第二次世界大战中通过对飞机场跑道的容纳量进行估算，排队论得到了进一步的发展，其相应的学科更新论、可靠性理论等也都发展起来。
　　因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具。此外还有分析方法和微分方程等。排队论把它所要研究的对象形象的描述为顾客来到服务台前要求接待。如果服务台已被其他顾客占用，那么就要排队；另外，服务台也时而空闲、时而忙碌。这就需要通过数学方法求得顾客的等待时间、排队长度等的概率分布。排队论在日常生活中的应用是相当广泛的，例如，水库水量的调节、生产流水线的安排、铁路分成场的调度、电网的设计等。
　　4.博弈论
　　博弈论也叫对策论，田忌赛马就是典型的博弈论问题。作为运筹学的一个分支，博弈论的发展也只有几十年的历史。最初用数学方法研究博弈论是在国际象棋中开始的——如何确定取胜的策略。由于是研究双方冲突、制胜对策的问题，所以这门学科在军事方面有着十分重要的应用。数学家还对水雷和舰艇、歼击机和轰炸机之间的作战、追踪等问题进行了研究，提出了追逃双方都能自主决策的数学理论。随着人工智能研究的进一步发展，博弈论也被提出了更多新的要求。
　　如果决策者的对方也是人(一个人或一群人），双方都希望取胜，这类具有竞争性的决策称为对策或博弈型决策。构成对策问题的三个根本要素是：局中人、策略以及一局对策的得失。对策问题一般可分为有限零和两人对策、阵地对策、连续对策、多人对策与微分对策等。
　　1.3 运筹学的主要特点与研究方法
　　1.运筹学的特点
　　(1)通用性。运筹学已被广泛应用于工商企业、军事部门、政府部门等研究组织内的统筹协调问题，故其应用不受行业、部门之限制。
　　(2)实践性。运筹学既涉及各种经营进行创造性的科学研究，又涉及组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效。
　　(3)系统性。它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，它所提供的是解决各类问题的优化方法。
　　2.运筹学的研究方法
　　(1)从现实生活场合抽出本质的要素来构造数学模型，同时寻求一个跟决策者的目标有关的解；
　　(2)探索求解的结构并导出系统的求解过程；
　　(3)从可行方案中寻求系统的最优解法。
　　3.运筹学中处理问题的步骤
　　应用运筹学处理问题的步骤可以概括如下：
　　(1)提出和形成问题。提出需要解决的问题，确定目标；分析问题所处的环境和约束条件。
　　(2)建立模型。把问题中的决策变量、参数与目标函数和约束条件之间的关系用一定的模型表示出来。模型是研究者经过研究后用文字、图表、符号和关系式，以及实体模样描述所认识到的客观对象，成功的模型对问题的解决有关键作用。
　　(3)最优化。确定与模型有关的各种参数，选择求解方法，求出最优解。
　　(4)解的评价。通过灵敏度分析等方法，对所求解进行分析和评价，并据此提出修正方案。
　　(5)决策。向决策者提出决策所需的数据、信息和方案，帮助决策者决定处理问题的方案。
　　第2章 线性规划
　　2.1 线性规划问题的提出
　　线性规划是运筹学中研究较早、方法较成熟的一个重要分支，在经济、管理、交通运输、军事等领域存在着广泛的应用。它具有适应性强，应用面广，计算技术比较简便的特点，是现代管理科学的重要基础和手段之一。线性规划研究的问题大体上可归为两类：
　　1.给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务；
　　2.对于给定的任务，如何运筹规划，合理安排，以最少资源来完成它。
　　线性规划要研究的两类问题中都包含有限制或约束条件：第一类问题的约束
　　条件是“给出一定量的人力、物力和财力等资源”；第二类问题是“给定的任务”。在线性规划中，我们常要求这种约束条件可以用一组线性方程或线性不等式来描述。在约束满足的条件下，所要达到的结果称“目标”，第一类问题的目标是利用有限资源完成最大任务，第二类问题的目标是要用最少资源完成给定任务。在线性规划中，要求可以用一个线性函数来描述这种目标，并称这个线性函数为目标函数。
　　线性规划研究的各种实际问题尽管约束条件与目标不相同，但规划的目的就是使这些资源最大限度地发挥作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用数学的方式描述，规划的目的就是在给定的限制条件(或称约束条件)下，求目标函数的极值问题(包括极小值和极大值）。
　　2.1.1 线性规划的数学模型
　　下面通过具有实际背景的例子来具体说明线性规划问题的数学描述。
　　例2.1 穗羊公司要加工两种产品I、n，需要使用两种原材料及某专用生产设备等三种资源，分别记为A、B、C。生产这两种产品的单位资源消耗、这些资源的每周可使用量及每单位产品可获利润如表2-1所示。
　　表2-1 穗羊公司生产过程的有关数据
　　问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？
　　解：这个问题是一个生产决策问题，可以用线性规划模型来描述。在这一决策问题中我们需要决定的是两种产品每周的产量，我们将要决定的产品I每周的产量用变量x1表示，产品II的产量用x2表示。
　　我们的目的是要使得每周的获利最大。根据问题所给数据，当产品I、II每周的产量分别是x1和x2时，总利润，这就是这一问题的目标函数。因此，我们的目标就是
　　Max z=3x1+2x2
　　再考虑资源的限制。首先当产品I、II每周的产量分别是x1和x2时，需要使用A原材料x1+2x2千克，但每周A原材料的可使用量为5千克，每周需要的A原材料的数量显然不能超过可使用量，因此关于A原材料，我们有约束条件
　　X1+2x2≤5
　　类似地，关于原材料B，有约束条件
　　2x1+ x2≤4
　　关于设备C，有约束条件
　　4x1+3x2≤9
　　此外由于变量x1和x2分别表示产品I和II每周的产量，不可能是负数，因此关于这两个变量，还有约束
　　x1≥0，x2≥0
　　将上述数学表达式合起来，就得到这个问题的数学模型为
　　max z=3x1+2x2
　　 (2.1)