第一章线性规划课件.ppt

1、第一章第一章 线性规划线性规划 1.1 1.1 线性规划的模型与图解法线性规划的模型与图解法 1.2 1.2 单纯形法单纯形法 1.3 1.3 对偶问题与灵敏度分析对偶问题与灵敏度分析 1.4 1.4 线性整数规划线性整数规划 1.5 1.5 运输问题运输问题1.1 1.1 线性规划的模型与图解法线性规划的模型与图解法一、线性规划问题及其数学模型一、线性规划问题及其数学模型 在生产管理和经营活动中经常需要解在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到决：如何合理地利用有限的资源，以得到最大的效益。最大的效益。例例1.1 1.1 某工厂可生产甲、乙两种产品，需消耗煤、某工

2、厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产计划方案。试拟订使总收入最大的生产计划方案。资源单耗资源单耗 产品产品资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 9 4 44 4 5 5 3 3 1010360360200200300300单位产品价格单位产品价格 7 7 12121 1）决策变量：）决策变量：需决策的量，即待求的未需决策的量，即待求的未知数；知数；2 2）目标函数：需优化的量，即欲达的目）目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；标，用决策变量的表达式表示；3 3）约

3、束条件：为实现优化目标需受到的）约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。限制，用决策变量的等式或不等式表示。线性规划模型的线性规划模型的三要素三要素 例例1.1 1.1 某工厂可生产甲、乙两种产品，需消耗煤、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产计划方案。试拟订使总收入最大的生产计划方案。资源单耗资源单耗 产品产品资源资源甲甲 乙乙资源限量资源限量煤煤电电油油9 9 4 44 4 5 5 3 3 1010360360200200300300单位产品价格单位产品价格 7

4、 7 1212在本例中在本例中约束条件：约束条件：分别来自资源煤、电、油限量的约分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为束，和产量非负的约束，表示为121212129436045200.310300,0 xxxxs txxx x 决策变量：决策变量：甲、乙产品的计划产量，记为甲、乙产品的计划产量，记为 ；12,x x目标函数：目标函数：总收入记为总收入记为 ,则则 ,为体为体现对其追求极大化，在现对其追求极大化，在 的前面冠以极大号的前面冠以极大号Max；z12712zxxz解：设安排甲、乙产量分别为解：设安排甲、乙产量分别为 ,总收总收入为入为 ，则，则模型为模型为：12,

5、x xz12Max712zxx121212129436045200.310300,0 xxxxs txxx x 线性规划模型的一个基本特点：线性规划模型的一个基本特点：目标和约束均为变量的目标和约束均为变量的线性线性表达式。表达式。如果模型中出现如如果模型中出现如的非线性表达式，则不属于线性规划。的非线性表达式，则不属于线性规划。212312lnxxx 例例1.2 1.2 某市今年要兴建大量住宅某市今年要兴建大量住宅,已知有三种住已知有三种住宅体系可以大量兴建，各体系资源用量及今宅体系可以大量兴建，各体系资源用量及今年供应量见下表：年供应量见下表：水泥水泥(公斤公斤/m/m2 2)400040

6、00(千工日千工日)147000147000(千块千块)150000150000(吨吨)2000020000(吨吨)110000110000(千元千元)资源限量资源限量3.53.51801802525120120大模住宅大模住宅3.03.01901903030135135壁板住宅壁板住宅4.54.52102101101101212105105砖混住宅砖混住宅人工人工(工日工日/m/m2 2)砖砖(块块/m/m2 2)钢材钢材(公斤公斤/m/m2 2)造价造价(元元/m/m2 2)资源资源住宅体系住宅体系 要求在充分利用各种资源条件下使建造住宅的要求在充分利用各种资源条件下使建造住宅的总面积为最

7、大，求建造方案。总面积为最大，求建造方案。解解:设今年计划修建砖混、壁板、大模住宅各设今年计划修建砖混、壁板、大模住宅各为为 ,为总面积为总面积,则本问题的数学则本问题的数学模型模型为为:12312312311231230.1050.1350.1201100000.0120.0300.025200000.1100.1900.180150000.0.2101470000.00450.0030.00354000,0 xxxxxxxxxs txxxxx xx 123Maxzxxx 前苏联的尼古拉也夫斯克城住宅兴建计划采用了上前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了述模型，共用了12

8、12个变量，个变量，1010个约束条件。个约束条件。123,x xxz练习：某畜牧厂每日要为牲畜购买饲料以使其获练习：某畜牧厂每日要为牲畜购买饲料以使其获取取A、B、C、D四种养分。市场上可选择的饲料四种养分。市场上可选择的饲料有有M、N两种。有关数据如下：两种。有关数据如下：0.4 0.6 2.0 1.70.4 0.6 2.0 1.7 0 0.1 0.2 0.10 0.1 0.2 0.1 0.1 0 0.1 0.20.1 0 0.1 0.24 41010售价售价（元（元/公斤）公斤）牲畜每日每头需要量牲畜每日每头需要量N M 每公斤含营养成分每公斤含营养成分 A B C D试决定买试决定买M

9、 M与与N N二种饲料各多少公斤而使支出的二种饲料各多少公斤而使支出的总费用为最少？总费用为最少？解：设购买解：设购买M、N饲料各为饲料各为 ，则，则 12Min104zxx 12121212120.100.400.10.6.0.10.22.00.20.11.7,0 xxxxs txxxxx x 12,x x线性规划模型的线性规划模型的一般形式一般形式：以：以MAX型、型、约束约束为例为例决策变量：决策变量：目标函数：目标函数：约束条件：约束条件：1,nxx11Maxnnzc xc x 11111111.,0nnmmnnmna xaxbs taxaxbxx 模型一般式的模型一般式的矩阵形式矩阵

10、形式111(,),(,),(),(,)TnnTijm nmXxxCccAabbb 则模型可表示为则模型可表示为Max.0zCXAXbs tX 记记回顾回顾例例1.11.1的模型的模型其中其中 表示决策变量的向量；表示决策变量的向量；表示产品的价格向量；表示产品的价格向量；表示资源限制向量；表示资源限制向量；表示产品对资源的单耗系数矩阵。表示产品对资源的单耗系数矩阵。12(,)TXx x(7,12)C (360,200,300)Tb 9445310A 一般地一般地中中 称为称为决策变量决策变量向量，向量，称为称为价格系数价格系数向量向量,称为称为技术系数技术系数矩阵矩阵,称为称为资源限制资源限制

11、向量。向量。Max.0zCXAXbs tX XCAb问题：为什么问题：为什么 称为技术系数矩阵？称为技术系数矩阵？Au 图解法是用画图的方式求解线性规划的一图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一而是在于能够直观地说明线性规划解的一些重要性质。些重要性质。二、线性规划问题的图解法二、线性规划问题的图解法1.1.做约束的图形做约束的图形 先做非负约束的图形；先做非负约束的图形；再做资源约束的图形。再做资源约束的图形。以

12、例以例1.11.1为例，其约束为为例，其约束为121212129436045200.310300,0 xxxxs txxxx 1x2x图解法步骤图解法步骤问题：问题：不等式的几何意义是什么？怎样做图？不等式的几何意义是什么？怎样做图？121212122112943609436094360,0,90,0,40,0 9040 0943600 0 xxxxxxxxxxxx如如，它它表表示示以以为为边边界界的的一一个个半半平平面面。因因此此，它它的的做做图图方方法法是是：先先做做直直线线用用两两点点连连线线方方法法（令令则则再再令令则则于于是是该该直直线线过过点点（，）、（，）；再再确确定定不不等等式

13、式表表示示上上述述直直线线的的哪哪半半平平面面，可可用用代代入入点点的的方方法法（如如把把原原点点（，）代代入入不不等等式式，满满足足，说说明明原原点点所所在在的的半半平平面面即即该该不不等等式式所所表表示示的的区区域域）。1.1.做约束的图形做约束的图形 先做非负约束的图形；先做非负约束的图形；再做资源约束的图形。再做资源约束的图形。以例以例1.11.1为例，其约束为为例，其约束为121212129436045200.310300,0 xxxxs txxxx 1x2x90400501004030图解法步骤图解法步骤各约束的公共部分即模型的约束，称可行域。各约束的公共部分即模型的约束，称可行域

14、。7121424 对于目标函数对于目标函数任给任给 二不同的值，二不同的值，便可做出相应的二便可做出相应的二直线，用虚线表示。直线，用虚线表示。11nnzc xc x z2.2.做目标的图形做目标的图形01x2x12712zxx 84168zz 和和z以例以例1.11.1为例，其目为例，其目标为标为 ，分别分别令令 ，做出相应的二直线，做出相应的二直线，便可看出便可看出 增大的增大的方向。方向。*X3.3.求出最优解求出最优解 将目标直线向使目将目标直线向使目标标 优化的方向移，直优化的方向移，直至可行域的边界为止，至可行域的边界为止，这时其与可行域的这时其与可行域的“切切”点点 即最优解。即

15、最优解。z*X01x2x9040501003040*(20,24)TX *X*X 如在例如在例1.11.1中，中，是可行域的一个角点，是可行域的一个角点，经求解交出经求解交出 的二约束的二约束直线联立的方程，可解直线联立的方程，可解得得由图解法的结果得到例由图解法的结果得到例1.11.1的最优解的最优解 ，将其代入目标函数求得相应的最，将其代入目标函数求得相应的最优目标值优目标值 。说明当甲产量安排。说明当甲产量安排 20 20 个个单位，乙产量安排单位，乙产量安排 24 24 个单位时，可获得最大个单位时，可获得最大的收入的收入 428428。*(20,24)TX *428z 1212121

16、2Min6421.341.5,0zxxxxs txxx x 01x2x10.50.3751.51*X*(0.5,0),3TXz练习：用图解法求解练习：用图解法求解下面的线性规划。下面的线性规划。-最优解在什么位置获得？最优解在什么位置获得？-线性规划的可行域是一个什么形状？线性规划的可行域是一个什么形状？问题：问题：在上两例中在上两例中 多边形，而且是多边形，而且是“凸凸”形的多边形。形的多边形。在边界，而且是在某个顶点获得。在边界，而且是在某个顶点获得。（1 1）线性规划的约束集（即可行域）是一个凸）线性规划的约束集（即可行域）是一个凸多面体。多面体。凸多面体是凸集的一种。所谓凸集是指：集中

17、任两点凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：的连线仍属此集。试判断下面的图形是否凸集：凸集中的凸集中的“极点极点”，又称顶点或角点，是指它属于凸集，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。但不能表示成集中某二点连线的内点。如多边形的顶点。由图解法得到线性规划解的一些特性由图解法得到线性规划解的一些特性因为，由图解法可知，只有当目标直线平移到边因为，由图解法可知，只有当目标直线平移到边界时，才能使目标界时，才能使目标 z 达到最大限度的优化。达到最大限度的优化。问题：问题：本性质有何重要意义？本性质有何重

18、要意义？（2 2）线性规划的最优解（若存在的话）必能在）线性规划的最优解（若存在的话）必能在可行域的顶点获得。可行域的顶点获得。它使得在可行域中寻优的工作由它使得在可行域中寻优的工作由“无限无限”上升为上升为“有限有限”，从而为线性规划的算法设，从而为线性规划的算法设计提供了重要基础。计提供了重要基础。（3 3）线性规划解的几种情形）线性规划解的几种情形1 1）唯一最优解）唯一最优解2 2）多重最优解）多重最优解3 3）无可行解）无可行解4 4）无有限最优解（无界解）无有限最优解（无界解）内容回顾与思考内容回顾与思考1.1.线性规划解决的是一类什么问题？线性规划解决的是一类什么问题？2.2.线

19、性规划模型构成的三要素？线性规划模型构成的三要素？3.3.线性规划模型的一般式？线性规划模型的一般式？4.4.图解法的一般步骤？图解法的一般步骤？5.5.图解法得到线性规划哪些性质？图解法得到线性规划哪些性质？单纯形法是求解线性规划的主要算法，单纯形法是求解线性规划的主要算法，19471947年由美国斯坦福大学教授年由美国斯坦福大学教授丹捷格丹捷格（G.B.Danzig）提出。）提出。尽管在其后的几十年中，又有一些尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的算法问世，但单纯形法以其简单实用的特色始终保持着绝对的特色始终保持着绝对的“市场市场”占有率。占有率。1.2 1.2

20、单纯形法单纯形法 早在二战期间，早在二战期间，在美国空军服在美国空军服役的科学家丹役的科学家丹捷捷格格就就提出了提出了“单纯单纯形方法形方法”。这个方法。这个方法当时曾经当时曾经保密，保密，直到战后的直到战后的19471947年，当丹年，当丹捷捷格离开格离开军队，转任斯坦福大学教授之后，军队，转任斯坦福大学教授之后，才公开发表。才公开发表。丹丹捷捷格格不仅提出了单纯形法，不仅提出了单纯形法，而且在线性规划相关研究领域做出而且在线性规划相关研究领域做出了一系列杰出的贡献。他了一系列杰出的贡献。他被被人们人们誉誉为为“线性规划之父线性规划之父”，以他的名字，以他的名字命名的命名的“丹丹捷捷格格奖奖

21、”成为运筹学界成为运筹学界的最高奖项之一。的最高奖项之一。（1914-20051914-2005）一、单纯形法的预备知识一、单纯形法的预备知识1.1.线性规划的标准型线性规划的标准型 来自实际问题的线性规划模型形式各异，来自实际问题的线性规划模型形式各异，在用单纯形法求解之前，先要将模型化为统在用单纯形法求解之前，先要将模型化为统一的形式一的形式标准型：标准型：Max.0zCXAXbs tX 标准型的标准型的特征：特征：Max型、等式约束、非负约束型、等式约束、非负约束,0m nAm mn b 其其中中，的的秩秩为为（）。非标准形式如何化为标准？非标准形式如何化为标准？（1 1）Min型化为型

22、化为Max型型 因为，求一个函数的极小点，因为，求一个函数的极小点，等价于求该函数的负函数的等价于求该函数的负函数的极大点。极大点。f(x)-f(x)*x注意注意：Min化为化为Max后，最优解不变，最优值差负号。后，最优解不变，最优值差负号。MinzCX/MaxzCX 加负号加负号Max.0zCXAXbs tX 12min2zxx 12max2zxx如如（2 2）不等式约束化为等式约束）不等式约束化为等式约束 分析：以例分析：以例1.11.1中煤的约束为例中煤的约束为例 x3 称为称为松弛变量松弛变量。问题：它的实际意义是什么？。问题：它的实际意义是什么？煤资源的煤资源的“剩余剩余”。129

23、4360 xx12394360 xxx之所以之所以“不等不等”是因为左右两边有一个差额，是因为左右两边有一个差额，可称为可称为“松弛量松弛量”，若在左边加上这个松弛量，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为则化为等式。而这个松弛量也是变量，记为x3 ，则有则有Max.0zCXAXbs tX 练习：请将例练习：请将例1.11.1的约束的约束 化为标准型化为标准型121212129436045200.310300,0 xxxxs txxx x 解：增加松弛变量解：增加松弛变量则约束化为则约束化为345,xxx1231241251234594 36045200.310 300

24、,0 xxxxxxstxxxx x x x x 可见：松弛变量的可见：松弛变量的系数恰构成系数恰构成单位单位阵阵问题：松弛变量在问题：松弛变量在目标中目标中的系数为何？的系数为何？问题：标准型与原问题：标准型与原来模型来模型解解的关系？的关系？一般地，记松弛变量的向量为一般地，记松弛变量的向量为 Xs，则，则.0 AXbs tX.,0 ssAXXbs tXIX.0 AXbs tX.,0 ssAXXbs tXIX (3)3)当模型中有某变量当模型中有某变量 x xk k 没有非负要求，称没有非负要求，称 为自由变量为自由变量,则可令则可令 /,0kkkkkxxxxx化为标准型。化为标准型。例如例

25、如1212121max22260zxxxxxxx 可化为可化为122122122122max2()()22()6,0zxxxxxxxxxx xx X X2 2为自由变量为自由变量2.2.基本概念基本概念（1 1）可行解与最优解）可行解与最优解X满满足足全全体体约约束束的的解解可可解解：，记记为为行行；,*XXCXCX 可可行行解解中中最最优优的的，记记为为则则对对 任任可可行行解解，有有最最优优解解：。直观上，可行解是可行域中的点，直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行是一个可行的方案；最优解是可行域的边界角点，是一个最优的方案。域的边界角点，是一个最优的方案。（2 2）

26、基矩阵与基变量）基矩阵与基变量基矩阵基矩阵(简称基简称基)：系数阵系数阵A中的中的m阶可逆子阵，阶可逆子阵，记为记为B；其余部分称为非基矩阵，记为；其余部分称为非基矩阵，记为N。基向量：基向量：基基B中的列；其余称非基向量。中的列；其余称非基向量。基变量：基变量：与基向量与基向量Pj对应的决策变量对应的决策变量xj，记其组记其组成成的的向量为向量为XB；与非基向量对应的变量称非基；与非基向量对应的变量称非基变量，记其组成的向量为变量，记其组成的向量为XN。32104015A，如如 指出指出A A中的基。中的基。记记A A中的列为中的列为P Pj j，则每个，则每个P Pj j 对应于一个对应于

27、一个xj，即，即 。1,.,nAPP 1,.,nxx121022101 解解：本本例例中中，中中的的 阶阶可可逆逆子子阵阵有有AA1313434410,;01 ，其其相相应应的的基基向向量量为为基基变变量量为为，BxBP PxxXx2121212212,21 其其相相应应的的基基向向量量为为基基变变量量为为。BxBP Px xXx123124142 12 3,0 xxxxxxxx 下下面面为为某某线线性性规规划划的的约约束束请请例例举举出出其其基基矩矩阵阵和和相相应应的的基基向向量量、量量。例例基基变变1.3 6 6个。个。一般地，一般地，mn 阶矩阵阶矩阵A A中基的个数最多有多中基的个数最

28、多有多少个？少个？个个。mnC问题：本例的问题：本例的 中一共有几中一共有几个基？个基？12102101 A（3 3）基本解与基本可行解）基本解与基本可行解 1111,0,.0当当 中中的的基基 取取定定后后，不不妨妨设设 表表示示 中中的的前前 列列，则则可可记记（）相相应应地地约约束束中中的的可可表表示示为为即即解解得得当当取取时时，有有,TBNBBNNBNNBABBAmABNXXXAXbXBNbBXNXbXXB bB NXB bXXB b X 可见：一个基本解是由一个基决定的。可见：一个基本解是由一个基决定的。注意：注意：基本解仅是资源约束的解，并未要求其基本解仅是资源约束的解，并未要求

29、其非负，因此其未必可行。非负，因此其未必可行。称非负的基本解为称非负的基本解为基本可行解基本可行解（简称基可行解）。（简称基可行解）。10B bAXbX 称称的的解解为为线线性性规规划划的的一一个个基基本本解解；例例1.4 在例在例1.3的模型的模型123124142123,0 xxxxxxxx中，中，求相应于基求相应于基B B1 1和和B B2 2的基本解，它们是否基本的基本解，它们是否基本可行解？可行解？11110101011,0101013311 解解：BBBb1(0,0,1,3),TBX 相相应应于于基基的的基基本本解解为为是是基基本本可可行行解解。1121212712155555,2

30、-1212131-5555522 BBBb271(,-,0,0),55 相相应应于于基基的的基基本本解解为为不不是是基基本本可可行行解解。TBX上二组概念间的联系：上二组概念间的联系：系数阵系数阵A A中可找出若干个中可找出若干个基基B B每个基每个基B B都对应于一个都对应于一个基本解基本解非负的基本解就是非负的基本解就是基本可行解基本可行解几种解之间的关系：几种解之间的关系：可行解可行解基本解基本解非可行解非可行解基本可行解基本可行解问题：问题：基本可行解是可行域中的基本可行解是可行域中的哪些点哪些点？3.3.基本定理基本定理（1 1）线性规划的可行域是一个）线性规划的可行域是一个凸多面体

31、凸多面体。（2 2）线性规划可行域的）线性规划可行域的顶点与基本可行解顶点与基本可行解一一 一对应。一对应。（3 3）线性规划的最优解（若存在的话）必能）线性规划的最优解（若存在的话）必能 在可行域的在可行域的顶点获得顶点获得。二、单纯形法的步骤二、单纯形法的步骤确定初始基本可行解确定初始基本可行解检验其是否最优？检验其是否最优？寻找更好的基本可行解寻找更好的基本可行解否否是是单纯形法是一单纯形法是一种迭代的算法，种迭代的算法，它的思想是在它的思想是在可 行 域 的 顶可 行 域 的 顶点点基本可基本可行解中寻优。行解中寻优。由于顶点是有由于顶点是有限 个（为 什限 个（为 什么？）么？）,因

32、此，因此，算法经有限步算法经有限步可终止。可终止。方法前提：模型化为标准型方法前提：模型化为标准型1.1.确定初始基可行解确定初始基可行解由于基可行解是由一个可行基决定的，因此，由于基可行解是由一个可行基决定的，因此，确定初始基可行解确定初始基可行解X0相当于确定一个初始可相当于确定一个初始可行基行基B0。方法：方法：若若A中含中含I，则，则B0=I；若若A中不含中不含I，则要用人工变量法构造一，则要用人工变量法构造一 个个I。问题：问题：若若B0=I，则，则X0=？1000,00 可可行行。bB bX2.2.最优性检验最优性检验分析：分析：用什么检验？用什么检验？目标。目标。(,)BBNNX

33、zCXCCX BBNNC XC X11()BNNNCB bB NXC X11()BNBNC B bCC B N X记为记为，当当 0 0时，当前解为最优。时，当前解为最优。称称检验数检验数向量向量。,zCX 而目标而目标11,BBNNXXXB bB NXX 所以所以方法：方法：（1 1）计算每个）计算每个x xj j的检验数的检验数1 jjBjcC BP（2 2）若所有）若所有j 0 0，则当前解为最优；，则当前解为最优；否则，非最优，转否则，非最优，转3 3。问题：问题：非最优的特征为何？非最优的特征为何？至至少少有有某某个个检检验验数数。0 k3.3.寻找更好的基可行解寻找更好的基可行解由

34、于基可行解与基对应，即寻找一个新的基由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基可行解，相当于从上一个基B B0 0变换为下一个新变换为下一个新的基的基B B1 1，因此，本步骤也称为，因此，本步骤也称为基变换基变换。改改善善：基基变变换换的的原原则则可可行行：10110 zzB b变变换换的的方方法法：（）1,lknPPPP进进基基保保证证“改改善善”令令对对应应的的进进基基；0 kkP110出出基基保保证证“可可行行”由由可可决决定定出出基基。BNXB bB NXi 称称 作作 检检 验验 比比。1110()()0()maxminkjkjilikilikiPB bB PP

35、B P 方方法法：令令对对应应的的 进进基基；令令对对应应的的 出出基基。换基后，转换基后，转2 2。即再检验，直至满足最优性条件。即再检验，直至满足最优性条件。以例以例1.11.1为例，可按上述单纯形法的步骤求为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。出其最优解，其大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型zxx12Max712 123124125123459436045200.310300,0 xxxxxxs txxxx x x xx A中含中含I（P3，P4，P5），），可以用单纯形法求解。可以用单纯形法求解。(2)(2)确定初始基可行解、检验确定

36、初始基可行解、检验0100,111BBB zxx12Max712 123124125123459436045200.310300,0 xxxxxxs txxxx xxxx 100360360200=200,300300(0,0,360,200,300);111TB bX 1jjBjcC B P 计算检验数计算检验数确定进基向量为确定进基向量为P P2 2943117(0,0,0)171 45102112(0,0,0)1121 11()(),iikiB bB P 再计算检验比再计算检验比确定出基向量为确定出基向量为P P5 5。1136042005300102,B bB P 336090,4 4

37、20040,5 530030,10 （3 3）换基、计算下一个基可行解、再检验，直换基、计算下一个基可行解、再检验，直 至最优至最优11111415,10(240,50,30),(0,24,240,50,0);TTBB bX1jjBjcC B P 计算检验数计算检验数，确定进基向量为，确定进基向量为P P1 111()()iikiB bB P 再计算检验比再计算检验比，确定出基向量为，确定出基向量为P P4 4计计算算检检验验数数均均非非正正，当当前前解解为为最最优优。212219445,310(84,20,24),(20,24,84,0,0);TTBB bX练习：对于下面的线性规划练习：对于

38、下面的线性规划12121212min2226,0 zxxxxxxx x（1 1）先用图解法求解；）先用图解法求解；（2 2）将模型化为标准型；）将模型化为标准型；（3 3）再用单纯形法步骤求出其最优解，并指）再用单纯形法步骤求出其最优解，并指出求解过程中每一个基可行解相当于可行域出求解过程中每一个基可行解相当于可行域的哪一个角点。的哪一个角点。解：解：（1 1）图解法求解）图解法求解1x2x0*X*(6,0),6TXz 12121212min2226,0 zxxxxxxx x（2 2）将模型化为标准型将模型化为标准型34121231241234,max2 22 +6,0 xxzxxxxxxxx

39、x xxx 增增加加松松弛弛量量A中含中含I（P3，P4），），可以用单纯形法求解。可以用单纯形法求解。12121212min2226,0 zxxxxxxx x（3 3）用单纯形法求解）用单纯形法求解01001 0,0 1(2,6),(0,0,2,6);TTBB bX 1jjBjcC B P 计算检验数计算检验数，确定进基向量为，确定进基向量为P P1 111()()iikiB bB P 再计算检验比再计算检验比，确定出基向量为，确定出基向量为P P4.4.确定初始基可行解、检验确定初始基可行解、检验121231241234max2 22 +6,0zxxxxxxxxx xxx 1111-1,0

40、 11 10 1 BB 121231241234max2 22 +6,0zxxxxxxxxx xxx 计计算算检检验验数数均均非非正正，当当前前解解为为最最优优。111(8,6),(6,0,8,0);TTB bX*6,6zz 1x2x0*X求解过程中每一个基可行解相当于可行域的求解过程中每一个基可行解相当于可行域的哪一个角点？哪一个角点？0(0,0,2,6)TX 1(6,0,8,0)TX 0111B bBBB bX 问题问题：当模型规模较大时，计算量很大。：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在事实上，单纯形法的实现是在单纯形表单纯形表上上完成的。完成的。总结总结上述过程：上

41、述过程：三、单纯形表三、单纯形表 单纯形表是基于单纯形法的步骤设计单纯形表是基于单纯形法的步骤设计的计算表格，是单纯形法的具体实现。的计算表格，是单纯形法的具体实现。回顾单纯形法步骤回顾单纯形法步骤0111000110()()000ijjBjik iB bB bBXcC B PBB P 1B A 需需计计算算1B b 需需计计算算 1,BbA 因因此此，单单纯纯形形表表的的主主体体内内容容是是 101112 即即 BbABbABbA1111101101 =,=1klkllmkaB BaEBE Ba 故故 B而相邻两个而相邻两个 之间只有一列不之间只有一列不同，可分析其同，可分析其逆阵间逆阵间关

42、系：关系：即每个即每个 可由上一个可由上一个 经以经以 为主元的为主元的初初等行变换等行变换得到，基于此设计了单纯形表。得到，基于此设计了单纯形表。1B 1B lka单纯形表的主要结构：单纯形表的主要结构：X C1 B A1 B b 表头的完整结构：表头的完整结构：X BC1 B b BX C第一张表的第一张表的B-1是什么？是什么？第一组第一组基变量基变量是什么？是什么？用用单纯形表单纯形表计算的主要过程：计算的主要过程：X CAb（1）建立初表：）建立初表：（4）计算下一张表（用）计算下一张表（用 初等行变换初等行变换）：）：X C1 B A1 B b（2）计算检验数）计算检验数 判断最优

43、：判断最优：1jjBjcC B P （3）计算检验比换基：）计算检验比换基：11()()iikiB bB P 例例1.5 1.5 用单纯形法解例用单纯形法解例1.11.1121212129436045200.310300,0 xxxxs txxxx12M ax712zxx 标准模型的标准模型的A中是否含中是否含I？松弛变量系数恰好构成松弛变量系数恰好构成I。12Max712zxx 12345123459436045200.310300,01212 xxxxxxs txxxx x x xx345,解解：增增加加松松弛弛变变量量将将模模型型化化为为标标准准型型：x xx12345 xxxxx1 B

44、 bBXBC 7 12 0 0 0941004501031 0001360200300345xxx0007 12 0 0 0 904030 中表示进基列与出基行的交叉元，下一张表将实行中表示进基列与出基行的交叉元，下一张表将实行以它为主元的初等行变换（也称高斯消去）。方法是：以它为主元的初等行变换（也称高斯消去）。方法是：先将主元消成先将主元消成1 1，再用此，再用此1 1将其所在列的其余元消成将其所在列的其余元消成0 0。111197(0 0 0)47;3 其其中中检检验验数数BcC Bp3360904 300.31000.1 2407.8010-0.4 502.5001-0.5342xxx

45、0012 3.4000-1.230.820100 12345 xxxxx1B b BXBC 712000941004501031 0001360200300345xxx000 712000 904030 201000.4-0.2 84001-0.321.16 24010-0.120.16312xxx0712*(20,24,84,0,0),TX （请解释其实际意义）（请解释其实际意义）-000-1.360.52428.z 300.31000.1 2407.8010-0.4 502.5001-0.5342xxx0012 3.4000-1.230.820100 甲乙产品产量的最优计划、相应的最大收入

46、和资源剩余甲乙产品产量的最优计划、相应的最大收入和资源剩余基变量基变量的检验数和系数列有何特征？的检验数和系数列有何特征？检验数均为检验数均为0 0，10 BBBCC BB系数列均为系数列均为单位向量单位向量列列12345 xxxxx1Bb BXBC 712000941004501031 0001360200300345xxx000 712000 904030 300.31000.1 2407.8010-0.4 502.5001-0.5342xxx0012 3.4000-1.230.820100 201000.4-0.2 84001-0.321.16 24010-0.120.16312xxx0

47、712 -000-1.360.52本题全部单纯形表本题全部单纯形表练习：用单纯形法求解下面的线性规划练习：用单纯形法求解下面的线性规划-2.26,0121212 xxs txxxx 12-2sxx M M i i n n1x2x0*X0(0,0,2,6)TX 1(6,0,8,0)TX 前面曾用图解法和单纯形法步骤求解过：前面曾用图解法和单纯形法步骤求解过：34,解解：增增加加松松弛弛变变量量将将模模型型化化为为标标准准型型：x x122Maxzxx1212312434-2.26,0 xxxstxxxx x x x12-2-2.26,0121212sxxxxs txxxx M M i i n n

48、 1234 xxxx 1-2001B b BXBC -111012012634xx00 6 1-200 61201 8031131xx01 0-40-1(6,0,8,0)TX 6s 注：注：1.1.表上每一列的含义：表上每一列的含义：11111(,)(,)nBb AB b B PB P 2.2.每张表上每张表上B B-1-1的位置在哪？的位置在哪？对应于初表中对应于初表中I I 的位置。的位置。101,1B 111 1,0 1B 122Maxzxx 1212312434-226,0 xxxxxxx x x x 111B P 1010BP 如果整个如果整个，则为，则为无界解无界解1011,1B

49、111-0.41-0.5,0.1B 121-3.12 1.160.4-0.2.-0.12 0.16B 每张表的每一列都等于本表的每张表的每一列都等于本表的B B-1-1乘以初表的相应列乘以初表的相应列 12345xxxxx1Bb BXBC 712000941004501031 0001360200300345xxx000 712000 300.31000.1 2407.8010-0.4 0 1 502.50-0.5342xxx0012 3.4000-1.2 201000.4-0.2 84001-0.321.16 24010-0.120.16312xxx0712 000-1.36-0.52123

50、45 xxxxx1B b BXBC941004501031 0001360200300345xxx000 712000 例例1.61.6：填出下面表中的空白：填出下面表中的空白 100.4-0.2 01-0.321.16 00-0.120.16312xxx0712 000-1.36-0.5213.12 1.163608400.40.220020,00.120.1630024 12345 xxxxx1B b BXBC941004501031 0001360200300345xxx000 712000 100.4-0.2 01-0.321.16 00-0.120.16312xxx0712 000-