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

中南大学环境系统工程薛生国中南大学冶金学院环境工程系中南大学§3.1线性规划§3.2整数规划§3.3非线性规划§3.4动态规划第三章最优化技术中南大学研究对象有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省§3.1线性规划中南大学问题的提出问企业如何安排生产计划，使一天的总利润最大？ABC原料产品ABC单位利润（百元）甲1103乙1214供应量683甲乙一、线性规划的数学模型中南大学MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥01）假设x1,x2为甲、乙产品每天的生产量—决策变量x1，x2≥0—非负约束2）假设Z为总利润,希望最大maxZ=3x1+4x23）考虑限制条件A原料：x1+x2≤6B原料：x1+2x2≤8C原料：x2≤3问题的提出-建模过程—引例中南大学OptZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn≤(≥,=)b1a21x1+a22x2+…a2nxn≤(≥,=)b2…am1x1+am2x2+…+amnxn≤(≥,=)bmx1,x2,…xn≥0线性规划模型由三部分组成1）一组决策变量；2）一个线性目标函数；3）一组约束方程。有n个决策变量，m个约束方程建模过程的一般形式中南大学决策变量：向量(x1…xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小线性规划模型特点中南大学比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,ci为确定值隐含的假设中南大学电力2000千瓦煤540吨金属4吨总量6/8吨80/50公斤50/10千瓦A/B产品需求量AA、B产品利润/吨6000元/5000元B线性规划建模例1—资源合理利用问题中南大学（1）确定变量。设用x1，x2（单位为吨）分别表示A、B产品的生产量。（2）目标函数。Z=6x1+5x2（千元）（3）约束条件。煤：6x1+8x2≤540（吨）金属:80x1+50x2≤4000（公斤）电力：50x1+10x2≤2000(千瓦）maxZ=6x1+5x26x1+8x2≤54080x1+50x2≤400050x1+10x2≤2000x1,x2≥0模型归纳问题分析线性规划建模例1—资源合理利用问题中南大学满足以下条件的称为标准型：目标函数为求最大值约束方程均为等式方程所有变量均为非负变量线性规划的标准型（一般型）中南大学a11X1+a12X2+…+a1nXn=b1a21X1+a22X2+…+a2nXn=b2…………am1X1+am2X2+…+amnXn=bmXj0(j=1,2,…,n)maxZ=C1X1+C2X2+…+CnXn其中bi0(i=1,2,…,m)二、线性规划的标准型(一)三种表示形式--①一般型中南大学maxZ=CXAX=BX0P1P2………Pna11a12………a1n其中A=a21a22………a2n…………………am1am2………amnX1X=X2Xn…b1B=b2bm…C=(C1C2…Cn)(一)三种表示形式--②矩阵型中南大学X1AX=(P1P2…Pn)X2=BXn…P1X1+P2X2+…+PnXn=B0Bmax1XXPCXZnjjj(一)三种表示形式--③向量型中南大学约束条件决策变量目标函数（二）化线性规划问题为标准型中南大学化不等式约束为等式约束约束方程为“≤”号：在方程左边加一个非负松弛变量，把“≤”改成“=”。约束方程为“≥”号：在方程左边减一个非负剩余变量，把“≥”改成“=”。（二）化线性规划问题为标准型中南大学njxmixCZjnjnjjj2,102,1bxaMax1ijij1mixnjxmiinjnj2,102,102,1bxxa1iinjij松弛变量例：约束条件的标准化中南大学X1+2X2+X3=303X1+2X2+X4=602X2++X5=24X1,…,X50松弛变量例1maxZ=40X1+50X2+0·X3+0·X4+0·X5松弛变量中南大学njxmixCZjnjnjjj2,102,1bxaMax1ijij1mixnjxmiinjnj2,102,102,1bxxa1iinjij剩余变量剩余变量中南大学4X1+6X2+X3+2X4-X5=12X1+X2+7X3+5X4-X6=142X2+X3+3X4-X7=8X1,…,X70剩余变量例2minZ=2X1+5X2+6X3+8X4中南大学化无约束变量为约束变量若Xk为无约束变量，令xk=xk’-xk”,其中xk’,xk”≥0（二）化线性规划问题为标准型中南大学3X1'-3X1+2X28X1'-X1-4X214X1',X1,X201、3X1+2X28X1-4X214X20令X1=X1'-X1X1:自由变量例：化无约束变量为约束变量中南大学X1'+X211X1'16X1',X202、X1+X25-6X110X20-6+6X1+610+6令X1'=X1+60X1'16中南大学xoZ-ZnjjjnjjjXCZZZXCZ11'max'min:令若目标函数为(3)化目标函数的最小值问题为最大值问题中南大学例：将minZ=-X1+2X2-3X3X1+X2+X37X1-X2+X32X1，X20，X3无限制化为标准型中南大学解：①令X3=X4-X5②加松弛变量X6③加剩余变量X7④令Z'=-ZmaxZ'=X1-2X2+3X4-3X5X1+X2+X4-X5+X6=7X1-X2+X4-X5-X7=2X1,X2,X4,…,X70中南大学确定一组决策变量确定一个线性目标函数确定一组线性约束条件线性规划模型建立步骤归纳中南大学三、线性规划图解法及几何意义中南大学MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0x168x2346x2=3x1+2x2=8x1+x2=6绘出可行解域图解法—例中南大学求最优解x168x2346x2=3x1+2x2=8x1+x2=6法线最优解（4，2）最优方案甲产品4吨，乙2吨，目标函数为Z=20(利润2000元)MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0图解法—例中南大学1）绘出每个约束方程的约束平面•设约束方程为a1x1+a2x2≤(≥,=)b(1)画出直线a1x1+a2x2=b(2)若约束方程为a1x1+a2x2≤b则半平面在直线-(a1,a2)方向(3)若约束方程为a1x1+a2x2≥b则半平面在直线(a1,a2)方向(4)若约束方程为a1x1+a2x2=b则半平面为该直线x1246x2246x1+x2=6x1+x26与(1,1)同方向(1,1方向)2x1-3x2=6(2,-3）方向2x1-3x26图解法：一般过程中南大学2）绘出可行解域各个约束半平面相交的区域3）作法线相垂直的目标函数等值线设目标函数为maxZ=c1x1+c2x2,作与方向（c1,c2)相垂直的目标函数等值线在可行解域中沿方向（c1，c2）同方向移动移动中确定使目标达到最优的可行解，该解即为最优解。4）解出最优解x1246x2246maxZ=3x1+4x2maxZ=3x1+4x2(3,4)方向法线(3,4)方向线性规划的标准型（一般型）中南大学无穷多最优解无界解无可行解图解法—最优解的种类中南大学MaxZ=x1+2x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0x1123456789x21234657x2=3x1+2x2=8x1+x2=6图解法—无穷多解例中南大学MaxZ=x1+x2-2x1+x2≤4x1-x2≤2x1,x2≥0x1123456789x21234657x1-x2=2-2x1+x2=4图解法—无界解例中南大学MaxZ=3x1+4x2x1+x2≥6x1≤2x2≤3x1,x2≥0x1123456789x21234657图解法—无可行解例中南大学线性规划的几何意义中南大学两点间线段上点的表示法设有两点W1(x1,y1)，W2(x2,y2).我们要求出W1，W2连线上任意一点W的表示方法。由于三角形的相似关系推导出W=λW1+（1-λ）W2λ=（0~1）W1(x1,y1)W2（x2,y2)W(x,y)xyx1xx2y2y1y线性规划的几何意义的基本概念中南大学线性规划几何意义中基本概念•凸集对于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表示。设有标准型AX=b(1-3)X≥0(1-4)A=(aij)mnmn中南大学==目标函数约束条件行列式≠0基矩阵B右边常数基本概念-基、基变量1)B在A中是任取的，因此A中有很多基2)基变量是针对基而言，不同的基有不同的基变量。中南大学基本概念-基,基变量说明11100A=1201001001x1+x2+x3=6x1+2x2+x4=8x2+x5=3x1~x5≥0100010001B2=|B2|≠0,XB=(x3,x4,x5),Xn=(x1,x2)111120010B1=|B1|≠0,XB=(x1,x2,x3),Xn=(x4,x5)中南大学基本概念-基,基变量说明2当在A中取定某一基B后，方程AX=b可以写表示为BXB+NXN=b101211100100001683x2x4x1X3X5+=x1x2x3x4x5=683111001201001001101211100B=|B|≠0,XB=(x2,x4,x1),XN=(x3,x5)中南大学基本概念—基解基可行解：若为某一个基解，且XB=B-1b≥0,则得一个满足方程的可行解，称为基可行解。X=XBXN基解：设B为某一个基则有BXB+NXN=b令XN=0，则得一个满足方程AX=b的解，称为基解。X=XBXNB-1b0=中南大学基本概念—基解可行解(域)基解基可行解最优解基解基可行解基解非基可行解基解基可行解中南大学1、可行(解)域是什么形状？是凸集？2、可行解与基可行解的关系，什么条件下可行解就是基可行解？3、基可行解与可行解域顶点什么关系？4、目标函数在何处达到最优？是不是在顶点上（基可行解）？5、最优解与基可行解是什么关系？6、解决线性规划问题步骤是什么？可行解域基可行解基可行解基可行解(最优解)基可行解基可行解中南大学进基变量、离基变量、基变换=目标函数约束条件基矩阵右边常数=基变量中南大学=进基变量离基变量目标函数约束条件右边常数=中南大学=目标函数约束条件新的基矩阵右边常数=中南大学基本定理定理1(重要)：若线性规划问题存在可行解，则其可行解域D={X|AX=b,X≥0}是凸集.证明：给出D中任意两个不同的点PQ属于D，即AP=b,P≥0；AQ=b,Q≥0设X=λP+(1-λ)Q(λ=0~1）（X在P,Q连线上）则AX=λAP