第1章线性规划与单纯形法第4节单纯形法的计算步骤4.1单纯形表•为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似•将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组线性规划的方程组x1a+1m+x1m++1"+a1nnx=1bx2a+2m+x1+m+1"+a2nnx=2b%xma+mm+1x++1m"+mnanx=mbz−c+x11+"mc+xm+cm1+++x1m"+nnc0=x•为了便于迭代运算，可将上述方程组写成增广矩阵形式z−x1x2"mxm+1x"xnb0⎛10"0a"ab⎞⎜1,m+11n1⎟0⎜01"0a2,m+1"a2nb2⎟⎜⎟⎜######⎟0⎜00"0am,m+1"amnbm⎟⎜⎟⎝1c1c2"mcm+c1"cn0⎠•若将z看作不参与基变换的基变量，它与x1,x2,…,xm的系数构成一个基这时可采用行初等变换将c1,c2,…,cm变换为零，使其对应的系数矩阵为单位矩阵:z−x1x2"mxm+1x"xnb0⎛10"0a"ab⎞⎜1,m+11n1⎟0⎜01"0a2,m+1"a2nb2⎟⎜#####⎟⎜#⎟0⎜00"0am,m+1"amnbm⎟⎜mmm⎟1⎜00"c0−ca"c−ca−cb⎟⎜m+1∑ii,m+1n∑iin∑ii⎟⎝i=1i=1i=1⎠单纯形表表1-2cj→c1"cmcm+1"cnθiCXbx"xxxBB1mm+1"nc1x11b1"0a1,m+1"a1nθ1c2x22b0"0a2,m+1a2nθ2########cxb01aaθmmm"m,m+1"mnmmmm−z−∑ciib0"0cm+1−∑ici,am+1"cn−∑ciinai=1i=1i=1表1-2的说明•XB列中填入基变量，这里是x1，x2,…，xm；•CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的；•b列中填入约束方程组右端的常数；•cj行中填入基变量的价值系数c1,c2,…,cn；•θi列的数字是在确定换入变量后，按θ规则计算后填入；•最后一行称为检验数行，对应各非基变量xj的检验数是m"cj−∑ci,aij1=j,2,n,i=14.2计算步骤•表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。•计算步骤：(1)按数学模型确定初始可行基和初始基可行解，建立初始单纯形表m(2)计算各非基变量x的检验数，jσj=cj−∑ciaij检查检验数，若所有检验数i=1σj≤0,j=1,2,"n则已得到最优解，可停止计算。否则转入下一步。计算步骤-确定换入/出变量(3)在σj＞0,j=m+1,…,n中，若有某个σk对应xk的系数列向量Pk≤0，则此问题是无界，停止计算。否则，转入下一步。(4)根据max(σj＞0)=σk，确定xk为换入变量，按θ规则计算⎛bi⎞blθ=min⎜a>0⎟=x为换出变量⎜aik⎟al⎝ik⎠lkXB的第l元计算步骤-旋转运算(5)以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量⎡a1k⎤⎡0⎤⎢a⎥⎢0⎥⎢2k⎥⎢⎥⎢#⎥⎢#⎥变换Pk=⎢⎥⇒⎢⎥a第行⎢lk⎥⎢1⎥←l⎢#⎥⎢#⎥⎢⎥⎢⎥⎣amk⎦⎣0⎦将XB列中的xl换为xk，得到新的单纯形表(6)重复(2)～(5)，直到终止用例1的标准型来说明计算步骤maxzx=12+x23+x3+0+4x05x0x1+2x2+x3=84+x1+x416=4x2+x5=12x0j≥1j=,2",,5取松弛变量x)1(3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)T将有关数字填入表中，得到初始单纯形表，见表1-3z中的各价值系数基变量表1-3→cj23000CBXBbx1x2x3x4x5θ0x38121008/2=40x41640010-0x5120400112/4=3-z0230003.确定主元素2.计算θ，确定换出变量1.计算检验数，由它确定为换入变量（1）计算非基变量的检验数•各非基变量的检验数为•σ1=c1-z1=2-(0×1+0×4+0×0)=2•σ2=c2-z2=3-(0×2+0×0+0×4)=3•填入表1-3的底行对应非基变量处。（2）检验、（3）确定主元素(2)因检验数都大于零，且P1，P2有正分量存在，转入下一步；(3)max