《线性规划算法》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二讲：线性规划算法,线性规划标准型,代数式maxZ=c,1,x,1,+c,2,x,2,+c,n,x,n,a,11,x,1,+a,12,x,2,+a,1n,x,n,=b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,=b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,=b,m,x,j,0,j,=1,2,n,线性规划标准型,和式：,maxZ=,c,j,x,j,a,ij,x,j,=b,i,i=1,2,m,x,j,0,j,=1,2,n,向量式：maxZ=C,T,X,p,j,x,j,=b,i,i,=,1,2,m,x,j,0,j,=,1,2,n,矩阵式：,maxZ=C,T,X AX=b X,0,线性规划解的概念,线性规划解的性质,可行域凸集（凸多面体）,可行域非空至多有有限个顶点,最优解若存在，必可在顶点达到,线性规划的基本定理：,线性规划的基本可行解就是可行域的极点。,这一定理的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。,计算流程,线性规划的单纯形算法,初始基本可行解,是否最优解或,无限最优解?,结束,沿边界找新,的基本可行解,N,Y,1.初始基本可行解的确定,从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,Pm)。进行等价变换约束方程两端分别左乘B1,2.最优性检验,3.基变换转轴变换,取某一非基变量x,k,换入基（即让x,k,0，其余非基变量仍为0）,同时，再从基变量中换出一个变量x,Br,作为非基变量。,如何求换入变量x,k,和换出变量x,Br,？K=?，r=?,3.基变换转轴变换,从目标函数看x,k,越大越好，但从可行性看x,k,又不能任意大。,若y,ik,0,i=1,，m,x,k,可任意取值，此时问题是无界的；,若y,ik,0,为保证可行性，即x,Bi,=b,i,-y,ik,x,k,0，应取,注意：x,Br,=0,3.基变换转轴变换,新可行解：,x,=(x,B1,x,Br-1,0,x,Br+1,x,Bm,0,，0,x,k,0,，0),可以证明此解为新的基本可行解。这是因为原来的基P,B1,P,Bm,线性无关，而y,k,=B,-1,P,k,故P,k,=By,k,=y,ik,P,Bi,，而P,Br,的系数y,rk,0，,所以，用P,k,代替P,r,后的向量组P,B1,P,k,P,Bm,线性无关，所以x为基本可行解,在新的基本可行解中，目标函数比原来增加了,k,x,k,。,重复上述过程，直至所有的,j,均0，得到最优解。因为基本可行解的个数是有限的，因此在非退化(r(A)=m)情况下，经有限次迭代必能达到最优解。,总结计算步骤：给定初始基B,步1,.令x,N,=0,，x,B,=B,-1,b=b，z,0,=c,B,T,x,B；,步2.,检验数,j,=c,j,-c,B,T,B,-1,P,j,，,j,0，停止，得最优解，否则取,k,max,j,，转步3；,步3.,解y,k,=B,-1,P,k,，若y,k,0，停止,不存在有限最优解.否则转步4；,步4,.计算,x,k,进基，x,Br,离基，用P,k,替代P,Br,得新的可行基B，,转步1。,例：用单纯形法的基本思路求解下面的线性规划问题：,Max,z,=1500,x,1,+2500,x,2,s.t.3,x,1,+2,x,2,+,x,3,=65,2,x,1,+,x,2,+,x,4,=40,3,x,2,+,x,5,=75,x,1,x,2,x,3,x,4,x,5,0,C=(1500,2500,0,0,0),T,b=(65,40,75),T,第一次迭代：,（1）取初始可行基,B,0,=(,p,3,p,4,p,5,)，那么,x,3,，x,4,，x,5,为基变量，,x,1,，x,2,为非基变量。将基变量和目标函数用非基变量表示：,z,=1500,x,1,+2500,x,2,x,3,=65-3,x,1,-2,x,2,x,4,=40-2,x,1,-,x,2,x,5,=75-3,x,2,当非基变量,x,1,，x,2,=0时，相应的基变量和目标函数值为,x,3,=65，,x,4,=40，,x,5,=75，,z,=0，得到当前的基本可行解：,x,(0),=(0,0,65,40,75),T,，,z,=0。,（2）最优性检验：,在目标函数,z,=1500,x,1,+2500,x,2,中，非基变量,x,1,，,x,2,的系数都是正数，此解非最优。取,k,max1500,2500，,（3）转轴变换：选择,x,2,为进基变量，另一个非基变量,x,1,保持零值不变。,确定出基变量。在约束条件,x,3,=65-3,x,1,-2,x,2,x,4,=40-2,x,1,-,x,2,x,5,=75 -3,x,2,中，当,x,2,的值从0开始增加时，基变量,x,3,、x,4,、x,5,的值分别从当前的值65、40和75开始减少，当,x,2,增加到25时，,x,5,首先下降为0成为非基变量。这时，新的基变量为,x,3,、x,4,、x,2,，,新的非基变量为,x,1,、x,5,，,当前的基本可行解和目标函数值为：,X,(1),=(0，25，15，15，0),T,，,z,=62500。,第二次迭代：,（1）当前的可行基为,B,1,=(,p,2,p,3,p,4,)，那么,x,2,，x,3,，x,4,为基变量，,x,1,，x,5,为非基变量。将基变量和目标函数用非基变量表示：,z,=62500+1500,x,1,(2500/3),x,5,x,2,=25 (1/3),x,5,x,3,=15-3,x,1,+(2/3),x,5,x,4,=15-2,x,1,+(1/3),x,5,（2）选择进基变量。在目标函数,z,=62500+1500,x,1,(2500/3),x,5,中，非基变量,x,1,的系数是正数，因此,x,1,进基可以使目标函数,z,增大，于是选择,x,1,进基，使,x,1,的值从0开始增加,另一个非基变量,x,5,保持零值不变。,(3)确定出基变量。在约束条件,x,2,=25 (1/3),x,5,x,3,=15-3,x,1,+(2/3),x,5,x,4,=15-2,x,1,+(1/3),x,5,中，由于进基变量,x,1,在两个约束条件中的系数都是负数，当,x,1,的值从0开始增加时，基变量,x,3,、x,4,的值分别从当前的值15、15开始减少，当,x,1,增加到5时，,x,3,首先下降为0成为非基变量。这时，新的基变量为,x,1,、x,2,、x,4,，新的非基变量为,x,3,、x,5,，,当前的基本可行解和目标函数值为：,X,(2),=(5，25，0，5，0),T,，,z,=70000。,第三次迭代：,（1）当前的可行基为,B,2,=(,p,1,p,2,p,4,)，那么,x,1,，x,2,，x,4,为基变量，,x,3,，x,5,为非基变量。将基变量和目标函数用非基变量表示：,z,=70000 500,x,3,500,x,5,x,1,=5 (1/3),x,3,+(2/9),x,5,x,2,=25 (1/3),x,5,x,4,=5+(2/3),x,3,(1/9),x,5,（2）选择进基变量。在目标函数,z,=70000 500,x,3,500,x,5,中，非基变量,x,3,、,x,5,的系数均不是正数，因此进基都不可能使目标函数,z,增大，于是得到最优解，,x,*=(5，25，0，5，0),T,，,最优目标值为,z,*=70000。,我们也称相应的基,B,2,=(,p,1,p,2,p,4,),为最优基。计算结束。,1,X,(0),=(0,0,65,40,75)T，,z,=0。对应于图中的,D,、E交点,X,(1),=(0，25，15，15，0)T，,z,=62500。对应于图中的C、D交点,。,x,*=(5，25，0，5，0)T，,z,*=70000。对应于图的,A,、,C,交点。,单纯形表,maxZ=C,T,X,=b,X,0,A=(B,N),z,x,B,x,N,右端项,0,B,N,b,1,c,B,c,N,0,z,x,B,x,N,右端项,0,I,B,-1,N=y,j,B,-1,b=b,-1,0,c,N,-c,B,T,B,-1,N,-C,B,T,B,-1,b=-z,0,初始单纯形表：,x,N,=0,，x,B,=B,-1,b=b，z,0,=c,B,T,B-1b,单纯形表的一般格式：,C,j,C,1,C,2,C,n,i,C,B,X,B,b,x,1,x,m,x,m+1,x,m+2,x,k,x,n,C,1,C,2,C,m,x,1,x,2,x,m,b,1,b,2,b,m,1 1 y,1m+1,y,1m+2,y,1k,y,1n,0 0 y,2m+1,y,2m+2,y,2k,y,2n,y,rk,0 1 y,mm+1,y,mm+2,y,mk,y,mn,1,2,m,j,z,0 0,m+1,m+2,k,n,k,max,j,，,y,kr,-换基转轴的,主元素,例2.10,Max,z,=1500,x,1,+2500,x,2,s.t.,3,x,1,+2,x,2,65,2,x,1,+,x,2,40,3,x,2,75,x,1,x,2,0,化标准形式：,Max,z=1500 x,1,+2500 x,2,s.t.,3 x,1,+2 x,2,+x,3,=65,2 x,1,+x,2,+x,4,=40,3 x,2,+x,5,=75,x,1,x,2,x,3,x,4,x,5,0,补充,