作者：左小德,薛声家
出版社：暨南大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
管理运筹学(第五版)试读：
第五版前言
本书是为高等院校管理专业编写的运筹学教材，重点介绍一些在解决复杂管理问题中应用最为广泛的定量分析方法。它同样适合其他有关专业的本科生、研究生和工程技术人员、科技人员、企事业管理人员学习科学管理及优化技术之用。
我们在编写时力求做到以下四点：（1）采用富有启发性的例子说明从实际问题导出各类运筹学模型的过程，重点突出问题的建模方法。通过大量各具特色的例题和习题来加强对学生建立运筹学模型能力的训练，培养他们运用运筹学解决实际管理问题的能力。（2）尽量避免较深的数学论证，着重讨论基本概念、方法，以及其在经济管理中的意义。对于算法，我们主要通过例子来介绍其基本思想而不作严格、详细的论述。由于实际问题总是在计算机上解决的，本书特别强调使用运筹学软件求解，并对计算机的输出进行分析。对软件有兴趣者可直接与作者联系，或从相关站点下载。（3）由于计算机的普及，Office是电脑装机的必装应用软件。因此，本书也突出了Office中Excel的应用，大部分规划问题都有相应的Excel求解方法。同时，Project也是Office中的应用软件包，在“CPM与PERT”一章中也介绍了Project的应用。（4）根据社会发展需要，对例子作了精选，并对有些例子补充了一些深入思考的问题。
全书分十二章，第一章到第五章及第十一章由薛声家执笔，第六章到第十章及第十二章由左小德执笔。本书写作过程中参考了国内外大量资料，书末列出的参考文献仅是其中的一部分。在此谨向这些文献的作者致以谢意！
本书自2000年出版以来，至今已加印多次，并于2004年、2007年、2010年分别作了修订。为了进一步提高其质量，我们进行了第五次修订，该次修订由左小德完成。同时，访问学者饶惠，梁云副教授，博士生许明辉、王海霞、李璨、龚娟，硕士生刘思远、徐颂雅为本书的校对也付出了辛勤的劳动。殷切期望广大读者提出宝贵意见，帮助我们将本书修订得更加完善。作 者 2016年2月于暨南园1 绪 论
本章要求
了解运筹学的含义。
理解管理决策的定性方法和定量方法。
了解运筹学的模型；掌握运筹学的工作步骤。
明了运筹学与计算机的关系。1.1 概 述
运筹学（Operations Research/Operational Research，缩写为OR）这一名称是在第二次世界大战期间出现的，当时指的是英、美等国因战争需要而成立的研究小组的研究活动。这些小组由多种学科的专家们组成，他们的任务是审查和研究各种军事行动，探求如何提高各种武器装备和作战系统的使用效率，如何有效地分配和供应各类军事资源。这些研究工作取得了极大的成效，为同盟国最后战胜法西斯轴心国作出了巨大贡献。
如今，运筹学已发展成为一门理论完善、门类齐全、有着广泛应用前景的科学学科。但由于它所研究问题的广泛性和复杂性，人们一直还没能形成一个统一且精确的运筹学定义。从管理的角度来看，可以说运筹学是用定量化方法来为管理决策提供依据的一门学科。运筹学把复杂的管理系统归结为模型（多数是数学模型），然后使用数学方法和计算机求解与分析，从而得到系统最优运行方案，供管理人员和决策人员参考。
英文“OR”一词，直译是“作战研究”，或“运用研究”，日本人译为“运用学”。我国学者从《史记•高祖本纪》中的“夫运筹帷幄之中，决胜于千里之外”，摘取了“运筹”一词作为OR的意译，比较贴切地反映了OR一词的含义——既有运用，又有筹划。
西方许多学者往往把“运筹学”称为“管理科学”（Management Science，缩写为MS）。我们认为与运筹学同义的管理科学只是狭义的管理科学（何况，两者之间在理论研究的界限和深度上是有差别的）。一般来说，管理科学包含的内容要比运筹学更广泛一些。可以说，运筹学是管理科学最重要的组成部分。1.2 管理决策的定性方法和定量方法
决策是指人们对未来的行动目标及其实现方案进行合理抉择的分析、判断过程，它是管理活动的核心。制定决策的两个基本方法是定性方法和定量方法。
定性方法主要是依靠决策者个人的直觉和判断能力以及过去的经验。定量方法一般是从数据出发，建立有关问题的模型（主要是数学模型），使用数学方法和计算机求解与分析。当采用定量方法如运筹学技术时，要计算出影响行动方案的各个变量的数值。行动方案的选择是建立在计算结果的比较和分析之上的。
例如，假设有一家商店的店主打算向制造商购买某些商品，他可能依靠过去的经验，并结合个人关于市场上对各种商品需求情况的判断来与制造商打交道，这时，这位店主是用定性方法来作决策的。
假如这位店主考虑这样一些因素，如需求预测情况、存贮费用、商品可能过时的损失、商店提供厂家的价格优惠等，并且把这些因素表达在一个数学模型中，以决定购买各种商品的数量，那么，这位店主就是运用定量方法来作决策的。
定性方法是人类长期以来制定决策的传统方法。随着科学技术的进步和现代化生产的发展，管理人员要处理的问题越来越复杂，要考虑的因素越来越多，仅依靠直觉判断或凭以往的经验来作决策会变得越来越困难，风险也会越来越大。因此，借助于定量方法进行决策就成为顺理成章的事情了，而计算机技术的快速发展也使定量方法在实际上的应用成为可能。定量方法的优点是客观、精确，但要求所有的因素必须是可以计量的。若大多数因素不能或很难量化，或者是时间、费用受到限制，则定性方法仍不失为较实用的或者是唯一可行的决策方法。
一般来说，制定决策的过程应做到定性方法和定量方法相结合。定量方法并不能代替决策，而是在决策制定过程中起协助作用，最后的“拍板权”应属于管理人员。过分依赖定量方法是有害的，但如果不能很好地利用定量方法也许会造成更为不利的结果。简而言之，定量方法不能代替决策者的判断和经验，但它对决策者是很有价值的。1.3 运筹学的模型
运筹学研究与分析问题需要广泛使用模型。通常，模型是指为了某个特定目的，对真实系统或现象所作的一种简化表述。为了协助解决实际问题，模型应具有简单和精确这两个特征，它应包含与分析问题有关的主要因素，同时，能反映各有关因素之间的相互关系。
可以使用各种不同的方法对模型进行分类。最简单的方法是把模型分为三种基本形式：（1）形象模型：是指规模缩小或放大的由实物制成的模型，如建筑模型、航空模型、物质的原子结构模型等。（2）模拟模型：是用具有某些性质的简单东西去代替具有另一种性质的复杂东西，当然，这两种不同性质的东西要具有相同的对应关系。体温表就是模拟模型的一个例子，体温表上的刻度用来代表温度的度数。同样，一把计算尺也是一个模拟模型。（3）符号或数学模型：是用符号和数学工具来描述现实系统的一种数学结构。它是目前使用最广泛、作用最大的一种模型。数学模型是运筹学中最常用的模型。使用数学模型有以下几方面的优点：首先，它比其他类型的模型更加精确，其精确度能根据使用者的要求加以调整。其次，在数学训练方面有一种固有的严密性，迫使决策者详细确定问题中的重要因素以及这些因素的存在关系。再次，容易通过增减变量、修改关系式来修改模型并进行灵敏度分析，因此，它比其他模型更灵活。另外，数学是一种使用数据的强有力的方法，并可从已知的假设条件导出结论，通过高速计算机，就有可能处理非常复杂的模型，并且能节省时间和费用。
运筹学模型的一个显著特点是它们大多是最优化模型。这类模型的结构一般可分为两大部分：目标函数和约束条件，其常见的形式为：
最大化或最小化目标函数 V=F（x，y，u）ijk（1.1）
约束条件 G（x，y，u）≥0ijk（1.2）
其中，x为可控变量（也称为决策变量），y为已知ij参数（也称为状态变量），u为随机因素。模型的目标是在满足约束k条件的前提下，使目标函数最大化或最小化（有时只要求满意化）。
目标函数可以是单一的，也可以是多个的。约束条件可以没有，也可以有多个。当目标函数和约束条件都是线性函数时，称模型为线性模型，否则称为非线性模型。当模型中不含随机因素时，称它为确定性模型，否则称为随机模型。当可控变量只取离散值时，称为离散模型，否则称为连续模型。此外，还可以按模型的用途、使用的数学工具、求解方法等来给运筹学模型分类，这里不再赘述。1.4 运筹学的工作步骤
应用运筹学解决实际问题的工作步骤一般包括：确定问题，搜集数据和建立模型，检验模型，模型求解，求解结果分析，求解结果实施，具体如图1-1所示。各个步骤有时是难以严格区分的，在某种程度上，它们相互影响，在实施过程中也应反复进行。例如，建立模型（简称建模）这一步就常常受到现有求解方法的影响，而对求解结果进行分析有时会导致重新建模或确定问题。这些都是在实际工作中经常出现的事情。图1-1（1）确定问题。
为了解决一个实际问题，必须清楚地了解并确定该问题，这是决策制定中的首要步骤。具体要分析问题的性质和环境，确定目标，弄清有关因素及其变化范围和相互关系，并将可控制因素与不可控制因素分开。问题提出后，还要分析解决该问题的可能性和可行性。（2）搜集数据和建立模型。
搜集数据和建立模型是紧密联系的。我们根据拟采用的模型搜集和整理有关数据，必须强调所使用数据的精确性。因为即使所用模型能正确表述实际现象，不正确的数据也必将导致错误的结果。对于大型问题，搜集精确的数据往往是一件费时、费力的艰巨工作。实际上，有时由于难以得到足够的所需数据而必须改变拟采用模型的结构或类型。而一个只要求少量数据但适用的近似模型，往往比一个虽然更为精确但对数据要求太高的模型更受到人们的欢迎。诺贝尔经济学奖获得者及决策理论专家西蒙曾说，数学建模并不要求完美，只需要通过它能得到比直觉更好的结果就行了。
建立模型是运筹学的关键工作步骤。运筹学模型一般是数学模型或仿真模型，以数学模型为主。实际问题通常比较复杂，而模型只是根据一些理论和假设条件对现实世界的简化表述。因此，建立的模型往往要经过多次修改才能在允许的限度内符合实际情况。典型的运筹学模型具有（1.1）和（1.2）的形式，即包含一组要通过求解模型确定的决策变量和各种已知参数（随机模型还包含随机变量），单个或多个反映决策目标的目标函数，一组反映各变量与参数之间复杂关系的约束条件。（3）检验模型。
模型建立以后，必须通过试验来检验其合理性和正确性。一般可通过解特殊的、众所周知的例子或通过使用历史数据对模型进行运算，并把运算结果与实际情况对照来检验模型。若发现有较大的差异，则有必要返回前面的工作步骤。（4）模型求解。
求解模型的途径完全取决于模型的性质和数学复杂性。
对于一些较简单的模型，有时可用经典的数学分析方法求得其解，但这种情况实际上是很少的。求解由（1.1）和（1.2）表示的那一类模型，更经常用到的是一种迭代法。所谓迭代法，就是用某种方法找出一个初始解，然后检验它是否为最优解；若不是最优解，它将会提供某种信息，说明如何可以求得一个比当前解有所改进（或至少一样好）的新解。重复进行这一过程，直到确认问题无最优解或求得一个最优解为止（对于一些复杂的问题，有时只可能求得近似最优解、次优解、满意解或满足最优解必要条件的解）。运筹学中大多数有名的算法都是迭代法，在后面各章我们将会作更详细的介绍。当然，在实际应用中，必须借助计算机进行求解，而解的精度要求可由决策者提出。
除了迭代法，运筹学中另一种常用的解法被称为模拟法或仿真法。它主要用来求解复杂、带有随机因素的模型，这里不多作介绍。
模型求解过程中的一个重要方面是，研究输入数据或模型发生变化时对解的影响，被称为灵敏度分析或优化后分析。灵敏度分析用于确定解的稳定性、所需输入数据的精确度以及引进或删除某些变量的可行性等。（5）求解结果分析。
由于模型只能包含实际问题的主要方面，有许多因素如政策因素、社会因素等都不能包含进去，因而要对求解结果进行全面评价，分析求解结果是否符合现实问题。（6）求解结果实施。
运筹学工作的最后一步是将求解结果付诸实施。这是反映工作成果最重要的一步，也可能是最困难的一步。运筹学工作者必须将求解结果表示为管理决策人员能理解和执行的形式。这些人员必须了解所使用模型的许多方面，包括它的优点和缺点、它所依据的假设条件，以及在执行中它应具备的保证条件。特别要指出的是，将求解结果所提出的新的或经过改变的管理方法用于现实系统的时候，往往需要一段足够长的时间，才能对求解结果实施的效果作出正确的评价。1.5 运筹学与计算机
六十年来，运筹学之所以能迅猛发展，除了它本身能适应社会的发展，有效地解决各个领域中很多依靠经验难以解决的问题以及一些运筹学家在理论和方法上作出了杰出贡献之外，电子计算机技术的快速发展起了重要的推动作用。因为运筹学着重定量解决问题，往往要做大量的运算和数据分析才能获得结果。如果用手工计算，不仅耗时、费力，甚至有时是不可能完成的。因此，计算机成了不可缺少的工具，如果没有计算机，绝大多数运筹技术是完全不能实现的。更重要的是，计算机能快速利用运筹学应用工作中所需的各种类型的管理信息，如果没有这些信息，许多运筹学工作就会变得毫无意义。所以，计算机是推动运筹学应用的基本因素。毫无疑问，随着时间的推移，运筹学与计算机之间的关系将会愈加密切。如今，运筹学方法已成为计算机基础信息系统（Computer-based Information System，缩写为CBIS）的一个主要部分。CBIS包含管理信息系统、决策支持系统、人工智能和专家系统。运筹学模型在这些系统中是大有作为的。
本书主要使用的运筹学软件包是QM（Quantitative Methods的缩写），有DOS和Windows两种版本，前者是在DOS支持下可求解多种运筹学问题的微机软件包。图1-2是QM的主菜单，它包含的内容有：线性规划、（全）整数规划、0-1规划、目标规划、运输问题、指派问题、盈亏平衡分析、决策分析、网络模型、项目管理（网络计划技术）、存贮模型、等待线（排队）模型、动态规划、仿真、预测、马尔柯夫分析和对策（博弈）论等。图1-2
图1-3是QM for Windows的主菜单，该软件能求解更多的运筹学问题，且操作更加方便，求解结果也更为深刻和丰富。读者可通过访问站点http://www.prenhall.com/weiss来下载和升级QM for Windows。图1-3
本书还将介绍如何使用微软公司的Excel for Windows中文版电子表格软件中的“规划求解”加载宏来求解一些运筹学问题。在Excel的启动窗口界面选取菜单栏的“工具”可得图1-4所示的界面。图1-4[1]
在“工具”菜单中选取“规划求解”便可进入规划求解参数对话框，如图1-5所示。根据数据在工作表中的位置和模型的结构，在图1-5所示界面中输入有关信息便可选择“求解”。具体操作方法将在下面各章中介绍。
除了“规划求解”，Excel还提供了很多有效的定量分析方法，读者可参考有关书刊。图1-5
本章小结
决策是管理活动的核心，制定决策的两个基本方法是定性分析法和定量分析法。运筹学是用定量分析方法为管理决策提供依据的一门学科，它是管理科学最重要的组成部分。运筹学研究与分析问题需要广泛使用数学模型，其中大多是最优化模型。应用运筹学解决实际问题的工作步骤一般包括：确定问题，搜集数据和建立模型，检验模型，模型求解，求解结果分析，求解结果实施。
电子计算机是推动运筹学发展的基本因素，是运筹学不可缺少的工具；而运筹学方法如今已成为计算机基础信息系统（CBIS）的一个主要部分。随着时间的推移，运筹学与计算机之间的关系将会更加密切。本章初步介绍了书中所使用的运筹学计算机软件。
[1] 若“工具”菜单中没有“规划求解”项目，可以使用“工具”的“加载宏”，在“现用加载宏”方块里，打开“规划求解加载宏”，选择“确定”，就能在“工具”中安装“规划求解”项目。2 线性规划与单纯形法
本章要求
掌握线性规划的数学模型及建模步骤。
掌握线性规划的图解法。
认识线性规划的标准型及掌握转化为标准型的方法。
掌握单纯形法与单纯形表；掌握人工变量方法的使用。
会使用计算机软件求解线性规划。
掌握线性规划一些常见的应用例子。
线性规划（Linear Programming）是运筹学中一个应用最为广泛的重要分支。自从1947年G. B. Dantzig提出了求解一般线性规划问题的有效方法——单纯形法（Simplex Method）之后，线性规划得到了较快的发展。由于线性规划的模型比较简单，理论与方法都比较成熟，又有很多供不同使用者使用的计算机软件，因此，线性规划在工业、农业、商业、交通运输业、军事、经济和管理等各领域中得到了广泛的应用。曾经有人做过调查，在世界500家大公司中，有85%的公司使用过线性规划解决经营管理中遇到的复杂问题。在经济管理活动中，人们经常利用线性规划模型求解有限资源的最优分配问题。随着电子计算机技术的迅速发展，线性规划将在经济管理中发挥越来越大的作用。
应该指出，近年来已出现了若干在理论上优越于单纯形法的算法，其中的Karmarkar算法及其变形在实际应用中也显示了巨大的潜力，尤其是对于大型问题。不过，并不能说新算法将要替代单纯形法，至少在可以预见的将来不会，沿用至今的单纯形法仍在继续发挥其积极作用。有兴趣的读者可参看有关参考文献（如本书参考文献3）。2.1 线性规划的基本概念2.1.1 线性规划的数学模型
在生产管理和经营活动中常常提出一类问题，即如何合理地利用有限的人力、物力、财力及时间等资源，以得到最好的经济效果。这类问题大部分可表示为如下的规划问题：在一定的约束条件（限制条件）下，使得某一目标函数取得最大（或最小）值。当规划问题的目标函数与约束条件都是线性函数时，便称为线性规划问题。下面通过一些具体例子来介绍线性规划的数学模型。
例1 生产计划问题。
某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表2-1所示。问应如何安排生产使该厂获利最大？表2-1产品A产品B资源限额劳动力 设 备 原材360工时 200台时 3009 4 34 5 10料千克单位产品利润（元）70120
首先建立问题的线性规划模型，通常有以下几个步骤：（1）确定决策变量。决策变量是模型要决定的未知量，或者说是决策者采用的模型所规定的抉择方案。确定合适的决策变量是成功地建立数学模型的关键。在本例中，工厂要确定各种产品的生产数量，因此可设x、x分别表示在计划期内产品A、B的产量。12（2）确定目标函数，就是将决策者所追求的目标表示为决策变量的函数。很明显，本例的目标函数是使z=70x+120x最大。可写为12
max z=70x+120x12（3）确定约束条件。这些约束条件可用决策变量的等式或不等式来表示。在例1中，资源的使用量必须受到限制，因此有
9x+4x≤360 （劳动力）12
4x+5x≤200 （设 备）12
3x+10x≤300 （原材料）12
此外，显然还应有变量非负约束条件，即x≥0，x≥0。12
综上所述，我们便得到如下的数学模型：
max z=70x+120x12
s.t. 9x+4x≤36012
4x+5x≤20012
3x+10x≤30012
x，x≥012
模型中所用的s.t.是“subject to”（受约束于）的缩写，它表明决策者的行为受后边限制条件的约束。
上述模型的解称为最优解。下面将看出其最优解为x=20，x=24；12目标函数最优值为z=4 280。这说明该厂的最优生产计划是：生产产品A 20单位，生产产品B 24单位，可获得最大利润4 280元。
例2 营养配方问题。
某公司饲养实验用的动物以供出售。已经知道这些动物的生长对饲料中的三种营养元素特别敏感，我们分别称它们为营养元素A、B和C。已求出这些动物每天至少需要700克营养元素A、30克营养元素B，而营养元素C的每天需要量刚好是200毫克，不够或者过量都是有害的。现有五种饲料可供选用，各种饲料每千克所含的营养元素及单价如表2-2所示。为了避免过多使用某种饲料，规定混合饲料中各种饲料的最高含量分别为50、60、50、70、40千克。要求确定满足动物需要而费用最低的饲料配方。表2-2
解：设x（j=1，…，5）为每天混合饲料内包含的第j种饲料的千j克数，则营养问题的线性规划模型如下：
使用软件求解，可得最优解：x=50，x=3，x=0，x=70，1234x=40，目标函数最优值z=951。因此，最优饲料配方是每天混合505千克第1种饲料，3千克第2种饲料，70千克第4种饲料以及40千克第5种饲料，最低成本为951元。
例3 人员排班问题。
某医院根据日常工作统计，每昼夜24小时中至少需要下列数量的护士。序号时段最少护士人数16：00~10：0060210：00~14：0070314：00~18：0060418：00~22：0050522：00~2：002062：00~6：0030
护士们分别在各时段开始时上班，并连续工作8小时，问应如何安排各个时段开始上班工作的人数，才能使护士的总人数最少？
解：设第j时段开始上班的人数为x，j=1，…，6，则为护士j的总人数，因此有
如下模型：
min z=x+x+x+x+x+x123456
s.t. x+x≥7012
x+x≥6023
x+x≥5034
x+x≥2045
x+x≥3056
x+x≥6061
x≥0且为整数，j=1，…，6j
上机求解可得最优解x=50，x=20，x=50，x=0，x=20，12345x=10，最优值z=150。因此，医院至少应配备150名护士。6
请读者使用例3的建模思路，解下列思考题。
思考题：一家银行每天营业的时间从上午9：00到下午5：00。除了管理层，银行最多可雇用12名全职员工，其余均为兼职员工。全职员工上午9时上班，下午5时下班，中间有1小时的午餐休息时间（一半全职员工在11时进餐，另一半在中午12时进餐）。兼职员工每天连续工作4小时，可以安排在上午9时到下午1时的任意整点时刻上班。一天中各时段所需员工的数目如下：时段员工的最少人数9：1000~10：00
10：1200~11：00
11：1400~12：00
12：1600~13：00
13：1800~14：00
14：1700~15：00
15：1500~16：00
16：1000~17：00
全职员工的平均工资是每天250元，而兼职员工的平均工资是每小时20元（每天80元）。银行规定兼职员工每天的总工作时间不能超过所需工作时间的一半，并允许不雇用一些全职员工。试求该银行支付最少工资的安排方案。
提示：最优安排方案不唯一，其中之一是：雇用10名全职员工，并安排2名、7名和5名兼职员工分别在上午10时、11时和中午12时开始上班。每天支付的最小工资额为3 620元。
从以上三个例子可以看出，线性规划问题是寻求满足若干线性等式与不等式的一组变量值以使得某一个线性函数取得最大值或最小值的极值问题。它的一般形式为：
其中，z称为目标函数，（2.2）、（2.3）称为约束条件；（2.3）也称为变量的非负约束条件。对于所有求解线性规划的软件，条件（2.3）几乎都是默认的。T
若向量X=（x，x，…，x）满足所有的约束条件，则称其为可12n行解，而使目标函数达到最大值（或最小值）的可行解称为最优解。最优解的目标函数值称为最优值。
在结束这一小节之前，有必要说一下线性规划问题隐含的假设，这就是比例性、可加性、可分性和确定性假设。（1）比例性假设：每个决策变量的变化所引起目标函数的改变量及约束条件左端的改变量与该变量的改变量成正比例。（2）可加性假设：每个决策变量对目标函数和约束条件的贡献是独立于其他变量的。总贡献是每个决策变量单独贡献之和。（3）可分性假设：每个决策变量都允许取分数值。换言之，决策变量允许为非整数值。（4）确定性假设：每个参数（c，a，b）都是确定性已知的。jiji在线性规划问题中不涉及随机因素。
在现实生活中，完全满足这些条件的问题是很有限的。但若问题近似满足这些条件，仍然可使用线性规划进行求解和分析。否则，可考虑使用其他方法，如非线性规划、整数规划、参数规划或随机性分析方法等。2.1.2 线性规划的图解法
简单的线性规划问题可用图解法求解。图解法虽然实际应用意义不大，但简单直观，有助于初学者了解线性规划问题的几何意义及求解基本原理。现用图解法求解例1。由于例1只有两个变量，我们可以在平面直角坐标系中描述该问题（如图2-1所示）。图2-1
首先，变量非负条件x，x≥0是指第一象限。每个不等式约束都12代表一个半平面，例如，第一个约束表示以直线9x+4x=360为边界12的左下方的半平面。同时满足所有约束条件的点必然落在由三个半平面与第一象限相交的区域内，即图2-1的阴影部分。阴影区域中的每一个点（包括边界点）都是例1线性规划问题的可行解，因而此区域是可行解的集合，称它为可行域。
目标函数z=70x+120x在坐标平面上表示以z为参数的一族平行12线，其法向量是任一与向量（70，120）平行且同向的向量。任选一个z，便可得到一条直线，该线上所有可行点都有相同的目标函数值，因此被称为等值线。让等值线沿其法线方向平行移动，目标函数值将逐渐增加，当移到B点后，再向外移就会脱离可行域，因此，z值最大的等值线与可行域的公共点B便是最优解。它是两条直线4x+5x=200与3x+10x=300的交点，其坐标为（20，24），于是可1212计算出相应的z=70×20+120×24=4 280。
上例求出的最优解是唯一的，但对一般线性规划问题，求解还可能出现以下几种情况。（1）无穷多个最优解。若将例1中的目标函数改为求max z=70x+87.5x，则等值线族与可行域的边界线4x+5x=200平行（如1212图2-2所示）。易见，线段BC上任意一点都使z取得相同的最大值，所以这线性规划有无穷多个最优解。图2-2（2）无界解。
对下述线性规划问题
max z=x+x12
s.t. -x+x≤212
3x+2x≥612
x，x≥012
用图解法的求解结果如图2-3，从图中可以看到，在可行域中，目标函数值可以趋向于正无穷大，因此，该问题有可行解但没有最优解。这种情况称为问题具有无界解或问题无界。图2-3（3）无可行解。如果在例1的数学模型中增加一个约束条件x+x12≥60，所得到的新问题的可行域为空集，即无可行解，当然不存在最优解。
当求解结果出现（2）、（3）两种情况时，一般说明建立的线性规划模型有缺陷或错误，尤其是后者有相互矛盾的约束条件，应对模型进行修改。
从以上的例子，我们可以直观地看到二维线性规划的两个几何特征：（1）若可行域非空，它是一个凸集[通俗地讲，如果一个集合S中任意两个点之间的连线都在S中，则称S是凸集。例如，图2-4中的（a）和（b）是凸集，而（c）和（d）不是凸集]。图2-4（2）若线性规划存在最优解，它一定可在可行域的某个顶点（极点）得到（直观地说，凸集的极点不是凸集中任一线段的内点）。
以后将指出，高维的线性规划也有这两个特征。读者不妨想象一下三维线性规划可行域的形状以及最优解在可行域中的位置。
对于变量数多于三个的线性规划问题，图解法就无能为力了。所以下一节将介绍一种有效的代数法——单纯形法。为了便于讨论，我们先规定线性规划的标准形式。2.1.3 线性规划的标准型
由上面的例子可知，线性规划问题的具体形式往往很不一致。目标函数可以是求max，也可以是求min；约束类型可以是“≥”“≤”或“=”；决策变量一般有非负限制，但也允许非正或无限制。为了便于统一处理，有必要规定线性规划的标准形式（SLP），本书使用的标准型为：
并规定各约束条件的右端项b≥0，否则，可在等式两端乘以i“-1”。
这样，（SLP）的约束条件由约束方程组和变量非负条件两部分组成。（SLP）可简写为（2.4）（2.5）
x≥0，j=1，…，n j（2.6）
引入下面的记号：T
X=（x，x，…，x），C=（c，c，…，c），b=（b，b，…，12n12n12Tb）mT
A=（a）（m×n阶矩阵），P=（a，a，…，a）（矩阵Aijm×nj1j2jnj
的第j列）
则（SLP）还可表述成以下两种形式。
用矩阵描述： max z=CX
s.t. AX=b
X≥0
用向量描述： max z=CX
x≥0，j=1，…，nj
一般称C为价值向量，b为资源向量，A为技术系数矩阵。
实际上，各种线性规划模型都需要转化成标准型后求解。下面介绍各种转化方法。（1）最小化问题的转化。求min z等价于求max（-z），因此，只需改变目标函数的符号就可以实现最大化和最小化之间的转换。（2）不等式约束的处理。不等式约束可以通过引入松弛变量或剩余变量转化为等式约束，具体为：
其中x称为松弛变量。s
其中x称为剩余变量。s（3）非正变量与符号无限制变量的处理。
若x≤0，令x′=-x，则新变量x′为非负变量。kkkk
若x为符号无限制变量（称为自由变量），可令x=x′-x″，其中xkkkk′，x″≥0，即以两个非负变量之差来代替自由变量。kk
从以上讨论可见，任何形式的线性规划都可转化为标准型，下面举例说明。
例4 把例1的线性规划模型转化为标准型。
例1的线性规划模型如下：
max z=70x+120x12
s.t. 9x+4x≤36012
4x+5x≤20012
3x+10x≤30012
x，x≥012
只需引入松弛变量x，x，x即可转化为标准型：345
例5 将下面的线性规划问题转化为标准型。
解：步骤如下：（1）令x=-x′，x=x-x，其中x，x≥0；1134545（2）在第一个约束不等式“≤”号的左端加入松弛变量x，在第6二个约束不等式“≥”号的左端减去剩余变量x；7（3）令z′=-z，把求min z改为求max z′，于是便可以得到该问题的标准型：
上述标准型有三个约束方程、六个非负变量。若我们一开始就从原问题的等式约束3x+x-3x=5解出自由变量x，代入目标函数与其1233他约束条件，然后再进行其他变换，将得到只有两个约束方程、四个非负变量的标准型。这样做可减小问题的规模。
由于任何形式的线性规划都能转化为（SLP），以下我们将以（SLP）为主要研究对象。2.1.4 高斯迭代
例1的标准型（SLP）为：
此时，技术系数矩阵和资源向量矩阵构成的增广矩阵为：
将x，x移到右边，左边保留x，x，x，则约束条件①变为：12345
令x=x=0，则x=360，x=200，x=300，得到第一个可行解：12345（0）
X=（0，0，360，200，300）（0）
z=70x+120x=0 12
在目标函数中，因为x，x的系数为正，即σ=70，σ=120，且1212σ> σ，将x换到左边可以改善目标函数的值，此时x仍然保留在右2121边，即x=0。1
对应条件②，要保持x，x，x≥0，则对应的x≤=90；x≤34522=40 ；x≤=30，即θ=min {90，40，30}=30，该结果意味着θ=30对2应的x趋于零的速度比x、x快。因此，将x换到右边。5345
左边的变量为x，x，x，右边的变量为x，x，则约束条件①23415变为：
对③进行行变换，得到
此时，增广矩阵为：
令x=x=0，则x=240，x=50，x=30，得到第二个可行解：15342（1）
X=（0，30，240，50，0） （1）
z=70x+120x=360+34x-12x=3601215
试读结束[说明：试读内容隐藏了图片]