教案3_单纯形原理

§3单纯形法(SimplexMethod)本节重点：检验数的概念和计算最优性判别基变换（换入变量和换出变量的确定）旋转变换3．1基本思想对于一个标准型LP问题，从一个初始基可行解出发，判断其是否为最优解，若是则结束；否则求一个与其“相邻”的、改进的基可行解。再判断这个解是否最优，若是则结束，否则再求一个“相邻”的、改进的基可行解……直至得到一个基最优解。x1x204•Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03•Q2如例1，OQ1Q2或OQ4Q3Q2maxz=CX(LP)s.t.0xbAX为说明其基本步骤，先考虑A中有单位矩阵或其变形的标准型问题。如例1maxz=2x1+3x2s.t.0,,12416482132155242xxxxxxxxx又如maxz=3x1-x2-x3s.t.01211223511x,,xxxxxxxx135254不失一般性，在推导过程中，考虑有如下约束方程组的问题：x1+a1m+1xm+1+…+a1nxn=b1x2+a2m+1xm+1+…+a2nxn=b2……xm+amm+1xm+1+…+amnxn=bm即nmjijijibxax1(i=1，…,m)3．2求初始基可行解因bi0(i=1，…,m),故取初始基为B(0)=(P1，P2，…,Pm)，x1，…,xm为基变量。可得初始基可行解X(0)=(b1，b2，…,bm，0，…,0)TZ0=c1b1+c2b2+…+cmbm=miiibc1基向量的下标视约束方程而异，不一定是1,2,…,m。B(0)=(P3,P4,P5)X(0)=(0，0，8，16，12)TZ0=0如例1maxz=2x1+3x2s.t.0,,12416482121321554xxxxxxxxx3．3最优性检验X(0)是否为最优解？如何检验？将nmjjijiixabx1(i=1，2，…,m)代入目标函数中消去基变量：njminmjnmjjjjijiijjxc)xab(cxcz1111=minmjmijijijiix)acc(bc111令jjmiijijjzcacc1，又miiibcz10则nmjjjxzz10——z与当前非基变量的关系nmjjjxzz10——z与当前非基变量的关系由此可知，若存在j0(m+1jn)，则有xj0，其它非基变量仍为零的可行解，其目标函数值,zxzzjj00这说明当前解不是最优解。若所有j0(m+1jn)，则z0为可行解所能取得的目标函数最大值，说明当前解是最优解。故称j为检验数。将基变量的系数0也视为其检验数，可得：注意：xj的检验数是当z表示为非基变量的函数时目标函数中xj的系数。基变量的检验数为零。例1中z=2x1+3x2，x1，x2为非基变量，1=20，2=30，X(0)不是最优解。最优性判别定理：若基可行解对应的检验数0(j=1，2，…,n)，则此解是最优解，否则不是最优解。j无穷多最优解判别定理：TmbbbX)0,,0,,,,(''2'1)0(若B的一个基可行解，且对一切的j=m+1,...,n有为对应于基,0j又存在某个非基变量的检验数,0km则线性规划问题又无穷多最优解。证明：kmx非基变量新基可行解)1(X新的目标函数值不变换入)1(X,)0(X两个最优解，联线上的所有点均是最优解。无界解的判别定理：若TmbbbX)0,,0,,,,(''2'1)0(一个基可行解，有一个,0,kmia为对应于基B的,0km并且对i=1,...,m有那么线性规划问题具有无界解（无最优解）。证明：构造新的解kmjnmjabxjkmkmiii且,,1,0,0,)1()1(',')1(lllxxi=1,2,…m验证可行性：因为i,m,00lka将)1(X代入到目标函数中得ll,00kmkmzz无可行解的判别：待以后将完人工变量法以后再讲。x1+a1,m+1’xm+1+…+a1n’xn=b1’x2+a2,m+1’xm+1+…+a2n’xn=b2’……………………xm+am,m+1’xm+1+…+amn’xn=bm’xj≥0，j=1,2,…,n每一个aij和bi均带“撇”3．4基变换求一个改进的、“相邻”的可行基，一个基变量将变成非基变量（换出），一个非基变量将变成基变量（换入）。1．换入变量的确定一般，当jmax{j|j0}=k，取xk为换入变量。例1中，21，可取x2为换入变量。x1=b1-a1kxk0b1a1kxkx2=b2-a2kxk0b2a2kxk…………xm=bm-amkxk0bmamkxk2.换出变量的确定)m,,2,1i(xabxn1mjjijii在中，令xk0，而xj=0(m+1jn，jk)，要保持xi0(i=1，2，…,m)，即必须lklikikikab0aabminx于是，当为换出变量。lllklkx,0x,abx若所有则xk可取无穷大，问题无最优解。,0aikX(1)=(b1-a1klklab，b2-a2klklab，…,0，…,bm-amklklab，0，…,0，lklab，0，…，0)T为一个新的基可行解。新基为B(1)=(P1，…,Pl-1，Pk，Pl+1，…,Pm)换出变量确定方法:一般，计算=lklikikiiabaabmin0，第l个约束对应的基变量为换出变量。例1中，当前解X(0)，x2为换入变量。要使x3=8–2x20x4=160x5=12–4x20x2最多取值=min{8/2,-,12/4}=3=x2=3，x5=0，故第3个约束中的x5是换出变量.323ab新的基B(1)=(P3，P4,P2)，新的解X(1)=(0，3，2，16，0)T3.5旋转变换由此形式很容易知新的基可行解和非基变量的检验数。重复3.23.5步骤，直至某X(k)对应的检验数均小于等于零，X(k)就是最优解。最优性判别定理：若基可行解对应的检验数0(j=1，2，…,n)，则此解是最优解，否则不是最优解。j换入变量的确定方法：一般，当jmax{j|j0}=k，取xk为换入变量。换出变量确定方法:一般，计算=lklikikiiabaabmin0，第l个约束对应的基变量为换出变量。结论:以alk为主元素的旋转变换：lka)l(:即'ljlkljaaa，'llklbab(i)-iklkaa)l((i=1,2,…,m,il):即'iiklkli'ijiklkljijbaabbaaaaa，(0)-klka)l(:即'klkl'jklkljjzabzaa，