第二讲：线性规划算法

.,第二讲：线性规划算法,.,线性规划标准型,代数式maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmxj0j=1,2,n,.,线性规划标准型,和式：maxZ=cjxjaijxj=bii=1,2,mxj0j=1,2,n,向量式：maxZ=CTXpjxj=bii=1,2,mxj0j=1,2,n,矩阵式：maxZ=CTXAX=bX0,.,线性规划解的概念,.,线性规划解的性质,可行域凸集（凸多面体）可行域非空至多有有限个顶点最优解若存在，必可在顶点达到线性规划的基本定理：线性规划的基本可行解就是可行域的极点。这一定理的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。,.,计算流程,线性规划的单纯形算法,.,1.初始基本可行解的确定,从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,Pm)。进行等价变换约束方程两端分别左乘B1,.,2.最优性检验,.,3.基变换转轴变换,取某一非基变量xk换入基（即让xk0，其余非基变量仍为0）,同时，再从基变量中换出一个变量xBr作为非基变量。,如何求换入变量xk和换出变量xBr？K=?，r=?,.,3.基变换转轴变换,从目标函数看xk越大越好，但从可行性看xk又不能任意大。若yik0,i=1,，m,xk可任意取值，此时问题是无界的；若yik0,为保证可行性，即xBi=bi-yikxk0，应取,注意：xBr=0,.,3.基变换转轴变换,新可行解：x=(xB1,xBr-1,0,xBr+1,xBm,0,，0,xk,0,，0)可以证明此解为新的基本可行解。这是因为原来的基PB1,PBm线性无关，而yk=B-1Pk,故Pk=Byk=yikPBi，而PBr的系数yrk0，所以，用Pk代替Pr后的向量组PB1,Pk,PBm线性无关，所以x为基本可行解,在新的基本可行解中，目标函数比原来增加了kxk。重复上述过程，直至所有的j均0，得到最优解。因为基本可行解的个数是有限的，因此在非退化(r(A)=m)情况下，经有限次迭代必能达到最优解。,.,总结计算步骤：给定初始基B,步1.令xN=0,，xB=B-1b=b，z0=cBTxB；步2.检验数j=cj-cBTB-1Pj，j0，停止，得最优解，否则取kmaxj，转步3；步3.解yk=B-1Pk，若yk0，停止,不存在有限最优解.否则转步4；步4.计算xk进基，xBr离基，用Pk替代PBr得新的可行基B，转步1。,.,例：用单纯形法的基本思路求解下面的线性规划问题：Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50,C=(1500,2500,0,0,0)T,b=(65,40,75)T,.,第一次迭代：（1）取初始可行基B0=(p3,p4,p5)，那么x3，x4，x5为基变量，x1，x2为非基变量。将基变量和目标函数用非基变量表示：z=1500 x1+2500 x2x3=65-3x1-2x2x4=40-2x1-x2x5=75-3x2当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5=75，z=0，得到当前的基本可行解：x(0)=(0,0,65,40,75)T，z=0。,.,（2）最优性检验：在目标函数z=1500 x1+2500 x2中，非基变量x1，x2的系数都是正数，此解非最优。取kmax1500,2500，（3）转轴变换：选择x2为进基变量，另一个非基变量x1保持零值不变。,.,确定出基变量。在约束条件x3=65-3x1-2x2x4=40-2x1-x2x5=75-3x2中，当x2的值从0开始增加时，基变量x3、x4、x5的值分别从当前的值65、40和75开始减少，当x2增加到25时，x5首先下降为0成为非基变量。这时，新的基变量为x3、x4、x2，新的非基变量为x1、x5，当前的基本可行解和目标函数值为：X(1)=(0，25，15，15，0)T，z=62500。,.,第二次迭代：（1）当前的可行基为B1=(p2,p3,p4)，那么x2，x3，x4为基变量，x1，x5为非基变量。将基变量和目标函数用非基变量表示：z=62500+1500 x1(2500/3)x5x2=25(1/3)x5x3=15-3x1+(2/3)x5x4=15-2x1+(1/3)x5,.,（2）选择进基变量。在目标函数z=62500+1500 x1(2500/3)x5中，非基变量x1的系数是正数，因此x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加,另一个非基变量x5保持零值不变。(3)确定出基变量。在约束条件x2=25(1/3)x5x3=15-3x1+(2/3)x5x4=15-2x1+(1/3)x5,.,中，由于进基变量x1在两个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。这时，新的基变量为x1、x2、x4，新的非基变量为x3、x5，当前的基本可行解和目标函数值为：X(2)=(5，25，0，5，0)T，z=70000。,.,第三次迭代：（1）当前的可行基为B2=(p1,p2,p4)，那么x1，x2，x4为基变量，x3，x5为非基变量。将基变量和目标函数用非基变量表示：z=70000500 x3500 x5x1=5(1/3)x3+(2/9)x5x2=25(1/3)x5x4=5+(2/3)x3(1/9)x5,.,（2）选择进基变量。在目标函数z=70000500 x3500 x5中，非基变量x3、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x*=(5，25，0，5，0)T，最优目标值为z*=70000。我们也称相应的基B2=(p1,p2,p4)为最优基。计算结束。,.,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=CTXs.t.AX=bX0,A=(B,N),.,初始单纯形表：,xN=0,，xB=B-1b=b，z0=cBTB-1b,.,单纯形表的一般格式：,kmaxj，,ykr-换基转轴的