清华大学运筹学(完整)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=1x1,x2,x3,x4,x50对于min问题，若minj0中，选下标小的非基变量入基；对相同的最小比值，选下标小的基变量出基。,第二章,j与i的计算同max问题。,.,45,习题P45，1.4分别用图解法和单纯形法求解下列线性规划,并指出单纯形法迭代的每一步相当于图形上的哪一个顶点？,.,46,第二章对偶理论与灵敏度分析,1单纯形法的矩阵描述设maxz=CXAX=bX0A为mn阶矩阵RankA=m,取B为可行基,N为非基，,.,47,.,48,.,49,求解步骤：,.,50,.,51,现在出租，设y1为设备单位台时的租金y2,y3为材料A、B转让附加费(kg-1),则M2为M1的对偶问题，反之亦然。,.,52,一般的，原问题：maxz=CXAXbX0,对偶问题：minw=YbYACY0,比较：maxzminw决策变量为n个约束条件为n个约束条件为m个决策变量为m个“”“”,.,53,3对偶问题的化法1、典型情况eg.2maxz=x1+2x2+x32x1+x262x2+x38x1,x2,x30,.,54,2、含等式的情况eg.3maxz=x1+2x2+4x32x1+x2+3x3=3x1+2x2+5x34x1,x2,x30,一般，原问题第i个约束取等式，对偶问题第i个变量无约束。,.,55,3、含“”的max问题eg.4maxz=x1+2x2+4x32x1+x2+3x33x1+2x2+5x34x1,x2,x30,.,56,一般:max问题第i个约束取“”，则min问题第i个变量0；,min问题第i个约束取“”，则max问题第i个变量0；,原问题第i个约束取等式，对偶问题第i个变量无约束；,max问题第j个变量0,则min问题第j个约束取“”；,min问题第j个变量0，则max问题第j个约束取“”；,原问题第j个变量无约束，对偶问题第j个约束取等式。,.,57,eg.5minz=2x1+3x2-5x3+x4x1+x2-3x3+x452x1+2x3-x44x2+x3+x4=6x10,x2,x30,x4无约束,.,58,4对偶问题的性质,1、对称性对偶问题的对偶为原问题.,.,59,.,60,.,61,推论：(1)max问题任一可解的目标值为min问题目标值的一个下界；(2)min问题任一可解的目标值为max问题目标值的一个上界。,3、无界性若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。,注：该性质的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。,.,62,4、最优性设X*，Y*分别为原问题和对偶问题可行解，当CX*=Y*b时，X*，Y*分别为最优解。,.,63,5、对偶定理若原问题有最优解，那么对偶问题也有最优解，且目标值相等。,.,64,Y*为对偶问题的最优解，且原问题和对偶问题的目标值相等。证毕,6、松弛性若X*，Y*分别为原问题及对偶问题的可行解，那么Ys*X*=0，Y*Xs*=0，当且仅当X*，Y*分别为最优解。,证明：,.,65,将b,C分别代入目标函数：,.,66,其中：,用分量表示：,.,67,7、检验数与解的关系(1)原问题非最优检验数的负值为对偶问题的一个基解。(2)原问题最优检验数的负值为对偶问题的最优解。,检验数：=(C0)-CBB-1(AI)=(C-CBB-1A-CBB-1)=(cs)c=C-CBB-1AX对应的检验数s=-CBB-1Xs对应的检验数,.,68,eg.6已知：minw=20y1+20y2的最优解为y1*=1.2,y2*=0.2-ys1y1+2y21试用松弛性求对偶-ys22y1+y22问题的最优解。-ys32y1+3y23-ys43y1+2y24y1,y20,y1*xs1*=0y2*xs2*=0ys1*x1*=0ys2*x2*=0ys3*x3*=0ys4*x4*=0,.,69,y1*=1.2,y2*0.20xs1*=xs2*=0由y1*+2y2*=1.61ys1*0x1*=0由2y1*+y2*=2.62ys2*0x2*=0由2y1*+3y2*=3=右边ys3*=0x3*待定由3y1*+2y2*=4=右边ys4*=0x4*待定,最优解：x1*=0 x2*=0 x3*=4x4*=4xs1*=0 xs2*=0最大值：z*=28=w*,.,70,5对偶问题的经济含义影子价格最优情况：z*=w*=b1y1*+biyi*+bmym*,.,71,6对偶单纯形法单纯形法：由XB=B-1b0，使j0，j=1,m对偶单纯形法：由j0(j=1,n)，使XB=B-1b0,步骤：(1)保持j0，j=1,n，确定XB，建立计算表格；,(2)判别XB=B-1b0是否成立？若成立，XB为最优基变量；若不成立，转(3)；,.,72,(4)消元运算，得到新的XB。,(3)基变换出基变量，,入基变量，,重复（2）-（4）步，求出结果。,.,73,eg.8用对偶单纯形法求解minw=2x1+3x2+4x3x1+2x2+x312x1-x2+3x34x1,x2,x30,.,74,x4,x50最优,最优解：x1*=2，x2*=0，x3*=0，x4*=1，x5*=0目标值：w*=-z*=4,.,75,7灵敏度分析,分析变化对最优解的影响。,.,76,.,77,例1已知下述问题的最优解及最优单纯形表,.,78,最优单纯形表如下:,.,79,由最优单纯形表得:,.,80,.,81,不可行!,用对偶单纯形法计算,.,82,3/4,-2,.,83,.,84,例2求例1c4的变化范围,使最优解不变.,解:,.,85,分析:,.,86,方法:,例3求例1c2的变化范围,使最优解不变.,.,87,解:,.,88,.,89,分析:,.,90,.,91,例4求例1a24的变化范围,使最优解不变.,解:,.,92,例5在例1的基础上，企业要增加一个新产品,每件产品需2个台时，原材料A6kg，原材料B3kg，利润5元/件，问如何安排各产品的产量，使利润最大？解：,.,93,表明生产新品有利。,.,94,.,95,2,.,96,小结,1、对偶问题及其化法,原问题决策变量决定对偶问题约束条件关系,原问题约束条件决定对偶问题决策变量取值方向。,.,97,2、检验数的计算方法,.,98,3、对偶问题的性质,4、对偶单纯形法,弱对偶性,无界性,最优性,松弛性,检验数与对偶问题的解,.,99,5、灵敏度分析,.,100,.,101,第三章整数规划IntegerProgramming,1问题的提出eg.1用集装箱托运货物问：甲乙货物托运多少箱，使总利润最大？,.,102,图解法：,x1*=4x2*=1zI*=90,.,103,一般，整数规划的最优解不会优于相应线性规划的最优解。,对于max问题，zI*zl*对于min问题，zI*zl*,数学模型：,.,104,2分枝定界法用单纯形法，去掉整数约束,.,105,30-1规划（xi=0或1的规划）eg.2选择投资场所Ai投资Bi元，总投资B，收益Ci元.问：如何选择Ai，使收益最大？,南区,西区,东区,.,106,eg.3求解如下0-1规划maxz=3x1-2x2+5x3x1+2x2-x32x1+4x2+x34x1+x234x2+x36x1,x2,x3=0或1,解：(1)观察一个可行解x1=1x2=x3=0此时，z=3,.,107,(3)列表计算,第四章,.,108,第四章非线性数规划NonlinearProgramming,1问题的提出eg.1某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？,分析：设长为米，宽为米，则有,f(x)为非线性函数,.,109,例2设某物理过程具有如下规律用试验法。现要确定参数使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足,.,110,非线性规划：目标函数或（和）约束条件为非线性函数的规划。,分析：,f(x)为非线性函数，求最小。,.,111,2基本概念,2.1非线性规划的数学模型数学模型的一般描述,.,112,或,.,113,2.2非线性规划的图示,例1求解如下非线性规划问题,.,114,分析：,非线性规划的最优解可能在可行域的任一点达到。,.,115,2.3极值问题,极值存在的条件,.,116,.,117,.,118,.,119,.,120,.,121,2.4凸函熟与凸规划,1、凸函熟与凹函熟,.,122,函数f(x)图示,.,123,2、凸性的判别,.,124,例3,.,125,3.凸函数的极值,对于定义在凸集上的凸函数，其极小点就是最小点，极小值就是最小值。4.凸规划下述问题为凸规划.,.,126,凸规划的局部最优解为全局最优解，当凸规划的目标函数为严格凸函数时，若存在最优解，则最优解必定唯一。凸规划是一类比较简单而又具有重要理论意义的非线性规划。,.,127,例如下非线性规划是否为凸规划：,.,128,的海赛矩阵：,所以，该问题为凸规划。,.,129,如图所示，该问题最优解（最小点）在C点取得。,.,130,5.下降迭代算法,下降迭代算法,.,131,几种终止迭代的准则：,.,132,3无约束非线性规划的解法,无约束非线性规划的数学描述解法分类：解析法：用函数的解析性（一阶、二阶导数）。梯度法、共扼梯度法、变尺度法等。直接法：用问题的函数值。步长加速法。,.,133,梯度法,1.基本原理,.,134,对于充分小的,.,135,2、求解步骤,(1),.,136,其中,重复迭代，直至满足精度为止。,.,137,例,.,138,找下一点,.,139,于是,.,140,几何分析,对于等值线为圆的无约束极小化问题，不管初始点选在哪里，只要一次迭代即可求得最优解。,.,141,4有约束的非线性规划,有约束非线性规划数学描述,.,142,4.1库恩-塔克(Kuha-Tucker)条件,1.几何说明,.,143,对于,.,144,2.库恩-塔克(Kuha-Tucker)条件,设,.,145,式中,.,146,例用K-T条件求解如下非线性规划。,.,147,引入乘子,.,148,讨论：,.,149,4.2二次规划,二次规划的数学描述,.,150,1.二次规划的K-T条件,求相应问题梯度,.,151,引拉格朗日乘子,.,152,2.线性规划描述,引入松弛变量及人工变量,.,153,取,.,154,于是得到相应的线性规划问题。,.,155,以,.,156,第五章动态规划(Dynamicprogramming),1.引言研究多阶段决策问题R.E.Bellman1951年提出动态规划。1957年出版DynamicProgramming应用：最优调度、资源分配最优路径、最优控制设备更新、库存问题,.,157,2.多阶段决策问题,例.某产品从A城运至F城，其间要经过若干个城镇和若干条道路，路线结构如图所示，图中给出了每段道路的运费（元），试选择一条合理的运输路线，使总运费最小？,.,158,分析：方案：AB1C1E1F运费：26元方案:AB3C3E3F运费：22元方案:AB2C1E2F运费：18元最优方案：方案,.,159,3.基本概念,1.阶段和阶段变量阶段：过程的划分，包括时间、空间的划分，阶段数:n阶段变量：描述阶段的变量用k表示，k=1,2,.,n2.状态和状态变量状态：描述过程的必要信息。状态应具有无后效性:若给定了某阶段状态，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.,.,160,状态变量：描述状态的变量，用s表示。,.,161,3.决策和决策变量,决策：决定（选择），从一个阶段的状态到下一个阶段状态的选择。决策变量：描述决策的变量，用u表示.,.,162,4.策略,策略：决策按顺序构成的序列，用p表示。,.,163,.,164,.,165,.,166,7.多阶段过程,对于