优化模型与AML.ppt

优化模型与优化模型与 AMPLAMPL最优化是工程技术、经济管理、科学研究、社最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题会生活中经常遇到的问题,如如:优化模型和算法的重要意义优化模型和算法的重要意义结构设计结构设计资源分配资源分配生产计划生产计划运输方案运输方案解决优化问题的手段解决优化问题的手段经验积累，主观判断经验积累，主观判断作试验，比优劣作试验，比优劣建立数学模型，求解最优策略建立数学模型，求解最优策略最优化最优化:在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大(小小)的决策的决策 优化问题三要素：优化问题三要素：决策变量；目标函数；约束条件决策变量；目标函数；约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式无约束优化无约束优化(没有约束没有约束)与约束优化与约束优化(有约束有约束)可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数5/11/20243局部最优解与整体最优解局部最优解与整体最优解局部最优解局部最优解(LocalOptimalSolution,如如x1)整体最优解整体最优解(GlobalOptimalSolution,如如x2)x*f(x)x1x2o5/11/20244优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解的难度增加常用优化软件常用优化软件 1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱/Mathematic的优化功能的优化功能3.SAS(统计分析统计分析)软件的优化功能软件的优化功能4.EXCEL软件的优化功能软件的优化功能5.AMPL/MINOS,CPLEXMATLABMATLAB优化工具箱能求解的优化模型优化工具箱能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：线性规划模型例线性规划模型例:奶制品生产计划奶制品生产计划 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天AMPL程序u模型文件,用文本编辑器编辑,保存为milk.modset P ordered;#产品集合param Ti in P0;#加工时间param Qi in P0;#单位产量param Li in P0;#单位利润var xi in P=0;#生产计划maximize profit:sumi in PLi*Qi*xi;subject to raw:sumi in Pxi=50;subject to time:sumi in PTi*xi=480;subject to capacity:Qfirst(P)*xfirst(P)=100;u数据文件文件,用文本编辑器编辑,保存为milk.datset P:=A1 A2;param T:=A1 12 A2 8;param Q:=A1 3 A2 4;param L:=A1 24 A2 16;u批处理文件,用文本编辑器编辑,保存为milk.runmodel milk.mod;data milk.dat;option solver cplexamp;solve;运行求解AMPL:milk.runCPLEX 11.0.0:optimal solution;objective 33602 dual simplex iterations(1 in phase I)x*:=A1 20A2 30;灵敏度分析AMPL:display x.rc,x.down,x.up;x.rc x.down x.up :=A1 0 64 96A2 0 48 72;x.rc最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增量的增量;x.down,x.up最优解最优解不变时目标函数系数允许变化范围不变时目标函数系数允许变化范围AMPL:display raw,time,capacity;aw=48time=2capacity=0原料增加原料增加1单位单位,利润增长利润增长48;时间增加时间增加1单位单位,利润增长利润增长2;加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格AMPL:display raw.down,raw.up,raw.current,raw.slack;raw.down=43.3333raw.up=60raw.current=50raw.slack=0影子价格有意义时约束右端的允影子价格有意义时约束右端的允许变化范围许变化范围;原料最少到原料最少到43.3,最最大到大到60,slack=0意为原料用完意为原料用完.模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3360z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。求解求解LP的基本思想的基本思想思路：从可行域的某一顶点开始，只需在有限多个思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到顶点中一个一个找下去，一定能得到最优解最优解。LP的约束和目标函数均为线性函数的约束和目标函数均为线性函数2维维可行域可行域线段组成的凸多边形线段组成的凸多边形目标函数目标函数等值线为直线等值线为直线最优解最优解凸多边形的某个顶点凸多边形的某个顶点n维维超平面组成的凸多面体超平面组成的凸多面体等值线是超平面等值线是超平面凸多面体的某个顶点凸多面体的某个顶点LPLP的通常解法是单纯形法的通常解法是单纯形法(G.B.Dantzig,1947)(G.B.Dantzig,1947)线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有可行解有可行解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)非线性规划模型例：选址问题非线性规划模型例：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型(LP)决策变量：决策变量：ci j(料场料场j到到工地工地i的的运量）运量）12维维选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型(NLP)整数规划整数规划-例例:聘用方案聘用方案决策变量决策变量：周一至周日每天：周一至周日每天(新新)聘用人数聘用人数x1,x2,x7目标函数目标函数：7天天(新新)聘用人数之和聘用人数之和约束条件约束条件：周一至周日每天需要人数：周一至周日每天需要人数连续工作连续工作5天天周一工作的应是周一工作的应是(上上)周四至周一聘用的周四至周一聘用的设系统已进入稳态（不是开始的几周）设系统已进入稳态（不是开始的几周）聘用方案聘用方案整数规划整数规划模型模型(IP)(IP)丁的蛙泳成绩退步到丁的蛙泳成绩退步到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”45名候选人的名候选人的百米成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。目标目标函数函数若选择队员若选择队员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规划规划:整数规划的特例整数规划的特例整数规划问题整数规划问题一般形式一般形式整数线性规划整数线性规划(ILP)目标和约束均为线性函数目标和约束均为线性函数整数非线性规划整数非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数整数规划问题的分类整数规划问题的分类纯纯(全全)整数规划整数规划(PIP)决策变量均为整数决策变量均为整数混合整数规划混合整数规划(MIP)决策变量有整数，也有实数决策变量有整数，也有实数0-1规划规划决策变量只取决策变量只取0或或15/11/202425取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入下界（对Min问题）上界（对Max问题）非最优解无无约约束束优优化化更多的优化问题更多的优化问题线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划连续优化连续优化离散优化离散优化从其他角度分类从其他角度分类应用广泛：应用广泛：生产和运作管理、经济与金融、图论和网生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等以及更加综合、更加复杂的决策问题等实际问题规模往往较大，用软件求解比较方便实际问题规模往往较大，用软件求解比较方便此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！