运筹学全册精品完整课件.ppt

1、运筹学全册精品完整课件运筹学全册精品完整课件 2 运运 筹筹 学学 1*. 绪论绪论 ( 4848学时可只讲有学时可只讲有* *的章节的章节) ) 2*. 线性规划建模及单纯形法线性规划建模及单纯形法 3*. 线性规划问题的对偶与灵敏度分析线性规划问题的对偶与灵敏度分析 4*. 运输问题运输问题 5*.动态规划动态规划 8. 图与网络分析图与网络分析 6*. 排队论排队论 9. 存储论存储论 7.目标规划目标规划 10. 决策分析决策分析 3 第一章第一章 绪论绪论 4 运筹学概述运筹学概述 运筹学运筹学(Operations Research，OR) 直译为“运作研究”。直译为“运作研究”。

2、 运筹学是运用科学的方法（如运筹学是运用科学的方法（如 分析、试验、量化等）来决定如何分析、试验、量化等）来决定如何 最佳地运营和设计各种系统的一门最佳地运营和设计各种系统的一门 学科学科。 5 运筹学概述运筹学概述 运筹学能够对经济管理系统中运筹学能够对经济管理系统中 的人力、物力、财力等资源进行统的人力、物力、财力等资源进行统 筹安排，为决策者提供有依据的最筹安排，为决策者提供有依据的最 优方案，以实现最有效的管理。优方案，以实现最有效的管理。 通常以最优、最佳等作为决策通常以最优、最佳等作为决策 目标，避开最劣的方案。目标，避开最劣的方案。 6 运筹学的产生和发展运筹学的产生和发展 运筹

3、学思想的出现可以追溯到很早运筹学思想的出现可以追溯到很早“田田 忌齐王赛马”（对策论）、孙子兵法等都忌齐王赛马”（对策论）、孙子兵法等都 体现了优化的思想。体现了优化的思想。 “Operational Research”这一名词最早这一名词最早 出现在第二次世界大战期间出现在第二次世界大战期间 是美、英是美、英 等国家的作战研究小组为了解决作战中所等国家的作战研究小组为了解决作战中所 遇到的许多错综复杂的战略、战术问题而遇到的许多错综复杂的战略、战术问题而 提出的。提出的。 7 运筹学的产生和发展运筹学的产生和发展 战后这些研究成果被应用到生产、战后这些研究成果被应用到生产、 经济领域，并得到

4、迅速发展经济领域，并得到迅速发展有关理有关理 论和方法的研究、实践不断深入。论和方法的研究、实践不断深入。 1947年美国数学家年美国数学家 G.B.Dantzig提出提出 了求解线性规划的有效方法了求解线性规划的有效方法单纯形单纯形 法法。 8 运筹学的产生和发展运筹学的产生和发展 数学对运筹学的作用数学对运筹学的作用是有关理是有关理 论和方法的研究基础，是建立运筹论和方法的研究基础，是建立运筹 学模型的工具。学模型的工具。 计算机的发展，促进运筹学的进一计算机的发展，促进运筹学的进一 步发展步发展高速、可靠的计算是运高速、可靠的计算是运 筹学解决问题的基本保障。筹学解决问题的基本保障。 9

5、 运筹学在管理中的应用运筹学在管理中的应用 生产计划生产计划：生产作业的计划、日程表生产作业的计划、日程表 的编排、合理下料、配料问题、物料的编排、合理下料、配料问题、物料 管理等。管理等。 库存管理库存管理：多种物资库存量的管理，多种物资库存量的管理， 库存方式、库存量等。库存方式、库存量等。 运输问题运输问题：确定最小成本的运输线路、确定最小成本的运输线路、 物资的调拨、运输工具的调度以及建物资的调拨、运输工具的调度以及建 厂地址的选择等厂地址的选择等。 10 运筹学在管理中的应用运筹学在管理中的应用 人事管理人事管理：对人员的需求和使用的：对人员的需求和使用的 预测，确定人员编制、人员合

6、理分预测，确定人员编制、人员合理分 配，建立人才评价体系等。配，建立人才评价体系等。 市场营销市场营销：广告预算、媒介选择、：广告预算、媒介选择、 定价、产品开发与销售计划制定等。定价、产品开发与销售计划制定等。 11 运筹学在管理中的应用运筹学在管理中的应用 财务和会计财务和会计：包括预测、贷款、成：包括预测、贷款、成 本分析、定价、证券管理、现金管本分析、定价、证券管理、现金管 理等。理等。 其他其他：设备的维修、更新，科学项：设备的维修、更新，科学项 目、工程项目的选择与评价，工程目、工程项目的选择与评价，工程 优化设计、管理等。优化设计、管理等。 12 运筹学的分支运筹学的分支 线性规

7、划线性规划 非线性规划非线性规划 整数规划整数规划 动态规划动态规划 多目标规划多目标规划 随机规划随机规划 模糊规划等模糊规划等 13 运筹学的分支运筹学的分支 图与网络理论图与网络理论 存储论存储论 排队论排队论 决策论决策论 对策论对策论 排序与统筹排序与统筹 方法方法 可靠性理论可靠性理论 等等 14 运筹学的推广应用前景运筹学的推广应用前景 -运筹学在国内或国外的推广应用前运筹学在国内或国外的推广应用前 景是非常广阔的。景是非常广阔的。 -工商企业对运筹学应用的需求是很工商企业对运筹学应用的需求是很 大的。大的。 -在工商企业推广运筹学有大量的工在工商企业推广运筹学有大量的工 作要做

8、。作要做。 15 运筹学解决问题的过程运筹学解决问题的过程 1 1）提出问题：认清问题。）提出问题：认清问题。 2 2）寻求可行方案：建模、求解。）寻求可行方案：建模、求解。 3 3）确定评估目标及方案的标准或方）确定评估目标及方案的标准或方 法、途径。法、途径。 4 4）评估各个方案：解的检验、灵敏）评估各个方案：解的检验、灵敏 性分析等。性分析等。 16 运筹学解决问题的过程运筹学解决问题的过程 5）选择最优方案：决策。）选择最优方案：决策。 6）方案实施：回到实践中。）方案实施：回到实践中。 7）后评估：考察问题是否得到圆）后评估：考察问题是否得到圆 满解决。满解决。 17 如何学习运筹

9、学课程如何学习运筹学课程 学习运筹学要把重点放在分析学习运筹学要把重点放在分析 和理解有关的概念、思路上。在学和理解有关的概念、思路上。在学 习过程中，应该多向自己提问，例习过程中，应该多向自己提问，例 如：一个方法的实质是什么？为什如：一个方法的实质是什么？为什 么这样进行？怎么进行？等等。么这样进行？怎么进行？等等。 学习时要掌握三个重要环节。学习时要掌握三个重要环节。 18 如何学习运筹学课程如何学习运筹学课程 1) 认真阅读教材和参考资料，以指认真阅读教材和参考资料，以指 定教材为主，同时参考其他有关书定教材为主，同时参考其他有关书 籍。籍。一般每一本运筹学教材都有自己的特一般每一本运

10、筹学教材都有自己的特 点，但是基本原理、概念都是一致的。注点，但是基本原理、概念都是一致的。注 意主从，参考资料会帮助你开阔思路，使意主从，参考资料会帮助你开阔思路，使 学习深入。但是，把时间过多地放在参考学习深入。但是，把时间过多地放在参考 资料上，会导致思路分散，不利于学好。资料上，会导致思路分散，不利于学好。 19 如何学习运筹学课程如何学习运筹学课程 2) 要在理解了基本概念和理论的基要在理解了基本概念和理论的基 础上研究例题。础上研究例题。注意例题是为了帮助理注意例题是为了帮助理 解概念、理论的，作业练习的主要作用也是解概念、理论的，作业练习的主要作用也是 这样，它同时还有让你自己检

11、查自己学习的这样，它同时还有让你自己检查自己学习的 状况的作用。因此，做题要有信心，要独立状况的作用。因此，做题要有信心，要独立 完成，不要怕出错。因为，整个课程是一个完成，不要怕出错。因为，整个课程是一个 整体，各节内容有内在的联系，只要学到一整体，各节内容有内在的联系，只要学到一 定程度，知识融会贯通起来，你自己就能够定程度，知识融会贯通起来，你自己就能够 对所做题目的正确性作出判断。对所做题目的正确性作出判断。 20 如何学习运筹学课程如何学习运筹学课程 3) 要认真做好章节的学习小结。要认真做好章节的学习小结。每一每一 节或一章学完后，应该用精练的语言概述学节或一章学完后，应该用精练的

12、语言概述学 习、体会深刻的内容。这样，才能够从较高习、体会深刻的内容。这样，才能够从较高 的角度来看问题，更深刻地理解有关知识和的角度来看问题，更深刻地理解有关知识和 内容，这就称作“把书读薄”；将来，结合内容，这就称作“把书读薄”；将来，结合 相关文献在深入理解、认识的基础上，创新相关文献在深入理解、认识的基础上，创新 性地把相关知识从更深入、广泛的角度进行性地把相关知识从更深入、广泛的角度进行 分析、论述，则称为“把书读厚”。分析、论述，则称为“把书读厚”。 21 在建立数在建立数 学模型时，要学模型时，要 结合实际应用结合实际应用 中可能发生的中可能发生的 情况和问题情况和问题。 22

13、第第二二章章 线性规划概念、建线性规划概念、建 模与求解模与求解 本章内容重点本章内容重点 线性规划模型结构线性规划模型结构 线性规划的图解法与线性规划线性规划的图解法与线性规划 的解的解 线性规划解的基本概念与性质线性规划解的基本概念与性质 线性规划单纯形法线性规划单纯形法 线性规划建模线性规划建模 某工厂拥有某工厂拥有A A、B B、C C 三种类型的设备，三种类型的设备， 生产甲、乙两种产品。每件产品在生产中需生产甲、乙两种产品。每件产品在生产中需 要占用的设备机时数，每件产品可以获得的要占用的设备机时数，每件产品可以获得的 利润以及三设备可利用的时数如下表所示：利润以及三设备可利用的时

14、数如下表所示： 问题：工厂应如何安排生产可获得最大的总问题：工厂应如何安排生产可获得最大的总 利润？利润？ 案例案例 产品甲 产品乙 设备能力/h 设备 A 3 2 65 设备 B 2 1 4 0 设备 C 0 3 75 利润/（元 / 件） 1500 2500 25 第一节第一节 线性规划模型结构线性规划模型结构 一、线性规划问题的提出一、线性规划问题的提出 在实践中，根据实际问题的要求，常常在实践中，根据实际问题的要求，常常 可以建立线性规划问题数学模型。可以建立线性规划问题数学模型。 例例2-1 我们首先分析开篇案例提到的问题。我们首先分析开篇案例提到的问题。 解：设变量解：设变量 xi

15、 为第为第 i 种种（甲甲、乙乙）产品的产品的 生产件数生产件数（i1，2）。根据题意根据题意，我们知道我们知道 两种产品的生产受到设备能力两种产品的生产受到设备能力（机时数机时数）的的 限制限制。对设备对设备A：两种产品生产所占用的机时：两种产品生产所占用的机时 数不能超过数不能超过65，于是我们可以得到不等式：于是我们可以得到不等式： 3 x1 + 2 x2 65； 26 对设备对设备B B：两种产品生产所占用的机时数两种产品生产所占用的机时数 不能超过不能超过4040，于是我们可以得到不等，于是我们可以得到不等 式：式：2 x1 + x2 40； 对设备对设备C C ：两种产品生产所占用

16、的机时：两种产品生产所占用的机时 数不能超过数不能超过7575，于是我们可以得到不于是我们可以得到不 等式：等式：3x2 75 ；另外；另外，产品数不可能产品数不可能 为负为负，即即 x1, x2 0。 27 同时，我们有一个追求目标，即获同时，我们有一个追求目标，即获 取最大利润。于是可写出目标函数取最大利润。于是可写出目标函数z z为为 相应的生产计划可以获得的总利润：相应的生产计划可以获得的总利润： z = 1500 x1 + 2500 x2 综合上述讨论综合上述讨论，在加工时间以及在加工时间以及 利润与产品产量成线性关系的假设下利润与产品产量成线性关系的假设下， 把目标函数和约束条件放

17、在一起把目标函数和约束条件放在一起，可可 以建立如下的线性规划模型：以建立如下的线性规划模型： 28 模型模型 目标函数目标函数 Max z =1500 x1+2500 x2 约束条件约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 29 这是一个典型的利润最大化的生这是一个典型的利润最大化的生 产计划问题产计划问题。其中其中，“Max是英文单是英文单 词词“Maximize的缩写的缩写，含义为含义为“最最 大化大化”；“s.t.是是“subject to的缩写的缩写， 表示表示“满足于满足于。因此因此，上述模型上述模型 的含义是：在给定条件

18、限制下的含义是：在给定条件限制下，求使求使 目标函数目标函数 z 达到最大的达到最大的x1, x2 的取值的取值。 30 约束条件： a11x1+a12x2+a1nxn( =, )b1 a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 0 2.1.2线性规划的一般模型结构：线性规划的一般模型结构： 一般形式一般形式 目标函数：目标函数： Max(Min) z = c1x1 + c2x2 + + cnxn 向量形式与矩阵形式向量形式与矩阵形式 设决策变量设决策变量 x = (x1, x2, , xn)T

19、， n mnmm n n mn ppp aaa aaa aaa A bbbbcccc ,., ),.,(,),.,( 21 21 22221 11211 T 21 T 21 向量形式与矩阵形式模型向量形式与矩阵形式模型 0,),(s.t. Max 0,),(s.t. Max T 1 1 i ii n i ii n i ii xbAx xcz xbpx xcz 矩阵形式 向量形式 33 第二节第二节 线性规划的图解法与线性规划线性规划的图解法与线性规划 的解的解 一一、 两个决策变量线性规划问题两个决策变量线性规划问题 的作图求解的作图求解 步骤：步骤： (1) 建立直角坐标系；建立直角坐标系；

20、 (2) 绘制可行域；绘制可行域； (3) 绘制目标函数等值线绘制目标函数等值线，并移动求并移动求 解解。 34 绘制可行域绘制可行域 对每个约束对每个约束（包括非负约束包括非负约束）条件条件， 作出其约束半平面作出其约束半平面（不等式不等式）或约束直或约束直 线线（等式等式）。 各半平面与直线交出来的区域若存各半平面与直线交出来的区域若存 在在，其中的点为此线性规划的可行解其中的点为此线性规划的可行解。 称这个区域为可行集或可行域称这个区域为可行集或可行域。然后进然后进 行下步；若交为空行下步；若交为空，那么该线性规划问那么该线性规划问 题无可行解题无可行解。 35 绘制目标函数等值线，并移

21、动求解绘制目标函数等值线，并移动求解 目标函数随着取值不同目标函数随着取值不同，为一族为一族 相互平行的直线相互平行的直线。 首先首先，任意给定目标函数一个值任意给定目标函数一个值， 可作出一条目标函数的等值线可作出一条目标函数的等值线（直直 线线）； 然后然后，确定该直线平移使函数值确定该直线平移使函数值 增加的方向；增加的方向； 最后最后，依照目标的要求平移此直依照目标的要求平移此直 线线。 36 结果结果 若目标函数等值线能够移动到若目标函数等值线能够移动到 既与可行域有交点又达到最优的位既与可行域有交点又达到最优的位 置置，此目标函数等值线与可行域的此目标函数等值线与可行域的 交点即最

22、优解交点即最优解（一个或多个一个或多个），此此 目标函数的值即最优值目标函数的值即最优值。 否则，目标函数等值线与可行否则，目标函数等值线与可行 域将交于无穷远处，此时称无有限域将交于无穷远处，此时称无有限 最优解。最优解。 例例2-2 考虑例考虑例2-1 某工厂拥有某工厂拥有A A、B B、C C 三种类型的设备三种类型的设备， 生产甲生产甲、乙两种产品乙两种产品。每件产品在生产中每件产品在生产中 需要占用的设备机时数需要占用的设备机时数，每件产品可以获每件产品可以获 得的利润以及三种设备可利用的时数如下得的利润以及三种设备可利用的时数如下 表所示表所示。问题问题：工厂应如何安排生产可获工厂

23、应如何安排生产可获 得最大的总利润得最大的总利润？ 产品甲 产品乙 设备能力/h 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润/（元/件） 1500 2500 38 用图解法求解用图解法求解 解：设变量解：设变量x xi i为第为第i种种（甲甲、乙乙）产品产品 的生产件数的生产件数（i1，2）。根据前面分根据前面分 析析，可以建立如下的线性规划模型：可以建立如下的线性规划模型： Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 65 (A) 2x1+ x2 40 (B) 3x2 75 (C) x1 , x2 0 (D, E) 39 按照图

24、解法的步骤按照图解法的步骤 （1）以决策变量以决策变量x1 ，x2 为坐标向量作为坐标向量作 平面直角坐标系；平面直角坐标系； 40 （2）对每个约束对每个约束（包括非负约包括非负约 束束）条件作出直线条件作出直线（A、B、C、 D、E），并通过判断确定不等并通过判断确定不等 式所决定的半平面式所决定的半平面。 各约束半平面交出来的区域各约束半平面交出来的区域 即可行集或可行域即可行集或可行域，如下图阴影如下图阴影 所示所示。 41 第第2步图示步图示(1) 分别作出各约束半平面分别作出各约束半平面 x2 0 x1 0 3x2 75 3x1+ 2x2 65 2x1+ x2 40 42 第第2步

25、图示步图示(2) 各约束半平面的交可行域各约束半平面的交可行域 43 （3）任意给定目标函数一个值任意给定目标函数一个值（例如例如 37500）作一条目标函数的等值线作一条目标函数的等值线，并并 确定该等值线平移后值增加的方向确定该等值线平移后值增加的方向（向向 上移动函数值增大上移动函数值增大），平移此目标函数平移此目标函数 的等值线的等值线，使其达到既与可行域有交点使其达到既与可行域有交点 又不可能使值再增加的位置又不可能使值再增加的位置。得到得到 最优解最优解 x* = (5,25)T 最优值 最优值 z* = 70000 44 第第3步图示步图示(1) 作目标函数等值线作目标函数等值线

26、 函数值增大 45 第第3步图示步图示(2) 求出最优解求出最优解 1 46 结论结论 这个线性规划的这个线性规划的 最优解最优解 x1 = 5、x2 = 25 最优值最优值 z = 70000 即最优方案为：即最优方案为： 生产甲产品生产甲产品 5 件、乙产品件、乙产品 25 件件 可获得最大利润为可获得最大利润为70000元。元。 47 二、二、 线性规划解的有关情况线性规划解的有关情况 线性规划的解有如下线性规划的解有如下3 3类类4 4种情况：种情况： (1)(1)存在有限最优解：存在有限最优解： 唯一最优解唯一最优解 无穷多个最优解无穷多个最优解 (2)(2)无有限最优解（无界解）无

27、有限最优解（无界解） (3)(3)无可行解（可行域空无可行解（可行域空） 48 无穷多个最优解情况无穷多个最优解情况 例例2-3 在例在例2-2的线性规划模型的线性规划模型 中中，如果目标函数变为：如果目标函数变为： Max z = 1500 x1 + 1000 x2 那么那么，最优情况下目标函数的最优情况下目标函数的 等值线与直线等值线与直线（A）重合重合。这时这时，最最 优解有无穷多个：从点优解有无穷多个：从点 (5,25)T到点到点 (15,10)T 线段上的所有点线段上的所有点，最优值为最优值为 32500。如下图所示：如下图所示： 49 无穷多个最优解图示无穷多个最优解图示 无穷多解

28、的情况 (15, 10)T 50 无有限最优解的情况无有限最优解的情况 例例2-4 在例在例2-2的线性规划模型中的线性规划模型中,如果如果 约束条件约束条件（A）、（C）变为：变为： 并且去掉并且去掉（D、E）的非负限制的非负限制。那么那么， 可行域成为一个上无界的区域可行域成为一个上无界的区域。这时这时， 没有有限最优解没有有限最优解，如下图所示：如下图所示： 3 x1 + 2 x2 65 (A） 3 x2 75 (C） 51 无有限最优解图示无有限最优解图示 无有限解的情况 52 无可行解的情况无可行解的情况 例例2-5 在例在例2-2的线性规划模型中，的线性规划模型中， 如果增加约束条

29、件（如果增加约束条件（F）为：）为： 那么，可行域成为空的区域。这时，那么，可行域成为空的区域。这时， 没有可行解，显然线性规划问题无没有可行解，显然线性规划问题无 解。如下图所示：解。如下图所示： x1 + x2 40 （F ） 53 无可行解图示无可行解图示 54 三、三、 线性规划可行域与解的特征线性规划可行域与解的特征 (1) 通过图解法引出的几个基本概念通过图解法引出的几个基本概念 直线、平面直线、平面 超平面和法向量超平面和法向量 半平面半平面 半空间半空间 多边形多边形 多面体多面体 凸集、凸组合凸集、凸组合 顶点顶点 极点极点 55 (2)线性规划解的特征线性规划解的特征 可以

30、证明，线性规划的可行域以及可以证明，线性规划的可行域以及 最优解有以下性质：最优解有以下性质： 若线性规划的可行域非空，则可行域若线性规划的可行域非空，则可行域 必定为一凸集；必定为一凸集； 若线性规划的可行域非空，则至多有若线性规划的可行域非空，则至多有 有限个极点；有限个极点； 若线性规划有最优解，则至少有一个若线性规划有最优解，则至少有一个 极点是最优解。极点是最优解。 56 线性规划解性质的启示线性规划解性质的启示 线性规划最优解的上述性质，为线性规划最优解的上述性质，为 人们求解多变量线性规划问题开辟了人们求解多变量线性规划问题开辟了 一条道路：从一条道路：从在可行域内无限个可行在可

31、行域内无限个可行 解中搜索解中搜索的问题转为的问题转为在其可行域的有在其可行域的有 限个极点上搜索限个极点上搜索的问题。的问题。 57 第三节第三节 线性规划解的概念与性质线性规划解的概念与性质 本节讨论本节讨论 线性规划的线性规划的常用形式常用形式以及以及 通过两个变量推广过来的有关通过两个变量推广过来的有关 极点极点的概念的概念 58 a11x1+a12x2+ +a1n xn b1 a21x1+a22x2+ +a2n xn b2 . . . am1x1+am2x2 +amnxn bm x1 ，x2 ， ，xn 0 一、线性规划问题的规范形式和标准形式一、线性规划问题的规范形式和标准形式 (

32、1) 线性规划规范形式线性规划规范形式 目标函数：目标函数： Max z = c1x1 + c2x2 + cnxn 约束条件：约束条件： 59 线性规划规范形式的特点线性规划规范形式的特点 规范形式有如下四个特点：规范形式有如下四个特点： 目标最大化目标最大化 约束为小于等于的不等式约束为小于等于的不等式 决策变量均非负决策变量均非负 右端项非负右端项非负。 0 s.t. Max T x bAx xcz 60 Max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . .

33、am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0 (2) 线性规划的标准形式线性规划的标准形式 目标函数：目标函数： 约束条件：约束条件： 61 线性规划标准形式的特点线性规划标准形式的特点 标准形式有如下四个特点：标准形式有如下四个特点： 目标最大化目标最大化 约束为等式约束为等式 决策变量均非负决策变量均非负 右端项非负右端项非负。 对于各种非标准形式的线性规划对于各种非标准形式的线性规划 问题，总可以通过以下变换，将其转问题，总可以通过以下变换，将其转 化为标准形式化为标准形式: : 62 设目标函数为 Min f = c1x1 + c2x2 + +

34、 cnxn 则可以令zf ，该极小化问题与下 面的极大化问题有相同的最优解，即 Max z = c1x1 c2x2 cnxn 但必须注意，尽管以上两个问题的 最优解相同，但他们最优解的目标函 数值却相差一个符号，即 Min f Max z 线性规划标准形式的转化：线性规划标准形式的转化： 极小化目标函数的问题：极小化目标函数的问题： 63 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于 约束右边与左边之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1

35、x1+ai2 x2+ +ain xn+s = bi 约束条件不是等式（约束条件不是等式（ ）的问题）的问题 64 当约束条件为当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时时，类似地令类似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 显然显然，s 也具有非负约束也具有非负约束，即即s0， 这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi 约束条件不是等式（约束条件不是等式（）的问题）的问题 65 为了使约束由不等式成为等式而为了使约束由不等式成为等式而 引进的变量引进的变量 s 称为“松弛变量”。

36、称为“松弛变量”。 如果原问题中有若干个非等式约如果原问题中有若干个非等式约 束，则将其转化为标准形式时，必须束，则将其转化为标准形式时，必须 对各个约束引进不同的松弛变量。对各个约束引进不同的松弛变量。 66 Min f = 3.6 x1 5.2 x2 + 1.8 x3 s.t. 2.3 x1 + 5.2 x2 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2+ x3 = 38 x1 , x2 , x3 0 例例2-6 将以下线性规划问题转化为将以下线性规划问题转化为 标准形式标准形式 解：首先,将目标函数转换成极大化： 令 z= f = 3.6x1+5.2x2

37、1.8x3 67 x4，x5 0。 于是，我们可以得到以下标准形式的 线性规划问题： Max z = - 3.6 x1 + 5.2 x2 1.8 x3 s.t. 2.3x1+5.2x26.1x3+x4 = 15.7 4.1x1 +3.3x3 x5= 8.9 x1+ x2+ x3 = 38 x1 ,x2 ,x3 ,x4 ,x5 0 其次考虑约束，有其次考虑约束，有2 2个不等式约束，个不等式约束， 引进松弛变量引进松弛变量 68 当某一个变量xj没有非负约束时， 可以令 xj = xjxj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符 号限制的变量，当然xj的符号取决于xj 和x

38、j”的大小。 变量无符号限制的问题变量无符号限制的问题 在标准形式中，必须每一个变量均在标准形式中，必须每一个变量均 有非负约束。有非负约束。 69 当某一个右端项系数为负时，如 果 bi m， 秩秩(A) = m，b Rm 。 约束等式实质上是一个由约束等式实质上是一个由m个方程个方程n个变个变 量构成的方程组量构成的方程组，有无穷多组解有无穷多组解。记：记： x = (x1，x2，xn)T 75 如果令其中如果令其中n-m个变量为零，当其个变量为零，当其 他他 m个变量在线性方程组中有唯一解时，个变量在线性方程组中有唯一解时， 则这则这 n个变量的值构成此方程组的一个个变量的值构成此方程组

39、的一个 解。若进一步有这解。若进一步有这 n 个变量的值都非负个变量的值都非负 时，这个解就是线性规划可行域的一个时，这个解就是线性规划可行域的一个 极点。极点。 根据以上分析根据以上分析，我们建立以下概念我们建立以下概念 基、基变量、非基变量基、基变量、非基变量 基本解、基本可行解（极点）基本解、基本可行解（极点） 可行基、最优基可行基、最优基 (1) 线性规划的基：线性规划的基： 对于线性规划的约束条件对于线性规划的约束条件 Ax=b， x0 设设B是是A矩阵中的一个非奇异矩阵中的一个非奇异 （可逆可逆）的的mm子矩阵子矩阵，则称则称B 为线性规划的一个基为线性规划的一个基。 A=( p1

40、 ，p2 ，pn ) ，其中，其中 pj=( a1j ，a2j ，amj )T Rm ， 任取任取 A 中的中的 m 个线性无关列向量个线性无关列向量 构成矩阵构成矩阵 那么那么B为线性规划的一个基。为线性规划的一个基。 称对应于基称对应于基B的变量的变量 为为基变量基变量；其余变量称为；其余变量称为非基变量非基变量。 77 m jjjj RPpppB im ),( 21 m jjj xxx, 21 矩阵描述矩阵描述 设设B是线性规划的一个基是线性规划的一个基，则则A可以可以 表示为表示为 A= B , N x 也可相应地分成也可相应地分成 xB 和和 xN 其中其中xB为为m维列向量维列向量

41、，它的各分量它的各分量 称为基变量称为基变量，与基与基B的列向量对应；的列向量对应；xN 为为n-m维列向量维列向量，它的各分量称为非基它的各分量称为非基 变量变量，与非基矩阵与非基矩阵N的列向量对应的列向量对应。 (2) 线性规划问题的基本可行解：线性规划问题的基本可行解： 对应于基对应于基B，约束等式约束等式 Ax = b 可表示为可表示为 xB B,N = b 或或 BxB + NxN = b xN 则基变量则基变量 xB = B-1b - B-1NxN 当取当取 xN = 0，这时有这时有xB = B-1b 。称称 这类特别的解为这类特别的解为基本解基本解。 80 进一步，若得到的基变

42、量进一步，若得到的基变量 的值均非负，即的值均非负，即 B-1 b 0 ， 则称为则称为基本可行解基本可行解，同时称这，同时称这 个基个基 B 为为可行基可行基。 例例2-8 把例把例2-1的线性规划模型标的线性规划模型标 准化，引入松驰变量准化，引入松驰变量 x3 ，x4 ，x5 0，得，得 到到 Max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2+x3 = 65 (A) 2x1+ x2 +x4 = 40 (B) 3x2 +x5= 75 (C) x1 , x2 , x3 , x4 , x5 0 用用(D)、 (E)、 (F)、(G)、(H) 分别表示分别表示 x1=

43、0、x2=0、x3=0、x4=0、x5=0 这里一共有这里一共有8 8个约束条件，其中个约束条件，其中 3 3 个等式约束。对此，任意固定两个变量个等式约束。对此，任意固定两个变量 为零，通过解等式构成的方程组（相当为零，通过解等式构成的方程组（相当 于求解由其中于求解由其中 5 5 个方程构成的方程组）个方程构成的方程组） ，可解得一个点。，可解得一个点。 由于当由于当 x2 = x5 = 0 时，即由时，即由(A)、 (B)、(C)、(E)、 (H)构成的方程组无解构成的方程组无解 。故总。故总共可求得共可求得9 9个点。个点。 83 问题图示中的约束直线交点与此对应问题图示中的约束直线交点与此对应 84 约束条件约束条件(A)、(B)、(C)、(F)、(G) 的解对应于的解对应于直线直线A、B的交点的交点，即：即： x(1) = (15,10,0,0,45)T 约束条件约束条件(A)、(B)、(C)、(F)、(H) 的解对应于的解对应于直线直线A、C的交点的交点，即：即： x(2) = (5,25,0,5,0)T 约束条件约束条件(A)、(B)、(C)、(D)、(F) 的解对应于的解对应于直线直线A、D的交点的交点，即：即： x(3) = (0,32.5,0,7.5,-22.5)T 85 约束条件约束条件(A)、(B)、(C)、(E)、(F)的的 解对应于解对应于直线直线