《单纯形法 (3)精选PPT.ppt》由会员分享，可在线阅读，更多相关《单纯形法 (3)精选PPT.ppt（112页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于单纯形法(3)第1页，讲稿共112张，创作于星期日一、问题的提出v图解法只能解决二维的线性规划问题，那更多图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？变量的问题怎么办？(jsj)v通过代数算法搜寻最优解。通过代数算法搜寻最优解。v单纯形法，就是这样的一种代数搜寻法。单纯形法，就是这样的一种代数搜寻法。v线性规划问题的解一般有无穷多个，如果不缩线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！小搜寻范围，工作量太大！v我们首先将最优解缩小在一个有限的范围。我们首先将最优解缩小在一个有限的范围。第2页，讲稿共112张，创作于星期日一、问题的提出v回顾图解法，我们知道
2、：最优解必定在可行域的顶点上取回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。得，而顶点的个数总是有限的。v多维线性规划问题的可行域也存在有限个顶点。多维线性规划问题的可行域也存在有限个顶点。v如果能够从一个顶点开始，通过某种方式向更优顶点转移，如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。总会找到最优点。v首先面临的问题：首先面临的问题：v如何通过代数方法找到第一个顶点？如何通过代数方法找到第一个顶点？第3页，讲稿共112张，创作于星期日一、问题的提出图解法中的例图解法中的例1.5模型为：模型为：Max z=50 x1+100 x2 s.t
3、.1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0，x2 0第4页，讲稿共112张，创作于星期日一、问题的提出从其标准形的解向量开始研究：从其标准形的解向量开始研究：Max z=50 x1+100 x2 s.t.1x1+1x2+1x3+0 x4+0 x5300 2x1+1x2+0 x3+1x4+0 x5400 0 x1+1x2+0 x3+0 x4+1x5250 xj 0 (j=1,2,3,4,5)第5页，讲稿共112张，创作于星期日一、问题的提出v顶点对应的解向量有何代数特顶点对应的解向量有何代数特征？征？vO(0,0,300,400,250)vA(0,250,
4、50,150,0)vB(50,250,0,50,0)vC(100,200,0,0,50)vD(200,0,100,0,50)v答案：都有两个变量取值为答案：都有两个变量取值为0，且非负。，且非负。X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)第6页，讲稿共112张，创作于星期日一、问题的提出v既然顶点解向量中有两个变量取值为既然顶点解向量中有两个变量取值为0，而标准形中又有三个约束方程，是否可以而标准形中又有三个约束方程，是否可以直接通过这种方式找顶点？直接通过这种方式找顶点？v如令如令x10，x20，则，则vx3300，x4400，x5250v可得
5、到解（可得到解（0，0，300，400，250）第7页，讲稿共112张，创作于星期日一、问题的提出又如：令又如：令x30，x50，由约束条件：由约束条件：x1+x2+x33002x1+x2+x4400 x2+x5250可得到解（可得到解（50，250，0，50，0）第8页，讲稿共112张，创作于星期日一、问题的提出若令若令x20，x50，会怎样？，会怎样？由约束方程可知：由约束方程可知：x1+x2+x3300 x1+x3300 2x1+x2+x4400 2x1+x4400 x2+x5250 0250？显然不能得到相应的解。显然不能得到相应的解。第9页，讲稿共112张，创作于星期日一、问题的提出
6、为什么令为什么令x20，x50时不能得到解？时不能得到解？因为其余三个变量的系数列向量为因为其余三个变量的系数列向量为该矩阵是非可逆矩阵，即去掉该矩阵是非可逆矩阵，即去掉x2和和x5后的三个约束后的三个约束方程线性相关，这种情况下得不到解。方程线性相关，这种情况下得不到解。第10页，讲稿共112张，创作于星期日一、问题的提出v既然如此，如果我们在技术矩阵中取出三列，组既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。则一定可以得到一个解。第11页，讲稿共112张，创作于星期日一、问题的提出v如，取如，
7、取1、2、3列得到：列得到：v此矩阵为可逆阵，故令此矩阵为可逆阵，故令x40，x50，一定可以，一定可以得到一个解。得到一个解。v对应的解为（对应的解为（75，250，-25，0，0）。）。第12页，讲稿共112张，创作于星期日一、问题的提出基的概念：基的概念：已知已知A是约束条件的是约束条件的mn阶系数矩阵，其秩阶系数矩阵，其秩为为m。设设B是是A矩阵中的一个非奇异（可逆）的矩阵中的一个非奇异（可逆）的mm阶子矩阵，则称阶子矩阵，则称B为线性规划问题的为线性规划问题的一个一个基基。B由由A中的中的m个线性无关列向量组成。个线性无关列向量组成。第13页，讲稿共112张，创作于星期日一、问题的提
8、出一个基对应一组概念：一个基对应一组概念：非基变量非基变量基变量基变量基向量基向量非基向量非基向量对应基本解：（对应基本解：（0，0，300，400，250）第14页，讲稿共112张，创作于星期日一、问题的提出(0,0,300,400,250)(0,300,0,100,-50)(0,400,-100,0,150)(0,250,50,150,0)(300,0,0,-200,-50)(200,0,100,0,50)不存在不存在(100,200,0,0,50)(50,250,0,50,0)(75,250,-25,0,0)基本解基本解是是x3,x5p3,p5x1,x2,x4p1,p2,p4B2=(p1
9、,p2,p4)是是x3,x4p3,p4x1,x2,x5p1,p2,p5B3=(p1,p2,p5)是是x1,x2p1,p2x3,x4,x5p3,p4,p5B10=(p3,p4,p5)否否x1,x3p1,p3x2,x4,x5p2,p4,p5B9=(p2,p4,p5)否否x1,x4p1,p4x2,x3,x5p2,p3,p5B8=(p2,p3,p5)是是x1,x5p1,p5x2,x3,x4p2,p3,p4B7=(p2,p3,p4)否否x2,x3p2,p3x1,x4,x5p1,p4,p5B6=(p1,p4,p5)是是x2,x4p2,p4x1,x3,x5p1,p3,p5B5=(p1,p3,p5)x2,x5
10、p2,p5x1,x3,x4p1,p3,p4B4=(p1,p3,p4)否否x4,x5p4,p5x1,x2,x3p1,p2,p3B1=(p1,p2,p3)是否可行是否可行非基变非基变量量非基非基向量向量基变量基变量基向量基向量基基第15页，讲稿共112张，创作于星期日一、问题的提出基本解可能可行，也可能不可行。基本解可能可行，也可能不可行。满足非负约束条件的基本解叫满足非负约束条件的基本解叫基本可行解基本可行解，相应的基称为相应的基称为可行基可行基。否则为否则为非可行基非可行基。第16页，讲稿共112张，创作于星期日一、问题的提出vA：(0,250,50,150,0)vB：(50,250,0,50
11、,0)vC：(100,200,0,0,50)vD：(200,0,100,0,50)vO：(0,0,300,400,250)vE：(75,250,-25,0,0)vF：(0,300,0,100,-50)vG：(0,400,-100,0,150)vH：(300,0,0,-200,-50)X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)G(0,400)E(75,250)F(0,300)H(300,0)第17页，讲稿共112张，创作于星期日一、问题的提出v线性规划解的集合关系：线性规划解的集合关系：基基本本解解最最优优解解基基本本可可行行解解可可行行解解第18
12、页，讲稿共112张，创作于星期日一、问题的提出v显然，将搜索范围控制在基本可行解显然，将搜索范围控制在基本可行解内，将大大减少搜索工作量。内，将大大减少搜索工作量。v但是，即使取得一个基，得到的解还但是，即使取得一个基，得到的解还不一定可行。不一定可行。v如何才能保证取得一个可行基呢？如何才能保证取得一个可行基呢？第19页，讲稿共112张，创作于星期日一、问题的提出总结：总结：1、可行域顶点对应的解必为基本可行解：、可行域顶点对应的解必为基本可行解：有有n-m个变量取值为个变量取值为0，满足非负条件。，满足非负条件。2、一个基对应一组基本解，可能可行，也可、一个基对应一组基本解，可能可行，也可
13、能不可行；能不可行；3、最优解必定在基本可行解中；、最优解必定在基本可行解中；第20页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理单纯形法的基本思路：单纯形法的基本思路：首先找到一个顶点；首先找到一个顶点；然后判断它是否最优；然后判断它是否最优；如果不是，则通过更换顶点的方式找到更如果不是，则通过更换顶点的方式找到更优的顶点；优的顶点；直到找到最优顶点。直到找到最优顶点。第21页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理第一步：找到一个顶点第一步：找到一个顶点 （初始基本可行解）（初始基本可行解）第22页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理思
14、考：思考：1、令、令n-m个变量为个变量为0（非基变量）是否一（非基变量）是否一定可以找到？定可以找到？答案：不一定。答案：不一定。如例中如例中x20，x50时不能得到解。时不能得到解。可行的办法：找到一个基。可行的办法：找到一个基。第23页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理2、一个基是否一定对应可行域顶点？、一个基是否一定对应可行域顶点？答案：不一定。必须是可行基。答案：不一定。必须是可行基。一般来说，判断一个基是否是可行基，需要一般来说，判断一个基是否是可行基，需要在求出其基本解后才能判断。在求出其基本解后才能判断。第24页，讲稿共112张，创作于星期日二、单纯形法
15、的基本思路和原理3、那有没有办法在求出解之前保证我们取得、那有没有办法在求出解之前保证我们取得的基为可行基？的基为可行基？解决办法：保证解决办法：保证右端项非负右端项非负，找到一个，找到一个单单位矩阵位矩阵，必定是一个可行基。，必定是一个可行基。第25页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理如范例系数阵：如范例系数阵：存在存在3阶单位阵阶单位阵（初始可行基）（初始可行基）右端项非负右端项非负第26页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理基本可行解为基本可行解为（0，0，300，400，250）此可行基称为此可行基称为初始可行基初始可行基。对应的解称为对应
16、的解称为初始基本可行解初始基本可行解。初始基本可行解在上页矩阵中一目了然。初始基本可行解在上页矩阵中一目了然。第27页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理第二步：最优性检验第二步：最优性检验第28页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理对应于每一组基本解，目标函数都可以表对应于每一组基本解，目标函数都可以表示成非基变量的函数，称为示成非基变量的函数，称为典式典式。如：初始基本可行解如：初始基本可行解（0，0，300，400，250）其非基变量为其非基变量为x1，x2目标函数为目标函数为Max z=50 x1+100 x2第29页，讲稿共112张，创作于
17、星期日二、单纯形法的基本思路和原理典式典式Z=50 x1+100 x2如果如果x1增加增加1，Z会怎样？会怎样？答案：答案：Z增加增加50。如果如果x2的值增加的值增加1，Z会怎样？会怎样？答案：答案：Z增加增加100。第30页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理x1，x2的取值是否有增加的可能？的取值是否有增加的可能？分析：该解中非基变量分析：该解中非基变量 x1，x2的取值为的取值为0，其值完全有可能增加。其值完全有可能增加。说明此时目标函数值还有增加的可能，没有说明此时目标函数值还有增加的可能，没有达到最优。达到最优。第31页，讲稿共112张，创作于星期日二、单纯形
18、法的基本思路和原理再如：基本再如：基本解（解（50，250，0，50，0）其非基变量为其非基变量为x3，x5由约束方程可得：由约束方程可得：x150-x3+x5 x2250-x5目标函数为目标函数为Max z=50 x1+100 x2 27500-50 x3-50 x5第32页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理典式典式Z=27500-50 x3-50 x5如果如果x3增加增加1，Z会怎样？会怎样？答案：答案：Z减少减少50。如果如果x5的值增加的值增加1，Z会怎样？会怎样？答案：答案：Z减少减少50。可见要使可见要使Z增加，只有使增加，只有使x3和和x5减少。减少。第3
19、3页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理x3，x5的取值是否有减少的可能？的取值是否有减少的可能？分析：该解中非基变量分析：该解中非基变量 x1，x2的取值为的取值为0，其值不可能再减少。其值不可能再减少。所以所以Z值不可能再增加。值不可能再增加。说明此基本解对应的目标函数值已经达到说明此基本解对应的目标函数值已经达到最优。最优。第34页，讲稿共112张，创作于星期日二、单纯形法的基本思路和原理由以上分析，可见，完全可以由典式中的系由以上分析，可见，完全可以由典式中的系数来判断解是否最优。数来判断解是否最优。如：如：Z=50 x1+100 x2系数系数0，未达到最优；，未达到最优；Z=27500-50 x3-50 x5系数系数0计算计算Qibi/aik令令Ql=min Qi 则则xl为出基为出基变量，变量，alk为主元为主元否否某非基变某非基变量检验数量检验数为零为零唯一最唯一最优解优解无无界界解解无可无可行解行解无穷多无穷多最优解最优解是是是是是是否否否否第111页，讲稿共112张，创作于星期日感感谢谢大大家家观观看看第112页，讲稿共112张，创作于星期日