单纯形法原理讲解课件

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

2、可行解 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单纯形法原理讲解 第2步 求出基可行解 )12,16, 8 , 0 , 0(, 0320 )0()0(2121xxxxxxz得一基可行解令：代入目标函数 4 12 416 2 8 2514213xxxxxxx基变量用非基基变量用非基变量表示，并变量表示，并令非基变量为令非基变量为 0时对应的解时对应的解是否是最优解？单纯形法原理讲解第3步 最优性检验分析目标函数z

3、xx02312检验数检验数0 时，时， 无解无解换基，继续换基，继续xxz1200 ,只要取只要取 或或 的的 值可能增大。值可能增大。换入？基变量换入？基变量换出？基变量换出？基变量考虑将考虑将 或或 换入为基变换入为基变量量21 xx单纯形法原理讲解第4步 基变换 换入基变量：zxxxx0230121122换入变量 x2（即选最大非负检验数对应的变量）一般选取一般选取 对应的变量),max(2121, xx,02, 1均可均可换入。单纯形法原理讲解 换出变量使换入的变量越大越好同时，新的解要可行。选非负 的最小者对应的变量换出i3241522 8 20 16 - 4 0 12 40 min

4、(8 / 2,12 / 4)3xxxxxxx2x为换入变量，应换出 ？ 变量。为换出变量变量：为换入变量，确定换出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx3)4/12, 2/8min(0,min2323222121kaababab思考：当 时会怎样？02ka单纯形法原理讲解因此，基由 变为bppp()342 转第转第2步：基变量用非基变量表示。步：基变量用非基变量表示。 第第3步：最优性判断步：最优性判断 检验数检验数 存在正，按第存在正，按第4步换基继续迭代步换基继续迭代 均非正，停止均非正，停止 （这时的解即是最优解）（这时的解即是最优

5、解）2x为换入变量，应换出 变量。为换出变量变量：为换入变量，确定换出522542323)4/12,2/8min( 04 12 0 16 02 8 xxxxxxxx)(543pppb单纯形法原理讲解 )0,16,2,3,0(,04329 41 3 416 21 8 124 416 82 )1()1(515152145135214123xxxxxxzxxxxxxxxxxxxxx得一基可行解令：代入目标函数)0 ,16, 2 , 3 , 0(, 04329 41 3 416 21 2 124 416 82 )1()1(515152145135214123xxxxxxzxxxxxxxxxxxxxx得

6、一基可行解令：代入目标函数转转 第第2步步单纯形法原理讲解 继续迭代, 可得到:43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxzxx目标函数为：最优值最优解单纯形法原理讲解 结合图形法分析（单纯形法的几何意义）6 5 4 3 2 1 0 x2|123456789x1)0,16,2,3,0(,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(xxz

7、xx目标函数为：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)单纯形法原理讲解单纯形法迭代原理单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单单纯形法迭代原理纯形法迭代原理。单纯形法原理讲解 观察法:直接观察得到初始可行基 约束条件: 加入松弛变量即形成可行基。（下页） 约束条件: 加入非负人工变量, 以后讨论. 1、初始基可行解的确定单纯形法原理讲解 0,.,. . . 2111221122111111nmnmnmmmmnnmmnnmmxxx

8、bxaxaxbxaxaxbxaxax1 1、初始基可行解的确定、初始基可行解的确定 不妨设不妨设 为松弛变量，为松弛变量，则约束方程组可表示为则约束方程组可表示为mxxx,21单纯形法原理讲解 是一初始基可行解。有：令：)0,.,0 , 0 ,.,(),.2 , 1( 0. . . . 21111211222111111miinmnmnmmmmmnnmmnnmmbbbxmibxxxxaxabxxaxabxxaxabx1 1、初始基可行解的确定、初始基可行解的确定单纯形法原理讲解2 2、最优性检验与解的判别、最优性检验与解的判别nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx

9、11211222111111. . . . 行解：一般情况下，对于基可单纯形法原理讲解 1 1221111111111. ().() . ()nnnnjjmmmjjj mj mmmnnmnmiijiijjij mizc xc xc xc ba xcba xcxc xcbcc ax2 2、最优性检验与解的判别、最优性检验与解的判别代入目标函数有：单纯形法原理讲解 jnmjjjjjjnmjjjmiijijmiiixzzzcxzczzaczbcz1010110 )()( 检验数令：令：2 2、最优性检验与解的判别、最优性检验与解的判别单纯形法原理讲解 (1) 最优解判别定理：若： 为基可行解，且全部

10、 则 为最优解。 （2）唯一最优解判别定理：若所有 则存在唯一最优解。 )0,.0 ,.,(21)0(mbbbxnmjj,.,1, 0)0(xnmjj,.,1 02 2、最优性检验与解的判别、最优性检验与解的判别单纯形法原理讲解 （3）无穷多最优解判定定理：若： 且存在某一个非基变量 则存在无穷多最优解。（4）无界解判定定理：若有某一个非基 变量 并且对应的非基变量的系数 则具有无界解。 nmjj,.,1, 00的kkx0的kmkmxmiakmi,.2,1,0,2 2、最优性检验与解的判别、最优性检验与解的判别单纯形法原理讲解 kmkmmmmkmkmkmkmxabxxabxxabx222111

11、. . . , , 0, 00zxxzzxakmkmkmkmkim当即解都可行，对任意（4）之证明：）之证明：2 2、最优性检验与解的判别、最优性检验与解的判别单纯形法原理讲解最优解判断小结 （用非基变量的检验数）所有 基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一 有 换基继续yyyynnn无界解njjika000jjika000jjika000以后以后讨论讨论单纯形法原理讲解3、基变换 换入变量确定 对应的 为换入变量. (一般)kmjmj)0(maxkmx注意注意：只要只要 对应的变量对应的变量 均可作为换入变量均可作为换入变量0jjxkmkmxzz0此时

12、，目标函数此时，目标函数单纯形法原理讲解 换出变量确定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx22211100. .0 0 min3 3、基变换、基变换kmkmxzz0kmxz 大大大大（在可行的范围内）（在可行的范围内）lx单纯形法原理讲解4、迭代运算 mmnkmmmmklmlmnkmmnlmmlbbbaaaaaaaaabxxxxxx211ln1111111. . 1 . . . . . 1 . . . . . 1 . 写成增广矩阵的形式,进行迭代.单纯形法原理讲解例： txxxzbxxx xx)12,16,8,0,0(320 121681 0 0 4 00 1 0 0 40