清华大学MBA课程讲义——运筹学.doc

课程介绍一、运筹学产生的和发展1. 运筹学产生的原因 科学技术的发展，利用和改造自然的规模扩大，生产规模扩大，生产组织形式复杂，出现了更复杂的管理方面的问题。 管理方面的新问题：如何有效和合理地利用有限的或稀缺的资源，使系统的整体目标达到最优。2. 运筹学的起源 运筹学的三个来源：军事、经济、管理 1981年美国军事运筹学会出版的 “System analysis and modeling in defence”一书中称孙武子是世界上第一个军事运筹学家。 第二次世界大战期间英、美等国军事部门成立的一些研究小组的研究活动。最初人们称这类研究为 “运作研究” (operational research)，或“运作分析” (operational analysis)。 研究的特点是集中一批跨多学科的研究人员，有组织地对一特定问题进行系统分析，提出提高某武器系统效率的操作方法和执行策略。 二战期间成功的运筹研究案例有： 英国防空部门如何布置防空雷达，建立有效的空防预警系统； 研究反潜飞机巡逻路线及深水炸弹引爆深度，击沉德军潜艇数提高4倍； 研究如何使用机载雷达提高轰炸命中率，两年内使命中率提高3倍； 研究船队在受敌机攻击时的躲避策略，使中弹率从47%下降到29%； 数理经济对运筹学的影响 Qusnay 的经济表 Walras 提出的经济平衡问题 Von Neumann 提出的广义经济平衡模型 康托洛维奇 (Kantorovich)发表的生产组织和计划中的数学方法 管理科学 - 运筹学的关系 管理理论中最有影响的三个学派中的两个（古典学派与系统学派）广泛应用定量分析与系统分析的方法。 古典学派的代表性人物 Taylor, Gantt 等提出的动作分析、甘特图至今还在使用。3. 运筹学的发展 二战结束后运筹学在理论上得到全面的发展；线性规划、非线性规划、动态规划、网络分析、整数规划、对策论、排队论等分枝得到迅速的发展。运筹学应用从军事部门迅速向工业部门转移。经过50多年的发展，运筹学已成为一个门类齐全、理论完善、有广泛应用前景的新兴的科学学科。运筹学发展有以下几方面的原因： 运筹学在战争中的成功吸引更多的资源投入这一研究领域； 二战结束后，经济发展成为各方注视的焦点，经济和工业界有许多问题可以用运筹学方法解决； 计算机的出现为运筹学的应用提供了最好的技术支持。线性规划的发明 丹捷格(Danzing)1947年提出单纯形法； 康托洛维奇 (Kantorovich) 于1939提出用于前苏联经济计划的类似模型及“解乘数法”的求解方法； 冯. 诺伊曼 (Von Neuman) 和摩根斯坦(Morgenstern) 1944年发表的对策论与经济行为涉及与线性规划等价的对策问题及线性规划对偶理论。 康托洛维奇和库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获1975年诺贝尔经济学奖 从1964年诺贝尔奖设经济学奖后，到1992年24年间的32名获奖者中有13人 (40%) 从事过与线性规划有关的研究工作，其中比较著名的还有Simon， Samullson，Leontief，Arrow，Miller 等。4. 运筹学对社会的影响运筹学应用领域的进一步扩大，运筹学已渗透到社会生活各个角落，在石油、电力、航空、冶金、交通运输、通讯、军事等领域有广泛的应用，给人们带来巨大的财富二、运筹学研究的对象与特点1. 运筹学的研究对象运筹学（Operations Research） Research：表明是一种研究，隐含其理性与科学性的一面； Operations：表明是针对具体运作的，隐含其实践与应用性的一面。一些教科书给运筹学下的定义： 运筹学是一种科学决策方法； 运筹学是依照给定目标和条件从多方案中选择最优方案的最优化技术； 运筹学是一门寻求在给定资源条件下，如何设计和运行一个系统的科学决策方法” 运筹学与事理科学 科学知识的两大类：自然科学与社会科学。 研究一般“事物”的科学称为哲学 研究“物”的科学称为“物”理科学 研究“事”的科学称为“事”理科学 运筹学与其它自然科学明显的区别在于它研究的对象是“事”而不是“物”。它揭示的是办事的内在规律，研究的是如何把事办好。因此也有人称运筹学为事理科学。 运筹学与其它自然科学明显的区别在于它研究的对象是“事”而不是“物”。它揭示的是办事的内在规律，研究的是如何把事办好。因此也有人称运筹学为事理科学。 物是看得见、摸得着的实实在在的东西，如石头，金属，有生命的，无生命的，自然界中的一切，包括人； 事是指有人参与的活动过程，这种过程是一种客观存在，但是看不见、摸不着。 物有明显的规律性，比较容易认识，大量关于物的科学构成了自然科学的主体； 事有明显的权变性，不同的人办事可能得到不同的结果，长期以来人们认为如何办事属于经验和艺术的范畴，不存在普遍规律性。 关于物的知识是硬的，科学的，可以形式化、定量化地加以描述和讲授； 关于事的知识是软的，非科学的，难以形式化、定量化地加以描述，只可意会而不可言传。 事理科学的存在性 在科学不发达的过去，事的复杂性并不突出，办事完全可以凭经验，没有必要寻找如何办事的科学； 工业革命之后，事变的越来越复杂，人们无法单凭经验对复杂的系统进行管理。 运筹学方法的提炼和发展过程对现代科学思想的贡献： 明确了事与物是一对矛盾，实践的对象包含了物和事两个方面。 事物总有一定的规律性，事的权变性不可能取消其规律性，只是更复杂，更难被认识。 事理是可以被认识和利用的，认识这些规律，就掌握了办事的主动权。 运筹学完成了对办事内在规律的形式化，定量化的描述，建立起可以研究、应用和讲授的理论框架。 事在人为靠运筹 物理科学回答“是什么”“为什么”等问题，揭示物质运动的规律； 事理科学回答“做什么”“怎么做”等问题，探讨如何办事的规律性； 事是由人的活动构成的，一切事情都需要人的参与才能完成，人的主观能动性有时起决定性的作用。2、运筹学的研究特点 科学性 在科学理论指导下，通过规范化步骤进行； 广泛利用多学科知识。 实践性 以实际系统为研究对象，通过分析鉴别问题的性质、系统目标以及系统内主要变量之间的关系； 以改进实际系统运行效率为目标，利用数学模型对系统进行优化； 分析获得的结果要在实践中进行检验，并可指导实际系统的优化运行。 系统性 用系统的观点来分析一个组织（或系统），着眼于整个系统而不是一个局部； 通过协调各组成部分之间的相互关系，使整个系统达到最优状态 综合性 问题的综合性：运筹学研究涉及的系统问题多，规模大，结构复杂； 知识的综合性：应用多学科知识，因此，需要一 个由各方面专家组成的专家组共同完成，个人是不可能完成的。3、运筹学的研究方法 运筹学研究广泛应用现代科学技术知识解决实践中提出的管理与决策问题； 运筹学研究有规范的分析方法和分析步骤，提高人们对问题的把握和理解； 运筹学研究借助数学模型与计算机； 运筹学定义：运筹学是一门应用学科，它广泛应用现代科学技术知识，通过规范化的分析方法和步骤，提高人们对实际事物的把握与理解，从而发现需要解决的管理与决策问题，并为选择最优决策提供定量分析的依据。三、运筹学研究的具体过程 运筹学研究的主要目的 - 发现问题和解决问题： 发现影响系统运行效率的主要问题； 提出改进现有系统的运行效率的建议； 合理配置和使用系统内的稀缺资源；发现问题和解决问题的过程：1 寻找、鉴别问题； 2 确定可能的解决方案； 3 确定方案选择、评价的准则； 4 进行方案评价； 5 方案选择； 6 执行选择的方案； 7 执行结果的评价 利用模型解决问题的过程： 系统分析与问题描述（1，2） 模型建立与修改（2，3） 模型求解与检验（4，5） 结果分析与实施（6，7）1、系统分析与问题描述提出问题，明确目标，找出系统变量，弄清其变化范围、相互关系、以及对目标的影响，分析解决问题的可行性： 技术可行性：有无现成方法可使用； 经济可行性：需要投入什么样的资源，研究成本是多少，预期效果如何； 操作可行性：研究的人员和组织是否落实，研究能否顺利进行；2、模型建立与修改模型是对现实世界的抽象和映射，构造模型时要根据一些假设对模型进行必要的抽象和简化。 模型构造是一门基于经验的艺术，既要有理论作指导，又要靠不断的实践来积累建模的经验。 模型往往要经过多次修改才能在允许的限度内符合实际情况。 3、模型求解与检验假设条件的合理性，模型结构的正确性要通过求解和分析进行检验，并通过一个反馈环节退回到模型建立和修改阶段，有时甚至还需要退回到系统分析阶段。 4、结果分析与实施运筹学研究的最终目的是要提高被研究系统的运行效率。不应把运筹学研究的结果理解为仅是一组最优解，它包括了获得这些结果的方法、步骤、以及与之相关的管理理论。 运筹学分析人员要与管理人员对问题取得共识，使管理人员了解分析过程，掌握分析方法，能独立完成分析，以保证研究成果的实施。 模型的分类： - 按呈现和表达的方式分类： 实物模型：如建筑模型，飞机模型等; 符号模型：用数学符号表示的写在记录介质上的模型，如 P = 10 x 计算机模型：可执行的由计算机语言表达的程序。 - 按描述方法分类： 描述型模型：描述实际发生的具体过程而不探讨过程背后的原因，如统计模型、模拟模型和排队模型； 规范化模型：使用规范的方法，对影响系统的内在规律进行探索，大部分优化模型属于这类模型； 启发式模型：经验模型，主要由直观的经验和规则构成。 - 按变量和参数的性质分类： 确定型模型：参数和变量是确定的，如线性规划、整数规划和网络模型； 随机型模型：参数和变量是随机的，如排队模型、决策模型和对策模型。 - 按时间因素分类： 静态模型：反映某一固定时点的状态，变量、参数与时间无关； 动态模型：反映一段时间内系统变化状态，变量、参数与时间有关。四、学习运筹学的目的1、掌握运筹学的基本分析方法 分析方法：线性规划、非线性规划、整数规划、网络规划、动态规划、决策理论、对策论等 分析方法论：实践的观点、系统观点、优化观点2、提高运用运筹学方法解决实际问题的能力 能运用运筹学基本分析步骤分析实际问题； 掌握一般类型的运筹学模型的构模技巧； 能运用计算机工具解决简单的管理问题；绪言运筹学(operations research)是近40年来发展起来的新兴学科，尽管古朴的运筹学思想可以追溯到几百年甚至上千年以前，世界上公认的运筹学的起源是第二次世界大战期间，英、美等国的军事部门为战争需要而成立的一些研究小组的研究活动。最初，人们称这类研究为“运作研究”(operational research)，或“运作分析”(operational analysis)。这些研究的最主要的特点是集中一批跨多种学科领域的科学研究人员，有组织地对一特定问题进行全面、系统的分析，提出提高某武器系统效率的操作方法和执行策略。比较成功的研究案例有：英国防空部门对如何布置防空雷达，建立最有效的空防预警系统进行的研究；英、美空军对如何提高轰炸机对德国地面目标轰炸的命中率进行的研究；英、美海军在反潜作战中，如何安排反潜巡逻飞机的飞行路线，如何投放深水炸弹以及如何确定深水炸弹的起爆深度等研究。这些研究大大提高了盟军的作战能力，为取得反法西斯战争的最后胜利作出了巨大的贡献。第二次世界大战结束后，运筹学的研究方法在理论上得到全面的发展，线性规划、非线性规划、动态规划、网络分析、整数规划、对策论、排队论等运筹学的分枝得到迅速的发展和完善。运筹学的应用也从军事部门迅速向经济和工业部门转移，并得到越来越广泛的重视。经过40多年的发展，运筹学已成为一个门类齐全、理论完善、有着广泛应用前景的新兴的科学学科。一、什么是运筹学什么是运筹学，人们一直试图给运筹学下一个简单明了的定义。但是事情并不那么简单，由于运筹学研究问题的广泛性和复杂性，以及与相邻学科的相似性，人们一直还没有形成一个统一的运筹学定义。以下是一些教科书给运筹学下的一些定义：“运筹学是一种科学决策的方法”；“运筹学是依照给定目标和条件从众多方案中选择最优方案的最优化技术”； “运筹学是一门寻求在给定资源条件下，如何设计和运行一个系统的科学决策的方法” . . . . . .以上定义都过于简单，不能令人满意。运筹学的内涵决不仅仅是解决复杂问题的优化技术或各种科学决策方法的组合。它实际是一种对系统进行科学的定量分析，从而发现问题、解决问题的哲学方法论。运筹学具有多学科交叉的特点，它广泛地应用现代科学技术和知识，如：数学、经济学、社会学、心理学、物理学、生物学、化学等，解决人们在各类实践活动中提出的管理问题。运筹学通过一整套规范化的分析方法和分析步骤，提高人们对实际问题的把握与理解，并为决策者选择最优决策提供定量分析的依据。运筹学与其它自然科学明显的区别在于它研究的对象是“事”而不是“物”。它揭示的是事的内在规律，研究的是如何把事办的更好。因此也有人称运筹学为“事理科学”。“事”是相对“物”存在的，物是看得见、摸得着的实实在在的东西；而事是指有人参与的活动，是看不见、摸不着的。物的运动有明显的规律性，人们比较容易认识它，大量的关于物的科学构成了自然科学的主体；而事有明显的权变性，不同的人们办相同的事可能得到不同的结果，因此，人们长期以来认为如何办事属于经验和艺术的范畴，不存在普遍的规律性。在20世纪之前，事的复杂性并不突出，人们也没有必要去寻找如何办事的科学。工业革命发生之后，事情发生了明显的变化，由于科学技术的加速发展，使人们面临的事物越来越复杂，人们无法再凭单纯的经验对如此复杂的系统进行管理。这些因素促使人们寻找如何办事的科学，从而引来的新的学科 - 运筹学的发展。人们认识和实践的对象包含物和事两个方面：物是“硬件”，如企业的厂房、设备和原料，战争中的军队和武器；事是“软件”，如企业的管理方法，战争中的战法和战略。很明显，硬件只有在软件的配合下才能发挥出更大的作用。物有物理，事有事理，事的权变性不可能取消它的规律性，只是它更复杂，更难被认识而以。运筹学的分析表明，许多看起来毫不相关的事，背后都被共同的规律支配着。一旦人们认识这些规律之后，就掌握了如何办事的主动权，“事在人为靠运筹”说的就是这个道理。运筹学的开拓者大都是自然科学家和数学家，良好的科学训练使他们意识到事理科学的存在，并将它们发掘出来。他们把自然科学方法应用到对事的规律的分析上，创造出运筹学的分析方法，成功地完成了对事的内在规律的形式化，定量化的描述，建立起可以研究和应用的理论框架。运筹学研究的核心是将科学方法应用到对具体事物的分析中去。从方法论上讲，运筹学和一些相邻学科有着密切的关系。例如，人们常常把运筹学和管理科学联系在一起。然而，管理科学涵盖的领域要比运筹学更宽一些。可以说，运筹学是管理科学最重要的组成部分。再例如，运筹学与系统科学、系统分析、工业工程等学科也有很多共同之处，但它们涉及的面要比运筹学窄一些。运筹学研究的特点可以简单地归纳如下：1. 1. 科学性：运筹学研究是建立在科学的基础上的。运筹学研究的科学性表现的两个方面：首先，它是在科学方法论的指导下通过一系列规范化步骤进行的；其次，它是广泛利用多种学科的科学技术知识进行的研究。运筹学研究不仅仅涉及数学，还要涉及经济科学、系统科学、工程物理科学等其它学科。2. 2. 实践性：运筹学是一门实践的科学，它完全是面向应用的。离开实践，运筹学就失去了存在的意义。运筹学以实际问题为分析对象，通过鉴别问题的性质、系统的目标以及系统内主要变量之间的关系，利用数学方法达到对系统进行优化的目的。更为重要的是分析获得的结果要能被实践检验，并被用来指导实际系统的运行。3. 3. 系统性：运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。4. 4. 综合性：运筹学研究是一种综合性的研究，它要涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。二、运筹学模型许多科学研究都要利用模型，模型通常是指为特定目的建立的，反映某种客观存在特征和特性的一种结构。模型可以是实际模型，也可以是抽象模型。运筹学研究的模型主要为抽象模型 - 数学模型。数学模型的基本特点是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理定律、外部环境等）。利用模型进行研究有以下优点：1. 1. 在建立模型的过程中，需要对被研究系统进行深入细致的分析，可增加人们对系统的了解和把握；2. 2. 模型可以更全面的描述一个复杂的系统，并揭示系统的一些用其它方法不可能发现的内在联系；3. 3. 利用模型，人们可以对系统进行多种试验分析，而这种分析是不可能利用实际系统完成的。模型的种类是多种多样的，分类的方法也很多，如：l l 按呈现和表达的方式可分为： 实物模型：规模缩小的由实物制成的模型，如建筑模型，飞机模型等; 符号模型：用数学符号表示的写在纸上或其它记录介质上的模型； 计算机模型：模型表现为可在计算机上执行的由计算机语言表达的程序。l l 按描述方法的特点，模型可分为以下几类：描述型模型：这类模型仅仅描述实际发生的具体过程而不探讨过程背后的原因。许多统计模型、模拟模型和排队模型都是这类描述性模型。规范化模型：这类模型使用规范的方法，对影响系统的内在规律进行探索，并详细描述系统的变量、目标和约束。大部分优化模型属于这类模型，也是我们主要研究的模型；启发式模型：这类模型是一种经验模型，它主要由一些直观的经验和规则构成。l l 按模型变量和参数的性质，模型可分为： 确定型模型：模型的参数和变量都是确定型的，如本书将要介绍的线性规划、整数规划、网络规划模型； 随机型模型 模型的参数和变量是随机型的，如排队模型、决策模型和对策模型就属于随机模型。l l 按模型是否考虑时间因素，模型还可分为： 静态模型：模型只反映某一固定时点的系统状态，变量、参数与时间无关； 动态模型：模型反映一段时间内系统变化的状态，变量、参数与时间有关，如动态规划模型就是典型的动态模型。 还有很多准则可用来对运筹学模型进行分类，这里就不一一列举了。 运筹学模型的一个显著的特点是它们大部分优化模型。一般来说，运筹学模型都有一个目标函数和一系列约束条件，模型的目标是在满足约束条件的前提下使目标函数最大化或最小化。三、运筹学分析的主要步骤运筹学的分析步骤一般包括：发现和定义待研究的问题；构造数学模型；寻找经过模型优化的结果，并通过应用这些结果来改善系统的运行效率。具体步骤如图I所示。图I 运筹学研究的基本步骤1.系统分析和问题描述运筹学分析的第一步是分析问题和提出问题，它是从对现有系统的详细分析开始的，通过分析找到影响系统的最主要的问题。另外，通过分析，还要明确系统或组织的主要目标，找出系统的主要变量和参数，弄清它们的变化范围、相互关系、以及对目标的影响。问题提出后，还要分析解决该问题的可能性和可行性。一般需要进行以下分析：(1) 技术可行性 - 有没有现成的运筹学方法可以用来解决存在的问题；(2) 经济可行性 - 研究的成本是多少，需要投入什么样的资源，预期效果如何；(3) 操作可行性 - 研究的人员和组织是否落实，各方面的配合如何，研究能否顺利进行；通过以上分析，可对研究的困难程度，可能发生的成本，可能获得的成功和收益做到心中有数，使研究的目的更加明确。2. 模型的建立和修改模型建立是运筹学分析的关键步骤。运筹学模型一般是数学模型或模拟模型，并以数学模型为主。模型是对现实世界的一种抽象和映射。由于实际问题的复杂性，模型不可能完全准确的反映现实世界或实际问题，人们在构造模型时，往往要根据一些理论的假设或设立一些前提条件来对模型进行必要的抽象和简化。人们对问题的理解不同，根据的理论不同，设立的前提条件不同，构造的模型也会不同。因此，模型构造是一门基于经验的艺术，既要有理论作指导，又要靠不断的实践来积累建模的经验。模型建立不是一个一次性的过程，由于实际问题与人们对它的认识之间存在的差异，模型往往要经过多次修改才能在允许的限度内符合实际情况。一个典型的模型包括以下组成部分：(1)一组需要通过求解模型确定的决策变量；(2)一个反映决策目标的目标函数；(3)一组反映系统复杂逻辑和约束关系的约束方程；(4)模型要使用的各种参数。简单的模型可以用一般的数学公式表示，复杂的模型由于必须借助于计算机求解，还必须表达为相应的计算机程序。3. 模型的求解和检验模型建成之后，它所依赖的理论和假设条件的合理性，以及模型结构的正确性都要通过试验进行检验。通过对模型的试验求解，人们可以发现模型的结构和逻辑错误，并通过一个反馈环节退回到模型建立和修改阶段，有时甚至还需要退回到系统分析阶段。模型结构和逻辑上的问题解决之后，通过收集数据、数据处理、模型生成、模型求解等过程得到了模型的最优解。值得强调的是，由于模型和实际之间存在的差异，模型的最优解并不一定是真实问题的最优解。只有模型相当准确地反映实际问题时，该解才是实际最优解的一个很好的近似。4. 结果分析与实施运筹学分析的最后一步是获取分析的结果并将之付诸实施。运筹学研究的最终目的是要提高被研究系统的效率，因此，这一步也是最重要的一步。绝不能把运筹学分析的结果理解为仅仅是一个或一组最优解，它也包括了获得这些解的方法和步骤，以及支持这些结果的管理理论和方法。通过分析，要使管理人员与运筹学分析人员对问题取得共识，并使管理人员了解分析的全过程，掌握分析的方法和理论，并能独立完成日常的分析工作，这样才能保证研究分析成果的真正实施。四、本教材的结构本教材是参考“试办工商管理硕士学位协作小组”发布的工商管理硕士教学大纲编写的。在讨论运筹学的基本理论和方法的同时，本教材还安排了大量的应用例题，每一章的结尾都安排了必要的习题。第一章 线性规划与单纯形方法根据统计，应用最广泛的运筹学学方法为： 数学规划（线性规划，整数规划） 模拟 网络模型（包括PERT/CPM） 决策分析 排队理论 库存模型最基本的运筹学方法：网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的； 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大； 线性规划是运筹学中应用最广泛的方法之一。自从1947年G.B.Dantzig发明了求解线性规划的单纯形方法后，线性规划已被广泛地应用于解决经济管理和工业生产中遇到的实际问题。曾经有人进行过调查，在世界500家最大的企业中，有85的企业使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用已为使用者节约了数以亿万计的资金。线性规划实质上是解决稀缺资源在有竞争的使用方向中如何进行最优分配的问题。这类最优分配问题大部分是从经营管理中引出的，例如：产品的最优组合，生产排序，最优投资方案，人力资源分配等。在这类问题中，一个共性的问题是一些稀缺或有限的资源必须被分配到一些指定的生产活动中去，而这些资源的使用会伴随着费用或效益的发生。线性规划可用于合理分配这些资源，并使付出的费用最小或获得的收益最大。在本章中我们将首先介绍什么是线性规划问题，线性规划问题的数学表达式，简单线性规划问题的图解法等线性规划的基本概念，然后介绍线性规划的基本理论和求解线性规划的单纯形方法。1.1 线性规划的基本概念本小节介绍什么是线性规划问题，如何将实际问题转化为线性规划模型，线性规划问题的标准形式以及求解简单线性规划问题的图解法。1.1.1 线性规划模型用线性规划方法解决实际问题的第一步是要将实际问题转化为线性规划模型。下面通过例子说明如何把具体问题转化为线性规划模型。 线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。 线性规划模型由三部分组成： 1一个反映决策目标的目标函数； 2一组线性等式、不等式约束方程； 3限制决策变量取值范围的非负约束 一、线性规划模型举例例1.1 生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元。椅子售价30元，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大。解：将一个实际问题转化为线性规划模型有以下几个步骤：1. 确定决策变量：决策变量是模型要决定的未知量，也是模型最重要的参数。对简单的模型，如上例，决策变量是显而易见的。但对较复杂的问题，决策变量的定义就不那么简单了。在本例中，家具厂要确定柜子和桌子的生产数量，因此可定义：x1 = 生产桌子的数量，x2 = 生产椅子的数量。2. 确定目标函数：目标函数决定线性规划问题的优化方向，是线性规划模型的重要组成部分。很明显，家具厂的目标是使销售收入最大，更具体一点，是使两种产品售价与产量的乘积的总和最大，因此目标函数可写为： max: z = 50x1 + 30x23. 确定约束方程：如果家具厂可以随意选择生产桌子和椅子的数量，他们的销售收入可以随意大。而这实际是不可能的，因为任何生产都会受到种种客观条件的限制。一个正确的模型应通过约束方程来反映这些客观条件。本例中的限制条件是每月可用的木工和油漆工的工时不能超过120和50小时。这两个条件可由以下方程表示： 4x1 + 3x2120 2x1 + x2504. 变量取值限制：一般情况下，决策变量只取正值（非负值）。因此，模型中应有变量的非负约束。在本例中，非负约束为x1 0，x2 0。将以上几部分结合起来就得到反映家具厂经营活动的完整的数学模型： max: z = 50x1 + 30x2 s.t. 4x1 + 3x2 120(1.1)2x1 + x2 50 x1, x2 0例1.2 营养配餐问题假定一个成年人每天需要从食物中获取3000大卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每公斤所含热量和营养成分以及市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。表1.1 各种食物的营养成分表序号食品名称热量(大卡)蛋白质(g)钙(mg)价格(元)1猪肉100050400142鸡蛋8006020063大米10002030034白菜200105002解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型如下：min: z = 14x1 + 6x2 + 3x3 + 2x4s.t. 1000x1 + 800x2 + 900x3 + 200x4 3000 50 x1 + 60 x2 + 20x3 + 10x4 55(1.2) 400 x1 + 200x2 + 300x3 + 500x4 800 xi 0 i =1, ., 4实用的配餐问题要比上例复杂的多，可包括几十甚至上百种原料，几十种营养配方。例如医院的营养配餐和养殖业中的配合饲料问题。二、线性规划的一般形式 由以上两个例子可知，线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的数学问题的统称。线性规划问题（或称线性规划模型）一般由三部分组成：1 由决策变量构成的反映决策者目标的线性目标函数；2 一组由决策变量的线性等式或不等式构成的约束方程；以及3 限制决策变量取值范围的非负约束。线性规划问题的一般形式可以写为：max: z = c1x1 + c2 x2 + + cnxns.t. a11x1 + a12 x2 + + a1nxn b1 a21x1 + a22 x2 + + a2nxn b2(1.3) am1x1 + am2 x2 + + amnxn bm x1, x2, xn 0 x1, ., xn为决策变量，表示第 n 种生产经营活动的规模， z = c1x1+cnxn 称为目标函数，反映生产活动的目标。cj (j = 1, 2, ., n) 为目标函数系数（又称价值系数）。表示与活动相关的费用或收益。 ai1x1+ai2x2+ainxn bi 为使用第 i种资源的资源限制约束；(1.3) 中的x1, x2, , xn为决策变量，一般可解释为反映n种生产经营活动的规模，例如，一个工厂生产的n种产品的产量。z = c1x1 + c2x2+ + cnxn被称为目标函数，记为z = f(x)，反映生产活动追求的目标。目标函数中的cj 称为目标函数系数，也称价值系数，代表伴随决策变量发生的单位费用和效益。模型(1.3)的每一个约束是一种资源约束，模型共有m中稀缺或受限制的资源，列向量b = (b1 ,.,bm )T 称为约束条件的右边项，它代表m种资源的可用量。aij 为技术系数或投入产出系数，代表第j种经营活动需要第i种资源的单位投入或产出量，这些系数构成一个矩阵。和右边项一起构成线性规划模型的约束条件。xj 0 限制决策变量的取值范围，是决策变量的非负约束，它表达了生产经营活动的规模不能为负值这样一个事实。三、线性规划隐含的假定 线性规划要求目标函数和约束方程必须是线性函数隐含了如下假定：1 比例性假定: 决策变量变化引起的目标函数的改变量和决策变量的改变量成比例每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。比例性假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。2 可加性假定: 每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。3 连续性假定: 线性规划问题中的决策变量应取连续值。4 确定性假定: 线性规划中的所有参数都是确定的参数。线性规划问题是确定性问题，不包含随机因素。上述隐含的假定条件是很强的，在现实生活中，完全满足这些条件的例子并不多见。因此在使用线性规划时必须注意你的问题在什么程度上满足这些假定。如果不满足，不满足的程度有多大。当不满足的程度较大时，应考虑使用其它方法，如：非线性规划、整数规划或不确定性分析方法。1.1.2 线性规划的标准型和矩阵表达式一、线性规划的标准型从以上例子可知线性规划形式的多样性。目标函数可求最大化也可求最小化；约束类型可以是，或=；变量限制既可非负，也可非正或无限制。为统一起见，人们为线性规划规定了标准形式。线性规划的标准型规定如下：max: z = c1x1 + c2 x2 + + cnxns.t. a11x1 + a12 x2 + + a1nxn = b1 a21x1 + a22 x2 + + a2nxn = b2(1.4) am1x1 + am2 x2 + + amnxn = bm x1, x2, xn 0线性规划的标准型要求所有的约束必须为等式约束，所有的变量为非负变量，对目标函数的类型原则上没有硬性规定，求最大化和最小化都可以。但是为了后面讨论方便，在本教材中规定目标函数最大化为标准型。二、如何将线性规划问题转化为标准型任何一个非标准的线性规划问题都可通过适当变化而转为标准形式。以下列出各种转化的方法：1.将最小化的目标函数转化最大化的目标函数：求一个函数的最小值等价于求该负函数的最大值，即：min f(x) = - max-f(x)。因此只需改变目标函数的符号就可以在最大和最小之间转换。2.把不等式约束转化为等式约束：可在约束中加入松弛变量或剩余变量。例如，把小于等于约束 x1+ x2 10 化为标准约束，需引入一松弛变量xs 0，标准约束即可写为 x1 + x2 + xs = 10 。将大于等于约束 x1 + x2 0化为标准形式，可引入一剩余变量xs 0，约束可改写为 x1 + x2 xs = 0。3.变量取值限制约束的转化：变量取值限制约束也可做相应的变化：变量的非正约束xi 0 可通过变量代换改为非负约束，即令 yi = -xi ，代入原模型后，新变量yi 即为非负变量。如果变量xi 是自由变量，则可做变量代换：xi = ui vi，ui 0,vi 0，代入原模型后，自由变量xi 被两个非负变量ui 和vi 取代。例1.3 将下列线性规划模型转变为标准形式：min: 3x1- x2 + 4x3s.t. x1 - 2x2 + 5x3 0 2x1 + x2 - 3x3 0 3x1 - 5x2 = 0 x1 0, x2 0解：令x2= -y，x3 = u - v，并引入松弛变量s1和s2，标准型为：max: -3x1 - y - 4u + 4vs.t. x1 + 2y + 5u - 5v - s1 = 0 2x1 - y - 3u + 3v + s2 = 0 3x1 + 5y = 0 x10, y0, u0, v0, s10, s20 三 线性规划的向量和矩阵表达形式 为理论讨论方便，线性规划还经常用向量和矩阵形式表示。例如，(1.4)可写为向量式：(1.5) xj 0j=1,2, ., n式中：pj = (a1j,.,amj )，b =(b1,.,bm)，还可写成更简洁的矩阵形式：max: cxs.t. Ax = b(1.6) x 0式中：c = (c1, ., cn)，x = (x1, ., xn)T，矩阵A = (aij)mn是约束系数矩阵，其他参数定义同前。1.1.3 线性规划的图解法 可行域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一 个可行解。 最优解：总是在可行域的边界上，一般由可行域的极点表示。 有效与无效(紧与松)约束：与最优解相关的约束为有效(紧)约束。 如果可行域为空集，线性规划 问题无可行解； 如果目标函数线可以无限制地在可行域内向改善的方向移动，线性规划问题无界； 线性规划问题可能存在无穷多个最优解。简单的线性规划问题可用图解法求解。图解法具有简单、直观、便于初学者了解线性规划基本原理和几何意义等优点。现用图解法求解例1.1。由于例1.1只有两个变量，我们可以在平面直角坐标系中描述该问题(见图1.1)。 图1.1 例1.1问题的图解 例1.1的每个不等式约束代表一个半平面（等式约束代表一直线）。例如第一个约束在图形上表示以直线 4x1 + 3x2 = 120 为界的左下方的半平面。该半平面内所有的点都满足第一个约束条件。两个非负条件分别表示以两个坐标轴为界的正半平面的交集，也即直角坐标系的第一象限。这四个半平面构成一个封闭的多边形。该多边形内的任一点以及边界上的点都能同时满足(1.2)的所有约束条件，因此都是(1.2)的可行解。线性规划所有可行解构成的集合称为线性规划的可行域。实际上，例1.1的线性规划模型有无数多可行解，哪一个解是最优解呢？这取决于目标函数的图形。目标函数 z = 50x1 + 30x2 在平面坐标系中的图形是一族以z为参数的平行线。任选一个z，便可得到一条直线，该线上所有的可行点都有相同的目标函数值，因此也被称为等值线。让目标函数线沿其法线方向平行移动，目标函数值将逐渐增加，当移到A点后，再向外移就会脱离可行区域，点A所代表的解即为最优解。本例的最优解值为x1 =15，x2 =20，即家具厂每周生产15个桌子和20个椅子时销售收入最大，销售收入z50(15)30(20)1350。总结一下，图解法可归纳为以下几个步骤：1.画直角坐标系。2.依次做每条约束线，标出可行域的方向并找出可行域。3.任取一目标函数值做一条目标函数线，然后根据目标的类型平移该线直到该线即将离开可行域为止。与目标函数线接触的最后的点即代表一个最优解。1.2 线性规划应用举例如何将一个复杂的实际问题转化为一个合理的线性规划模型既是一门科学，又是一门艺术。仅仅了解求解线性规划的数学原理是不够的，还需要在实践中学习将实际问题抽象为数学模型的技巧，不断总结和提高构造模型的技术，才能真正将线性规划技术应用到实际中。下面再举几个比较典型的线性规划问题。1.2.1 调和问题调和问题是研究将若干种不同的原料按一定的技术要求调和成不同的产品，例如化工、塑料、冶炼、石油加工都会遇到调和问题。典型的调和问题包含了具有不同技术特性的原料和产品并有相应的成本和价格与之相关。调和问题的目标是在满足产品需求和调和指标的前提下使调和成本最小或生产收益最大。例1.4 新星炼油厂生产三种牌号的汽油：70#,80#和85#汽油。每种汽油有不同的辛烷值和含硫量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用数量、质量指标和生产成本见表1.2，每种汽油的质量要求和销售价格见表1.3。问该炼油厂如何安排生产才能使其利润最大？假定在调和中辛烷值和含硫量指标都符合线性相加关系。表1.2 汽油组分的质量和成本数据序号i原料辛烷值含硫量%成本(元/吨)可用量(吨/日)1直馏汽油621.560020002催化汽油780.890010003重整汽油900.21400500表1.3 汽油产品的质量和价格数据序号j产品辛烷值含硫量销售价(元/吨)170# 汽油701900280# 汽油8011200385# 汽油850.61500这个问题要比前两个问题要复杂一些。首先决策变量的选择就不很直观。如果定义决策变量为各种汽油的产量，在写模型时会遇到不少麻烦。正确的方法是定义决策变量xij 代表第i 种原料调入第j 种成品汽油的数量。令pj 代表第j 种产品的销售价格，ci 为第i 种原料的生产成本，ei 和ej 分别为原料和产品的辛烷值，hi 和hj 为分别为原料和产品的含硫量，si 为原料每日的可用量，则模型可写为：(1.7)模型(1.7)目标函数的意义很清楚：调入j 种产品的i 种原料的产品售价与原料成本之差(pj ci )即为调和组分xij 对目标函数（利润）的贡献。前两个约束方程分别是辛烷值和含硫量的质量约束，每种产品都有两个质量约束。我们仅举70#汽油的辛烷值含量为例来说明这些约束的写法。该约束可写为：62x11 + 78x21 + 90x31 70(x11 + x21 + x31 )(1.8)不等式(1.8)左边是调入70汽油不同组分油辛烷值含量的总和，右端则为70汽油质量要求的最低标准，x11 + x21 + x31代表70汽油的实际产量，整理后可得：(62 - 70)x11 + (78 - 70)x21 + (90 - 70)x31 0(1.9)式(1.9)与(1.7)的形式一样。最后一组约束表示所用原料不能超过原料可用量的限制。将数据代入并化简后的模型如下：max: 300x11+600x12+900x13+300x22+600x23+500x31+200x32+100x33s.t. 8x11 + 8x21 + 20x31 0 18x12 + 2x22 + 10x32 0 23x13 + 7x23 + 5 x33 0 0.5x11 + 0.2x21 + 0.8x31 0 0.5x12 + 0.2x22 + 0.8x32 0 0.9x13 + 0.2x23 + 0.4x33 0 x11 + x12 + x13 2000 x21 + x22 + x23 1000 x31 + x32 + x33 500 xij 0 i =1, 2, 3；j=1, 2, 31.2.2 生产工艺优化问题许多企业的生产过程是一个连续的生产过程，各道工序之间有紧密和稳定的联系，这些生产工程是可以用数学模