《管理运筹学》课件02-单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 单纯形法,Simplex Method,SM,1,第2章 单纯形法,2.1 单纯形法的基本思想,2.2 单纯形法的计算过程,2.3 人工变量法,2.4 单纯形法补遗,第2章 单纯形法,2,第2章 单纯形法,2.1,单纯形法的基本思想,单纯形法有三种形式：,方程组形式,表格形式,矩阵形式,2.1.1 方程组形式的单纯形法,思路,：,由一个基本可行解转化为另一个基本可行解。,s.t.,x,1,+,x,3,=,8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,x,1 ，,x,2 ，,x,3，,x,4，,x,5,0,max,z,=,3,x,1,+,5,x,2,z,-,3,x,1,-,5,x,2,=,0,例1,范例,等价改写为,s.t.,z,-,3,x,1,-,5,x,2,=,0,x,1,+,x,3,=,8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,x,1 ，,x,2 ，,x,3，,x,4，,x,5,0,max,z,目标方程,3,第2章 单纯形法,2.1,单纯形法的基本思想,0 0,0,1,0,0 0,1,典式,条 典,当前基：m阶,排列阵,目标方程,中：一切基变量,的系数,j,=,0,Z,-,3,x,1,-,5,x,2,=,0,x,1,+,x,3,=,8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,(,),0,最优性检验：,一切,j,0,？,初始基本可行解,X,0,=,(0,0,8,12,36,),T,z,0,=,0,排列阵,：,每行每列有且仅有一个元素,为,1,，其余元素全为,0,的方阵。,1,=,-,3,0,2,=,-,5,0,当前解,X,0,非优；,+,0,x,3,+,0,x,4,+,0,x,5,须由,X,0,转化为另一个基本可行解,X,1,。,满足,条典,的,方程组,称为,典式,(,方程组,)。,思路,：让,X,0,中的一个,非基变量,进基,，去替换原来的一个,基变量,（,离基,）。,4,第2章 单纯形法,2.1,单纯形法的基本思想,x,1,仍为非基变量，其值为,0,。,x,3,=,8,x,4,=,12,-,2,x,2,x,5,=,36,-,4,x,2,x,2,12/2,x,2,36/4,离基,（,最小比值规则,）,：,x,2,min,，,12/2,，,36/4,=,6,x,2,=,min,，,12/2,，,36/4,=,6,x,4,x,4,为,离基变量,进基,（,最小检验数规则,）：,在,负检验数,中选择,最小的,进基,。,min,j,j,0 =,k,x,k,进基,min,-,3,，,-,5 =,-,5,=,2,x,2,进基,0,0,0,=,=,12,X,1,=,(,12,0,6,8,0,),T,z,-,3,x,1,-,5,x,2,=,0,x,1,+,x,3,=,8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,(,),0,由,有,5,第2章 单纯形法,2.1,单纯形法的基本思想,主方程,0,主列,进基,主元,z,-,3,x,1,-,5,x,2,=0,x,1,+,x,3,=8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,(),-,6,9,比值,min,离基,以,主列,中,正值元素,为,分母,，同行,右端常数,为,分子,，求,比值,；,按,最小,比值,规则,确定,主方程,和,主元素,，以及,离基变量,。,6,第2章 单纯形法,X,0,=(0,0,8,12,36 ),T,z,0,=0,(,),x,1,+,x,3,=8,3,x,1,-,2,x,4,+,x,5,=,12,得,X,1,=,z,0,=30,称为单纯形法的一次,迭代,。,z,-,3,x,1,-,5,x,2,=,0,x,1,+,x,3,=,8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,(,),2,0,x,2,+,x,4,=6,1,2,z-3,x,1,+,x,4,=,30,0,5,2,(,12,0,6,8,0,),T,换基运算,方程组,的,初等变换,目的,是把,主列,变为,单位向量,：主元,变,为,1,，其余变为,0,。,用,换基运算,将,X,0,转化为,另一个基本,可行解,X,1,。,0,0,1,0,2.1,单纯形法的基本思想,7,第2章 单纯形法,2.1,单纯形法的基本思想,(,),x,1,-,x,4,+,x,5,=,4,2,3,1,3,x,2,+,x,4,=,6,1,2,(,),x,1,+,x,3,=8,3,x,1,-,2,x,4,+,x,5,=,12,x,2,+,x,4,=6,1,2,z,-,3,x,1,+,x,4,=30,0,5,2,x,3,+,x,4,-,x,5,=,4,2,3,1,3,z,+,x,4,+,x,5,=42,0,1,2,得,X,*,=,(,4,6,4,0,0,),T,z*,=,42,8,-,4,min,比值,1,0,8,第2章 单纯形法,2.1,单纯形法的基本思想,2.1.2 单纯形法的几何意义,D(0,6),O(0,0),C(4,6),B(8,3),A(8,0),x,1,x,2,z,=,0,脊线,(4,6,4,0,0),T,(0,0,8,12,36),T,(0,6,8,0,12),T,z,法向,或,棱线,9,第2章 单纯形法,单纯形表,范例,:基于,典式,标准形,c,j,基,解,x,1,x,2,x,3,x,4,x,5,3,5,0 0,0,比 值,1,0,1 0,0,x,3,x,4,x,5,8,12,36,0,2,0 1,0,0,0,0,3,4,0 0,1,0 0,0,0,-,3,-,5,检验行,C,B,b,3,5,2.2,单纯形法的计算过程,s.t.,x,1,+,x,3,=,8,2,x,2,+,x,4,=,12,3,x,1,+,4,x,2,+,x,5,=,36,x,1 ，,x,2 ，,x,3，,x,4，,x,5,0,max,z,=,3,x,1,+,5,x,2,z,0,=,C,B,b,T,检验行,计算公式,j,=,C,B,a,j,-,c,j,T,j=1,2,n,10,第2章 单纯形法,2.2,单纯形法的计算过程,初始单纯形表,的一般形式,11,第2章 单纯形法,2.2,单纯形法的计算过程,2.2.2 单纯形法的计算步骤,1,把LP问题化为,标准形,。,2,在系数阵中找出或构造一个,m阶,排列阵,作为初始,可行基，建立,初始单纯形表,。,3,最优性检验,:若所有检验数,j,0，就得到一个,最优基本解，停止计算；否则转,4,。,4,解无界判断,:在所有,j,0中,只要有一个,r,0,所对应的系数列向量,a,r,0,，即一切,a,ir,0，i,=,1,2,m,则该LP问题,解无界,，停止计算；否则转,5,。,预,备,步,骤,迭,代,步,骤,12,第2章 单纯形法,2.2,单纯形法的计算过程,5,确定主元,先按,最小检验数规则,min,j,j,0,=,a,ik,b,i,a,l,k,b,l,迭,代,步,骤,13,第2章 单纯形法,2.2,单纯形法的计算过程,2,.,2,.,3 单纯形法计算之例,范例,第0次迭代,c,j,基,解,x,1,x,2,x,3,x,4,x,5,3,5,0 0,0,比 值,1,0,1 0,0,x,3,x,4,x,5,8,12,36,0,2,0 1,0,0,0,0,3,4,0 0,1,0,-,3,-,5,0 0,0,-,6,9,min,2,14,第2章 单纯形法,2.2,单纯形法的计算过程,第一次迭代,c,j,基,解,x,1,x,2,x,3,x,4,x,5,3,5,0 0,0,比 值,1,0,1 0,0,x,3,x,4,x,5,8,12,36,0,2,0 1,0,0,0,0,3,4,0 0,1,0,-,3,-,5,0,0,0,-,6,9,min,2,x,3,x,2,x,5,0,5,0,1/2,8,1,0,1,0,0,-,2,5/2,4,min,1,6,0,0,0,12,3,0,0,1,30,-,3,0,0,0,8,-,15,第2章 单纯形法,2.2,单纯形法的计算过程,c,j,基,解,x,1,x,2,x,3,x,4,x,5,3,5,0 0,0,比 值,1,0,1 0,0,x,3,x,2,x,5,8,6,12,0,1,0,1/2,0,0,5,0,3,0,0,-,2,1,30,-,3,0,0 5/2,0,x,3,x,2,x,1,0,5,3,6,0,1,0 1/2,0,4,0,0,1,2/3,-,1/3,4,1,0,0,-,2/3,1/3,42,0,0,0,1/2,1,8,-,4,min,3,X,*,=,(4,6,4,0,0),T,z,*,=,42,第二次迭代,16,第2章 单纯形法,2.2,单纯形法的计算过程,s.t.,max,z=3,x,1,+,2,x,2,-,2,x,1,+,x,2,2,x,1,-,3,x,2,3,x,1，,x,2,0,s.t.,max,z=3,x,1,+,2,x,2,-,2,x,1,+,x,2,+,x,3,=,2,x,1,-,3,x,2,+,x,4,=,3,x,1，,x,2，,x,3，,x,4,0,c,j,基,解,x,1,x,2,x,3,x,4,3,2,0,0,-,2,1 1,0,x,3,x,4,2,3,1,-,3,0,1,0,0,0,-,3,-,2,0,0,1,3,1,-,3,0,1,x,3,x,1,0,3,8,0,-,5,1,2,9,0,-,11,0,3,解无界,例2,求解下述,LP,问题,17,第2章 单纯形法,2.3,人工变量法,考虑,标准型,(M)：,分别给每个约束方程,硬性加入,一个非负变量,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,+,x,n+1,=,b,1,(0),a,12,x,1,+,a,22,x,2,+,+,a,2n,x,n,+,x,n+2,=,b,2,(0),a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,+,x,n+m,=,b,m,(0),n,个,x,n+1,x,n+2,x,n+m,称为,人工变量,。,初始基本可行解：,(,人造基本解,),X,0,=(0,0,0,b,1,b,2,b,m,),T,(,2,.,1,),18,第2章 单纯形法,基本思想：,人造解,X,0,不是原,LP,问题的基本可行解。,但若能通过单纯形法的迭代步骤，将虚拟,的人工变量都替换出去，都变为非基变量（即,人工变量,x,n,+,1,=,x,n,+,2,=,=,x,n,+,m,=,0,），则,X,0,的,前,n,个分量就构成原,LP,问题的一个基本可行解。,反之，若经过迭代，不能把人工变量都变,为非基变量，则表明原,LP,问题,无可行解,。,2.3,人工变量法,19,第2章 单纯形法,2.3,人工变量法,大,M,法,在原问题的目标函数中添上全部人工变量，并令其系数 都为,-,M,，,而,M,是一个,充分大的正数,。即,max z,=,c,1,x,1,+,c,2,x,2,+,c,3,x,3,+,+,c,n,x,n,M,(,x,n+1,+,x,n+2,+,+,x,n+m,),由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系,数的人工变量从基变量中替换出去。,若迭代最终得到,最优解,X*,，而且,基变量,中,不含有人工变量,，则,X*,的,前n个分量就构成原问题的一个,最优基本解,；否则，原问题,无可行解,。,若迭代结果是,解无界,，而且,基变量,中,不含有人工变量,，则原问题也,解无界,；否则，原问题,无可行解,。,20,第2章 单纯形法,2.3,人工变量法,例3,用大,M,法求解下述LP问题,max z,=,3,x,1,x,2,2,x,3,3,x,1,+,2,x,2,3,x,3,=,6,x,1,2,x,2,+,x,3,=,4,x,1，,