优化问题与LINGO软件.ppt

优化问题与 LINGO软件,（一）线性规划问题概述,【例1】生产计划问题,max f=5x1+2x2,求最大利润,三种材料量的限制,生产量非负,【例2】运输问题,解：设A1,A2调运到三个粮站的大米分别为x1，x2，x3，x4，x5，x6吨。,题设量可总到下表：,结合存量限制和需量限制得数学模型：,m个产地A1,Am联合供应n个销地B1,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?,一般运输问题,总运价,产量限制,需量限制,运量非负,假设产销平衡:,在很多实际问题中,解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题.,设有n件工作B1,B2,Bn,分派给n人A1,A2,An去做,每人只做一件工作且每件工作只派一个人去做,设Ai完成Bj的工时为cij,问应如何分派才能完成全部工作的总工时最少.,每件工作只派1人,每个人只派做1件,【例3】分派问题,变量xi只取0和1,故建立的模型也称0-1规划.,【例4】选址问题,现要做100套钢架,用长为2.9m、2.1m和1.5m的元钢各一根,已知原料长7.4m,问如何下料,使用的原材料最省?,分析:,下料方式：,最省：,1.所用刚架根数最少；,2.余料最少,【例5】下料问题,不同方法截得每种根长的总数至少100,例3,4中的此例的变量xi只取正整数,故建立的模型也称整数规划.0-1规划是整数规划的特殊情形.,某公司生产某产品,最大生产能力为100单位,每单位存储费2元,预定的销售量与单位成本如下:,求一生产计划,使 1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.,【例6】阶段生产问题,解:假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.,第j+1个月的库存量,第j+1个月的库存费,共3个月的库存费,到本月总生产量大于等于销售量,4个月总生产量等于总销售量,4个月总生产成本,本题3个模型为整数规划模型.,线性规划模型特点,决策变量：向量(x1 xn)T,决策人要考虑和控制的因素非负；约束条件：线性等式或不等式；目标函数：Z=(x1 xn)线性式，求Z极大或极小；,线性规划问题的数学模型,将实际问题转化为在一组线性不等式或等式约束下求线性目标函数的最大最小问题。,一般形式,目标函数,约束条件,用CAI补充矩阵知识,矩阵形式,满足约束条件的变量的值称为可行解，,可行解的集合称为可行域。,使目标函数达到最大（小）值的可行解称为最优解，,相应的目标函数的值称为最优值。,线性规划问题的性质:,比例性 每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比.可加性 每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关.连续性 每个决策变量的取值都是连续的.,应 用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用),（二）一般优化问题概述,优化问题三要素：决策变量decision bariable；目标函数objective function；约束条件constraints,优化问题的一般形式,等约束equality constraint,不等约束inequality constraint,要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件,特点,可行解feasible solution（满足约束）与可行域feasible region（可行解的集合）最优解optimal solution（取到最小minimum大值maximum的可行解,对应最优值optimal value）,局部最优解或相对最优解local/relative optimizer,全局或整体最优解global optimizaer,优化模型的基本类型,无约束优化unconstrained optimization,约束优化constrained optimization,特殊：等式（不等式）方程组 system of equations(inequations),约束优化constrained optimization的简单分类,1.数学规划mathematical programming或连续优化continuous optmization,线性规划(LP)目标和约束均为线性函数 Linear programming非线性规划(NLP)目标或约束中存在非线性函数 Nonlinear programming 二次规划(QP)目标为二次函数、约束为线性 Quadratic programming,整数规划(IP)决策变量(全部或部分)为整数Integer programming 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)Pure(mixed)Integer programming 一般整数规划，0-1（整数）规划Zero-one programming,2.离散优化discrete optimization或组合优化combinatorial optimization,线性规划,比例性,可加性,连续性,最优解在凸多面体的某个顶点上取得,此时，有积极约束或紧约束active/tight constraints非积极约束inactive constraints,敏感性分析sensitivity analysis,不可行infeasible,最优解optimizer,无界unbounded,单纯形法simplex method,基变量basic barible,非基变量nonbasic barible,基解basic solution,迭代或旋转pivot,内点算法interior point method:内部逼近，适用大规模,二次规划,积极集方法 active set method,非线性规划算法,非线性规划,迭代，判停，一般只能找到局部最优解,整数规划,枚举法，隐枚举法分支定界法branch and bound method,常用优化软件,1.LINDO/LINGO软件2.MATLAB优化工具箱3.EXCEL软件的优化功能4.SAS(统计分析)软件的优化功能5.其他,（三）线性规划问题的基本理论,【例1】,用图解法求解线性规划问题,是一簇斜率为-5/2的平行直线族,斜率为-2,C/2为直线与y轴的交点,4,3,如图所示:,显然直线向右上移动时，与y轴交点越高，从而c/2越大，使得目标函数值c 越大。,结论,从上述几何直观可看出：,线性规划问题的任意两个可行解联线上的点都是可行解；,线性规划问题的任意两个最优解联线上的点都是最优解；,线性规划问题的最优值若存在，则一定在某个顶点达到。,标准形式:,任何一个线性规划问题都可以化为标准形式,如果给定的LP问题是极大化问题,即,可化为极小化问题,约束条件不变,其最优解是一致的,但目标函数值的符号相反.,则:,结论:如果问题是求目标函数的最大值,则化为求 f 的最小值;,1.关于目标函数,2.关于约束条件,(1)如果给定的LP有约束不等式,注意:新引入的变量在目标函数和约束条件中的系数均为0.,(2)如果给定的LP有约束不等式,3.关于变量,在标准形式中,所有的变量都有非负限制,如果某些变量没有非负限制,则称这些变量为自由的.,两种处理办法:,【例2】,【例】,相应的典式如下:,最优值为5.,非基可行解,是最优解，,某工厂可以用A、B两种原料生产、三种产品（每种产品都同时需要用两种原料），有关数据如下表：,【例】,问:1、若目前市场上原料A的实际价格为0.5万元/吨,工厂应如何决策?2、若目前市场上原料A的实际价格为0.8万元/吨,工厂应如何决策?,解:设x1,x2,x3分别表示,的生产量,建立模型:,互为对偶问题,对应目标函数值为 f=13万元.,最优解:,原料A 的数量b1在11/3,22之间变化时，最优基不变.,对偶问题的最优解为：,y1=3/5,y2=4/5,(1)若目前市场上原料A的实际价格为0.5万元/吨时,它低于原料A的影子价格0.6,因此,可以考虑购进原料,以扩大生产能力,为保证原最优基不变,购进原料A的最大数量为22-7=15吨.此时,问题的目标值为f=13+150.6=22万元,扣除购进原料成本0.5 15=7.5万元,实际赢利为14.5万元,比现有原料进行生产多赢利1.5万元.,(2)若目前市场上原料A的实际价格为0.8万元/吨时,它高于原料A的影子价格0.6,因此,可以考虑出售部分原料,为保证原最优基不变,出售原料A的最大数量为10/3吨.此时,实际赢利为13-10/3 0.6+10/30.8=13+2/3万元,比用现有原料生产多赢利2/3万元.,分枝定界法,连续投资10万元,A：从第1年 到第4年每年初要投资，次年末回收本利1.15,B：第3年初投资，到第5年末回收1.25，最大投资4万元,C：第2年初投资，到第5年末回收1.40，最大投资3万元,D：每年初投资，每年末回收1.11。,求：5年末总资本最大。,练习1:连续投资,练习2某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，现规定应聘者需连续工作5天，试确定聘用方案。,练习3某班准备从5名游泳员中选择人组成接力队，藏家学校的4100m混合泳接力比赛，5名队员4种泳姿的百米平均成绩如表，问如何选拔队员。,