优化模型与AMPL.ppt
优化模型与 AMPL,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化:在一定条件下，寻求使目标最大(小)的决策,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值),局部最优解与整体最优解,局部最优解(Local Optimal Solution,如 x1)整体最优解(Global Optimal Solution,如 x2),优化模型的简单分类,线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标或约束中存在非线性函数 二次规划(QP)目标为二次函数、约束为线性 整数规划(IP)决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,常用优化软件,1.LINDO/LINGO软件2.MATLAB优化工具箱/Mathematic的优化功能3.SAS(统计分析)软件的优化功能4.EXCEL软件的优化功能5.AMPL/MINOS,CPLEX,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性极小fminunc,非光滑(不可微)优化fminsearch,非线性方程(组)fzerofsolve,全局优化暂缺,非线性最小二乘lsqnonlinlsqcurvefit,线性规划linprog,纯0-1规划 bintprog一般IP(暂缺),非线性规划fminconfminimaxfgoalattainfseminf,上下界约束fminbndfminconlsqnonlinlsqcurvefit,约束线性最小二乘lsqnonneglsqlin,约束优化,二次规划quadprog,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,线性规划模型例:奶制品生产计划,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,AMPL程序,模型文件,用文本编辑器编辑,保存为milk.mod,set 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;,数据文件文件,用文本编辑器编辑,保存为milk.dat,set P:=A1 A2;param T:=A1 12 A2 8;param Q:=A1 3 A2 4;param L:=A1 24 A2 16;,批处理文件,用文本编辑器编辑,保存为milk.run,model milk.mod;data milk.dat;option solver cplexamp;solve;,运行求解,AMPL:milk.run,CPLEX 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意为原料用完.,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。,LP的约束和目标函数均为线性函数,2维,可行域 线段组成的凸多边形,目标函数 等值线为直线,最优解 凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G.B.Dantzig,1947),线性规划模型的解的几种情况,非线性规划模型例：选址问题,某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型(LP),决策变量：ci j(料场j到工地i的运量）12维,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：ci j，(xj,yj)16维,非线性规划模型(NLP),整数规划-例:聘用方案,决策变量：周一至周日每天(新)聘用人数 x1,x2,x7,目标函数：7天(新)聘用人数之和,约束条件：周一至周日每天需要人数,连续工作5天,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划模型(IP),丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？,如何选拔队员组成4100米混合泳接力队?,0-1规划 混合泳接力队的选拔,5名候选人的百米成绩,穷举法：组成接力队的方案共有5!=120种。,目标函数,若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(秒)队员i 第j 种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,每种泳姿有且只有1人,0-1规划:整数规划的特例,整数规划问题一般形式,整数线性规划(ILP)目标和约束均为线性函数 整数非线性规划(NLP)目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP)决策变量均为整数 混合整数规划(MIP)决策变量有整数，也有实数,0-1规划 决策变量只取0或1,取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题,整数规划问题对应的松弛问题,下界（对Min问题）上界（对Max问题）,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,
