清华大学运筹学课件(完整课件)

1第一章线性规划与单纯形法§1线性规划问题及其数学模型1.1问题的提出[eg.1]生产计划问题问：产品Ⅰ、Ⅱ各生产多少件，使利润最大？ⅠⅡ限制设备台时128台时材料A4016kg材料B0412kg利润23分析：设：产品Ⅰ生产x1件，产品Ⅱ生产x2件。这里z为利润函数，maxz:表示求z的最大值。目标函数：maxz=2x1+3x2约束条件：1x1+2x2≤84x1≤164x2≤12x1，x2≥02[eg.2]污水处理问题环保要求河水含污低于2‰，河水可自身净化20%。问：化工厂1、2每天各处理多少污水，使总费用最少？分析：化工厂1处理污水x1万m3,化工厂2处理污水x2万m3。minz=1000x1+800x2(2-x1)/500≤2/1000[(1-0.2)(2-x1)+1.4-x2]/(500+200)≤2/1000x1≤2x2≤1.4x1，x2≥0这里minz:表示求z的最小值。200万m3500万m32万m31.4万m3化工厂1化工厂21000元/万m3800元/万m33线性规划的数学模型：max(min)z=c1x1+c2x2+···+cnxna11x1+a12x2+···+a1nxn≤(=,≥)b1a21x1+a22x2+···+a2nxn≤(=,≥)b2┆┆am1x1+am2x2+···+amnxn≤(=,≥)bmx1，x2，···，xn≥04说明：(1)决策变量：x1，x2，···，xn。一组决策变量表示为问题的一个方案；(2)目标函数：max(min)zz为决策变量的线性函数;(3)约束条件一组线性不等式。cj为价值系数,bi为资源，aij为技术系数(i=1,…,m;j=1,…,n).51.2图解法[eg.3]用图解法求eg.1。maxz=2x1+3x21x1+2x2≤8①4x1≤16②4x2≤12③x1，x2≥0解：(1)建立x1-x2坐标；x2x1(2)约束条件的几何表示；①②Q1Q2③Q3Q4(3)目标函数的几何表示；*z=2x1+3x2o43zxx3132126首先取z=0，然后，使z逐渐增大，直至找到最优解所对应的点。*可见，在Q2点z取到最大值。因此，Q2点所对应的解为最优解。Q2点坐标为(4，2)。即:x1=4，x2=2∴由此求得最优解：x1*=4x2*=2最大值：maxz=z*=2x1+3x2=14(元)x2x1①②Q1Q2(4,2)③Q3Q4*437讨论：(1)唯一最优解maxz=z*时，解唯一，如上例。(2)无穷多最优解[eg.4]对eg.1，若目标函数z=2x1+4x2，此时表示目标函数的直线与表示条件①的直线平行，最优点在线段Q3Q2上。即存在无穷多最优解。x2x1②Q1Q2(4,2)③Q3(2,3)Q4o43*①8(3)无界解[eg.5]maxz=2x1+3x24x1≤16x1，x2≥0则x2→∞，z→∞。即存在无界解。在实际问题中，可能是缺少约束条件。o2241x2x9(4)无可行解[eg.6]maxz=2x1+3x22x1+4x2≥8x1+x2≤1x1，x2≥0无公共部分，无可行域。即无可行解。在实际问题中，可能是关系错。1124x1x2101.3线性规划的标准型1、标准型maxz=c1x1+c2x2+···+cnxna11x1+a12x2+···+a1nxn=b1a21x1+a22x2+···+a2nxn=b2┆┆am1x1+am2x2+···+amnxn=bmx1，x2，···，xn≥0njxmibxaxczjinjjijnjjj,,10,,1max11，简记：11用向量表示njxbxptsCXzjnjjj,,1,0.max1TmjTmjjjjnTnbbbbxaaapcccCxxxX)(:)()()(:21212121的系数列向量其中12用矩阵描述为：maxz=CXAX=bX≥0其中:X=(x1,x2,···,xn)TC=(c1,c2,···,cn)b=(b1,b2,···,bm)T为系数矩阵212222111211mnmmnnaaaaaaaaaA132、标准型的化法(1)min→max∵minz=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+x3≤7①x1-x2+x3≥2②-3x1+x2+2x3=5③x1,x2≥0，x3无约束解：令x3=x3’-x3”，x3’,x3”≥0；①式加上一个松弛变量x4；②式减去一个剩余变量x5；令z’=-zmaxz’=x1-2x2+3(x3’-x3”)+0x4+0x5x1+x2+(x3’-x3”)+x4=7x1-x2+(x3’-x3”)-x5=2-3x1+x2+2(x3’-x3”)=5x1,x2,x3’,x3”,x4,x5≥0151.4线性规划解的概念设线性规划为maxz=CX①AX=b②X≥0③A为m×n矩阵,nm,RankA=m(A为行满秩矩阵）1、可行解：满足条件②、③的X；2、最优解：满足条件①的可行解；3、基：取B为A中的m×m子矩阵，RankB=m，则称B为线性规划问题的一个基。取B=(p1,p2,···,pm)pj=(a1j,a2j,···,amj)T则称x1,x2,···,xm为基变量，其它为非基变量。164、基解：取B=(p1,p2,···,pm)a11,···,a1mx1a1m+1,···,a1nxm+1b1┆┆┆+┆┆┆=┆am1,···,ammxmamm+1,···,amnxnbm↑↑↑↑基基变量非基非基变量令xm+1=···=xn=0(非基变量为0)则BXB=b∴)!(!!mnmnCmn基解个数TmnmTmBxxxXxxxbBX)0,,0,,,,(),,,(m)0()0(2)0(1)0()0(2)0(11个个基解：175、基可行解满足③式要求的基解。如右图所示，各边交点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为凸集。（0α1）非凸集X(1)X(1)X(2)X(2)凸集X(1)X(2)X(2)X(1)192、顶点：X∈K，X(1)∈K，X(2)∈K(任意两点)。若X不能用αX(1)+(1-α)X(2)表示，则称X为K的一个顶点。(0α1)注：顶点所对应的解是基可行解。3、凸组合：设X(i)∈En，若存在0μi1，i=1,2,···,k，使,则称X为X(i)(i=1,2,···,k)的凸组合。1k1iik1i)i(iXX2.2基本定理1、定理1若线性规划存在可行域，则:可行域D={X|AX=b,X≥0}为凸集。20证明：设X(1)=(x1(1),x2(1),···,xn(1))T∈D；X(2)=(x1(2),x2(2),···,xn(2))T∈D；(X(1)≠X(2))有AX(1)=b，AX(2)=b令X=αX(1)+(1-α)X(2)(0α1)则AX=αAX(1)+(1-α)AX(2)=αb+(1-α)b=b∵α01–α0∴X≥0，即D为凸集2、定理2线性规划的基可行解对应于可行域的顶点。3、定理3若线性规划有解，则一定存在基可行解为最优解。21§3单纯形法基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。3.1初始基可行解的确定1、松弛基（松弛变量对应的B）[eg.8]maxz=x1+3x2x1+2x2≤32x1+3x2≤4x1,x2≥0maxz=x1+3x2+0x3+0x4x1+2x2+x3=32x1+3x2+x4=4x1,x2,x3,x4≥0化标准型取x3、x4为基变量,令非基变量x1=x2=0∴初始基可行解：X(0)=(0034)TB,10320121434321ppppppA则系数矩阵222、观察法[eg.9]maxz=x1+3x2+2x3+x4x1+2x2+3x3=33x2+x3+x4=4x1,x2,x3,x4≥0选XB=(x1x4)T令x2=x3=0则初始基可行解：X(0)=(3004)TB,11300321:414321ppppppA则解233、人工基[eg.10]maxz=x1+2x2+3x3x1+3x2+2x3=32x1+x2+x3=4x1,x2,x3≥0分析：A=132211∵找不到单位矩阵基∴引入人工变量为初始基变量（2个）243.2最优性的检验与解的判别mnjxmibxxaxcxczjnjiinjijmiininnjjj,,10,,1max111对于代入目标函数为非基变量可行为基变量设,,1,,,1,1njjijiinjinxabxnjxmix25则njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111)()()(miijinjjjjmiiinaczzcbcZ110,,其中26解的判别：1.若，则此时的基可行解为最优解；2.若存在某个非基变量的检验数，且，则该线性规划问题具有无界解（或称无最优解）；3.若所有，又，对于某个非基变量有，则该线性规划问题具有无穷多最优解。..的检验数为称jjxkx0knjj,,1,00kp0j0kkx27为主元出基行对应的变量则若、出基变量0minmin02'''''''''lkllklikikiiiiikikiiaxlabaabaab为入基变量。则，若、入基变量kkjjx0max13.3基变换283.4旋转运算（消元运算）a1k’0┆┆al-1k’0pk’=（alk’）（1）al+1k’0┆┆amk’0得到基可行解，重复3.2—3.4，求出最优解。293.5单纯形表展开如下：a11x1+a12x2+···+a1nxn+xn+1=b1-cn+1a21x1+a22x2+···+a2nxn+xn+2=b2-cn+2┆┆┆am1x1+am2x2+···+amnxn+xn+m=bm-cn+mc1x1+c2x2+···+cnxn+cn+1xn+1+···+cn+mxn+m-z=0σ1x1+2x2+···+nxn+0xn+1+···+0xn+m-z=Z0mn,,2,1j0xbxxaxczmaxjiinn1jjijmn1jjj，设30建立单纯形表cBxBbc1···cncn+1···cn+mθx1···xnxn+1···xn+mcn+1xn+1b1a11···a1n1···0θ1┆┆┆┆┆┆┆┆cn+mxn+mbmam1···amn0···1θm-z-z0σ1···σn0···0σj[eg.11]用单纯形法求解maxz=x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2≥031解：①标准化，建立单纯形表引入松弛变量x3，x4，x5为初始基变量maxz=x1+3x2+0x3+0