大学精品课件：运筹学（一）.ppt

1、 运运 筹筹 学学 （O.R.)郑州大学管理工程系：冯小玲郑州大学管理工程系：冯小玲 主要授课内容：主要授课内容：o 绪论绪论o 线性规划及单纯形法线性规划及单纯形法o 线性规划的对偶理论与灵敏度分析线性规划的对偶理论与灵敏度分析o 运输问题运输问题o 目标规划目标规划o 整数规划整数规划o 动态规划动态规划o 图与网络分析图与网络分析绪论绪论一、运筹学的起源与发展一、运筹学的起源与发展二、运筹学研究的基本特点与基本方法二、运筹学研究的基本特点与基本方法三、运筹学研究的主要分支三、运筹学研究的主要分支四、运筹学在企业管理中的应用四、运筹学在企业管理中的应用一、运筹学的起源与发展一、运筹学的起源

2、与发展1.什么是运筹学什么是运筹学英文：英文：Operational Research(英国英国)Operations Research(美国美国)（直译为（直译为“作业研究作业研究”、“运用研究运用研究”）中文：运筹学（来源于中文：运筹学（来源于“夫夫运筹运筹帷幄之中，决胜帷幄之中，决胜于千里之外于千里之外”）运筹学是一种科学决策的方法；运筹学是一种科学决策的方法；运筹学是运筹学是用数学方法用数学方法研究经济、民政和国防研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使物力、财力等资源，使实际系统实际系统有效运行的技术

3、有效运行的技术科学，它可以用来预测发展趋势，制定行动规划科学，它可以用来预测发展趋势，制定行动规划或优化可行方案（或优化可行方案（中国大百科全书中国大百科全书）；）；运筹学是应用运筹学是应用分析、试验、量化的方法分析、试验、量化的方法，对，对经济管理系统经济管理系统中人、财、物等资源进行统筹安排，中人、财、物等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效为决策者提供有依据的最优方案，以实现最有效的管理（的管理（中国企业管理百科全书中国企业管理百科全书）。2.运筹学的发展历史运筹学的发展历史（1）二战以前：萌芽）二战以前：萌芽 齐王齐王-田忌赛马、丁渭修皇宫等。田忌赛马、丁渭修皇

4、宫等。（2）二战期间：产生）二战期间：产生 1938年，英国某雷达站负责人罗伊提出整个防空作战系统运行年，英国某雷达站负责人罗伊提出整个防空作战系统运行的研究，并用到了的研究，并用到了operational research 来描述此研究。来描述此研究。1940年，英国军事部门成立了第一个由一些数学家、物理学家年，英国军事部门成立了第一个由一些数学家、物理学家和工程专家等组成的和工程专家等组成的OR小组，负责研究一些武器有效使用的问题。小组，负责研究一些武器有效使用的问题。1942年，美国也成立了由年，美国也成立了由17人组成的人组成的OR小组，研究反潜艇策小组，研究反潜艇策略等问题。略等问题

5、。（3）二战后：推广与发展）二战后：推广与发展 战时从事运筹学研究的许多专家转到了经济部门、民用企业、大战时从事运筹学研究的许多专家转到了经济部门、民用企业、大学或研究所，继续从事决策的数量方法的研究，运筹学作为一门学学或研究所，继续从事决策的数量方法的研究，运筹学作为一门学科逐步形成并得以迅速发展。运筹学发展到今天，已成为分支学科科逐步形成并得以迅速发展。运筹学发展到今天，已成为分支学科众多的一个繁荣昌盛的大家族。随着电子计算机的发展和使用，运众多的一个繁荣昌盛的大家族。随着电子计算机的发展和使用，运筹学处理复杂性问题的能力大大加强，成为解决实际问题的有力工筹学处理复杂性问题的能力大大加强，

6、成为解决实际问题的有力工具，广泛地应用于企业管理、交通运输、公共服务等领域。具，广泛地应用于企业管理、交通运输、公共服务等领域。二、运筹学研究的基本特征与基本方法二、运筹学研究的基本特征与基本方法 1.运筹学研究的基本特征运筹学研究的基本特征（1）系统性特征）系统性特征 运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。统达到最优状态。（2）综合性特征）综合性特征 运筹学是一门交叉学

7、科，具有综合性，它的起源就是由不同学术背景运筹学是一门交叉学科，具有综合性，它的起源就是由不同学术背景的专家共同解决实际问题。它充分利用了数学、计算机科学、统计学及其的专家共同解决实际问题。它充分利用了数学、计算机科学、统计学及其它科学的成就，这决定了运筹学内容的跨学科性和综合性。它科学的成就，这决定了运筹学内容的跨学科性和综合性。（3）模型方法的应用）模型方法的应用 运筹学研究建立在科学的研究方法之上，它研究的第一步就是根据实运筹学研究建立在科学的研究方法之上，它研究的第一步就是根据实际问题和管理要求建立必要的数学或模拟模型。然后对模型进行求解、分际问题和管理要求建立必要的数学或模拟模型。然

8、后对模型进行求解、分析和检验。因此学习运筹学要掌握的重要技巧就是对运筹学模型的表达、析和检验。因此学习运筹学要掌握的重要技巧就是对运筹学模型的表达、运算和分析的能力。运算和分析的能力。2.运筹学研究的基本方法运筹学研究的基本方法 （1 1）分析和表述问题；）分析和表述问题；（2 2）建立模型；）建立模型；（3 3）求解模型；）求解模型；（4 4）测试模型；）测试模型；（5 5）对模型进行必要的修正；）对模型进行必要的修正；（6 6）建立对解的有效控制；）建立对解的有效控制；（7 7）方案的实施。）方案的实施。三、运筹学研究的主要分支三、运筹学研究的主要分支o 线性规划（线性规划（linear

9、programming)o 非线性规划非线性规划o 动态规划动态规划o 图论与网络分析图论与网络分析o 存贮论存贮论o 排队论排队论o 对策论对策论o 决策论决策论四、运筹学在企业管理中的应用四、运筹学在企业管理中的应用o生产计划生产计划。使用运筹学方法从总体上确定适应需求的生产、储存和劳。使用运筹学方法从总体上确定适应需求的生产、储存和劳动力安排等计划，动力安排等计划，以谋求最大的利润或最小的成本。以谋求最大的利润或最小的成本。o库存管理库存管理。存储论应用于多种物资库存量的管理，确定某些设备的合。存储论应用于多种物资库存量的管理，确定某些设备的合理的能力或容量以及适当的库存方式和库存量理的

10、能力或容量以及适当的库存方式和库存量o运输问题运输问题。用运筹学中运输问题的方法，可以确定最小成本的运输线。用运筹学中运输问题的方法，可以确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择。路、物资的调拨、运输工具的调度以及建厂地址的选择。o人事管理人事管理。可以用运筹学方法对人员的需求和获得情况进行预测；确。可以用运筹学方法对人员的需求和获得情况进行预测；确定合适需要的人员编制；用指派问题对人员合理分配；用层次分析法定合适需要的人员编制；用指派问题对人员合理分配；用层次分析法等方法来确定一个人才评价体系等。等方法来确定一个人才评价体系等。o市场营销市场营销。可把运筹学方法用

11、于广告预算和媒体的选择、竞争性的定。可把运筹学方法用于广告预算和媒体的选择、竞争性的定价、新产品的开发、销售计划的制定等方面。价、新产品的开发、销售计划的制定等方面。o财务和会计财务和会计。可以用运筹学方法进行预测、贷款、成本分析、定价、。可以用运筹学方法进行预测、贷款、成本分析、定价、证券管理、现金管理。证券管理、现金管理。第一章第一章线性规划与单纯形法线性规划与单纯形法主要内容：主要内容：第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型第二节第二节 图解法图解法第三节第三节 单纯形法原理单纯形法原理第四节第四节 单纯形法计算步骤单纯形法计算步骤第五节第五节 单纯形法的进一步讨

12、论单纯形法的进一步讨论第六节第六节 线性规划在经济管理中的应用例子线性规划在经济管理中的应用例子第一节第一节线性规划问题及其数学模型线性规划问题及其数学模型一、线性规划问题举例一、线性规划问题举例 例例1 1（生产计划问题）（生产计划问题）：美佳公司计划制：美佳公司计划制造造，两种家电产品。已知各制造一两种家电产品。已知各制造一件时分别占用的设备件时分别占用的设备A,BA,B的台时、调试时的台时、调试时间、调试工序及每天可用于这两种家电间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如的能力、各售出一件的获利情况，如表表1-11-1所示。问该公司应制造两种家电各多所示。问该公司

13、应制造两种家电各多少件，使获取的利润为最大。少件，使获取的利润为最大。表表1-1项目项目每天可用能力每天可用能力设备设备A（h)0515设备设备B（h)6224调试工序（调试工序（h)115利润（元）利润（元）21 设设x x1 1,x,x2 2 分别代表分别代表，两种家电两种家电的生产量，的生产量，此问题的数学模型为：此问题的数学模型为：目标函数目标函数 约束条件约束条件212maxxxz0,52426155.2121212xxxxxxxst 例例2 2（仓库租借问题）（仓库租借问题）：某公司在下一年度的：某公司在下一年度的1 14 4月的月的4 4个月内拟租用仓库堆放物资。已知各个月内拟租

14、用仓库堆放物资。已知各月份所需仓库面积列于月份所需仓库面积列于表表1-21-2.仓库租借费用随仓库租借费用随合同期而定，期限越长，折扣越大，具体数字合同期而定，期限越长，折扣越大，具体数字见表见表1-3.1-3.租借仓库的合同每月月初都可办理，租借仓库的合同每月月初都可办理，每份合同具体规定租用面积和期限。因此该厂每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。可根据需要，在任何一个月初办理租借合同。每次办理时可签订一份合同，也可签若干份租每次办理时可签订一份合同，也可签若干份租用面积和租用期限不同的合同，试确定该公司用面积和租用期限不同的合同，试确定该公司签订

15、租借合同的最优策略，目的使所付租借费签订租借合同的最优策略，目的使所付租借费最小。最小。合同租借期限合同租借期限1个月个月2个月个月3个月个月4个月个月 租借费租借费（元（元/100m2)2800 450060007300表表1-2月份月份1234所需仓库面积所需仓库面积（100m2)15102012表表1-3 设设x xijij公司在第公司在第i i（i=1,2,3,4)i=1,2,3,4)个月初签订租借期为个月初签订租借期为j j（j=1,2,3,4)j=1,2,3,4)个月的合同的仓库面积，此问题的数学个月的合同的仓库面积，此问题的数学模型为：模型为：142313322212413121

16、117300)(6000 )(4500)(2800minxxxxxxxxxxz)4,1;4,1(015 201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij二、线性规划问题的数学模型二、线性规划问题的数学模型 线性规划问题数学模型的三个组成要素线性规划问题数学模型的三个组成要素1.决策变量决策变量:是决策者为实现规划目标采取的方是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量案、措施，是问题中要确定的未知量。2.目标函数目标函数:指问题要达到的目的要求，表示为指问题要达到的目的要求，表

17、示为决策变量的函数。决策变量的函数。3.约束条件约束条件:指决策变量取值时受到的各种可用指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等资源的限制，表示为含决策变量的等式或不等式。式。1 12 211 112 21121 122 2221 12 212max(min)()(,)(,).(,),0:;:;:;:;:n nn nn nmmmn nmnjjijf xcxc xc xa xa xa xba xa xa xbsta xa xa xbx xxnmn mcba 变量个数约束行数线性规划问题的规模价值系数右端项技术系数nnxcxcxcz2211min)max(或n:变量个

18、数变量个数m：约束个数：约束个数cj:价值系数价值系数bi:资源拥有量资源拥有量aij:工艺系数工艺系数线性规划问题数学模型的线性规划问题数学模型的一般表示形式一般表示形式：该模型的该模型的简化表示简化表示：njjjxcz1min)max(或),1(0),1(.1njxmibxastjnjijij），或该模型的该模型的向量表示向量表示：);,(.min)max(212121211mmjjjjnnnjjjbbbaaaxxxcccxtszbPXC0XbPCX；其中，），（或或该模型的该模型的矩阵表示矩阵表示：.min)max(212222111211mnmmnnaaaaaaaaaAXAXtsz其中

19、，），（或或0bCX三、线性规划问题的标准形式三、线性规划问题的标准形式 为了使线性规划问题的解法标准，就要把为了使线性规划问题的解法标准，就要把一般形式化为标准形式。标准形式如下：一般形式化为标准形式。标准形式如下：njjjxcz1max),1(0),1(.1njxmibxastjnjijij标准形式特点：标准形式特点：4.决策变量取值非负。决策变量取值非负。1.目标函数为求极大值；目标函数为求极大值；2.约束条件全为等式；约束条件全为等式；3.约束条件右端常数项约束条件右端常数项bi全为非负值；全为非负值；把非标准形式转化为标准形式的方法：把非标准形式转化为标准形式的方法：（1 1）目标函

20、数为）目标函数为minmin型，即型，即 等价于求等价于求 ，令，令 ，即化为：，即化为：；（2 2）约束条件的右端项）约束条件的右端项b bi i 为负值，则该行左右两端为负值，则该行左右两端 同同时乘以（时乘以（-1-1），同时不等号也要反向；），同时不等号也要反向；（3 3）第第i i 个约束为个约束为 型，在不等式左边增加一个非负型，在不等式左边增加一个非负的变量的变量，称为称为松弛变量松弛变量；同时该变量在目标函数中的；同时该变量在目标函数中的系数为系数为0 0；njjjxcz1min)max(zzz njjjxcz1max （4 4）第）第i i 个约束为个约束为 型，在不等式左边

21、减去型，在不等式左边减去一个非负的变量一个非负的变量，称为称为剩余变量剩余变量；同时令该变量在；同时令该变量在目标函数中的系数为目标函数中的系数为0 0；（5 5）若）若 ，令，令 （6 6）若）若 无约束，令无约束，令 ，其中，其中，xxxxxx 0,xx0 x例例3：将下述线性规划模型化为标准形式：将下述线性规划模型化为标准形式：32132minxxxz取值无约束321321321321,0,0632442392.xxxxxxxxxxxxst54332100332maxxxxxxxz 0,63324422392.54332133215332143321xxxxxxxxxxxxxxxxxxx

22、xst标准形式化为：和剩余变量同时引入松弛变量，其中解：令,0,543333311xxxxxxxxxzz 第二节第二节图解法图解法一、图解法的步骤一、图解法的步骤1.1.画出直角平面坐标系；画出直角平面坐标系；2.2.图示约束条件，找出可行域；图示约束条件，找出可行域；3.3.图示目标函数；图示目标函数；4.4.最优解的确定。最优解的确定。212maxxxz0,52426155.2121212xxxxxxxst242621 xx32x521 xx2x1xo4Q3Q1Q2Q最优解在最优解在Q2处获得，此时处获得，此时x1=3.5,x2=1.5,目标函数值为目标函数值为8.5例例4：用图解法求解以

23、下线性规划问题：用图解法求解以下线性规划问题二、由图解法得到的启示二、由图解法得到的启示（2 2）无穷多最优解（若上例中目标函数变为）无穷多最优解（若上例中目标函数变为max z=3x1+x2)max z=3x1+x2)；242621 xx32x521 xx2x1xo4Q3Q2Q1Q(3)(3)无界解（若去掉例子中第无界解（若去掉例子中第2 2、3 3个约束）；个约束）；32x2x1xo1.求解线性规划问题时，解的情况有四种类型。求解线性规划问题时，解的情况有四种类型。（1 1）惟一最优解（如上例）；）惟一最优解（如上例）；(4)(4)无可行解。无可行解。62;22121xxxx目标函数为目标

24、函数为max z=3x1+x2，约束条件为，约束条件为2x1xo2.2.若线性规划问题的可行域存在，则可行域一若线性规划问题的可行域存在，则可行域一定是个凸集。定是个凸集。3.3.线性规划问题的最优解若存在，则最优解或线性规划问题的最优解若存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。最优解之一一定是可行域的凸集的某个顶点。4.4.解题思路是，先找凸集的任一顶点，计算解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。更优，则逐点转移，直到找到最优解。第三节第三节单纯形法原理单纯形法原理 可

25、行解可行解：满足约束条件的解称为满足约束条件的解称为可行解可行解，可行解的集合称，可行解的集合称为为可行域可行域。最优解最优解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。基基：约束方程组的一个满秩子矩阵称为规划问题的一个：约束方程组的一个满秩子矩阵称为规划问题的一个基基，基中的每一个列向量称为基中的每一个列向量称为基向量基向量，与基向量对应的变量称，与基向量对应的变量称为为基变量基变量，其他变量称为，其他变量称为非基变量非基变量。基解基解：在约束方程组中，令所有非基变量为在约束方程组中，令所有非基变量为0，可以解出，可以解出基变量的唯一解，这组解与非基变量的基变量的唯一解，这

26、组解与非基变量的0共同构成共同构成基解基解。基可行解基可行解：满足变量非负的基解称为满足变量非负的基解称为基可行解基可行解可行基可行基：对应于基可行解的基称为对应于基可行解的基称为可行基可行基一、线性规划问题的解一、线性规划问题的解212maxxxz0,52426155.2121212xxxxxxxst543210002maxxxxxxz0,5 24 2615 5 .5432152142132xxxxxxxxxxxxxst化为标准形式化为标准形式O是是5241500 x3,x4,x5Q4是是218030 x2,x4,x5P3否否-70-45120 x2,x3,x5P4否否020-1050 x2

27、,x3,x4Q1是是101504x1,x3,x5P1否否0-61505x1,x3,x4P2否否-10033x1,x2,x5Q3是是06032x1,x2,x4Q2是是007.51.53.5x1,x2,x3对应点对应点是否为基是否为基可行解可行解x5x4x3x2x1基变量基变量序号序号242621 xx32x521 xx2x1xo4Q3Q1Q2Q1P2P3P4P二、凸集和顶点二、凸集和顶点凸集：凸集：如果集合如果集合 C 中任意两个点中任意两个点X1,X2,其连线上的所有点也其连线上的所有点也都是集合都是集合C 中的点。中的点。上图中（上图中（1）（）（2）是凸集，（）是凸集，（3）（）（4）不是

28、凸集）不是凸集顶点：顶点：如果对于凸集如果对于凸集 C 中的点中的点 X，不存在，不存在C 中的任意其它中的任意其它两个不同的点两个不同的点X1,X2，使得，使得 X 在它们的连线上，这时称在它们的连线上，这时称 X 为凸集的顶点。为凸集的顶点。三、线性规划问题基本定理三、线性规划问题基本定理定理一定理一 若线性规划问题存在可行解，则问题的可行若线性规划问题存在可行解，则问题的可行 域是凸集。域是凸集。定理二定理二 线性规划问题的基本可行解线性规划问题的基本可行解 X 对应线性规划对应线性规划 问题可行域（凸集）的顶点。问题可行域（凸集）的顶点。定理三定理三 若线性规划问题有最优解，一定存在一

29、个基若线性规划问题有最优解，一定存在一个基 可行解是最优解。可行解是最优解。从上述三个定理可以看出，要求线性规划问题的最从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。标函数值即可，最大的就是我们所要求的最优解。是可行解。是可行解。设设21，XXbAX 1bAX 221)1(XaaXX 则其连线上的点为则其连线上的点为21)1(XaAAaXAX 221aAXAXaAX babbab 定理一证明：定理一证明：X1和和X2连线上的点也在可行域内，因此可行域是凸集。连线上的

30、点也在可行域内，因此可行域是凸集。定理二证明：定理二证明：X是可行域的顶点是可行域的顶点X是基可行解是基可行解即证明：即证明：相当于证明：相当于证明：X不是可行域的顶点不是可行域的顶点X不是基可行解不是基可行解1、证明：、证明：X不是基可行解不是基可行解X不是可行域的顶点不是可行域的顶点(1)1bxPjrjj 则有则有不是基本可行解不是基本可行解（设可行解设可行解)0,0,21 rxxxX由于由于X不是基可行解，因此不是基可行解，因此P1,P2,Pr线性相关。线性相关。使得：使得：数数即存在一组不全为零的即存在一组不全为零的),2,1(rii (2)02211 rrPPP (3)02211 r

31、rPPP 的的数数，得得：(2 2)乘乘以以一一个个不不为为零零 )()()(222111bPxPxPxrrr (3 3)，得得：(1 1)()()(222111bPxPxPxrrr (3 3)，得得：(1 1)0,0),(,),(),(2211)2(rrxxxX 有有：有有为为某某个个值值，使使得得对对于于所所可可以以取取,r,i10 0 iix。都都是是可可行行解解和和因因此此)2()1(XX)2()1(2121XXX 又又因因为为：所以所以X不是可行域的顶点。不是可行域的顶点。0,0),(,),(),(2211)1(rrxxxX令：令：2、证明：、证明：X不是基可行解不是基可行解X不是可

32、行域的顶点不是可行域的顶点不是可行域的顶点不是可行域的顶点设设TrxxxX)0,0,21),1(0 )1(为可行域中的两个点为可行域中的两个点ZYaZaaYX且 则有：则有：且且因因为为0,01 ,0 jjzyaa0 0 jjjzyx时时，所所以以当当 TrTrzzzZyyyY)0,0,)0,0,2121 ,即即因此：因此：(1)11byPyPjrjjjnjj (2)11bzPzPjrjjjnjj 0)(211 jjrjjPzy得：得：），），（）（0)-()-()-(222111 rrrPzyPzyPzy即：即：z-yYXjj不不会会全全为为零零为为不不同同的的两两点点，因因此此和和因因为为

33、 21线线性性相相关关因因此此 ,P,，PPr因此因此X不是基可行解不是基可行解四、确定初始基可行解四、确定初始基可行解 线性规划问题的最优解一定会在基可行解中取线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，直到找到最优解为止。换到另一个基可行解，直到找到最优解为止。设给定线性规划问题：设给定线性规划问题：），（），（njxmibxaxczjinjjijnjjj1 01 max11100010001212222111211mnmmnnaaaaaaaaa其标准形为：其标准形为：），（），（njxmi

34、bxxaxxczjisinjjijmisinjjj1 01 0max111因此约束方程组的系数矩阵为：因此约束方程组的系数矩阵为：由于该矩阵含有一个由于该矩阵含有一个单位子矩阵单位子矩阵，因此，一这个单位阵做基，因此，一这个单位阵做基，就可以求出一个基可行解：就可以求出一个基可行解：TmbbX,0,01五、从一个基可行解转换为相邻基可行解五、从一个基可行解转换为相邻基可行解相邻基可行解：相邻基可行解：如果两个基可行解，它们有且只有一个基变如果两个基可行解，它们有且只有一个基变量不同，则称它们为相邻基可行解。量不同，则称它们为相邻基可行解。），（njxbxPxczjnjjjnjjj1 0 max

35、11 mnmnnjmmmmmjmmjmmbbbaaaaaaaaaaaa21,2,1,2,1,22,21,2,12,11,1100010001njmmmPPPPPPP 2121 TmmxxxXPPP）（的的基基可可行行解解为为：是是一一个个可可行行基基，设设对对应应可可见见0,0,0,2121 mmxcxcxcZ 2211函函数数值值为为：该该基基可可行行解解对对应应的的目目标标mmxcxcxcZ 2211函函数数值值为为：该该基基可可行行解解对对应应的的目目标标(1)1bxPmiii 且且有有 miiijjPaP1 又有又有01 miiijjPaP(2)0)(1 miiijjPaP bPaPx

36、Pmiiijjmiii )()2()1(11 bPaxPjmiijii 1)(整理得：整理得：满足所有约束方程满足所有约束方程可见可见)0,0,(2211 mjmjjaxaxaxX 为基可行解为基可行解要使要使)0,0,(2211 mjmjjaxaxaxX 0 0 0 2211 mjmjjaxaxax 必有：必有：号号且其中至少有一个取等且其中至少有一个取等 0mini ijijiaax ljlax 则有：则有：也是基可行解也是基可行解，)0,0,0,()1(1)1(12211 mjmjlljlljjaxaxaxaxaxX 对对应应的的目目标标函函数数值值为为：，)0,0,0,()1(1)1(

37、12211 mjmjlljlljjaxaxaxaxaxX jmjmmjjcaxcaxcaxcZ )()()(222111 jmjmmmjjcacxcacxcacxc 22221111mjmjjjmmacacaccxcxcxc 22112211)(22112211mjmjjjmmacacaccxcxcxc )(12211 miijijmmaccxcxcxc 六、最优性检验和解的判别六、最优性检验和解的判别1.当所有当所有 时，现有顶点对应的基可行解即为最优解。时，现有顶点对应的基可行解即为最优解。2.当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 且可以找到且可以找到 ，则该线性规

38、划问题有无穷多最优解。，则该线性规划问题有无穷多最优解。3.如果存在某个如果存在某个 ，又，又 向量的所有分量向量的所有分量 ，对任，对任意意 ，恒有，恒有 ，则存在无界解。，则存在无界解。0j0i00jjP0ija000ijiax0jix令令miijijjacc1，其中其中 随基的改变而改变随基的改变而改变ija）（和和比比较较 miijijaccZZZZ1,则则有有：第四节第四节单纯形法计算步骤单纯形法计算步骤第一步：第一步：求初始可行解，列初始单纯形表求初始可行解，列初始单纯形表第二步：第二步：进行最优性检验进行最优性检验 如果表中，所有检验数如果表中，所有检验数 ，则表中，则表中的基可

39、行解就是问题的最优解，计算到此为的基可行解就是问题的最优解，计算到此为止，否则转入下一步。止，否则转入下一步。0j第三步：第三步：转换到新的基可行解，构造新单纯形表转换到新的基可行解，构造新单纯形表1.1.确定换入变量确定换入变量取使得取使得0maxjjjk所对应的所对应的 作为换入基的变量。作为换入基的变量。kx2.2.确定换出变量确定换出变量取使得取使得lklikikiiabaab0min所对应的所对应的 作为换出基的变量。作为换出基的变量。lx3.3.用换入变量替换换出变量，做新单纯形表用换入变量替换换出变量，做新单纯形表（1）klllabb liaabbbikkllii（2）kljlj

40、laaaliaaaaaikkljlijij（3）检验数）检验数 的求法与初始单纯形表中求法相同的求法与初始单纯形表中求法相同j第四步：第四步：重复第二、三步直到计算结束。重复第二、三步直到计算结束。例例5 5：用单纯形法求解如下线性规划问题用单纯形法求解如下线性规划问题212maxxxz0,52426155.2121212xxxxxxxst543210002maxxxxxxz0,5 24 2615 5 .5432152142132xxxxxxxxxxxxxst解：解：将原线性规划问题化为标准形式有将原线性规划问题化为标准形式有 第一步：第一步：取系数矩阵中单位阵部分为基，得取系数矩阵中单位阵部

41、分为基，得初始基可行解。初始基可行解。TX5,24,15,0,0列出初始单纯形表：列出初始单纯形表：000121001150010262400015015000012jjzc jcBCBxb4x2x3x4x5x3x1x5x60第二步第二步：由于：由于：都大于零，因此，目前没有得都大于零，因此，目前没有得到最优解。到最优解。2112存在大于零的检验数中，由于存在大于零的检验数中，由于 ，且，且211221所以所以 为换入变量。为换入变量。1x第三步：第三步：由于由于462415,624,min所以确定所以确定 为换出变量为换出变量4x1.确定换入变量确定换入变量2.确定换出变量确定换出变量3.作

42、新单纯形表作新单纯形表0-1/301/301-1/602/301001/601/31420015015000012jjzc jcBCBxb1x2x3x4x5x3x1x5x第四步第四步：由于还存在检验数由于还存在检验数 ，因此重复上述步骤。，因此重复上述步骤。0221000015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2jjzc jcBCBxb1x2x3x4x5x3x1x2x 由于上表中所有检验数都小于等于零，因此已经得由于上表中所有检验数都小于等于零，因此已经得到最优解，最优解为：到最优解，最优解为：代入目标函数得最优值：代入目标函

43、数得最优值：217*zTX0,0,215,23,27*第五节第五节单纯形法的进一步讨论单纯形法的进一步讨论一、人工变量法一、人工变量法0,93 1 24 3max3213232132131xxxxxxxxxxxxxz例例6：求如下线性规划问题求如下线性规划问题解：解：化为标准型化为标准型0,9 3 1 24 003max5432132532143215431xxxxxxxxxxxxxxxxxxxz约束条件的系数矩阵为：约束条件的系数矩阵为：001301011201111 54321PPPPP这个矩阵中不含有单位矩阵，因此很难找到初始基。这个矩阵中不含有单位矩阵，因此很难找到初始基。对于这种线性

44、规划问题的系数矩阵不含有单位对于这种线性规划问题的系数矩阵不含有单位矩阵的情况，我们往往采用添加矩阵的情况，我们往往采用添加人工变量人工变量 的方法，的方法，来认为构造一个单位矩阵。这样的方法就是来认为构造一个单位矩阵。这样的方法就是人工变人工变量法量法。为了构造出单位矩阵，在系数矩阵中添加两列单位为了构造出单位矩阵，在系数矩阵中添加两列单位列向量，系数矩阵变为：列向量，系数矩阵变为：100013001101120001111 7654321PPPPPPP线性规划问题的约束条件就变为：线性规划问题的约束条件就变为：0,9 3 1 -24 7654321732653214321xxxxxxxxx

45、xxxxxxxxxx因为因为 、是人为添加的，因此其对应的变量是人为添加的，因此其对应的变量 、称为称为人工变量人工变量。6P7P6x7x目标函数中人工变量的系数：目标函数中人工变量的系数：添加人工变量前，在线性规划问题的标准形中，各约束条添加人工变量前，在线性规划问题的标准形中，各约束条件已经是等式约束了，因此为了保证等式约束满足不变，在最件已经是等式约束了，因此为了保证等式约束满足不变，在最优解中，人工变量的取值必须为优解中，人工变量的取值必须为0。为此，令目标函数中人工变量的系数为为此，令目标函数中人工变量的系数为任意大的一个负值任意大的一个负值，用用“”来表示，这样，只要人工变量取值不

46、为零，则目标来表示，这样，只要人工变量取值不为零，则目标函数就不能达到极大化函数就不能达到极大化。M目标函数变为：目标函数变为：765431003maxMxMxxxxxz添加添加 M 来处理人工变量的方法，称为大来处理人工变量的方法，称为大M 法法求解过程：求解过程：因此最优解为：因此最优解为：TX0,0,0,0,23,25,023maxz二、两阶段法二、两阶段法 用大用大 M 处理人工变量时，用计算机求解会出处理人工变量时，用计算机求解会出现错误，由此产生了两阶段法。现错误，由此产生了两阶段法。第一阶段：先求解一个目标函数中只含有人工第一阶段：先求解一个目标函数中只含有人工变量的线性规划问题

47、。变量的线性规划问题。即令目标函数中其它变量的系数取零，人工变即令目标函数中其它变量的系数取零，人工变量的系数取某个量的系数取某个正的常数正的常数（一般取（一般取1），在保持原问），在保持原问题约束条件不变的情况下求这个目标函数极小化时题约束条件不变的情况下求这个目标函数极小化时的解。的解。第二阶段：从第一阶段的最终单纯形表出发，第二阶段：从第一阶段的最终单纯形表出发，去掉人工变量，按原问题的目标函数，继续寻找原去掉人工变量，按原问题的目标函数，继续寻找原问题的最优解。问题的最优解。若最优解对应的目标函数为若最优解对应的目标函数为0，则转入第二阶段；，则转入第二阶段；若最优解对应的目标函数不为

48、若最优解对应的目标函数不为0，即最优解的基变量，即最优解的基变量中含非中含非0的人工变量，则说明原问题无可行解。的人工变量，则说明原问题无可行解。例例7：用两阶段法求解例：用两阶段法求解例6 0931247654321732653214321xxxxxxxxxxxxxxxxxxx,-76minxxz 第一阶段：第一阶段：化成标准形式：化成标准形式：0931247654321732653214321xxxxxxxxxxxxxxxxxxx,-76maxxxz-1004-2001309-1-10-11-21-1011114000000jjzc jcBCBxb6x2x3x4x5x4x1x7x01000

49、16x7x-1-100130406304066-1-10-11-2101120330jjzc 2x4x7x1-301-40-106000001/202/3011000-1/31030-1/210000000000jjzc jcBCBxb2x2x3x4x5x4x1x1x1/20-1/2-1/21/31/66x7x-1-1-1-1该模型最优解为该模型最优解为X=（1，3，0，0，0，0，0）T，其基变量不含人工变量，说明原问题的一个基可行解为其基变量不含人工变量，说明原问题的一个基可行解为X=（1，3，0，0，0）T，转入第二阶段。，转入第二阶段。第二阶段：第二阶段：3/203001/202/30

50、11-3001/31130-1/21000000010-3jjzc jcBCBxb2x2x3x4x5x4x1x1x-3/4000-9/23/40103/23/21-1/4001-1/25/20-1/2100000jjzc 2x4x3x2/3该问题的最优解为该问题的最优解为X=（5/2，0，0，0，3/2）T，对应的目标函数值为对应的目标函数值为z*=3/2。三、关于解的判断三、关于解的判断1.当所有当所有 时，时，基变量中不含非零的人工变基变量中不含非零的人工变量，量，且对于所有非基变量且对于所有非基变量 的的 ，则该线，则该线性规划问题有惟一最优解。性规划问题有惟一最优解。0jix0i2.当