单纯形法原理讲解ppt课件(PPT 29页).pptx

1、 本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。第1页，共29页。引例引例（上一章例）（上一章例）0,12 4 16 48 200032max54321524132154321xxxxxxxxxxxxxxxxxz第2页，共29页。求解线性规划问题的基本思路求解线性规划问题的基本思路1 1、构造初始可行基；、构造初始可行基；2 2、求出一个基可行解（顶点）、求出一个基可行解（顶点）3 3、最优性检验：判断是否最优解；、最优性检验：判断是否最优解；4 4、基变化，转、基变化，转2 2。要保证目标函数值比。要保证目标函数值比 原来

2、更优。原来更优。从线性规划解的性质可知求解线从线性规划解的性质可知求解线性规划问题的基本思路。性规划问题的基本思路。第3页，共29页。第第1 1步步 确定初始基可行解确定初始基可行解 1 0 00 1 00 0 1),(543PPPB令：1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根据根据显然显然，可构成初等可行基可构成初等可行基B。543,PPP 为基变量543,xxx第4页，共29页。第第2 2步步 求出基可行解求出基可行解)12,16,8,0,0(,0320 )0()0(2121XXxxxxZ得一基可行解令：代入目标函数 4 12 416 2 8 25142

3、13xxxxxxx基变量用非基变基变量用非基变量表示，并令非量表示，并令非基变量为基变量为 0时对时对应的解应的解是否是最优解？第5页，共29页。第第3 3步步 最优性检验最优性检验分析目标分析目标函数函数zxx02312检验数检验数0 时，时，无解无解换基，继续换基，继续xxz1200,只要取只要取 或或 的的 值可能增大。值可能增大。换入？基变量换入？基变量换出？基变量换出？基变量考虑将考虑将 或或 换入为基变换入为基变量量21 xx第6页，共29页。第第4 4步步 基变换基变换l换入基变量：换入基变量：zxxxx0230121122换入变量 x2（即选最大非负检验数对应的变量）一般选取一

4、般选取 对应的变量),max(2121,xx,02,1均可均可换入。第7页，共29页。l换出变量换出变量使换入的变量越大越好同时，新的解要可行。选非负 的最小者对应的变量换出i3241522 8 20 16 -4 0 12 40 min(8/2,12/4)3xxxxxxx2x为换入变量，应换出？变量。为换出变量变量：为换入变量，确定换出522542323)4/12,2/8min(04 12 0 16 02 8 xxxxxxxx3)4/12,2/8min(0,min2323222121kaababab思考：当 时会怎样？02ka第8页，共29页。因此，基由因此，基由 变为变为BPPP()342

5、转第转第2步：基变量用非基变量表示。步：基变量用非基变量表示。第第3步：最优性判断步：最优性判断 检验数检验数 存在正，按第存在正，按第4步换基继续迭代步换基继续迭代 均非正，停止均非正，停止 （这时的解即是最优解）（这时的解即是最优解）2x为换入变量，应换出 变量。为换出变量变量：为换入变量，确定换出522542323)4/12,2/8min(04 12 0 16 02 8 xxxxxxxx)(543PPPB第9页，共29页。)0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxx

6、xxxxx得一基可行解令：代入目标函数)0,16,2,3,0(,04329 41 3 416 21 2 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目标函数转转 第第2步步第10页，共29页。继续迭代继续迭代,可得到可得到:43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目标函数为：最优值最优解第11页，共29页。l结合图形法分析结合图形法分析（单纯形法的几何意义）（单纯形法的几何意义）6 5 4 3 2 1 0 x2|123456789x1)0,16,2,3,0(

7、,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目标函数43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目标函数为：43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目标函数为：A(0,3)B(2,3)C(4,2)D(4,0)第12页，共29页。单纯形法迭代原理单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单纯形法迭代原单纯形法迭代原理理。第

8、13页，共29页。l观察法观察法:直接观察得到初始可行基直接观察得到初始可行基l约束条件约束条件:加入松弛变量即形成加入松弛变量即形成可行基。（下页）可行基。（下页）l约束条件约束条件:加入非负人工变量加入非负人工变量,以后讨论以后讨论.1 1、初始基可行解的确定、初始基可行解的确定第14页，共29页。0,.,.2111221122111111nmnmnmmmmnnmmnnmmxxxbxaxaxbxaxaxbxaxax1 1、初始基可行解的确定、初始基可行解的确定 不妨设不妨设 为松弛变量，为松弛变量，则约束方程组可表示为则约束方程组可表示为mxxx,21第15页，共29页。是一初始基可行解。

9、有：令：)0,.,0,0,.,(),.2,1(0.21111211222111111miinmnmnmmmmmnnmmnnmmbbbXmibxxxxaxabxxaxabxxaxabx1 1、初始基可行解的确定、初始基可行解的确定第16页，共29页。2 2、最优性检验与解的判别、最优性检验与解的判别nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx11211222111111.行解：一般情况下，对于基可第17页，共29页。1 1221111111111.().().()nnnnjjmmmjjj mj mmmnnmnmiijiijjij miZc xc xc xc ba xcba

10、 xcxc xcbcc ax2 2、最优性检验与解的判别、最优性检验与解的判别代入目标函数有：第18页，共29页。jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ1010110 )()(检验数令：令：2 2、最优性检验与解的判别、最优性检验与解的判别第19页，共29页。l(1)(1)最优解判别定理：若：最优解判别定理：若：为基可行解，且全部为基可行解，且全部 则则 为最优解。为最优解。l（2 2）唯一最优解判别定理：若所有）唯一最优解判别定理：若所有 则存在唯一最优解。则存在唯一最优解。)0,.0,.,(21)0(mbbbXnmjj,.,1,0)0(Xnmjj,

11、.,1 02 2、最优性检验与解的判别、最优性检验与解的判别第20页，共29页。l（3 3）无穷多最优解判定定理：若：无穷多最优解判定定理：若：且存在某一个非基变量且存在某一个非基变量 则存在无穷多最优解。则存在无穷多最优解。l（4 4）无界解判定定理：若有某一个非基）无界解判定定理：若有某一个非基 变量变量 并且对应的非基变量的系数并且对应的非基变量的系数 则具有无界解。则具有无界解。nmjj,.,1,00的kkx0的kmkmxmiakmi,.2,1,0,2 2、最优性检验与解的判别、最优性检验与解的判别第21页，共29页。kmkmmmmkmkmkmkmxabxxabxxabx222111.

12、,0,00ZxxZZxakmkmkmkmkim当即解都可行，对任意（4）之证明：）之证明：2 2、最优性检验与解的判别、最优性检验与解的判别第22页，共29页。最优解判断小结 （用非基变量的检验数）所有 基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一 有 换基继续YYYYNNN无界解Njjika000jjika000jjika000以后以后讨论讨论第23页，共29页。3 3、基变换、基变换l换入变量确定换入变量确定 对应的对应的 为换入变量为换入变量.(一般一般)kmjmj)0(maxkmx注意注意：只要只要 对应的变量对应的变量 均可作为换入变量均可作为换入变

13、量0jjxkmkmxZZ0此时，目标函数此时，目标函数第24页，共29页。l换出变量确定换出变量确定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx22211100.0 0 min3 3、基变换、基变换kmkmxZZ0kmxZ 大大大大（在可行的范围内）（在可行的范围内）lx第25页，共29页。4 4、迭代运算、迭代运算 mmnkmmmmklmlmnkmmnlmmlbbbaaaaaaaaabxxxxxx211ln1111111.1 .1 .1 .写成增广矩阵的形式,进行迭代.第26页，共29页。例：例：TXxxZbxxx xx)12,16,8,0,0(3

14、20 121681 0 0 4 00 1 0 0 40 0 1 2 1 )0(21543211x3x2x4x5xb4 4、迭代运算、迭代运算非基变量非基变量基变量基变量001通过初等行变通过初等行变换化主列为换化主列为主元主元第27页，共29页。15(1)1 0 1 0 -1/224 0 0 1 0160 1 0 0 1/433924(0,3,2,16,0)TZxxX1x3x2x4x5xb4 4、迭代运算、迭代运算检验数检验数第28页，共29页。感谢亲观看此幻灯片，此课件部分内容来源于网络，感谢亲观看此幻灯片，此课件部分内容来源于网络，如有侵权请及时联系我们删除，谢谢配合！如有侵权请及时联系我们删除，谢谢配合！第29页，共29页。