工程类数学建模.ppt

2000年B题 钢管订购和运输 ?? 要铺设一条 的输送天然气的主管道 , 如图一所示 (见下页 )。经筛选后可以生产这种主管道钢管的钢厂有 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道 (假设沿管道或者原来有公路，或者建有施工公路 )，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程 (单位 km)。为方便计， 1km主管道钢管称为 1单位钢管。?? 注意的几个问题 合理假设 基本原理 公式推导 模型检验 * * 请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用 )。| 160 150 155 160 155 155 160 pi 3000 2000 2000 2000 1000 800 800 si 7 6 5 4 3 2 1 i 一个钢厂如果承担制造这种钢管，至少需要生产 500个单位。钢厂 在指定期限内能生产该钢管的最大数量为si 个单位，钢管出厂销价 1单位钢管为pi 万元，如下表： 32 29 26 23 20 运价 (万元 ) 451～ 500 401～ 450 351～ 400 301～ 350 ≤ 300 里程 (km) 60 55 50 44 37 运价 (万元 ) 901～ 1000 801～ 900 701～ 800 601～ 700 501～ 600 里程 (km) 1单位钢管的铁路运价如下表： 1000km以上每增加 1至 100km运价增加 5万元。公路运输费用为 1单位钢管每公里 0.1万元（不足整公里部分按整公里计算） 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） （沿管道建有公路） 问题的基本模型和解法 总费用最小的优化问题 总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,…7; j=1, …15 ），铺设管道Aj Aj+1 （j=1, …14) 由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij 由Aj向Aj Aj-1段铺设的长度zj及向Aj Aj+1段铺设的长度yj 最优购运计划 约束条件 钢厂产量约束：上限和下限（如果生产的话） 运量约束：xij对i求和等于zj 加yj； yj与 zj+1之和等于Aj Aj+1段的长度lj 基本模型 由Aj向Aj Aj-1段铺设的运量为 1+ … +zj= zj( zj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+ … +yj= yj( yj+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 需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。 如S7至A10的最小费用路线 先铁路1130km，再公路70km, 运费为77（万元） 先公路（经A15）40km, 再铁路1100km，再公路70km, 运费为76（万元） 实际上只有S4和S7需要分解成子问题求解 (P96) 3) 每个子问题是标准的二次规划，决策变量为xij,yj,zj, 不超过135个 。 问题的其它模型和解法 1）运输问题的0-1规划模型 将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题 cij为从供应点i到需求点j的最小购运费 xij=1表示从点i到点j购运1单位钢管 2002车灯线光源的优化设计模型 汽车头部的车灯形状为一旋转抛物面，其对称轴水平地指向正前方，并已知其开口半径为36毫米，深度为21.6毫米。经过车