环境系统工程-线性规划(图解法)

环境系统工程,薛生国中南大学冶金学院环境工程系,3.1线性规划3.2整数规划3.3非线性规划3.4动态规划,第三章最优化技术,研究对象有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省,3.1线性规划,问题的提出,问企业如何安排生产计划，使一天的总利润最大？,A,B,C,甲,乙,一、线性规划的数学模型,1）假设x1,x2为甲、乙产品每天的生产量决策变量x1，x20非负约束,2）假设Z为总利润,希望最大maxZ=3x1+4x2,3）考虑限制条件A原料：x1+x26B原料：x1+2x28C原料：x23,问题的提出-建模过程引例,有n个决策变量，m个约束方程,建模过程的一般形式,决策变量：向量(x1xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=(x1xn)线性式，求Z极大或极小,线性规划模型特点,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值,隐含的假设,线性规划建模例1资源合理利用问题,（1）确定变量。设用x1，x2（单位为吨）分别表示A、B产品的生产量。,（2）目标函数。Z=6x1+5x2（千元）,（3）约束条件。煤：6x1+8x2540（吨）金属:80 x1+50 x24000（公斤）电力：50 x1+10 x22000(千瓦）,模型归纳,问题分析,线性规划建模例1资源合理利用问题,满足以下条件的称为标准型：目标函数为求最大值约束方程均为等式方程所有变量均为非负变量,线性规划的标准型（一般型）,maxZ=C1X1+C2X2+CnXn,其中bi0(i=1,2,m),二、线性规划的标准型,(一)三种表示形式-一般型,maxZ=CXAX=BX0,C=(C1C2Cn),(一)三种表示形式-矩阵型,P1X1+P2X2+PnXn=B,(一)三种表示形式-向量型,约束条件决策变量目标函数,（二）化线性规划问题为标准型,（二）化线性规划问题为标准型,松弛变量,例：约束条件的标准化,例1maxZ=40X1+50X2+0X3+0X4+0X5,松弛变量,剩余变量,剩余变量,例2minZ=2X1+5X2+6X3+8X4,（二）化线性规划问题为标准型,1、,令X1=X1-X1,X1:自由变量,例：化无约束变量为约束变量,2、,-6+6X1+610+6令X1=X1+60X116,(3)化目标函数的最小值问题为最大值问题,例：将minZ=-X1+2X2-3X3,化为标准型,解：令X3=X4-X5,加松弛变量X6,加剩余变量X7,令Z=-Z,maxZ=X1-2X2+3X4-3X5,确定一组决策变量确定一个线性目标函数确定一组线性约束条件,线性规划模型建立步骤归纳,三、线性规划图解法及几何意义,MaxZ=3x1+4x2x1+x26x1+2x28x23x1,x20,图解法例,求最优解,最优方案甲产品4吨，乙2吨，目标函数为Z=20(利润2000元),MaxZ=3x1+4x2x1+x26x1+2x28x23x1,x20,图解法例,1）绘出每个约束方程的约束平面设约束方程为a1x1+a2x2(,=)b(1)画出直线a1x1+a2x2=b(2)若约束方程为a1x1+a2x2b则半平面在直线-(a1,a2)方向(3)若约束方程为a1x1+a2x2b则半平面在直线(a1,a2)方向(4)若约束方程为a1x1+a2x2=b则半平面为该直线,图解法：一般过程,2）绘出可行解域各个约束半平面相交的区域3）作法线相垂直的目标函数等值线设目标函数为maxZ=c1x1+c2x2,作与方向（c1,c2)相垂直的目标函数等值线在可行解域中沿方向（c1，c2）同方向移动移动中确定使目标达到最优的可行解，该解即为最优解。4）解出最优解,maxZ=3x1+4x2,maxZ=3x1+4x2(3,4)方向,线性规划的标准型（一般型）,无穷多最优解无界解无可行解,图解法最优解的种类,图解法无穷多解例,x1-x2=2,-2x1+x2=4,图解法无界解例,图解法无可行解例,线性规划的几何意义,两点间线段上点的表示法,设有两点W1(x1,y1)，W2(x2,y2).我们要求出W1，W2连线上任意一点W的表示方法。由于三角形的相似关系推导出W=W1+（1-）W2=（01）,线性规划的几何意义的基本概念,线性规划几何意义中基本概念,凸集,对于N维欧氏空间点集D中的任意不同两点，W1属于D空间，W2也属于D空间，若它们的连线上的任意点W=W1+(1-）W2也属于D空间，则称D空间为“凸集”,凸集,不是凸集,线性规划几何意义中基本概念,顶点,设D为凸集，W是D中一点；若W不能用其他两点的线性规划组合表示。即不存在有：W=W1+(1-)W2成立则称W为凸集D的一个“顶点”。,6个顶点,无穷个顶点,线性规划的几何意义,线性规划问题的可行解域为凸集；线性规划问题可行解域的顶点个数是有限的；若线性规划问题存在最优解，则最优解一定在可行解域的某个顶点得到。,可行解域,基可行解,(最优解),线性规划问题中的基本概念,可行解：满足约束方程(1-3),(1-4)的解X称为线性规划问题的可行解。,基(矩阵)：设B是从A中任取m列元素所构成的方阵。且|B|0则称B是线性规划问题的一个基(矩阵)。,基变量：若B为基，则B中列所对应的变量称为基变量，用XB表示，余下的其他变量称为非基变量，用XN表示。,基本概念-基、基变量,1)B在A中是任取的，因此A中有很多基2)基变量是针对基而言，不同的基有不同的基变量。,基本概念-基,基变量说明,基本概念-基,基变量说明2,当在A中取定某一基B后，方程AX=b可以写表示为BXB+NXN=b,基本概念基解,基可行解：若为某一个基解，且XB=B-1b0,则得一个满足方程的可行解，称为基可行解。,基本概念基解,1、可行(解)域是什么形状？是凸集？2、可行解与基可行解的关系，什么条件下可行解就是基可行解？3、基可行解与可行解域顶点什么关系？4、目标函数在何处达到最优？是不是在顶点上（基可行解）？5、最优解与基可行解是什么关系？6、解决线性规划问题步骤是什么？,进基变量、离基变量、基变换,进基变量,离基变量,目标函数,约束条件,右边常数,目标函数,约束条件,新的基矩阵,右边常数,=,基本定理,定理1(重要)：若线性规划问题存在可行解，则其可行解域D=X|AX=b,X0是凸集.,证明：给出D中任意两个不同的点PQ属于D，即AP=b,P0；AQ=b,Q0设X=P+(1-)Q(=01）（X在P,Q连线上）则AX=AP+(1-）AQ=b+(1-）b=b得AX=b,X0,X属于D由凸集定义知D是凸集。,基本定理,引理1：线性规划问题的可行解X为基可行解的充要条件是，X的正分量所对应的系数列向量是线性独立的。,说明：X=(x1,0,x3,0,x5)是可行解，则满足方程AX=b,正分量：就是不为0的X分量,基本定理,定理2(重要)：线性规划问题的基可行解X对应于可行解域D的顶点。,证明：（略）,可行解,基可行解,基可行解,基可行解(最优解),基可行解,基可行解,基本定理,定理3(重要)：若可行解有界，线性规划问题的目标函数一定可以在可行解域顶点上达到最优。,基本结论,1、线性规划的可行解域是凸集2、基可行解是可行解域的顶点，可行解域的顶点即是基可行解，因此每个基可行解对应可行解域的一个顶点。3、可行解域的顶点个数是有限的，不超过Cnm。4、若线性规划问题有最优解，则最优解必在某个顶点上得到,可行解,基解,基可行解,(最优解),以例说明基本结论,x2=3,x1+2x2=8,x1+x2=6,绘出可行解域,以例说明基本结论,如取x1,x2,x3为基变量x1+x2+x3=6x1+2x2=8x2=3,Z值的计算：Z=3x1+4x2,以例说明基本结论,可行解(可行域中）,基解(Q0Q8),基可行解Q0Q4,(