[文学]数学建模讲座2008Sep河北大学.ppt

数学建模：数学与实际问题的桥梁 数学建模: 应用数学知识解决实际问题的第一步 数学建模: 通常有本质性的困难和原始性的创新(关键一步) Pure Math vs Applied Math: Logic vs Problem Driving “源”（Motivation）远“流”（Impact）长 美国MCM+ICM竞赛规模 我国CUMCM竞赛规模 fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量 小结： CUMCM评阅标准 模型完整明确 模型/算法创新 软件使用恰当 例 CUMCM-2000B 钢管订购和运输 由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道 A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 306 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 管道 铁路 公路 S1~S7 钢管厂 火车站 450 里程（km) （沿管道建有公路） 钢厂的产量和销价（1单位钢管=1km管道钢管） 钢厂产量的下限：500单位钢管 1单位钢管的铁路运价 1000km以上每增加1至100km运价增加5万元 1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计） 601 = 300 + 301 44 20 + 23 ? （1）制定钢管的订购和运输计划，使总费用最小. （2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？ A1 3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 306 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 S2 S3 S4 S5 S6 S7 A16 130 A17 A18 A19 A20 A21 190 260 100 （3）讨论管道为树形图的情形 问题1的基本模型和解法 总费用最小的优化问题 总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,…7; j=1, …15 ），铺设管道Aj Aj+1 （j=1, …14) 由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij 由Aj向Aj Aj-1段铺设的长度yj及向Aj Aj+1段铺设的长度zj 最优购运计划 约束条件 钢厂产量约束：上限和下限（如果生产的话） 运量约束：xij对i求和等于zj 加yj； zj与 yj+1之和等于Aj Aj+1段的长度lj yj zj Aj 基本模型 由Aj向Aj Aj-1段铺设的运量为 1+ … +yj= yj( yj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+ … +zj= zj( zj+1)/2 二次规划？ 求解步骤 1）求由Si至Aj的最小购运费用路线及最小费用cij 难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。 A1 70 10 88 10 70 62 70 30 20 20 30 300 220 210 420 500 170 690 462 160 320 160 110 290 A10 A11 A12 A13 A14 A15 S4 S5 S6 S7 需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。-- 至少求3次最短路 如S7至A10的最小费用路线 先铁路1130km，再公路70km, 运费为77（万元） 先公路（经A15）40km, 再铁路1100km，再公路70km, 运费为76（万元） 实际上只有S4和S7需要分解成子问题求解 每个子问题是标准的二次规划，决策变量为xij,yj,zj, 不超过135个 。 c) 比较好的方法：引入0-1变