优化模型与AMPL.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,上一页,下一页,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,优化模型与,AMPL,1,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:,优化模型和算法的重要意义,结构设计,资源分配,生产计划,运输方案,解决优化问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型，求解最优策略,最优化:在一定条件下，寻求使目标最大(小)的决策,2,优化问题三要素：,决策变量；目标函数；约束条件,约束条件,决策变量,优化问题的一般形式,无约束优化,(,没有约束,),与约束优化,(,有约束,),可行解（只满足约束）与最优解,(,取到最优值,),目标函数,6/3/2025,3,局部最优解与整体最优解,局部最优解,(Local Optimal Solution,如,x,1,),整体最优解,(Global Optimal Solution,如,x,2,),x,*,f,(,x,),x,1,x,2,o,6/3/2025,4,优化模型的,简单分类,线性规划,(LP),目标和约束均为线性函数,非线性规划,(NLP),目标或约束中存在非线性函数,二次规划,(QP),目标为二次函数、约束为线性,整数规划,(IP),决策变量,(,全部或部分,),为整数,整数,线性,规划,(ILP),，整数,非线性,规划,(INLP),纯整数规划,(PIP),混合整数规划,(MIP),一般整数规划，,0-1,（整数）规划,连续优化,离散优化,数学规划,5,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,6,常用优化软件,1.LINDO/LINGO软件,2.MATLAB优化工具箱/Mathematic的优化功能,3.SAS(统计分析)软件的优化功能,4.EXCEL,软件的优化功能,5.AMPL/MINOS,CPLEX,7,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0(MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线性,极小,fminunc,非光滑(不可,微)优化,fminsearch,非线性,方程(组),fzero,fsolve,全局,优化,暂缺,非线性,最小二乘,lsqnonlin,lsqcurvefit,线性规划,linprog,纯0-1规划 bintprog,一般IP,(暂缺),非线性规划,fmincon,fminimax,fgoalattain,fseminf,上下界约束,fminbnd,fmincon,lsqnonlin,lsqcurvefit,约束线性,最小二乘,lsqnonneg,lsqlin,约束优化,二次规划,quadprog,8,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,50桶牛奶,时间480小时,至多加工100公斤A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,线性规划模型例:奶制品生产计划,9,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,x,1,桶牛奶生产A,1,x,2,桶牛奶生产A,2,获利 243,x,1,获利 164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A,1,50桶牛奶,每天,10,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;,11,数据文件文件,用文本编辑器编辑,保存为,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;,12,运行求解,AMPL:milk.run,CPLEX 11.0.0:optimal solution;objective 3360,2 dual simplex iterations(1 in phase I),x*:=,A1 20,A2 30,;,13,灵敏度分析,AMPL:display x.rc,x.down,x.up;,x.rc x.down x.up :=,A1 0 64 96,A2 0 48 72,;,x.rc最优解下“资源”增加1单位时“,效益”的增量;x.down,x.up最优解不变时目标函数系数允许变化范围,AMPL:display raw,time,capacity;,aw=48,time=2,capacity=0,原料增加1单位,利润增长48;,时间增加1单位,利润增长2;,加工能力增长不影响利润,影子价格,AMPL:display raw.down,raw.up,raw.current,raw.slack;,raw.down=43.3333,raw.up=60,raw.current=50,raw.slack=0,影子价格有意义时约束右端的允许变化范围;原料最少到43.3,最大到60,slack=0意为原料用完.,14,模型求解,图解法,x,1,x,2,0,A,B,C,D,l,1,l,2,l,3,l,4,l,5,约束条件,目标函数,Z,=0,Z,=2400,Z,=3360,z,=,c,(常数)等值线,c,在,B,(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,15,求解LP的基本思想,思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到,最优解,。,LP的约束和目标函数均为线性函数,2维,可行域,线段组成的凸多边形,目标函数,等值线为直线,最优解,凸多边形的某个顶点,n维,超平面组成的凸多面体,等值线是超平面,凸多面体的某个顶点,LP的通常解法是单纯形法(G.B.Dantzig,1947),16,线性规划模型的解的几种情况,线性规划问题,有可行解(Feasible),无可行解（Infeasible）,有最优解（Optimal）,无最优解(Unbounded),17,非线性规划模型例：选址问题,某公司有6个建筑工地，位置坐标为(,a,i,b,i,)(单位：公里),水泥日用量,d,i,(单位：吨）,假设：,料场和工地之间有直线道路,18,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型(LP),决策变量：,c,i j,(,料场j,到,工地i的运量）12维,19,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(,x,j,y,j,)和运量,c,ij,，在其它条件不变下使总吨公里数最小。,决策变量：,c,i j，,(,x,j,y,j,)16维,非线性规划模型,(NLP),20,整数规划-例:,聘用方案,决策变量,：周一至周日每天(新)聘用人数,x,1,x,2,x,7,目标函数,：7天(新)聘用人数之和,约束条件,：周一至周日每天需要人数,21,连续工作5天,周一工作的应是(上)周四至周一聘用的,设系统已进入稳态（不是开始的几周）,聘用方案,整数规划,模型(IP),22,丁的蛙泳成绩退步到,115”2,；戊的自由泳成绩进步到,57”5,组成接力队的方案是否应该调整,？,如何选拔队员组成4,100米混合泳接力队?,0-1规划 混合泳接力队的选拔,甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,5名候选人的,百米成绩,穷举法,：,组成接力队的方案共有,5!=120,种,。,23,目标函数,若选择队员,i,参加泳姿,j,的比赛，记,x,ij,=1,否则记,x,ij,=0,0-1,规划模型,c,ij,(秒),队员,i,第,j,种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,c,ij,i,=1,i,=2,i,=3,i,=4,i,=5,j,=1,66.8,57.2,78,70,67.4,j,=2,75.6,66,67.8,74.2,71,j,=3,87,66.4,84.6,69.6,83.8,j,=4,58.6,53,59.4,57.2,62.4,每种泳姿有且只有1人,0-1规划:,整数规划的特例,24,整数规划问题一般形式,整数线性规划,(ILP),目标和约束均为线性函数,整数非线性规划,(NLP),目标或约束中存在非线性函数,整数规划问题的分类,纯,(,全,),整数规划,(PIP),决策变量均为整数,混合整数规划,(MIP),决策变量有整数，也有实数,0-1,规划,决策变量只取,0,或,1,6/3/2025,25,取消整数规划中决策变量为整数的限制（,松弛,），对应的连续优化问题称为原问题的,松弛问题,整数规划问题对应的松弛问题,松弛问题,松弛,整数规划问题,最优解,最优解,整数,非整数,整数,舍入,下界（对Min问题）,上界（对Max问题）,非最优解,26,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：,生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等,实际问题规模往往较大，用软件求解比较方便,27,