数学建模优化问题解析.ppt

优化方法建模 侯为根 安徽工业大学数理学院 Email：wghou@ 优化模型和算法的重要意义 最优化: 在一定条件下，寻求使目标最大(小)的决策 最优化是工程技术、经济管理、科学研究、社会 生活中经常遇到的问题, 如: 运输方案结构设计 资源分配 生产计划 • 经验积累，主观判断 • 作试验，比优劣 • 建立数学模型，求解最优策略 解决优化问题的手段 CUMCM赛题：约有一半为优化问题须用软件求解 (最)优化理论是运筹学的重要内容 OR/ MS/ DS 运筹学(OR: Operations/Operational Research) 管理科学(MS: Management Science) 决策科学(DS: Decision Science) 优化(Optimization), 规划(Programming) 线 性 规 划 无 约 束 优 化 非 线 性 规 划 网 络 优 化 组 合 优 化 整 数 规 划 多 目 标 规 划 目 标 规 划 动 态 规 划 优化问题的一般形式 优化问题三要素：决策变量；目标函数；约束条件 目标函数 约 束 条 件 决 策 变 量 可行解(满足约束条件)，可行域(可行解的集合)， 最优解(使目标达到最大/最小的可行解) 无约束优化:只有目标函数; 约束优化:有目标函数和 约束条件。

实际问题一般总有约束 例1 加工奶制品的生产计划 获利24元/公斤 获利16元/公斤 1桶 牛奶 12小时 8小时 3公斤A1 4公斤A2 或 每天: 50桶牛奶 时间480小时 A1至多加工100公斤 制订生产计划，使每天获利最大 •35元可买到1桶牛奶，买吗？若买，每天最多买多少? •可聘用临时工人，付出的工资最多是每小时几元? •A1的获利增加到30元/公斤，应否改变生产计划？ 获利24元/公斤 获利16元/公斤 1桶 牛奶 12小时 8小时 3公斤A1 4公斤A2 或 每天： 50桶牛奶 时间480小时 A1至多加工100公斤 决策变量x1桶牛奶生产A1x2桶牛奶生产A2 目标函数获利24×3x1获利16×4x2 每天获利 Max z =72x1 +64 x2 约束条件 原料供应 劳动时间 加工能力 非负约束 x1+x250 线性 规划 模型 (LP) 12x1+8x2480 3x1100 x1, x20 模型求解图解法 约 束 条 件 x1+x250 12x1+8x2480 3x1100 x1, x20 l1:x1+x2=50 l2:12x1+8x2=480 l3: 3x1=100 l4: x1=0, l5: x2=0 目标 函数 Max z =72x1 +64 x2 z=c(常数)~等值线 在B(20,30)点得到最优解 最优解一定在 凸多边形的某 个顶点取得 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 模型求解 软件实现 Objective value: 3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000 max=72*x1+64*x2; x1+x2= required(J)); end 8 名同学准备分成4 个调查队（每队两人）前往4 个 地区进行社会调查。

设两两之间组队的效率如表所 示（由于对称性只列出了上三角部分），问如何组 队可以使总效率最高？ 例8: 匹配问题 学生s1s2s3s4s5s6s7s8 s1_9342156 s2__173521 s3___44291 s4____1552 s5_____876 s6______23 s7_______4 “元素过滤”法 设mij为0-1变量，mij=1表示学生i与j匹配，设bij为 学生i与j匹配的效率，目标为总效率最高： 目标函数 对学生i有且只有一个其他的学生与其匹配 约束条件 mij为0-1变量 MODEL: SETS: students / 18/; pairs(students,students)| ENDSETS DATA: efects = 9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4; ENDDATA MAX=@SUM( pairs(I,J):efects(I,J)*match(I,J)); @FOR(students(I):@SUM(pairs(J,K)|J#EQ#I #OR# K#EQ#I:match(J,K))=1); @FOR(pairs(I,J):@BIN(match(I,J))); END 结果为{1,8},{2,4},{3,7},{5,6}匹配,效率为30 。

在公路网中，司机希望找到一条从一个城市到另一 个城市的最短路. 假设图表示的是该公路网, 节点表示 货车可以停靠的城市,弧上的权表示两个城市之间的距 离（百公里）.那么,货车从城市S 出发到达城市T,如何 选择行路线,使所经过的路程最短? S A1 A2 A3 B1 B2 C1 C2 T 6 3 3 6 5 8 6 7 4 6 7 8 9 5 6 S到T的最优行驶路线P 先求出从Ck(k=1,2)到T的 最优行驶路线. 从Bk到T的最优行驶路线. 从Ak到T的最优行驶路线 . 例9 最短路问题 从S到T的行驶过程分成4 个阶段,即S→Ai(i=1,2 或 3), Ai→ Bj(j=1或2), Bj → Ck(k=1或2), Ck → T 记d(Y,X)为城市Y与城市X之间的直接距离（若这两 个城市之间没有道路直接相连，则可以认为直接距 离为无穷大），用L(X)表示城市X到城市T的最优行 驶路线的路长, 则: !最短路问题; model: sets: cities/S,A1,A2,A3,B1,B2,C1,C2,T/: L; roads(cities,cities)/ S,A1 S,A2 S,A3 A1,B1 A1,B2 A2,B1 A2,B2 A3,B1 A3,B2 B1,C1 B1,C2 B2,C1 B2,C2 C1,T C2,T /: P,D; endsets data: D=6 3 3 6 5 8 6 7 4 6 7 8 9 5 6; L= , , , , , , , ,0; enddata !L(@index(T))=0; @for(cities(i)|i#LT#@INDEX(T):L(i)=@min(roads(i,j): D(i,j)+L(j));); !显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i-j，否则就不是。

由此，我们就可方便的确定出最短路径; @for(roads(i,j):P(i,j)=@if(L(i) #eq# D(i,j)+L(j),1,0)); end 结果L(S)=20，路径为：S→A3→B2→C1→T 1 3 2 4 5 6 7 8 9 10 5 1 2 13 12 11 6 3 10 4 12 14 9 6 8 5 10 5 2 现有10个城市的交通网，我们想找到从城市1到城 市10的最短路径; 动态规划图示说明 SETS: ! 这里是10个城市的基础集，其中F( i) 表示从城市i到最后一个城 市的最短路径; CITIES /110/: F; ! 派生集ROADS列出了城市间所有存在的道路（注：并非所有城市间 都有道路直接连接，并假定所有直接连接路径仅有一条 ; ROADS( CITIES, CITIES)/ 1,2 1,3 1,4 2,5 2,6 2,7 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D( i, j) 是城市 i 到 j的距离; ENDSETS DATA: ! 这里是对应于上述直接连接的道路的长度 ; D = 1 5 2 13 12 11 6 10 4 12 14 3 9 6 5 8 10 5 2; ENDDATA ! 如果你已经位于城市10，则你到城市的10旅行长度为0; F( @SIZE( CITIES)) = 0; ! 下列是经典的动态规划递归式。

用语言叙述就是：从城市i到城市 10的最短路径为城市i到所有能直达的城市j的路径长度加上城市j到 城市10的最短路径的和的最小值; @FOR( CITIES( i)| i #LT# @SIZE( CITIES): F( i) = @MIN( ROADS( i, j): D( i, j) + F( j))); 例10: 装车问题 要把七种不同规格的包装箱装到两辆铁路平板车上去 ，包装箱的宽和高都是相等的，但厚度（t以厘米计） 及重量（w以千克计）却不同，下表给出它们的厚度、 重量及数量 c1c2c3c4c5c6c7 t(厘米)48.752.061.372.048.752.064.0 w(千克 ) 200030001000500400020001000 k(箱数)8796648 每辆平板车有10.2米长的地方可用于装箱（像面包片那 样），载重量为40吨，由于当地的货运的限制，对c3、 c6、c7三类包装箱的总数有如下特殊约束： 他们所占的空间不得超过302.7厘米，是把这些包装 箱装到车上去，而浪费的空间最小 问题分析 包装箱总重89吨，平板车能载80吨，装不完，究竟 在车上装那些包装箱，每种装多少，必须有一个标 准，该标准应遵循：重量、厚度等约束，目标是使 车上的剩余空间最小。

还要注意：对5、6、7三种包装箱的厚度约束，问题并 没有给出是每辆车上5、6、7三种包装箱的厚度不超过 302.7厘米，还是两辆车上的总厚度不超过302.7厘米， 应分别加以考虑 问题假设 1）集装箱在装车时两个集装箱之间不留缝隙，其在给 定集装箱尺寸时已考虑了 2）假定5、6、7三种包装箱在每节平板车上装载的厚 度不超过302.7厘米 模型建立 设xij表示第i辆平板车上装cj箱的个数，则有如下约束 ： 自然约束： xij0 且为整数 (1) 箱数约束： x11+ x21 8 (2) x12+ x22 7 (3) x13+ x23 9 (4) x14+ x24 6 (5) x15+ x25 6 (6) x16+ x26 4 (7) x17+ x27 8 (8) 重量约束： 2xi1+ 3xi2+ xi3+ 0.5xi4+ 4xi5+ 2xi6+ xi7+ 40 i=1,2 (9, 10) 厚度约束： 0.487xi1+ 0.520xi2+ 0.613xi3+ 0.72xi4+ 0.487xi5+ 0.520xi6+ 0.640xi7+ 10.2 i=1,2 (11, 12) 。