单纯形法迭代原理

上页下页返回引例（上一章例）0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz上页下页返回求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。上页下页返回第1步确定初始基可行解100010001),,(543PPPB令：100400100400121),...,(51PPA根据显然，可构成初等可行基B。543,,PPP为基变量543,,xxx上页下页返回第2步求出基可行解)12,16,8,0,0(,0320)0()0(2121XXxxxxZ得一基可行解令：代入目标函数412416282514213xxxxxxx基变量用非基变量表示，并令非基变量为0时对应的解是否是最优解？上页下页返回第3步最优性检验分析目标函数zxx02312检验数=0时，最优解0时，无解换基，继续xxz1200,只要取或的值可能增大。考虑将或换入为基变量21xx上页下页返回第4步基变换•换入基变量：zxxxx0230121122换入变量x2（即选最大非负检验数对应的变量）一般选取对应的变量),max(2121,xx,02,1均可换入。上页下页返回•换出变量使换入的变量越大越好同时，新的解要可行。选非负的最小者对应的变量换出i为换出变量52254233)4/12,,2/8min(0412016028xxxxxxx2x为换入变量，应换出？变量。为换出变量变量：为换入变量，确定换出522542323)4/12,,2/8min(0412016028xxxxxxxx3)4/12,,2/8min(}0,,min{2323222121kaababab思考：当时会怎样？02ka上页下页返回因此，基由变为BPPP()342转第2步：基变量用非基变量表示。第3步：最优性判断检验数存在正，按第4步换基继续迭代均非正，停止（这时的解即是最优解）2x为换入变量，应换出变量。为换出变量变量：为换入变量，确定换出522542323)4/12,,2/8min(0412016028xxxxxxxx)(543PPPB上页下页返回)0,16,2,3,0(,0432941341621812441682)1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目标函数)0,16,2,3,0(,0432941341621212441682)1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目标函数转第2步上页下页返回继续迭代,可得到:43)3()2(125.05.114)4,0,0,2,4()0,8,0,3,2(xxZXX目标函数为：最优值Ｚ＝１４最优解上页下页返回•结合图形法分析（单纯形法的几何意义）6—5—4—3—2—1—0x2|||||||||123456789x1)0,16,2,3,0(,0432941341621812441682)1()1(515152145135214123XXxxxxZxxxxxxxxxxxxxx得一基可行解令：代入目标函数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)上页下页返回单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法——单纯形法迭代原理。上页下页返回•观察法:直接观察得到初始可行基•≤约束条件:加入松弛变量即形成可行基。（下页）•≥约束条件:加入非负人工变量,以后讨论.1、初始基可行解的确定上页下页返回0,...,,...................................................2111221122111111nmnmnmmmmnnmmnnmmxxxbxaxaxbxaxaxbxaxax1、初始基可行解的确定不妨设为松弛变量，则约束方程组可表示为mxxx,,,21上页下页返回是一初始基可行解。有：令：)0,...,0,0,,...,,(),...2,1(0......................................................21111211222111111miinmnmnmmmmmnnmmnnmmbbbXmibxxxxaxabxxaxabxxaxabx1、初始基可行解的确定上页下页返回2、最优性检验与解的判别nmnmmmmmnnmmnnmmxaxabxxaxabxxaxabx'11''2'112''221'111''11.......................................行解：一般情况下，对于基可上页下页返回nmjmijijijmiiinnmmjnmjmjmmjnmjjnnxaccbcxcxcxabcxabcxcxcxcZ11'1'111''1'1'112221)(...)(...)(...代入目标函数，有：2、最优性检验与解的判别上页下页返回jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：2、最优性检验与解的判别上页下页返回•(1)最优解判别定理：若：为基可行解，且全部则为最优解。•（2）唯一最优解判别定理：若所有则存在唯一最有解。)0,...0,,...,,(''2'1)0(mbbbXnmjj,...,1,0)0(Xnmjj,...,102、最优性检验与解的判别上页下页返回•（3）无穷多最优解判定定理：若：且存在某一个非基变量则存在无穷多最优解。•（4）无界解判定定理：若有某一个非基变量并且对应的非基变量的系数则具有无界解。nmjj,...,1,00的kkx0的kmkmxmiakmi,..2,1,0',2、最优性检验与解的判别上页下页返回kmkmmmmkmkmkmkmxabxxabxxabx''2''221''11....................,,0,00'ZxxZZxakmkmkmkmkim当即解都可行，对任意（4）之证明：2、最优性检验与解的判别上页下页返回最优解判断小结（用非基变量的检验数）所有基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一有换基继续YYYYNNN无界解Njjika000jjika000jjika000以后讨论上页下页返回3、基变换•换入变量确定对应的为换入变量.(一般)kmjmj)0(maxkmx注意：只要对应的变量均可作为换入变量0jjxkmkmxZZ0此时，目标函数上页下页返回•换出变量确定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx'''''''2''221''1100...................00min3、基变换kmkmxZZ0kmxZ大大（在可行的范围内）则对应的为换出变量.lx上页下页返回4、迭代运算mmnkmmmmklmlmnkmmnlmmlbbbaaaaaaaaabxxxxxx211ln1111111......1...........................1..........................1....写成增广矩阵的形式,进行迭代.上页下页返回例：TXxxZbxxxxx)12,16,8,0,0(32012168100400100400121)0(21543211x3x2x4x5xb4、迭代运算非基变量基变量001通过初等行变换化主列为主元上页下页返回TXxxZ)0,16,2,3,0(432931621/40010010041/2-0101)1(511x3x2x4x5xb4、迭代运算每次迭代的信息都在增广矩阵及目标函数中。检验数上页下页返回2.3单纯形法迭代原理上页下页返回2.4单纯形法的计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。上页下页返回在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。0........................................................111111221122111111nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcZbxaxaxbxaxaxbxaxax单纯形表上页下页返回0...1...10................10...10.......Z-211211212111121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxE单位阵N非基阵基变量XB非基变量XNN0单纯形表上页下页返回xxxxmn1221000jcBCbBXjjzc检验数bbm''1xxm1ccm1单纯形表结构单纯形表—24/65/1minA0znmcccc21C已知上页下页返回xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1单纯形表结构单纯形表A0z)0,,0,,,(1mbbX基可行解：上页下页返回单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：有时不写此项求上页下页返回单纯形表结构单纯形表xxxxmn1221000jcBCbBXjjzc—24/65/1minC检验数bbm''1xxm1ccm1A0zjnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ10101'1'0)()(检验数令：令：jcmjjaa1j求上页下页返回单纯形表结构单纯形表xxxxmn1221000jcBC