资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二节 单纯形法,Simplex Method,第二节 单纯形法Simplex Method,1,一、单纯形法原理及步骤,二、用向量矩阵描述单纯形法原理,三、单纯形表,四、,两阶段法和大,M,法,五、退化和循环,一、单纯形法原理及步骤,2,用向量矩阵描述单纯形法原理,并设 是,A,的一个基。,设标准的线性规划问题为,则 ，相应地，向量,X,和,C,可以记为,max,z,=,C,X,A,X=,b,X0,s.t.,BX,B,+,NX,N,=,b,X,B,=,B,-1,b-B,-1,NX,N,C,B,X,B,+,C,N,X,N,z,=,C,B,B,-1,b-,(C,B,B,-1,N-C,N,)X,N,用向量矩阵描述单纯形法原理并设,3,用向量矩阵描述单纯形法原理,z,=,C,B,B,-1,b-(C,B,B,-1,N-C,N,)X,N,X,N,=0,基础解,C,B,B,-1,N-C,N,=0,：任意非基变量进基，目标函数值减少，当前解已经是最优解。,检验数！,变量,x,j,的检验数：,用向量矩阵描述单纯形法原理z=CBB-1b-(CBB-1N-,4,用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路：,(1),取得初始可行基,B,、相应的基本可行解,及对应的目标函数值,(2),从当前的,非基变量,中选取一个,x,k,使,x,k,的值由当前的值,0,开始增加，,其余非基变量的值均保持零值不变。如果任何一个非基变量的值由,0,增加时，目标函数都不能增加，则当前的基已经是最优基。,用向量矩阵描述单纯形法原理基于向量矩阵的单纯形法基本思路：,5,用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路：,(3),当,x,k,的值由,0,开始增加时，当前各基变量的值也会随之变化：,1),当,x,k,的值增加时，,某些基变量的值随之减小，则必定有一个基变量,x,r,的值在,x,k,的增加过程中首先降为,0,。,这时，这个基变量,x,r,成为非基变量，而非基变量,x,k,进基成为基变量，相应地，,x,k,在矩阵,A,中相应（不在基,B,中）的列向量,p,k,将取代基变量,x,r,在基,B,中的列向量,p,r,。,此时基变换后的目标函数值必定大于原目标函数值。,用向量矩阵描述单纯形法原理基于向量矩阵的单纯形法基本思路：,6,用向量矩阵描述单纯形法原理,基于向量矩阵的单纯形法基本思路：,2),当,x,k,的值增加时，所有,基变量的值,都,随之,增加，则不会有任何基变量出基，这时,x,k,值的增加没有任何限制。,此时可行域无界，即目标函数无界,。,(4),重复步骤,(2),和,(3),，就一定可以获得最优基或确定目标函数无界。,用向量矩阵描述单纯形法原理基于向量矩阵的单纯形法基本思路：,7,用向量矩阵描述单纯形法原理,单纯形法的几何意义：,从几何意义方面解释，单纯形法就是,在可行域的边界上，沿着相邻的极点进行搜索的一种算法,。所谓相邻的极点，就是每次只有一个变量进基，一个变量出基转换前后所对应的基本可行解。我们把这两个基本可行解所对应的两个基称为“相邻的”基。,用向量矩阵描述单纯形法原理单纯形法的几何意义：从几何,8,单纯形表,根据单纯形法的向量矩阵描述，,可,得：,系,数,矩,阵,B,-1,B,-1,B,-1,=E,C,B,C,B,C,B,需要变成,0,！,单纯形表根据单纯形法的向量矩阵描述，可得：系B-1B-1B-,9,单纯形表,与基,B,对应的单纯形表,目标函数值,基变量的目标函数系数,令,则检验数,j,可以记为,单纯形表与基B对应的单纯形表目标函数值基变量的目标函数系数令,10,单纯形表,单纯形表,11,单纯形表,列出以,x,3,、,x,4,为基,变量,的单纯形表,如下。,z,2,-c,2,=-30,，最优！,X,*,=(2,1,0,0),Z*=7,旋转运算,C,j,2 3 0 0,单纯形表(2)x1进基 X3离基(3)0，最优,13,单纯形表,例,2,列出以,x,3,、,x,4,为基,变量,的单纯形表,如下。,x,2,进基,X,3,离基,(1),C,j,1 2 0 0,单纯形表例2列出以x3、x4为基变量的单纯形表如下。x2进基,14,单纯形表,(2),x,1,进基,X,4,离基,(3),x,3,进基,目标函数无界！,能确定,进基,变量，无法确定离基变量,C,j,1 2 0 0,单纯形表(2)x1进基 X4离基(3)x3进基目,15,单纯形表,例,3,标准化（加入松弛变量,x,3,、,x,4,，,z=-z,）后，,列出以,x,3,、,x,4,为基,变量,的单纯形表,如下。,(1),x,2,进基,X,3,离基,C,j,-2 2 0 0,单纯形表例3标准化（加入松弛变量x3、x4，z=-z）后，,16,单纯形表,(2),x,1,进基,X,4,离基,最优解,X,1,=(0,1,0,1),T,，,z=2,(3),最优解,X,2,=(1,2,0,1),T,，,z=2,最优解,X=t X,1,+(1-t)X,2,=(1-t,2-t,0,t),T,，,(0t1),C,j,-2 2 0 0,单纯形表(2)x1进基 X4离基最优解X1=(0,17,单纯形表,单纯形算法流程图,单纯形表单纯形算法流程图,18,单纯形表,例,4,列出以,x,3,、,x,4,为基,变量,的单纯形表,如下。,x,1,进基,X,4,离基,(1),C,j,10 5 0 0,单纯形表例4列出以x3、x4为基变量的单纯形表如下。x1进基,19,单纯形表,(2),x,2,进基,X,3,离基,(3),0,，最优！,X,*,=(1,3/2,0,0),Z*=35/2,旋转运算,C,j,10 5 0 0,单纯形表(2)x2进基 X3离基(3)0，最,20,单纯形表,例,5,引进松弛变量，标准化并初始单纯形表：,x,2,进基,X,5,离基,(1),C,j,1 2 1 0 0 0,单纯形表例5引进松弛变量，标准化并初始单纯形表：x2进基,21,单纯形表,x,3,进基,X,4,离基,(2),(3),最优解为,x,1,=0,，,x,2,=3,，,x,3,=9,，,x,4,=0,，,x,5,=0,，,x,6,=12,，,max z=15,C,j,1 2 1 0 0 0,单纯形表x3进基 X4离基(2)(3)最优解为x,22,docin/sanshengshiyuan,doc88/sanshenglu,更多精品资源请访问,docin/sanshengshiyuan 更多精品,23,
展开阅读全文