数学建模竞赛中的优化问题市公开课一等奖百校联赛特等奖课件.pptx

数学建模竞赛中优化问题数学建模竞赛中优化问题 数学建模 培训组 .3第1页本次讲座目v让大家了解数学建模中经常碰到问题优化问题；v初步认识数学建模需要准备算法，软件。第2页优化问题v优化问题解题步骤：1、确定最优目标函数。2、寻找组成目标函数各元素应该恪守约束条件。3、利用对应软件或算法求解。第3页数学规划数学规划线性规划线性规划(linear programming)是康托洛维奇是康托洛维奇1939年提年提出，出，1947年（年（G.B.Dantzig）提出求线性规划单纯形）提出求线性规划单纯形法（法（simplemethod），理论上趋向成熟，实际上应），理论上趋向成熟，实际上应用也越来越广泛，几乎各行各业都可建立线性规划用也越来越广泛，几乎各行各业都可建立线性规划模型。模型。第4页 某企业要在计划期内安排生产甲、乙两种产某企业要在计划期内安排生产甲、乙两种产品，这个企业现有生产资料是：设备品，这个企业现有生产资料是：设备18台时，原台时，原材料材料A 4吨，原材料吨，原材料 B 12吨；已知单位产品所需吨；已知单位产品所需消耗生产资料及利润以下表。问应怎样确定生产消耗生产资料及利润以下表。问应怎样确定生产计划使企业赢利最多。计划使企业赢利最多。1.1 线性规划问题线性规划问题例例1生产计划问题生产计划问题第5页表表1 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万万元元35第6页Formulation as a linear programming problemvx1=number of units of product 1v x2=number of units of product 2vz=total profit from producting these two products x1,x2 are the decision variables for the model.maximize z=3x1+5x2第7页非负约束非负约束 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35182321+xx 设备限制设备限制 原料原料A限制限制 原料原料B限制限制第8页对应数学模型对应数学模型 产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35第9页资源合理利用问题资源合理利用问题 -the allocating resources to activities普通资源利用问题可表述为：普通资源利用问题可表述为：设某企业利用设某企业利用 m 种资源来生产种资源来生产 n 种产品，已知种产品，已知该企业拥有第该企业拥有第 i 种资源数量是种资源数量是b i,生产单位第生产单位第 j 种产种产品所消耗第品所消耗第 i 种资源数量为种资源数量为 aij，第，第j种产品单位利润是种产品单位利润是 c j。现制订一个生产计划方案，使总利润最大。现制订一个生产计划方案，使总利润最大。第10页ResourceResource Usage per Unit of ActivityAmount of Resource AvailableActivity 1 2 n 12 m a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bmContribution to z per unit of activity c1 c1 c1z=value of overall measure of performancexj=level of activities j(for j=1,2,n)cj=increase in z that would resule from each unit increase in level of activity j-价值系数价值系数第11页ResourceResource Usage per Unit of ActivityAmount of Resource AvailableActivity 1 2 n 12 m a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bmContribution to z per unit of activity c1 c1 c1aij=amount of resource i consumed by each unit of activity j.-技术系数技术系数bi=amount of resource i that is available for allocation to activities(for i=1,2,m)-资源系数资源系数第12页ResourceResource Usage per Unit of ActivityAmount of Resource AvailableActivity 1 2 n 12 m a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2bmContribution to z per unit of activity c1 c1 c1x1,x2,xn are called the decision variables.cj,bi,aij(for i=1,2,m and j=1,2,n)are the input constants or the parameters for the model.第13页资源利用问题数学模型为资源利用问题数学模型为：the objective functionfunctional constrainsnonegativeconstrains第14页假设企业决议者不考虑自己生产产品甲乙，而是将假设企业决议者不考虑自己生产产品甲乙，而是将厂里现有资源（见表厂里现有资源（见表1）买出。试问该厂决议者应给每种）买出。试问该厂决议者应给每种资源制订一个怎样价格，才能取得良好收益？资源制订一个怎样价格，才能取得良好收益？产品产品资源资源甲甲乙乙资源量资源量设备设备/台时台时3218原料原料A/吨吨104原料原料B/吨吨0212单位赢利单位赢利/万元万元35例例2资源定价问题资源定价问题第15页问题分析问题分析解：决议者显然要考虑两个原因：解：决议者显然要考虑两个原因：第一，每种资源所收回费用应不底于自己生产第一，每种资源所收回费用应不底于自己生产 时所取得利润；时所取得利润；第二，定价又不能太高，要使对方轻易接收。第二，定价又不能太高，要使对方轻易接收。总之，定价要公平合理，使双方都能接收。总之，定价要公平合理，使双方都能接收。第16页问题分析问题分析v设设y1,y2,y3分别表示这三种资源收费单价。则由分别表示这三种资源收费单价。则由第一条标准：将用于加工产品甲或乙全部资源，第一条标准：将用于加工产品甲或乙全部资源，如用来加工外来产品所取得收回费用，应不低于如用来加工外来产品所取得收回费用，应不低于可取得利润，即可取得利润，即第17页从工厂决议者来看当然是越大越好。不过依据第从工厂决议者来看当然是越大越好。不过依据第二条标准，也应该使对方支出尽可能少；二条标准，也应该使对方支出尽可能少；从而这个问题就能够转化为下述数学问题：从而这个问题就能够转化为下述数学问题：当然对价格还要有非负限制。即：当然对价格还要有非负限制。即：将该厂全部资源都用来加工外来产品，其总将该厂全部资源都用来加工外来产品，其总收入（即对方总支出）是收入（即对方总支出）是第18页定价问题数学模型定价问题数学模型第19页设某单位现有设某单位现有n个人员个人员A1,A2,An来完成来完成n项工作项工作B1,B2,Bn。按工作要求，每。按工作要求，每个人员需干一项工作，每项工作也需一人个人员需干一项工作，每项工作也需一人去完成。已知人员去完成。已知人员A i做工作做工作B j效率是效率是c ij。问应怎样分配，才使总效率最好。问应怎样分配，才使总效率最好。例例3人员分配问题人员分配问题第20页问题分析问题分析令令x ij表示分配人员表示分配人员A i完成工作完成工作 B j决议变量。决议变量。x ij=1 表示分配表示分配Ai干工作干工作Bj xij=0 表示不分配表示不分配Ai干工作干工作Bj 按问题要求，每人要做一项工作，每项工作需一人去做。按问题要求，每人要做一项工作，每项工作需一人去做。建立该问题数学模型过程：建立该问题数学模型过程：第21页问题分析问题分析派工方案总效益派工方案总效益对工作对工作Bj；要求一人员去完成要求一人员去完成对人员对人员Ai；要求负担一项工作：要求负担一项工作：第22页分配问题数学模型分配问题数学模型第23页某企业要运销一个物资。该物资有甲、乙两个产地，某企业要运销一个物资。该物资有甲、乙两个产地，产量分别是吨、产量分别是吨、1000吨；另有吨；另有A、B、C三个销地，三个销地，销量分别是销量分别是1700吨、吨、1100吨、吨、200吨。已知该物资单吨。已知该物资单位运价如表位运价如表1-2。问应怎样确定调运方案，才能使在。问应怎样确定调运方案，才能使在产销平衡条件下，总运费最低？产销平衡条件下，总运费最低？例例4物资运输问题物资运输问题第24页销销地地单位运价单位运价产产地地甲甲乙乙销销量量ABC2125751513717001100200产产量量1000表表3v分析分析确定调运方案就是确定从不一样产地到各个销地确定调运方案就是确定从不一样产地到各个销地运输量运输量。设设xij表示这些要找运量。表示这些要找运量。即即x11、x12、x13分别表示从甲地调往分别表示从甲地调往A、B、C三地运量。三地运量。x21、x22、x23分别表示从已地调往分别表示从已地调往A、B、C三地运量。三地运量。第25页因为要求产销平衡：因为要求产销平衡：从两产地甲、乙分别调往三销地从两产地甲、乙分别调往三销地A、B、C物资数量物资数量应该分别等于两产地甲、乙产量，所以应该分别等于两产地甲、乙产量，所以xij应满足：应满足：第26页运到运到A、B、C三销地物资数量应分别等于三销地物资数量应分别等于A、B、C三销地销量，所以三销地销量，所以x ij 还应该满足：还应该满足：因为因为xij是运量，不能是负数：是运量，不能是负数：调运方案总运费为：调运方案总运费为：建立产销平衡下运费最省调运问题建立产销平衡下运费最省调运问题数学模型数学模型：第27页运输问题数学模型运输问题数学模型销销地地单位运价单位运价产产地地甲甲乙乙销销量量ABC2125751513717001100200产产量量1000第28页 某种物资有某种物资有 m 个产地，个产地，A1,A2,Am，产量分别，产量分别a1,a2,am个单位，另有个单位，另有 n 个销地个销地B1,B2,Bn,销销量分别是量分别是b1,b2,bn个单位。假设产销是平衡，个单位。假设产销是平衡，即总产量等于总销量。已知由产地即总产量等于总销量。已知由产地A i 向销地向销地B j 运输一运输一个单位物资运价个单位物资运价x ij；问应该怎样调运物资才能使总；问应该怎样调运物资才能使总运费最省。运费最省。令令xij表示由产地表示由产地Ai向销地向销地Bj运量运量运输问题普通提法运输问题普通提法：第29页运输问题运输问题数学模型数学模型为：为：第30页上述例子，即使有不一样实际内容，上述例子，即使有不一样实际内容，不过它们都是要求一组变量值，这组值满足一定不过它们都是要求一组变量值，这组值满足一定约束条件，如资源限制、供求关系等。约束条件，如资源限制、供求关系等。这种约束条件都能够用一组这种约束条件都能够用一组线性不等式线性不等式或或线性方线性方程程来表示，同时使某个来表示，同时使某个线性函数指标线性函数指标到达最大或最到达最大或最小。含有这些特征问题，称为小。含有这些特征问题，称为线性规划问题线性规划问题。第31页1.2 图解法图解法-graphical method 图解法适合用于来解只有图解法适合用于来解只有两个变量两个变量线性规划问题线性规划问题.第32页The feasible regionisthecollectionofallfeasiblesolutions.A feasible solutionisasolutionforwhichalltheconstraintsaresatisfied.Itispossibleforaproblemtohavenotfeasiblesolutions.An in feasible solutionisasolutionforwhichatleastoneconstraintisviolated.An optimal solutionisafeasiblesolutionthathasthemostfavorablevalue(thelargestorthesmallest)oftheobjectivefunction.Itispossibleforaproblemtohavemorethanoneoptimalsolution.Anyproblemhavingmultipleoptimalsolutionswillhaveaninfinitenumberofthem.第33页例例1 图解法求解线性规划问题图解法求解线性规划问题图解法简单直观，有利于了解线性规划问题求解图解法简单直观，有利于了解线性规划问题求解基本原理和思想。基本原理和思想。下面举例说明图解法求解线性规划问题步骤。下面举例说明图解法求解线性规划问题步骤。解解该线性规划问题可行域见图该线性规划问题可行域见图1。第34页 2 4 6 8 x1x2 8 6 4 2 0 x1=42 x 2=123x1+2x2=18QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)图解法解题过程图解法解题过程图图1-1可行域可行域-thefeasibleregion第35页 2 4 6 x1x2 8 6 4 2 0 x1=42 x 2=123x1+2x2=18QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)3x1+5x2=z=363x1+5x2=z=203x1+5x2=z=0图解法解题过程图解法解题过程图图1-1让直线束让直线束沿正法线沿正法线在可行域在可行域Q移动，移动，经过点经过点(2,6)直线：直线：第36页注：本问题只有唯一最优解。注：本问题只有唯一最优解。例例例例1 1最优生产方案为：最优生产方案为：最优生产方案为：最优生产方案为：生产生产生产生产产品甲为产品甲为产品甲为产品甲为2 2件，生产产品乙件，生产产品乙件，生产产品乙件，生产产品乙6 6件，最大利润为件，最大利润为件，最大利润为件，最大利润为3636万元。万元。万元。万元。x1 8 6 4 2 0 x1=4QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)x1第37页注：注：问题问题可行域可行域是是一个有界一个有界凸多边形凸多边形，其边界由其边界由5条直线所围成：条直线所围成：X1=0,X2=0X1=42x2=123x1+2x2=18最优解最优解(2,6)在在凸多边形顶点凸多边形顶点Q2上。上。x2 8 6 4 2 0 x1=4QQ0(0,0)Q1(0,6)Q2(2,6)Q3(4,3)Q4(4,0)x1第38页例例2第39页解解该问题可行域该问题可行域Q是一个有界凸多边形（是一个有界凸多边形（如图如图1-2）。）。-x1+x2=0X1+x2=56x1+2x2=213x 1+x 2=z=03x 1+x 2=z=63x 1+x 2=z=21/2A(11/4,9/4)B(21/6,0)x1x2第40页让直线束让直线束3x1+x2=z沿正法线向移动，抵沿正法线向移动，抵达线段达线段AB时，使时，使Z抵达最大。所以线段抵达最大。所以线段AB上每一点都可使上每一点都可使Z抵达最大值，抵达最大值，注：本问题有没有穷注：本问题有没有穷多个最优解。多个最优解。-x1+x2=0 x1+x2=56x1+2x2=213x 1+x 2=z=03x 1+x 2=z=63x 1+x 2=z=21/2A(11/4,9/4)B(21/6,0)x1x2第41页例例3第42页图图1-3解解该问题可行域是一个无界凸多边形该问题可行域是一个无界凸多边形第43页让直线束让直线束沿其负法线方向移动，能够无限沿其负法线方向移动，能够无限制地移动下去，一直与制地移动下去，一直与相交，所以其最小值为相交，所以其最小值为；即；即函数函数在在上无下界。上无下界。注：本问题有可行解，注：本问题有可行解，但无最优解。但无最优解。第44页例例4第45页解解该问题可行域是空，即无可行解该问题可行域是空，即无可行解X1-x2=-1x1+x2=-1注：本问题无可行解，更无最优解。注：本问题无可行解，更无最优解。第46页深入讨论深入讨论给定只有给定只有两个变量两个变量线性规划问题：线性规划问题：图解法求解线性规划问题步骤以下：图解法求解线性规划问题步骤以下：第47页若若若若是空集，则说明线性规划问题无可行解。是空集，则说明线性规划问题无可行解。是空集，则说明线性规划问题无可行解。是空集，则说明线性规划问题无可行解。假如假如假如假如不是空集，那么不是空集，那么不是空集，那么不是空集，那么是平面上一个凸多边形，这是平面上一个凸多边形，这是平面上一个凸多边形，这是平面上一个凸多边形，这个凸多边形可能是有界（封闭），也可能是无界（不封闭）个凸多边形可能是有界（封闭），也可能是无界（不封闭）个凸多边形可能是有界（封闭），也可能是无界（不封闭）个凸多边形可能是有界（封闭），也可能是无界（不封闭）。表示一个以表示一个以表示一个以表示一个以zz为参数平行直线束。为参数平行直线束。为参数平行直线束。为参数平行直线束。沿正法线方向沿正法线方向移动可得最大值，沿负移动可得最大值，沿负法线方向法线方向移动可得最小值。移动可得最小值。注意注意:一定要准确一定要准确在平面在平面在平面在平面上取定直角坐标系，画出上取定直角坐标系，画出上取定直角坐标系，画出上取定直角坐标系，画出可行域可行域可行域可行域，记为，记为，记为，记为。第48页经过以上例子能够看出，两个变量线性规划解可经过以上例子能够看出，两个变量线性规划解可能有以下能有以下4种情况：种情况：有唯一最优解。有唯一最优解。最优解一定是可行域一个顶点。最优解一定是可行域一个顶点。有没有穷多最优解。有没有穷多最优解。最优解是可行域一段边界。最优解是可行域一段边界。有可行解，但无最优解。目标函数值无界有可行解，但无最优解。目标函数值无界.无可行解。无可行解。（最大值点（最小值点）一定在可行域边界上）（最大值点（最小值点）一定在可行域边界上）问题是对于普通线性规划问题有没有类似结论，问题是对于普通线性规划问题有没有类似结论，结论成立判定准则怎样。结论成立判定准则怎样。第49页 1.3 整数规划整数规划例例1、集装箱运货、集装箱运货货物货物体积体积(米米3/箱箱)重量重量(百千克百千克/箱箱)利润利润(千元千元/箱箱)甲甲5220乙乙4510装运限制装运限制2413第50页解：设解：设X1 ,X2 为甲、乙两货物各托运箱数为甲、乙两货物各托运箱数5X1+4X2 242X1+5X2 13X1,X2 0 0X1,X2为整数为整数maxZ=20 maxZ=20 X1+10 X2第51页例例2、背包问题、背包问题背包可再装入背包可再装入8单位重量，单位重量，10单位体积物品单位体积物品物品物品名称名称重量重量体积体积价值价值1书书52202摄像机摄像机31303枕头枕头14104休闲食品休闲食品23185衣服衣服4515第52页解：解：Xi为是否带第为是否带第i 种物品种物品maxZ=20X1+30X2+10X3+18X4+15X55X1+3X2+X3+2X4+4X5 82X1+X2+4X3+3X4+5X5 10Xi为为0,1第53页普通形式：普通形式：,整数整数第54页(1)、Xi为为i 物品携带数量物品携带数量 ai为为i 物品单位重量物品单位重量 ci为为i 物品主要性估价物品主要性估价b为最大负重为最大负重(2)、投资决议投资决议Xi为在为在i 地域建厂规模地域建厂规模 ai为在为在i 地域建厂基建费用地域建厂基建费用 ci为在为在i 地域建厂单位利润地域建厂单位利润b为最大资本为最大资本(3)、Xi 取取0或或1时，可作项目投资模型时，可作项目投资模型第55页例例3、选址问题、选址问题A1A3B2B4B3B1A2Ai:可建仓库地点，容量可建仓库地点，容量ai,投资费用投资费用bi，建，建2个个Bj:商店，需求商店，需求dj(j=14)Cij:仓库仓库i 到商店到商店j 单位单位运费运费问：选择适当地点建仓库，在满足商店需问：选择适当地点建仓库，在满足商店需求条件下，总费用最小。求条件下，总费用最小。第56页解：设解：设Xi(i=1,2,3)为是否在为是否在Ai 建仓库建仓库 yij(i=1,2,3,j=14)由由i仓库向仓库向 j商店运货量商店运货量y11+y21=d=d1 1y12+y22+y32=d=d2 2y23+y33=d=d3 3y14+y24+y34=d=d4 4x1+x2+x3=2y11+y12+y14 a a1 1x1y21+y22+y23+y24 a a2 2x2y32+y33+y34 a a3 3x3xi 为为01，yij 0 0混合整数规划混合整数规划第57页01决议变量应用决议变量应用可用于相互排斥计划中可用于相互排斥计划中例例1、运输方式：火车、船。、运输方式：火车、船。火车：火车：5X1+4X2 24 (体积体积)船：船：7X1+3X2 45 (体积体积)第58页maxZ=20X1+10X2 2X1+5X2 135X1+4X2 24+MX37X1+3X2 45+M(1-X3)X1,X2 0 整数整数X3为为0或或1 M0当当X3=0 =0 火车火车 X3=1 =1 船船 第59页例例2、ai1x1+ai2x2+ainxn b bi i(i=1,m)相互排斥相互排斥m个约束，只有一个起作用个约束，只有一个起作用ai1x1+ainxn b bi i+yi M M (i=1,m)y1+ym=m-1yi为为0或或1M0第60页例例4:聘用方案聘用方案决议变量决议变量：周一至周日天天：周一至周日天天(新新)聘用人数聘用人数x1,x2,x7目标函数目标函数：7天天(新新)聘用人数之和聘用人数之和约束条件约束条件：周一至周日天天需要人数：周一至周日天天需要人数第61页连续工作连续工作5天天周一工作应是周一工作应是(上上)周四至周一聘用周四至周一聘用设系统已进入稳态（不是开始几周）设系统已进入稳态（不是开始几周）聘用方案聘用方案整数规划整数规划模型模型(IP)(IP)第62页丁蛙泳成绩退步到丁蛙泳成绩退步到115”2；戊自由泳成绩进步到；戊自由泳成绩进步到57”5,组成接力队方案是否应该调整组成接力队方案是否应该调整？怎样选拔队员组成怎样选拔队员组成4 4 100100米混合泳接力队米混合泳接力队?0-1规划规划 混合泳接力队选拔混合泳接力队选拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4例例5：5名候选人名候选人百米成绩百米成绩穷举法穷举法：组成接力队方案共有组成接力队方案共有5!=120种种。第63页目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 比赛，记比赛，记xij=1,不然记不然记xij=0 0-1规划模型规划模型 cij(秒秒)队员队员i 第第j 种泳姿百米成绩种泳姿百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 0-1规划规划:整数规划特例整数规划特例第64页整数规划问题整数规划问题普通形式普通形式整数线性规划整数线性规划(ILP)目标和约束均为线性函数目标和约束均为线性函数整数非线性规划整数非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数整数规划问题分类整数规划问题分类纯纯(全全)整数规划整数规划(PIP)决议变量均为整数决议变量均为整数混合整数规划混合整数规划(MIP)决议变量有整数，也有实数决议变量有整数，也有实数0-1规划规划决议变量只取决议变量只取0或或1第65页取消整数规划中决议变量为整数限制（松弛），对应取消整数规划中决议变量为整数限制（松弛），对应连续优化问题称为原问题松弛问题连续优化问题称为原问题松弛问题整数规划问题对应松弛问题整数规划问题对应松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入下界（对Min问题）上界（对Max问题）非最优解第66页用连续优化方法求解松弛问题，假如松弛问题最优解（分量）全为整数，则也是原整数规划问题最优解对松弛问题最优解（分量）舍入为整数，得到往往不是原整数规划问题最优解（甚至不是可行解）IPIP可行解对应于整点可行解对应于整点A(2,2)A(2,2)和和B(1,1),B(1,1),而最优解为而最优解为A A点点.但但LPLP松弛最优解为松弛最优解为C(3.5,2.5)C(3.5,2.5)目标函数下降方向目标函数下降方向 x1 1x2 2CABO第67页x1x20Po69Zmax56去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3.75)围成4边形从LP最优解经过简单“移动”不一定能得到IP最优解例例1.6第68页基本思想：基本思想：隐式地枚举一切可行解（隐式地枚举一切可行解（“分而治之”）所所谓谓分分枝枝，就就是是逐逐次次对对解解空空间间（可可行行域域）进进行行划划分分；而而所所谓谓定定界界，是是指指对对于于每每个个分分枝枝（或或称称子子域域），要要计计算算原原问问题题最最优优解解下下界界（对对极极小小化化问问题题）.这这些些下下界界用用来来在在求求解解过过程程中中判判定定是是否否需需要要对对当当前前分分枝枝深深入入划划分分，也也就就是是尽尽可能去掉一些显著非最优点，防止完全枚举可能去掉一些显著非最优点，防止完全枚举.分枝定界法（分枝定界法（B&B:BranchandBound）对于极小化极小化问题，在子域上解LP，其最优值是IP限定在该子域时下界；IP任意可行点函数值是IP上界。这里仅介绍整数线性规划分枝定界算法这里仅介绍整数线性规划分枝定界算法第69页假设假设A产销平衡产销平衡假设假设Bp随随x(两种牌号两种牌号)增加而减小，呈线性关系增加而减小，呈线性关系例例1：产销计划问题：产销计划问题某厂生产两个牌号同一个产品，怎样确定产量使利润最大某厂生产两个牌号同一个产品，怎样确定产量使利润最大1.4 二次规划模型二次规划模型第70页目标目标利润最大利润最大=（100-x1-0.1 x2-2）x1+（280-0.2x1-2x2-3）x2=98 x1+277 x2x120.3 x1 x22x22约束约束x1+x2100 x12 x2x1,x20二次规划模型二次规划模型(QP)若还要求产量为整数，则是整数二次规划模型若还要求产量为整数，则是整数二次规划模型(IQP)第71页1.5 非线性规划模型非线性规划模型例例2：选址问题：选址问题某企业有某企业有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路第72页用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型(LP)决议变量：决议变量：ci j(料场料场j到到工地工地i运量）运量）12维维第73页选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和运量和运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决议变量：决议变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型(NLP)第74页优化建模与优化建模与LINDO/LINGO软件软件原书相关信息谢金星,薛毅编著,清华大学出版社,7月第1版.http:/ 第78页优化问题三要素：优化问题三要素：决议变量决议变量；目标函数目标函数；约束条件约束条件约约束束条条件件决议变量决议变量优化问题普通形式优化问题普通形式无约束优化无约束优化(没有约束没有约束)与约束优化与约束优化(有约束有约束)可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数第79页局部最优解与整体最优解局部最优解与整体最优解局部最优解局部最优解(LocalOptimalSolution,如如x1)整体最优解整体最优解(GlobalOptimalSolution,如如x2)x*f(x)x1x2o第80页优化模型优化模型简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决议变量决议变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)普通整数规划，普通整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划第81页优化模型简单分类和求解难度优化模型简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解难度增加第82页2.优化问题建模实例优化问题建模实例第83页例例1:1:家俱厂生产计划家俱厂生产计划例例2:2:奶制品生产计划奶制品生产计划 例例3:3:运输问题运输问题线性规划模型线性规划模型第84页1桶牛奶 3千克A1 12小时 8小时 4千克A2 或赢利24元/千克 赢利16元/千克 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100千克千克A1制订生产计划，使天天赢利最大制订生产计划，使天天赢利最大 35元可买到元可买到1桶牛奶，买吗？若买，天天最多买多少桶牛奶，买吗？若买，天天最多买多少?可聘用暂时工人，付出工资最多是每小时几元可聘用暂时工人，付出工资最多是每小时几元?A1赢利增加到赢利增加到30元元/千克，应否改变生产计划？千克，应否改变生产计划？天天：天天：例例2:奶制品生产计划奶制品生产计划第85页1桶牛奶 3千克A1 12小时 8小时 4千克A2 或赢利24元/千克 赢利16元/千克 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2赢利赢利243x1赢利赢利164 x2原料供给原料供给 劳动时间劳动时间 加工能力加工能力 决议变量决议变量 目标函数目标函数 天天赢利天天赢利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100千克千克A150桶牛奶桶牛奶天天天天第86页线性规划模型解几个情况线性规划模型解几个情况 线性规划问题线性规划问题有有可可行行解解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)第87页无无约约束束优优化化更多优化问题更多优化问题线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划连续优化连续优化离散优化离散优化从其它角度分类从其它角度分类应用广泛：应用广泛：生产和运作管理、经济与金融、图论和网生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存放论，络优化、目标规划问题、对策论、排队论、存放论，以及愈加综合、愈加复杂决议问题等以及愈加综合、愈加复杂决议问题等实际问题规模往往较大，用软件求解比较方便实际问题规模往往较大，用软件求解比较方便第88页LINDO/LINGO软件使用介绍软件使用介绍第89页使用使用LINDOLINDO一些注意事项一些注意事项1.“”（或（或“=”（或（或“=”）功效相）功效相同同2.变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符3.变量名以字母开头，不能超出变量名以字母开头，不能超出8个字符个字符4.变量名不区分大小写（包含变量名不区分大小写（包含LINDO中关键字）中关键字）5.目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件6.行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结结束束7.行中注有行中注有“!”符号后面部分为注释。如符号后面部分为注释。如:!Its Comment.8.在模型任何地方都能够用在模型任何地方都能够用“TITLE”对模型命名对模型命名（最多（最多72个字符），如：个字符），如：TITLE This Model is only an Example第90页9.变量不能出现在一个约束条件右端变量不能出现在一个约束条件右端10.表示式中不接收括号表示式中不接收括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X211.表示式应化简，如表示式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X212.缺省假定全部变量非负；可在模型缺省假定全部变量非负；可在模型“END”语句后用语句后用“FREE name”将变量将变量name非负假定取消非负假定取消13.可在可在“END”后用后用“SUB”或或“SLB”设定变量上下界设定变量上下界 比如：比如：“sub x1 10”作用等价于作用等价于“x1=10”但用但用“SUB”和和“SLB”表示上下界约束不计入模型约表示上下界约束不计入模型约束，也不能给出其松紧判断和敏感性分析。束，也不能给出其松紧判断和敏感性分析。14.“END”后对后对0-1变量说明：变量说明：INT n 或或 INT name15.“END”后对整数变量说明：后对整数变量说明：GIN n 或或 GIN name使用使用LINDOLINDO一些注意事项一些注意事项第91页二次规划规划(QP)问题vLINDO可求解二次规划可求解二次规划(QP)问题，但输入方式较问题，但输入方式较复杂，因为在复杂，因为在LINDO中不许出现非线性表示式中不许出现非线性表示式v需要为每一个实际约束增加一个对偶变量需要为每一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加相关乘子），在实际约束前增加相关变量一阶最优条件，转化为互补问题变量一阶最优条件，转化为互补问题v“END”后面使用后面使用QCP命令指明实际约束开始行号，命令指明实际约束开始行号，然后才能求解然后才能求解v提议总是用提议总是用LINGO解解QP注意注意对对QP和和IP:敏感性分析意义不大敏感性分析意义不大第92页状态窗口状态窗口（LINDO Solver Status）v当前状态：已达最优解当前状态：已达最优解v迭代次数：迭代次数：18次次v约束不满足约束不满足“量量”(不是不是“约束个数约束个