运筹学02单纯形法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,设线性规划的标准形式：,max z=c,j,x,j,(1),s.t.a,ij,x,j,=b,i,i=1,2,m(2),x,j,0 j=1,2,n (3),可行域,：由约束条件,(2),、,(3),所围成的区域；,可行解,：满足,(2),、,(3),条件的解,X=(x,1,，,x,2,，,，,x,n,),T,为,可行解,；,基,：设,A,是约束条件方程组的,m,n,维系数矩阵,其秩为,m,，,B,是,A,中,m,m,阶非奇异子矩阵，则称,B,为线性规划问题的一个,基,。,设,复习,:,线性规划问题解的概念,B=,=(p,1,p,2,p,m,),a,11,a,12,a,1m,a,21,a,22,a,2m,a,m1,a,m2,a,mm,基向量、非基向量、基变量、非基变量：,称,p,j,(j=1,2,m,）为,基向量,，其余称为,非基向量,；,与基向量,p,j,(j=1,2,m,）对应的,x,j,称为,基变量,，其全体写成,X,B,=,（,x,1,，,x,2,，,，,x,m,）,T,；否则称为,非基变量,，其全体经常写成,X,N,。,基解,：对给定基,B,设,X,B,是对应于这个基的基变量,X,B,=(x,1,，,x,2,，,，,x,m),T,；,令非基变量,x,m+1,=x,m+2,=,=x,n,=0,，,由（,2,）式得出的解,X=,（,x,1,，,x,2,，,，,x,m,，,0,，,，,0,）,T,称为,基解,。,基可行解,：所有决策变量满足非负条件,(x,j,0),的基解,称作,基可行解,。,可行基,：基可行解所对应的基底称为,可行基,。,写出下述线性规划问题对应的基、基变量、基解、基可行解和可行基。,定理,2,：,X,是线性规划问题的基可行解的充要条件是它对应于可行域,D,的顶点。（线性规划问题的基可行解,X,对应于可行域,D,的顶点。）,定理,3,：,若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优,.,3,单纯形法（,Simplex Method,）,例子：,求解线性规划问题,线性规划问题的最优解，可以从基可行解中找到,图解法有局限性；,枚举法计算量大；,3.1,单纯形法的引入,0,Q,4,Q,3,1,1,2,3,2,3,4,Q,2,Q,1,X,1,X,2,x,1,+2x,2,=8,4x,1,=16,4x,2,=12,解,:,首先,:,将该问题化成标准形,第二,:,找初始可行解,(,即一个顶点,),。,系数矩阵,A=(p,1,p,2,p,3,p,4,p,5,),矩阵形式,因为,p,3,，,p,4,，,p,5,线性独立，故,B=(p,3,p,4,p,5,),构成一个基底，对应的基变量,x,3,，,x,4,，,x,5,解出来为（用非基变量表示基变量）,x,3,=8-x,1,-2x,2,x,4,=16-4x,1,(a),x,5,=12-4x,2,将,(a),代入目标函数中得,z=0+2x,1,+3x,2,令非基底变量,x,1,=x,2,=0,，则有,z=0,。这时得到一个基可行解,X,(0),=(0,0,8,16,12),T,-,原点,第三,:,判别,从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步,第四,:,换基底,(,旋转迭代,),确定换入变量：由于,z=0+2x,1,+3x,2,中非基底变量,x,2,系数贡献最大,3,，故换入基底为,x,2,。,换入变量已定，必须从,x,3,，,x,4,，,x,5,换出一个，并且要保证其余均是非负的，即,x,3,，,x,4,，,x,5,0,。,x,3,=8-2x,2,0,x,4,=16,0,x,5,=12-4 x,2,0,由此，只要选择,x,2,=min(8/2,，,-,，,12/4)=3,，对应基底变量,x,5,=0,，从而确定用,x,2,和,x,5,对调，即将,x,5,换出。有,x,3,=2-x,1,+1/2x,5,x,4,=16-4x,1,(b),x,2,=3-1/4 x,5,将,(b),代入目标函数中得,z=9+2x,1,-3/4x,5,令非基变量为零，又得到另一个基可行解,X,(1),=(0,3,2,16,0),T,顶点,Q,4,返回 第三步：非基变量,x,1,的系数是正的，还可增大，,X,(1),不是最优解。重复上述步骤。由于,x,1,的系数是正的，从而,x,1,为转入变量，再由,x,3,=2-x,1,0,x,4,=16-4 x,1,0,x,2,=3,0,只要选,x,1,=min2,，,16/4,，,-=2,上式就成立，因为,x,1,=2,时，基变量,x,3,=0,，从而由,x,1,换出,x,3,，得,x,1,=2-x,3,+1/2x,5,4x,1,+x,4,=16,(c),x,2,=3-1/4 x,5,高斯消去法（行变换）得,x,1,=2-x,3,+1/2x,5,x,4,=8-2 x,5,+4 x,3,x,2,=3-1/4 x,5,代入目标函数中，得,z=13-2 x,3,+1/4x,5,令非基变量,x,3,=x,5,=0,，又得到另一个基可行解,X,(2),X,(2),=(2,3,0,8,0),T,新顶点,Q,3,同理，返回第三步，再迭代，,x,5,作为转入变量,x,1,=2+1/2x,5,0,x,4,=8-2 x,5,0,x,2,=3-1/4 x,5,0,只要取,x,5,=min-,，,8/2,，,12=4,就有上式成立。,x,5,=4,时，,x,4,=0,，故决定用,x,5,换,x,4,x,1,=4-1/4 x,4,x,5,=4-1/2 x,4,+2 x,3,x,2,=2+1/8 x,4,1/2 x,3,代入得,z=14-3/2 x,3,1/8 x,4,，令,x,3,，,x,4,=0,得,z=14,。新基可行解为,X,(3),=(4,2,0,0,4),T,为最优解，新顶点,Q,2,最优目标值,z=14,。,从实际例子中分析单纯形法原理的基本框架为,第一步：将线性规划模型变换成标准型，确定一个初始可行解（顶点）。,第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。,第三步：从初始基可行解向相邻的基可行解（顶点）转 换，且使目标值有所改善,目标函数值增加，重复第二和第三步直到找到最优解。,3.2,初始可行基的确定,设线性规划问题：,为了确定初始基可行解，首先要找出初始可行基，其方法如下：,从,P,j,(j=1,2,n),中一般能直接观察到存在一个,初始可行基,确定初始可行基的几种方法：,形式的不等式,形式的不等式,=,的情形,观察,“,小加大减,+,人造”,约束是,形式的不等式，可以利用化标准型的方法，左端加一个松弛变量，经过整理，重新对,x,j,及,a,ij,（,i=1,2,m,；,j=1,，,2,，,，,n,）进行调整编号，则可得下列方程组,“,小加”,x,1,+a,1,m+1,x,m+1,+,+a,1n,x,n,=b,1,x,2,+a,2,m+1,x,m+1,+,+a,2n,x,n,=b,2,x,m,+a,m,m+1,x,m+1,+,+a,mn,x,n,=b,m,x,j,0,，,j=1,2,n,显然得到一个,m,m,单位矩阵,注意：,a,ij,和,b,i,已经变化,移项整理得,x,1,=b,1,-,a,1,m+1,x,m+1,-,-a,1n,x,n,x,2,=b,2,a,2,m+1,x,m+1,-,-a,2n,x,n,x,m,=b,m,a,m,m+1,x,m+1,-,-a,mn,x,n,令,x,m+1,=x,m+2,=,=x,n,=0,，可得,x,i,=b,i,（,i=1,，,2,，,，,m,）,又因,b,i,0,，所以得到一个,初始基可行解：,X,（,0,）,=,（,x,1,x,2,x,m,0 ,0),T,=(b,1,b,2,b,m,0 ,0),T,非基向量可以用基向量的线性组合表示,将,(3),式乘以一个正的数,0,得到,记初始基可行解为,X,(0),有,该解满足约束方程,即,3.3,从初始基可行解转换为另一基可行解,(4),式和,(1),式相加,整理后得到,由,(5),式可以找到满足约束方程的另一个点,X,(1),其中是点,X,(1),的第,j,个坐标值,要使,X,(1),是一个基本可行解,则要求,并且这,m,个等式中至少要有一个等号成立,当 时,(6),式必然成立,当 时,令,因此有,所以,X,(1),中的正分量最多有,m,个,可证明,m,个向量,P,1,P,s-1,P,s+1,P,m,P,j,线性无关,按照式,(7),确定,值,X,(1),就是一个新的基可行解,.,线性规划解的,四种可能：,1,、有唯一解；,2,、无穷多最优解；,3,、无界解；,4,、无可行解。,何时达最优解,何种最优解？,3.4,最优性检验和判别定理,将基本可行解,X,(0),和,X,(1),分别代入目标函数得,由此,j,称做检验数,是对线性规划问题的解进行最优性检验的标志,.,最优解的判别定理,：,且对一切的,j=m+1,.,n,有,则,X,(0),为最优解。,若 是一个基可行解，,无穷多最优解判别定理,：,若 是一个基可行解，,且对一切的,j=m+1,.,n,有,又存在某个非基变量的检验数 则线性规划问题有无穷多最优解。,无界解的判别定理,：,3.5,基变换,换入变量的确定,:,max(,j,0)=,k,j=m+1,n;x,k,是换入变量,(,也可任选,).,换出变量的确定,:,确定换出变量的原则是保持解的可行性,就是说要使原基可行解的某一正分量,x,s,变成零,同时保持其它的分量均非负,(,换基原则,)min(x,i,/a,ij,|a,ij,0)=x,s,/a,sj,=,s1,2,m,(,最小比值准则,或,准则,),3.6,旋转运算,在确定换入变量,x,k,和换出变量,x,s,以后，要把,x,k,所对应的系数列向量,p,k,变成单位向量，为此,只要对系数矩阵的增广阵进行“行”的初等变换即可。行变换的定义：,(,第,s,行,),*,1/,a,sk,得,:,当,i,s,时,(,第,i,行,)-(,第,s,行,)*,a,ik,经过初等变换后,新的增广矩阵是,4,单纯形法的计算步骤和单纯形表,约束方程组和目标函数组成,n+1,个变量,m+1,个方程的方程组,该方程组对应的增广矩阵是,确定初始单纯形表后可以得到初始基可行解,x,0,若有某个非基底变量,x,k,对应的检验数,k,=(c,k,-z,k,)0,则当前解不是最优解，,取使目标增长最大的非基底变量进入基底。,根据 确定,x,k,为换入变量,根据 确定,x,s,为换出变量,将,x,k,对应的列向量,P,k,=(a,1k,a,sk,a,nk,),T,变换为,a,ik,=0,，,i s,a,ik,=1,，,i=s,重复上述步骤直到所有的检验数满足最优条件，得最优解。,5,单纯形法的进一步讨论,人工变量法（确定初始可行基）：,原约束方程：,AX=b,加入人工变量：,x,n+1,，,，,x,n+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。,1,、大,M,法,方法,：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-,M,）。,理由,：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。,例,1,：用大,M,法求解如下线性规划问题,11 1 -2 1 1 0 0 0 11,3 -4 1 2 0 -1 1 0 3/2,1 -2 0 1 0 0 0 1 1,0,M,1,6,x,x,4,x,3,10 3 -2 0 1 0 0 -1,1 0 1 0 0 -1 1 -2 1,1 -2 0 1 0 0 0 1,-3,x,1,1,x,2,1,x,3,4 1 0 0 1/3 -2/3 2/3 -5/3,1 0 1 0 0 -1 1 -2,9 0 0 1 0 2/3 4/3 -7/3,-3 1 1 0 0,M M,-1 0 0 0 1 M-1 M+1,z,j,-,c,j,0 0 0 1/3 1/3,M,-1/3,M,-2/3,z,j,-,c,j,0,x,4,1,x,2,1,x,3,12 3 0 0 1 -2 2 -5 4,1 0 1 0 0 -1 1 -2,1 -2 0 1 0 0 0 1,c,j,0MM,X,4,X,6,X,7,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,X,6,X,7,i,-3+6M 1-M 1-3M 0 M 0 0,c,j,-z,j,-1 1-M 0 0 M 0 3M-1,c,j,-z,j,最优解是,目标函数为,-2,。,2,、两阶段法,第一阶段：,建立一个辅助线性规划并求解，,以此判断原线性规划是否存在可行解,。,辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准型的约束条件。,所有人工变量都变成非基变量，目标函数值为,0,，原问题存在基可行解。转到第二阶段。,若目标函数值不为,0,，至少有一个人工变量不能从基变量中转出，原问题没有可行解。停止。,第二阶段：,从第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，用单纯形法计算，直到得到最优解为止。,第一阶段：求解辅助规划问题,11 1 -2 1 1 0 0 0 11,3 -4 1 2 0 -1 1 0 3/2,1 -2 0 1 0 0 0 1 1,0,1,0,6,x,x,4,x,3,10 3 -2 0 1 0 0 -1,1 0 1 0 0 -1 1 -2 1,1 -2 0 1 0 0 0 1,0 0 0 0 0,1 1,0 0 0 0 0 1 1,z,j,-,c,j,0,x,4,0,x,2,0,x,3,12 3 0 0 1 -2 2 -5 4,1 0 1 0 0 -1 1 -2,1 -2 0 1 0 0 0 0,c,j,0 1 1,X,4,X,6,X,7,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,X,6,X,7,i,6 -1 -3 0 1 0 0,c,j,-z,j,0 -1 0 0 1 0 3,c,j,-z,j,12 3 0 0 1 -2 4,1 0 1 0 0 -1,1 -2 0 1 0 0,-3,1,1,2,x,x,1,x,3,4 1 0 0 1/3 -2/3,1 0 1 0 0 -1,9 0 0 1 2/3 -4/3,-3 1 1 0 0,c,j,0 1 1,X,4,X,2,X,3,b,C,B,X,B,X,1,X,2,X,3,X,4,X,5,i,-1 0 0 0 1,c,j,-z,j,0 0 0 1/3 1/3,c,j,-z,j,x,6,，,x,7,是人工变量，第一阶段求解的最优结果是,=0,，因此得最优解为：,第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。,最优解为：,最优值为：,z=-2,两阶段法：,辅助规划；去掉人工变量，单纯形法。,对目标函数求,max,的线性规划问题,用单纯形法计算步骤的框图,唯一最优解,N,N,N,Y,Y,Y,添加松弛变量,、,人工变量,列出初始单纯形表,计算非基变量,对应的检验数,j,所有,j,0,基变量中,有非零的,人工变量,某非基变量检验数为零,无可行解,无穷多最优解,对某,j,0,有,a,ij,0,无界解,令,k,=max,j,对所有,a,ik,0,计算,i,=b,i,/a,ik,令,s,=min,i,x,s,为换出变量,a,sk,为主元素,迭代运算,.,用非基变量,x,k,替换基变量,x,s;,.,对主元素行,(,第,s,行,),，令,b,s,/a,sk,b,s,;a,sj,/a,sk,a,sj,.,对主元素列,(,第,k,列,),，令,1a,sk,；,0,其它元素,表中其它行列元素,令,a,ij,-a,sj,/a,sk,a,ik,a,ij,b,i,-b,s,/a,sk,a,ik,b,i,Y,N,用单纯形法求解以下问题。,用单纯形法求解以下问题。,例,1,：,max z=2,x,1,+3x,2,x,1,+2x,2,8,s.t.,4x,1,16,x,1,x,2,0,例,2,：,max z=2x,1,+4x,2,x,1,+2x,2,8,s.t.4x,2,12,3x,1,12,x,1,x,2,0,例,3,：,例,4,：,max z=4x,1,+3x,2,-3x,1,+2x,2,6,s.t.-x,1,+3x,2,18,x,1,x,2,0,例,3,：无可行解,例,4,：,(18/7,48/7),用大,M,法和两阶段法求解以下问题,