北京交通大学运筹学教案3单纯形原理(改)

§3单纯形法如例1maxz=2x1+3x2s.t.0,,12416482132155242xxxxxxxxx第一轮：选择初始的基变量x3、x4、x5可以得到初始的基可行解通过初等变换把约束方程写成，方程左边是一个基变量，右边是非基变量的形式x3＝8－x1－2x2x4＝16－4x1x5＝12－4x2代入目标函数，将目标函数用非基变量来表达令非基变量为零，得到基可行解X（0）＝（0，0，8，16，12）TZ=2x1+3x2在目标函数的表达式中，只要非基变量的系数是正数，就说明目标值还有增加的可能，也就是说目前的基可行解还不是最优解。就需要将非基变量与基变量进行对换。一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量。可按以下方法来确定换出变量。当将x2定为换入变量后，必须要从x3、x4、x5中换出一个，并要保证其余的都是非负，即x3、x4、x5≥0。当x1＝0时，x3＝8－2x2≥0x4＝16≥0x5＝12－4x2≥0只有选择x2＝min（8/2，－，12/4）＝3时当x2＝3时，x5＝0，这就决定了x5为换出变量，用x2去替换x5。第二轮x2与x5互换，即x2为基变量，x5为非基变量，为了求得新的基本可行解，并将目标函数z用非基变量x1、x5表示以判别所求的基本可行解是否为最优解,需将约束方程组进行初等变换，使方程左边是一个基变量，右边是非基变量的形式x3＝2－x1+1/2x5x4＝16－4x1x2＝3－1/4x5令非基变量为零，得到基可行解X（1）＝（0，3，2，16，0）Tz=9+2x1－3/4x5即目前的基本可行解不是最优解，x1应为换入变量。在方程组中，用各方程负的x1的系数（如果x1在方程的左边，则用正的x1系数）去除对应的常数项，选最小者，x1＝min（2/1，16/4，－）＝2第三轮x1与x3互换。将第二轮的方程组进行初等变换，使得由基变量x1、x4、x2所构成的基为单位矩阵。x1＝2－x3+1/2x5x4＝8+4x3－2x5x2＝3－1/4x5X（2）＝（2，3，0，8，0）Tz=13－1/2x3+1/4x5x5与x4互换。将约束方程组进行初等变换，使得每个约束方程只含一个基变量且基变量的系数为1。第四轮：x1＝4－1/4x4x5＝4＋2x3－1/2x5x2＝2－1/2x3＋1/8x4X（3）＝（4，2，0，0，4）Tz=14－3/2x3-1/8x4§4单纯形法的计算步骤不失一般性，考虑如下的线性规划模型Z=c1x1+c2x2+…cmxm+cm+1xm+1+…cnxnx1+a1m+1xm+1+…+a1nxn=b1x2+a2m+1xm+1+…+a2nxn=b2……xm+amm+1xm+1+…+amnxn=bm即nmjijijibxax1(i=1，…,m)cjc1…cmcm+1…cnCBXBbx1…xmxm+1…xnIc1c2cmx1x2xmb1b2bm100…………001a1,m+1a2,m+1…am,m+1…………a1na2namn12…m-z-z值0…0m+1…nXB列——基变量，CB列——基变量的价值系数(目标函数系数)cj行——价值系数，b列——方程组右侧常数列——确定换入变量时的比率计算值下面一行——检验数，中间主要部分——约束方程系数4．1单纯形表用表格法求解LP，规范的表格——单纯形表如下：检验数的表达形式将nmjjijiixabx1(i=1，2，…,m)代入目标函数中消去基变量：njminmjnmjjjjijiijjxc)xab(cxcz1111=minmjmijijijiix)acc(bc111令jjmiijijjzcacc1，又miiibcz10则nmjjjxzz10——z与当前非基变量的关系最优性判别定理：若基可行解对应的检验数0(j=1，2，…,n)，则此解是最优解，否则不是最优解。j用单纯形方法求解maxz=40x1+45x2+24x3s.t.0,,12023310032321321321xxxxxxxxxmaxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20用单纯形方法求解maxz=40x1+45x2+24x3s.t.0,,12023310032321321321xxxxxxxxxmaxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20用单纯形方法求解maxz=40x1+45x2+24x3s.t.0,,12023310032321321321xxxxxxxxxmaxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20cjCBXBbx1x2x3x4x5-z2300012100400100400102300000081612x3x4x54-3例1的初始单纯形表：cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=0用单纯形方法求解maxz=40x1+45x2+24x3s.t.0,,12023310032321321321xxxxxxxxxmaxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20cjCBXBbx1x2x3x4x5-z2300012100400100400102300000081612x3x4x54-3例1的初始单纯形表：cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=0cjCBXBbx1x2x3x4x5-z2300021010-1/2-1300-201/4203x1x4x2-412301001/4800-412cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-301001/41640010()X(1)=(0，3，2，16，0)T，z1=9用单纯形方法求解maxz=40x1+45x2+24x3s.t.0,,12023310032321321321xxxxxxxxxmaxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20cjCBXBbx1x2x3x4x5-z2300012100400100400102300000081612x3x4x54-3例1的初始单纯形表：cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=0cjCBXBbx1x2x3x4x5-z2300021010-1/2-1300-201/4203x1x4x2-412301001/4800-412cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-301001/41640010()X(1)=(0，3，2，16，0)T，z1=9用单纯形方法求解maxz=40x1+45x2+24x3s.t.0,,12023310032321321321xxxxxxxxxmaxz=2x1+3x2s.t.x1+2x284x1164x212x1，x20cjCBXBbx1x2x3x4x5-z2300012100400100400102300000081612x3x4x54-3例1的初始单纯形表：cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=0cjCBXBbx1x2x3x4x5-z2300021010-1/2-1300-201/4203x1x4x2-412301001/4800-412cjCBXBbx1x2x3x4x5-z2300021010-1/2-92000-3/4003x3x4x224-301001/41640010()X(1)=(0，3，2，16，0)T，z1=9cjCBXBbx1x2x3x4x5-z2300021010-1/2-1300-201/4203x1x4x2-412301001/4800-412()cjCBXBbx1x2x3x4x5-z2300041001/40-1400-1.5-1/80203x1x5x22011/2-1/80400-21/21X(2)=(2，3，0，8，0)T，z2=13X(3)=(4，2，0，0,4)T，z3=14(5).以alk为主元素进行迭代(即用高斯消去法或称为旋转变换)，把xk所对应的列向量变换为(0，0，…，1，…，0)T，将XB列中的第l个基变量换为xk，得到新的单纯形表，返回(2)。计算步骤(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。(2).检验各非基变量xj的检验数，若j0，j=m+1，…，n；则已得到最优解，可停止计算，否则转入下一步。(3).在j0，j=m+1，…，n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界解，停止计算。否则，转入下一步。(4).根据max(j0)=k，确定xk为换入变量，按规则计算=min{bi/aik\aik0}可确定第l行的基变量为换出变量。转入下一步。