与清华大学《运筹学》教材相应的授课文档第一章.ppt

1,第一章线性规划与单纯形法,1线性规划问题及其数学模型1.1问题的提出eg.1生产计划问题问：产品、各生产多少件，使利润最大？,2,eg.2污水处理问题环保要求河水含污低于2，河水可自身净化20%。问：化工厂1、2每天各处理多少污水，使总费用最少？,分析：化工厂1处理污水x1万m3,化工厂2处理污水x2万m3。minz=1000 x1+800 x2(2-x1)/5002/1000(1-0.2)(2-x1)+1.4-x2/(500+200)2/1000 x12x21.4x1，x20这里minz:表示求z的最小值。,3,线性规划的数学模型：max(min)z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2am1x1+am2x2+amnxn(=,)bmx1，x2，xn0,4,说明：,(1)决策变量：x1，x2，xn。一组决策变量表示为问题的一个方案；(2)目标函数：max(min)zz为决策变量的线性函数;(3)约束条件一组线性不等式。cj为价值系数,bi为资源，aij为技术系数(i=1,m;j=1,n).,5,1.2图解法eg.3用图解法求eg.1。maxz=2x1+3x21x1+2x284x1164x212x1，x20,解：(1)建立x1-x2坐标；,(2)约束条件的几何表示；,(3)目标函数的几何表示；,z=2x1+3x2,o,4,3,6,首先取z=0，然后，使z逐渐增大，直至找到最优解所对应的点。,可见，在Q2点z取到最大值。因此，Q2点所对应的解为最优解。Q2点坐标为(4，2)。即:x1=4，x2=2由此求得最优解：x1*=4x2*=2最大值：maxz=z*=2x1+3x2=14(元),4,3,7,讨论：(1)唯一最优解maxz=z*时，解唯一，如上例。,(2)无穷多最优解eg.4对eg.1，若目标函数z=2x1+4x2，此时表示目标函数的直线与表示条件的直线平行，最优点在线段Q3Q2上。即存在无穷多最优解。,8,(3)无界解eg.5maxz=2x1+3x24x116x1，x20则x2，z。即存在无界解。在实际问题中，可能是缺少约束条件。,9,(4)无可行解eg.6maxz=2x1+3x22x1+4x28x1+x21x1，x20无公共部分，无可行域。即无可行解。在实际问题中，可能是关系错。,10,1.3线性规划的标准型1、标准型maxz=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0,11,用向量表示,12,用矩阵描述为：maxz=CXAX=bX0其中:X=(x1,x2,xn)TC=(c1,c2,cn)b=(b1,b2,bm)T,13,2、标准型的化法(1)minmaxminz=cx=-max(-z)max(-z)=-minz=-cx令z=-z则maxz=-cx,(2)不等式(，)对于“”情况：在“”左边加上一个松弛变量（非负），变为等式；对于“”情况：在“”左边减去一个剩余变量（非负），变为等式。注意：松弛变量、剩余变量在目标函数中的价值系数为0。,(3)无约束变量令xk=xk-xk”，xk,xk”0，代入即可。,14,eg.7将下述问题化为标准型minz=-x1+2x2-3x3x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20，x3无约束,解：令x3=x3-x3”，x3,x3”0；式加上一个松弛变量x4；式减去一个剩余变量x5；令z=-zmaxz=x1-2x2+3(x3-x3”)+0 x4+0 x5x1+x2+(x3-x3”)+x4=7x1-x2+(x3-x3”)-x5=2-3x1+x2+2(x3-x3”)=5x1,x2,x3,x3”,x4,x50,15,1.4线性规划解的概念设线性规划为maxz=CXAX=bX0A为mn矩阵,nm,RankA=m(A为行满秩矩阵）,1、可行解：满足条件、的X；,2、最优解：满足条件的可行解；,3、基：取B为A中的mm子矩阵，RankB=m，则称B为线性规划问题的一个基。取B=(p1,p2,pm)pj=(a1j,a2j,amj)T则称x1,x2,xm为基变量，其它为非基变量。,16,4、基解：取B=(p1,p2,pm)a11,a1mx1a1m+1,a1nxm+1b1+=am1,ammxmamm+1,amnxnbm基基变量非基非基变量令xm+1=xn=0(非基变量为0)则BXB=b,17,5、基可行解满足式要求的基解。如右图所示，各边交点O,Q1,Q2,Q3,Q4均为基可行解；而其延长线的交点Q5为基解，但不是基可行解。,O(0,0),Q1(4,0),Q2(4,2),Q4(0,3),Q3(2,3),Q5(4,3),6、可行基基可行解对应的B为可行基。,18,2线性规划问题的几何意义2.1基本概念1、凸集：设K为En(n维欧式空间)的一点集，X(1)K，X(2)K。若X(1)+(1-)X(2)K，则称K为凸集。（01）,19,2、顶点：XK，X(1)K，X(2)K(任意两点)。若X不能用X(1)+(1-)X(2)表示，则称X为K的一个顶点。(01)注：顶点所对应的解是基可行解。3、凸组合：设X(i)En，若存在00x(0)非最优解,基变换max1,2=3=2x2入基min8/2,-,12/4=12/4x5出基,33,此时的解：x(1)=(032160)Tz(1)=9x(1)非最优x1入基x3出基,此时的解：x(2)=(23080)Tz(2)=11x(2)为最优解,即：最优解：x*=(23080)T最大值：z*=11,34,X(0)=(0081612)TO(0,0)X(1)=(032160)TQ4(0,3)X(2)=(23080)TQ3(2,3),35,4单纯形法的进一步讨论4.1人工变量法1、大M法（M为很大的正数）法则：对于max问题，人工变量在目标函数中的价值系数为-M；对于min问题，人工变量在目标函数中的价值系数为M。eg.12minz=x1+5x2+0 x3+0 x42x1+3x2+x3=62x1+x2x4=1x1,x2,x3,x40解：minz=x1+5x2+0 x3+0 x4+Mx5：x5为人工变量2x1+3x2+x3=62x1+x2x4+x5=1x1,x2,x3,x4,x50列单纯形表求解。,36,minz=x1+5x2+0 x3+0 x4+Mx52x1+3x2+x3=62x1+x2x4+x5