线性规划的单纯形法表格方法.doc

=5x1+2x2+3x3-x4++2x2+2x3+x4=83x1+4x2+x3+x5=7xj≥0j=1,2,3,4,5表1Z中cb的值cj→523-11常数b基变量X1X2X3X4X5-1X41221088/2=41X53410177/1=7cj-zj30400Z=-1由表的中间行可求出基本可行解,令x1=x2=x3=0,由约束条件得x4=8,x5=:因为cj-zj行中存在正值,所以当前基本可行解不是最优解。cj-zj行中的4最大因而非基变量X3使z有最大的单位增量,把X3选作新的(换入)基变量。为确定被换出的基变量,采用最小比值法。用X3列的值除以约束条件的常数(8/2=4,7/1=7)。第一行有最小比值,把它叫做旋转行。第一行原来的基变量是X4,此时X4为换出基变量,新的基变量为X3、X5。为此需要把表中X3对应在约束条件中系数变为单位值(1,0)。在表1中:1)用2除旋转行使X3系数为1;2)用-1/2乘旋转行加到第二行消去X3。Z中cb的值cj→523-11常数b基变量X1X2X3X4X53X31/2111/2044/(1/2)=81X55/230-1/2133/(5/2)=6/5cj-zj1-40-20Z=15因为cj-zj行中仍存在正值,所以当前基本可行解不是最优解。cj-zj行中的1最大因而非基变量X1使z有最大的单位增量,把X1选作新的(换入)基变量。为确定被换出的基变量,采用最小比值法。用X1列的值除以约束条件的常数(4/(1/2)=8,3/(5/2)=6/5)。第二行有最小比值,把它叫做旋转行。第二行原来的基变量是X5,此时X5为换出基变量,新的基变量为X3、X1。为此需要把表中X1对应在约束条件中系数变为单位值(0,1)。在表1中:1)用5/2除旋转行使X1系数为1;2)用-1/5乘旋转行加到第一行消去X1。Z中cb的值cj→523-11常数b基变量X1X2X3X4X53X302/513/5-1/517/55X116/50-1/52/56/5cj-zj0-26/50-9/5-2/5Z=81/5cj-zj行中系数全为非正,说明不可能再改进目标函数值,因此这个基本可行解x1=6/5,x2=0,x3=17/5,x4=0,x5=0是最优解,z=81/5是目标规划的最优解。