管理运筹学单纯形法精选文档.ppt

《管理运筹学单纯形法精选文档.ppt》由会员分享，可在线阅读，更多相关《管理运筹学单纯形法精选文档.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学单纯形法本讲稿第一页，共二十九页5.1 线性规划求解的相关概念 一、相关定理定理定理1 1 线性规划问题的可行解集线性规划问题的可行解集S S是凸集。是凸集。定理定理2 2 线性规划问题的基本可行解线性规划问题的基本可行解X X对应于可对应于可行域行域S S的顶点。也就是说，可行域的顶点就的顶点。也就是说，可行域的顶点就是线性规划问题的基本可行解。是线性规划问题的基本可行解。定理定理3 3 若线性规划问题有最优解，它一定在其若线性规划问题有最优解，它一定在其可行域的顶点上达到。可行域的顶点上达到。本讲稿第二页，共二十九页二、基本概念o单纯形法的基本思路：单纯形法也可以说是一种找凸集极

2、点的计算方法，但它并不是要求去计算所有的极点，而是从凸集的一个初始解出发，沿凸集的边缘逐个验算所遇到的极点，直到找到使目标函数最优的极点为止。o初始可行解:第一个找到的可行域的顶点。o三、单纯形法试算程序框图（见图51）本讲稿第三页，共二十九页开 始转变为标准型增加额外变量(松弛、剩余、人工变量)建立初始单纯形表最优停找出“换入”“换出”变量修正单纯形表是否图51本讲稿第四页，共二十九页5.2 线性规划模型的变换 一、线性规划模型标准型的特点一、线性规划模型标准型的特点 o目标函数是求极大值或极小值；目标函数是求极大值或极小值；o所有的变量都是非负的；所有的变量都是非负的；o除变量的非负约束外

3、，其余的约束条件都除变量的非负约束外，其余的约束条件都是等式约束；是等式约束；o每个约束方程右边的常数都是非负的每个约束方程右边的常数都是非负的 。除变量的非负约束除变量的非负约束等式约束等式约束思考思考:若右边的若右边的常数不是非负怎常数不是非负怎么办么办?本讲稿第五页，共二十九页二、线性规划模型的变换 根据线性规划模型约束条件的不同，将其划分为三种类型：1.“”类型的约束条件的变换类型的约束条件的变换 变换的方法：在不等式中增加一个额外的变量，称为变换的方法：在不等式中增加一个额外的变量，称为松弛变量，以松弛变量，以S S表示之。松弛变量在约束方程中的系数为表示之。松弛变量在约束方程中的系

4、数为1 1，在目标函数中的系数为，在目标函数中的系数为0 0，所以它的引入并不影响目标函，所以它的引入并不影响目标函数值。数值。松弛变量即表示作为决策限制条件的某种有限资源未被利松弛变量即表示作为决策限制条件的某种有限资源未被利用的部分。用的部分。本讲稿第六页，共二十九页2“”类型的约束条件的变换o变换的方法：引入剩入变量及人工变量，以变换的方法：引入剩入变量及人工变量，以S和和A表示。表示。o剩余变量在约束方程中的系数为剩余变量在约束方程中的系数为-1，在目标函数中的系数，在目标函数中的系数为为0，人工变量在约束方程中的系数为，人工变量在约束方程中的系数为1，在目标函数中的系，在目标函数中的

5、系数为是一任意大正数，以数为是一任意大正数，以M表示之。在求最大值的目标函数表示之。在求最大值的目标函数中，中，M取负号；在求最小值的目标函数中，取负号；在求最小值的目标函数中，M取正号。取正号。o剩余变量一般用来表示决策要求的某一最低标准超过要求剩余变量一般用来表示决策要求的某一最低标准超过要求的量，人工变量仅为了单纯形法在运算上方便，无其它特的量，人工变量仅为了单纯形法在运算上方便，无其它特殊意义。殊意义。本讲稿第七页，共二十九页3“=”类型的约束条件 变换的方法：引入人工变量，人工变量在约变换的方法：引入人工变量，人工变量在约束方程中的系数为束方程中的系数为1 1，在目标函数中的系数，在

6、目标函数中的系数为任意大的正数为任意大的正数M M。在求最大值的目标函数。在求最大值的目标函数中，中，M M取负号；在求最小值的目标函数中，取负号；在求最小值的目标函数中，M M取正号。取正号。本讲稿第八页，共二十九页三、模型变换方法归纳 约束条件类型约束条件类型变变 换换 方方 法法对于约束条件对于约束条件对于目标函数对于目标函数+S+S+0+0S S-S+A-S+A求求maxmax时，时，+0+0S-S-MAMA求求minmin时，时，+0+0S+MAS+MA=+A+A求求maxmax时，时，-MA-MA求求minmin时，时，+MA+MA表中，表中，表中，表中，S S S S为松弛变量或

7、剩余变量，为松弛变量或剩余变量，为松弛变量或剩余变量，为松弛变量或剩余变量，A A A A为人工变量，为人工变量，为人工变量，为人工变量，M M M M为一任意大的为一任意大的为一任意大的为一任意大的正数。正数。正数。正数。本讲稿第九页，共二十九页单纯形法 1.单纯形法的基本思想 从一个初始的基本可行解出发，沿着不断改进目标函数值的方向进行迭代，经过若干基本可行解，直到得出最优解。计算顺利进行的保证条件：最优性条件：它保证每次变动不会得到更差的解可行性条件：它保证每次变动仍是基本可行解可行域是不变的 本讲稿第十页，共二十九页2.2.单纯形法的计算步骤单纯形法的计算步骤o将线性规划问题转化为标准

8、型将线性规划问题转化为标准型o编制初始单纯行表编制初始单纯行表o判别基本可行解是否为最优判别基本可行解是否为最优o找出找出“换入换入”或或“换出换出”变量，以便进行换基变量，以便进行换基n先找出主元行与主元列：对于求极大值问题，取先找出主元行与主元列：对于求极大值问题，取Cj-Zj为正为正数且最大者所在的列为主元列，取数且最大者所在的列为主元列，取bi/aij为正数且最大者所在的为正数且最大者所在的行为主元行，主元行与主元列之交点元素称为主元素，在右上方行为主元行，主元行与主元列之交点元素称为主元素，在右上方记记“*”主元素正上方对应的变量为主元素正上方对应的变量为“换入换入”变量，主元素左边

9、变量，主元素左边对应的基变量为对应的基变量为“换出换出”变量。变量。o修正单纯形表修正单纯形表n运算规则：新行主元行元素运算规则：新行主元行元素=旧行元素旧行元素/主元素主元素n其他新行元素其他新行元素=旧行元素旧行元素-交点元素交点元素*新主元行相应元素新主元行相应元素【交交点元素指该行与主元列之交点元素点元素指该行与主元列之交点元素】o对新基本可行解进行判别，是否达到最优，是则停；否则继对新基本可行解进行判别，是否达到最优，是则停；否则继续上述程序续上述程序对于求最大值问题，对于求最大值问题，全部判别数为零与全部判别数为零与负数时，即负数时，即C Cj j-Z-Zj j 00，得最优解得最

10、优解本讲稿第十一页，共二十九页线性规划模型的一般形式：求求一一组组变变量量x1，x2，xn的的值值,使使目目标标函函数数：Z=c1x1+c2x2+cnxn的的值值最最大大或或最最小小，并并满满足足的的约约束束条条件：件：a a11x x1+a+a12x x2+a+a1nx xn(，=)b=)b1 a a21x x1+a+a22x x2+a+a2nx xn(，=)b=)b2 a am1x x1+a+am2x x2+a+amnx xn(，=)b=)bm x x1，x x2 x xn 0 0本讲稿第十二页，共二十九页线性规划一般形的标准型：本讲稿第十三页，共二十九页一般型的初始单纯形表：C CjC

11、C1 C C2 C Cn 0 0 0 x x1 x x2 x xn S Sn+1 S Sn+2 S Sn+m解解b b0 S0 Sn+10 S0 Sn+2 0 S0 Sn+ma a11 a a12 a a1n 1 0 1 0 0 0a a21 a a22 a a2n 0 1 0 a am1 a am2 a amn 0 0 1 b b1b b2b bn机会成本机会成本行行Z Zj判别数行判别数行C Cj-Z-Zj目标函目标函数数本讲稿第十四页，共二十九页例1求求max Z=7xmax Z=7x1+10 x+10 x2 满满足足 7x7x1+7x+7x2494910 x10 x1+5x+5x250

12、50 x x1，x x20 0 用用单纯单纯形法求解。形法求解。本讲稿第十五页，共二十九页例2 第第2章例章例1中我中我们们得得线线性性规规划模型划模型为为：目目标标函数：函数：max Z=50 x1+100 x2 满满足足 x1 +x2 300 2x1+x2 400 x2 250 x1，x2 0 0用用单纯单纯形法求解。形法求解。本讲稿第十六页，共二十九页本题模型的标准型为：求求max Z=50 x1+100 x2+0S3+0S4+0S5 满满足足 x1+x2+S3 =300 2x1+x2 +S4 =400 x2 +S5=250 x1，x2，S3，S4，S50本讲稿第十七页，共二十九页Cj

13、50100000 x1x2S3S4S5解解0 S30 S40 S51 1 1 0 02 1 0 1 00 1*0 0 1300400250 ZjCj-Zj0 0 0 0 050 100 0 0 000 S0 S30 S0 S4100100 x x2 1*0 1 0 -1 2 0 0 1 -1 0 1 0 0 150150250 ZjCj-Zj 0 100 0 0 10050 0 0 0 -10025000本讲稿第十八页，共二十九页Cj 50100 0 0 0 x1 x2 S3 S4 S5 解解50 x10 S4100 x2 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050

14、250ZjCj-Zj50 100 50 0 500 0 -50 0 -5027500此时，此时，C Cj j-Z-Zj j0 0 则此时为最优解。则此时为最优解。即：即：x x1 1=50=50 x x2 2=250=250 S S3 3=0=0S S4 4=50=50 S S5 5=0=0 Z=27500 Z=27500 本讲稿第十九页，共二十九页3.人工变量法o用单纯形法求最小值问题，与求最大值问题类似，其区别在于判别数为零或者正值，即Cj-Zj0时得到最优解，在决定时得到最优解，在决定“换入换入”及及“换出换出”变变量时，取量时，取Cj-Zj为负且绝对值最大者为主元列，其余步为负且绝对值

15、最大者为主元列，其余步骤同求最大值问题。骤同求最大值问题。o这种求线性规划的方法，称为这种求线性规划的方法，称为“人工变量法人工变量法”或称为或称为“大大M”法，这就是当一个法，这就是当一个 线性规划问题在增加了松线性规划问题在增加了松弛变量后弛变量后 仍不能提供基本可行解时，需要采用仍不能提供基本可行解时，需要采用“人工人工变量变量”来获得一个初始的基本可行解。来获得一个初始的基本可行解。本讲稿第二十页，共二十九页例3求求线线性性规规划：划：min Z=2x1+3x2 满满足足 2x1+x24 -x1+x22 x1,x20本讲稿第二十一页，共二十九页单纯形法的步骤归纳如下：o根据线性规划模型

16、的特点，将问题改写成标准型根据线性规划模型的特点，将问题改写成标准型o以各变量为列，各约束方程的系数为行，全部决策变量为以各变量为列，各约束方程的系数为行，全部决策变量为0，松弛变量或人工变量为基变量，建立初始单纯形，松弛变量或人工变量为基变量，建立初始单纯形表表o计算机会成本行计算机会成本行Zj及判别数行及判别数行Cj-Zj，检验问题是已达，检验问题是已达最优，是则停，否则进行下一步最优，是则停，否则进行下一步o找出主元素，确定找出主元素，确定“换出换出”及及“换入换入”变量变量o进行换基及迭代运算，修正单纯形表进行换基及迭代运算，修正单纯形表o重返第重返第3步步本讲稿第二十二页，共二十九页

17、单纯形法的经济信息例：设某制药厂生产例：设某制药厂生产A A和和B B两种药品，在已有条两种药品，在已有条件下。药品件下。药品A A的生产能力为的生产能力为5 5吨吨/月月,药品药品B B生生产能力为产能力为4 4吨吨/月，设每吨药品月，设每吨药品A A耗电耗电0.50.5万度，万度，每吨药品每吨药品B B耗电耗电1 1万度，电力部门供电能力为万度，电力部门供电能力为每月每月5 5万度，若药品万度，若药品A A价格为每吨价格为每吨4 4千元，药千元，药品品B B的价格为每吨的价格为每吨1 1千元，问每月应如何分配千元，问每月应如何分配电力资源，使产值最大？电力资源，使产值最大？本题解题过程本题

18、解题过程本讲稿第二十三页，共二十九页由题：oCjCj列表示每一个基变量对目标函数的贡献列表示每一个基变量对目标函数的贡献o初始表最右端初始表最右端bibi列，表示的是各松弛变量的最大列，表示的是各松弛变量的最大值，即相应资源的约束条件的上限值，即相应资源的约束条件的上限o初始表提供的基本可行解为初始表提供的基本可行解为 x x1 1=x=x2 2=0 =0 不生产不生产A A、B B S S3 3=5 =5 闲置的药品闲置的药品A A的生产能力的生产能力 S S4 4=4 =4 闲置的药品闲置的药品B B的生产能力的生产能力 S S5 5=5 =5 闲置的电力资源闲置的电力资源本讲稿第二十四页

19、，共二十九页例2：某医院营养室专门为病员制作甲、乙、丙三某医院营养室专门为病员制作甲、乙、丙三种营养食品，其中每种食品都要包含两种主要种营养食品，其中每种食品都要包含两种主要营养素营养素A A、B B，具体数据如下表，而且，具体数据如下表，而且A A营养素的营养素的供应量为供应量为1212千克，千克，B B营养素的供应量为营养素的供应量为2020千克，千克，试问该营养室每天制作甲、乙、丙三种食品各试问该营养室每天制作甲、乙、丙三种食品各多少份才能使其利润最高？多少份才能使其利润最高？甲甲乙乙丙丙A111B132利润（元利润（元/份）份）586本讲稿第二十五页，共二十九页对偶规划线性规划是研究资

20、源最优利用的途径，所谓最优利用包含两线性规划是研究资源最优利用的途径，所谓最优利用包含两方面的含意：方面的含意：1.1.在一定的资源条件下完成最多的任务或做出最大的贡献在一定的资源条件下完成最多的任务或做出最大的贡献2.2.完成给定的任务，使用的资源最小完成给定的任务，使用的资源最小对于一个求极大值问题必存在一个求极小值的问题与其对应，对于一个求极大值问题必存在一个求极小值的问题与其对应，而且两者包含相同的数据，称前一个问题为原问题，则后一个而且两者包含相同的数据，称前一个问题为原问题，则后一个问题便是原问题的对偶问题。反之，若称后一问题为原问题，问题便是原问题的对偶问题。反之，若称后一问题为

21、原问题，则前一个问题是对偶问题。则前一个问题是对偶问题。本讲稿第二十六页，共二十九页对偶规划的定义例2：某人某月营养成分的最低需求量，不同食品的营养成分含量及其单件如表所示，问某人每月怎样购买这些食品，才能满足营养要求，又可花钱最少？ABCD最低需求量（单位）含量（单位/千克）糖524260 蛋白质321440 脂肪312535单价（元/千克）1.50.70.91.2某食品厂拟生产单一营养成分的食品糖、蛋白质和脂肪，仍用例2中的数据，问该厂如何确定食品的单价，才能在市场竞争中立于不败之地，并可获利润最多？本讲稿第二十七页，共二十九页食品食品单一营单一营养成分单价养成分单价A B C DA B

22、C D （x x1 1）（x x2 2）（x x3 3）（x x4 4）单一营养单一营养成分需求量成分需求量y y1 1y y2 2y y3 3 5 2 4 2 5 2 4 2 3 1 1 4 3 1 1 4 3 1 2 5 3 1 2 5 606040403535食品单价食品单价1.5 0.7 0.9 1.21.5 0.7 0.9 1.2 minZminZmaxWmaxW例例3 3是例是例2 2的对偶问题，例的对偶问题，例3 3与例与例2 2互为对偶线性规划互为对偶线性规划原规划与对偶规划具有对称性，如图所示：原规划与对偶规划具有对称性，如图所示：本讲稿第二十八页，共二十九页原规划与对偶规划

23、之间的关系o1.1.原规划若有原规划若有n n个变量，则对偶规划有个变量，则对偶规划有n n个约束条件；原规划有个约束条件；原规划有m m个约束条件，则对偶规划有个约束条件，则对偶规划有m m个变量。个变量。o2.2.若原规划的目标函数是求极大值，则对偶规划的目标函数是求极若原规划的目标函数是求极大值，则对偶规划的目标函数是求极小值，且这两个极值相等。小值，且这两个极值相等。o3.3.原规划目标函数中变量的系数等于对偶规划中相应约束条件的右端原规划目标函数中变量的系数等于对偶规划中相应约束条件的右端常数项；原规划约束条件右端常数项等于对偶规划目标函数中相应变常数项；原规划约束条件右端常数项等于对偶规划目标函数中相应变量的系数。量的系数。o4.4.原规划约束条件中不等号与对偶规划约束条件的不等号方原规划约束条件中不等号与对偶规划约束条件的不等号方向相反。向相反。o5.5.原规划中一个等式约束，对应于对偶规划的一个符号无限制的原规划中一个等式约束，对应于对偶规划的一个符号无限制的变量；反之，当一个原规划的变量无符号限制，它的对偶约束变量；反之，当一个原规划的变量无符号限制，它的对偶约束条件就是等式约束。条件就是等式约束。本讲稿第二十九页，共二十九页