运筹学课件 单纯形法的迭代原理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学教程,四、单纯形法的迭代原理,1,、确定初始基可行解,(1),初始可行基的确定,观察法,观察系数矩阵中是否含有现成的单位阵？,LP,限制条件中全部是“”类型的约束,将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；,先将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；,然后用大,M,法或两阶段法求解；,线性规划限制条件都是“”或“,=”,类型的约束,等式约束左端引入人工变量的目的,使约束方程的系数矩阵中出现一个,单位阵,，,用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的,B(i),列（即约束方程的右边常数）值正好就是基变量的取值。,如果限制条件中既有“”类型的约束，又有“”或“,=”,类型的约束，怎么办？,构造单位阵,问题,初始可行基一定要选,单位阵,？,b,列正好就是基变量的取值，因此称,b,列为,解答列,（,2,）写出初始基可行解,令,非基变量取,0,，基变量对应,b(i),，,一起构成初始基可行解,此时,LP,的标准型为,在约束条件中的变量系数矩阵中总会有一个单位矩阵,初始可行基,：,当线性规划的约束条件均为，其松弛变量的系数矩阵为单位矩阵；当线性规划的约束条件均为或,=,，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。,初始基本可行解：,式中,p,1,p,m,为基变量,同其所对应的,x,1,x,2,.,x,m,为基变量；其它变量,x,m+1,x,m+2,，,x,n,为非基变量。令所有的非基变量等于零。,定义：两个基可行解称为相邻的，如果它们之间变换,且仅变换一个基变量。,初始基可行解的前,m,个为基变量，,2,、基变换,代入约束条件有,系数矩阵的增广矩阵,因为,p,1,p,m,是一个基，其他向量,p,j,可以这个基的线性组合表示：,相减，然后乘上一个正数,加上,经过整理得到：,找到满足约束方程组,的另一点：,第,j,个大于,0,只变换,1,个变量；,前,m,个变量必须换出,1,个,其中,是,X,（,1,）,的第,j,个坐标的值，要使,X,（,1,）,是一个基可行解，对所有的,i=1,m,存在,令这,m,个不等式至少有一个等号成立，当,是一个可行解。因为变量,x,1,1,x,2,1,x,l-1,1,x,l+1,1,x,m,1,x,j,1,所对应的向量，,经过重新排列后加行,b,列形成的增广矩阵为：,L,a,lj,(1/a,lj,)=1,r,L,(-a,l-1j,)+r,L-1,0,-(b,L,/a,Lj,)+b,L-1,所以，,P,1,P,2,P,l-1,P,j,P,l+1,P,m,是一个基。,进行初等行变换，将第,L,行乘上,1/a,lj,再分别乘以,-,a,ij,(i,=1,l-1,l+1,m),加到各行，增广矩阵,的左边变成一个单位矩阵，,、最优性检验和解的判别,将代入目标函数计算：,最优性判别,、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。,、当所有的检验数，又对某个非基变量,x,j,的检验数等于，并且可以找到,0,这表明可以找到一个顶点目标函数达到最大，说明,LP,有无穷多个最优解。,、如果存在某个检验数,0,又,0,表明目标函数达到无限，说明,LP,有无界解。,第四节 单纯形法计算步骤,第一步：求,初始基可行解，列出初始单纯形表。,将,LP,化为标准型，,并加以整理。,引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，,并且约束方程组的系数阵中有一个单位阵。,c,j,c,1,c,m,c,j,c,n,C,B,基,b,x,1,x,m,x,j,x,n,c,1,c,2,.,c,m,x,1,x,2,.,x,m,b,1,b,2,.,b,m,1,0,.,0,0,0,.,1,a,1j,a,2j,.,a,mj,a,1n,a,2n,.,a,mn,c,j-,z,j,0,0,第二步：最优性检验,计算检验数，检查：,所有检验数是否,0,？,是,结束，写出最优解和目标函数最优值；,还有正检验数,检查相应系数列,0,？,是,结束，该,LP,无界解。,不属于上述两种情况,，转入下一步,基变换。,确定是停止迭代还是转入基变换？,选择（最大）,正检验数,对应的系数列为,主元列,，主元列对应的非,基变量,x,k,为,换入变量；,最小比值,对应的行为,主元行,，主元行对应的基变量,x,l,为,换出变量,。,主元行和主元列的交叉元素,a,lk,称为主元素。,第三步：基变换,利用矩阵的初等行变换把主元列变成单位向量，主元素变为,1,，进基变量对应的检验数变成,0,，从而得到一张新的单纯形表，返回第二步。,完成一次迭代，得到新的基可行解和相应的目标函数值,该迭代过程直至下列情况之一发生时停止,检验数行全部变为非正值；,（,得到最优解）,或,主元列,0,（无界）,例题：使用单纯形法求解线性规划问题,解：化成标准形式,其约束条件系数矩阵的增广矩阵为,p,3,p,4,p,5,构成单位矩阵，对应的基变量,x,3,x,4,x,5,令非基变量,x,1,x,2,=0,找到一个初始基可行解,X=(0,0,15,24,5),T,以此列出初始单纯形表,Cj,2,1,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,0,X,3,15,0,5,1,0,0,0,X,4,24,6,2,0,1,0,0,X,5,5,1,1,0,0,1,j,=,C,j,-Z,j,=C,j,-(C,1,a,1j,+C,2,a,2j,+,C,m,a,mj,),2,1,0,0,0,1,=2-(00+06+01)=2,;,2,=1-(05+02+01)=1,3,=0-(01+00+01)=0,;,4,=0-(00+01+01)=0,5,=0-(00+00+01)=0,检验数,1,和,2,均大于,0,，所以表中的基可行解不是最优解。,1,2,，选择最大正检验数对应的系数列为主元列，,主元列对应的非基变量,X1,为换入变量；,，,Cj,2,1,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,0,X,3,15,0,5,1,0,0,0,X,4,24,6,2,0,1,0,0,X,5,5,1,1,0,0,1,j,=,C,j,-Z,j,=C,j,-(C,1,a,1j,+C,2,a,2j,+,C,m,a,mj,),2,1,0,0,0,最小比值对应的行为主元行，主元行对应的基变量,X,4,为换出变量。得到一个新的基,P,3,P,1,P,5,，列出新的单纯形表，,继续计算。,x1,2,1,4,2/6,0,1/6,0,0,1,4/6,0,1,-1/6,0,1/3,0,-1/3,0,Cj,2,1,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,0,X,3,15,0,5,1,0,0,2,X,1,4,1,2/6,0,1/6,0,0,X,5,1,0,4/6,0,-1/6,1,j,=,C,j,-Z,j,=C,j,-(C,1,a,1j,+C,2,a,2j,+,C,m,a,mj,),0,1/3,0,-1/3,0,2,最大，,X2,为进基变量；,x2,1,1,0,6/4,0,-1/4,3/2,0,1,7/2,0,1/4,-1/2,0,0,15/2,1,5/4,-15/2,0,0,0,-1/4,-1/2,X,5,为出基变量。,P,2,P,3,P,1,一个新的基,列出新的单纯形表，,继续计算。,Cj,2,1,0,0,0,C,B,基,b,X,1,X,2,X,3,X,4,X,5,0,X,3,15/2,0,0,1,5/4,-15/2,2,X,1,7/2,1,0,0,1/4,-1/2,1,X,2,3/2,0,1,0,-1/4,3/2,j,=,Cj-Zj,=Cj-(C,1,a,1j,+C,2,a,2j,+,C,m,a,mj,),0,0,0,-1/4,-1/2,1,=0,2,=0,3,=0,4,=0-(05/4+21/4-11/4)=-1/4,5,=0-(-015/2-21/2+13/2)=-1/2,所有的,0,，基变量不含有人工变量，,所以可行解,X=(7/2,3/2,15/2,0,0),T,为最优解，,代入目标函数得到,Z=8.5,小结,1,、线性规划单纯形法基本原理。,2,、单纯形法计算步骤。,作业,1.3(1)1.4(1),