线性规划与单纯形法-第4节

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第1章 线性规划与单纯形法,第,4,节,单纯型法的计算步骤,第,4,节 单纯型法的计算步骤,根据以上讨论的结果，将求解线性规划问题的单纯形法的计算步骤归纳如下。,如,利用单纯型表,，求解线性规划问题。,4.1 单纯型表,为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。,将,(1-22),式与目标函数组成,n+1,个变量，,m+1,个方程的方程组。,线性规划的方程组,为了便于迭代运算，可将上述方程组写成增广矩阵形式,若将,z,看作不参与基变换的基变量，它与,x,1,x,2,x,m,的系数构成一个基，这时可采用行初等变换将,c,1,c,2,c,m,变换为零，使其对应的系数矩阵为单位矩阵。得到,可根据上述增广矩阵设计计算表，表,1-2,。,表,1-2,的说明,X,B,列中填入基变量，这里是,x,1,，,x,2,，,x,m,；,C,B,列中填入基变量的价值系数，这里是,c,1,c,2,c,m,；它们是与基变量相对应的；,b,列中填入约束方程组右端的常数；,c,j,行中填入基变量的价值系数,c,1,c,2,c,n,；,i,列的数字是在确定换入变量后，按,规则计算后填入；,最后一行称为检验数行，对应各非基变量,x,j,的检验数是,4.2,计算步骤,表,1-2,称为初始单纯形表，每迭代一步构造一个新单纯形表。,计算步骤：,(1),按数学模型确定,初始可行基,和,初始基可行解，建立初始单纯形表。,(2),计算,各非基变量,x,j,的检验数,，,检查检验数，若所有检验数,则已得到最优解，可停止计算。否则转入下一步。,(3),在,j,0,j=m+1,n,中，若有某个,k,对应,x,k,的系数列向量,P,k,0,，则此问题是无界，停止计算。,否则，转入下一步。,(4),根据,max(,j,0)=,k,，确定,x,k,为换入变量，按,规则计算,(5),以,a,lk,为主元素进行迭代,(,即用高斯消去法或称为旋转运算,),，把,x,k,所对应的列向量,将,X,B,列中的,x,l,换为,x,k,，得到新的单纯形表。重复,(2),(5),，直到终止。,现用例,1,的标准型来说明上述计算步骤。,(1),取松弛变量,x,3,x,4,x,5,为基变量，它对应的单位矩阵为基。这就得到初始基可行解,X,(0),=(0,0,8,16,12),T,将有关数字填入表中，得到初始单纯形表，见表,1-3,。表中左上角的,c,j,是表示目标函数中各变量的价值系数。在,C,B,列填入初始基变量的价值系数，它们都为零。,目标函数中各变量的价值系数,。,1.,计算检验数，由它确定为换人变量,2.,计算,，由它确定为换出变量,3.,确定主元素,表,1-3,基变量,计算非基变量的检验数,各非基变量的检验数为,1,=c,1,-z,1,=2-(01+04+00)=2,2,=c,2,-z,2,=3-(02+00+04)=3,填入表,1-3,的底行对应非基变量处。,进行（,2,），（,3,）,它所在行对应的,x,5,为换出变量，,x,2,所在列和,x,5,所在行的交叉处,4,称为主元素或枢元素,(pivot element),。,（,4,）,以,4,为主元素进行旋转运算或迭代运算，即初等行变换，使,P,2,变换为（,0,0,1,）,T,在,X,B,列中将,x,2,替换,x,5,于是得到新表,1-4,。,换人变量,换出变量,主元素,(5),检查表,1-4,的所有,c,j,-z,j,这时有,c,1,-z,1,=2,；说明,x,1,应为换入变量。重复,(2),(4),的计算步骤，得表,1-5,。,还存在检验数0，继续进行。,换人变量,换出变量,主元素,(6),表,1-6,最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解,c,j,2,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,X,4,x,5,2,x,1,4,1,0,1,1/4,0,0,x,5,4,0,0,-2,1/2,1,3,x,2,2,0,1,1/2,-1/8,0,c,j,-z,j,0,0,-3/2,-1/8,0,最优解,X,*,=X,(3),=(4,2,0,0,4),T,目标函数的最大值,z,*,=14,课堂练习,用单纯形法求解下列线性规划问题。,Max Z=x,1,+x,2,+3x,3,x,1,+x,2,+2x,3,40,x,1,+2x,2,+x,3,20,x,2,+x,3,15,x,1,、,x,2,、,x,3,0,C,j,1,1,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,40,1,1,2,1,0,0,20,0,x,5,20,1,2,1,0,1,0,20,0,x,6,15,0,1,1,0,0,1,15,C,j,-Z,j,1,1,3,0,0,0,参考答案,C,j,1,1,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,10,1,-1,0,1,0,-2,10,0,x,5,5,1,1,0,0,1,-1,5,3,x,3,15,0,1,1,0,0,1,C,j,-Z,j,1,-2,0,0,0,-3,参考答案,C,j,1,1,3,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,5,0,-2,0,1,-1,-1,1,x,1,5,1,1,0,0,1,-1,3,x,3,15,0,1,1,0,0,1,C,j,-Z,j,0,-3,0,0,-1,-2,参考答案,X=(5,0,15),T,，,Z=50,