优化模型与AMPL

1、优化模型与AMPL优化模型和算法的重要意义最优化：在一定条件下，寻求使目标最大（小）的决策最优化是工程技术.经济管理.科学研究、社 会生活中经常遇到的问题，如：结构设计资源分配生产计划运输方案解决优化问题的手段经验积累,主观判断作试验,比优劣建立数学模型,求解最优策略优化问题的一般形式优化问题三要素:决策变量;目标函数；约束条件无约束优化（没有约束）与约束优化（有约束）约束条件可行解（只满足约束）与最优解（取到最优值）局部最优解与整体最优解局部最优解(Local Optimal Solution,如 xx)整体最优解(Global Optimal Solution,如 x2)优化模型的min

2、f(x)简单分类s.t. % (x) = 0, i = 1,.g7(x)0, j = 1,.线性规划(LP)目标和约束均为线性函数非线性规划(NLP)目标或约束中存在非线性函数 /二次规划(QP)目标为二次函数、约束为线性整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP),整数非线性规划(INLP) “纯整数规划(PIP),混合整数规划(MIP) /一般整数规划，0-1 (整数)规划优化模型的简单分类和求解难度优化连续优化整数规划线性规划二次规划非线性规划问题求解的难度增加常用优化软件1. LINDO/LINGO软件2. MATLAB优化工具箱/ Mathematic的优化功能

3、3SAS（统计分析）软件的优化功能4. EXCEL软件的优化功能5. AMPL/ MINOS, CPLEXMATLA B优化工具箱能求解的优化模型线性规划模型例：奶制品生产计划获利24元/公斤获利16元/公斤每天:50桶牛奶时间480小时至多加工100公斤A】制订生产计划,使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元? A】的获利增加到30元/公斤，应否改变生产计划？每天50桶牛奶时间480小时至多加工100公斤A】获利24元/公斤获利16元/公斤决策变量 目标函数约束条件勺桶牛奶生产A 获利16X4x2Max z = 72 + 6

4、4 x2xx +x2 5012xj + 8兀2 5 4803西 0心桶牛奶生产A】 获利24X3可 每天获利原料供应 劳动时间 加工能力 非负约束AMPL程序模型文件，用文本编辑器编辑，保存为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

5、=480; subject to capacity: Qfirst(P)*xfirst(P)=100;数据文件文件，用文本编辑器编辑，保存为milk.datset P:=A1 A2;param T:=A1 12 A2 8;param Q:=A1 3 A2 4;param L:=A1 24 A2 16;批处理文件，用文本编辑器编辑，保存为milk.ru nmodel milk.mod;data milk.dat;option solver cplexamp;solve;运行求解AMPL: milk.runCPLEX 11.0.0: optimal solution; objective 3360

6、2 dual simplex iterations (1 in phase I)x *=A1 20A2 30灵敏度分析x.rc x.downx.up :=A1 06496A2 048572AMPL: displayf raw, time, capacity;AMPL: display x.rc, x.down, x.up;aw = 48time = 2capacity = 0xrc最优解下“资源”增加1单位时raw.slack=0raw. do w n = 43.3333raw. up = 60raw. current = 50效益”的增量；x.down5x.up最优解 不变时目标函数系数允许

7、变化范围影子价格原料增加1单位，利润增长48; 时间增加1单位，利润增长2;加工能力增长不影响利润AMPL: display raw.down, raw. up,raw. current, raw. si ack;影子价格有意义时约束右端的允 许变化范围;原料最少到43.3，最 大到60, slack=0意为原料用完.模型求解图解法约束条件%! + x2 5012jV + 8x2 4803旺0 目q厶：无+卷=50j 12:12xj + 8x2 = 480Z3: 3西=100?4 ：兀1 = 0, 5 ：兀2 = 0 Max z = 72兀+64x2目标函数 z=c (常数)等值线X15Z=3

8、360DZ=0Z=2400在 (20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线J最优解一定在凸多边U形的某个顶点取得。n维超平面组成的凸多面体 等值线是超平面LP的约束和目标函数均为线性函数2维可行域线段组成的凸多边形目标函数 等值线为直线【最优解 凸多边形的某个顶点凸多面体的某个顶点求解LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个 顶点中一个一个莪卞去，一是能得至d最优强。LP的通常解法是单纯形法(GB. Dantzig, 1947)线性规划模型的解的几种情况非线性规划模型-例：选址问题某公司有6个建筑工地，位置坐标为

9、（為仏）（单位：公里）,水泥日用量%（单位：吨）1123456假设：料场a1.258.750.55.7537.25b1.250.754.7556.57.75和工地之间d3547611有直线道路1）现有2料场，位于A （5, 1）,B（2, 7）, 记（Xj,yj）,j=l,2,日储量q各有20吨。目标：制定每天的供应计划，即从A, B两料场分别向 各工地运送多少吨水泥，使总的吨公里数最小。决策变量：c订 （料场j到工地i的 运量）12维min线性规划模型（LP）2 6工-勺）2 +（力-勿）21/2 7=1 /=12S7=16用例中数 据计算， 最优解为1123456（料场A：1350701J

10、 = 1，260040105 （料场B）c505050Xj e Z+, 即为非负整数乂 + 乂2 + 乂3 + XA- + 乂5 二 80整数规划%2 + 乂3 + 兀4 + 兀5 + x6 90 乂3 + x4 + 乂5 + 乂6 + 乂7 二 8 0模型（IP）o-i my 混合泳接力队的选拔5名候选人的百米成绩甲乙蝶泳1,06,857”2仰泳F06”蛙泳V2T91,06,4自由泳58”653”丙丁戊1，18”F10”1，07”41，07”819142rir124610961，23”859”457”2192”4如何选拔队员组成4x 100米混合泳接力队？ 丁的蛙泳成绩退步到1，15”2；戊

11、的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？ 穷举法：组成接力队的方案共有5!=120种。01规划模型 勺（秒）队员i第/种泳姿的百米成绩-% 1 j=2 j=3 466.875.6i=257.26666A53i=37867.4.659.4i=47074.269.657.2i=567.4713.62.4若选择队员i参加泳姿/的比赛，iBx.=l,否则记勺=0目标函数Min45Z 二工工CjjXij（M规划:整数规划的特例约束条恋每人最多入选泳姿之一每种泳姿有且只有1人4工列 15工吗=I，丿二1A 4i=lat数规划问题皿埠 f (x) 一般形式xeZs.t. hj (x) = 0, z = 1,. ,m gy.(x)0, j =1,.,/ 匸曹 Jfc数规划问题的分类整数线性规划