2000B 钢管订购和运输.ppt

2000B 钢管订购和运输由钢管厂订购钢管,经铁路、公路运输,铺设一条钢管管道 15 21AAA???? A1 3 2 5 80 10 10 31 2012 42 7010 8810 7062 7030 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 S4S5 S6 S7管道铁路公路 S1~S7 钢管厂火车站 450 里程( km ) (沿管道建有公路) 钢厂i 1234567 产量上限 is 800 800 1000 2000 2000 2000 3000 销价ip (万元) 160 155 155 160 155 150 160 钢厂的产量和销价( 1单位钢管=1 km 管道钢管) 钢厂产量的下限: 500 单位钢管里程(km) ≤ 300 301 ~ 350 351 ~ 400 401 ~ 450 451 ~ 500 运价( 万元) 20 23 26 29 32 里程(km) 501 ~ 600 601 ~ 700 701 ~ 800 801 ~ 900 901 ~ 1000 运价( 万元) 37 44 50 55 60 1单位钢管的铁路运价 1000 km 以上每增加 1至100 km 运价增加 5万元 1单位钢管的公路运价: 万元/km (不足整公里部分按整公里计) (1)制定钢管的订购和运输计划,使总费用最小. (2)分析对购运计划和总费用影响:哪个钢厂钢管销价的变化影响最大;哪个钢厂钢管产量上限的变化影响最大? A1 3 2 5 80 10 10 31 2012 42 7010 8810 7062 7030 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 S4S5 S6 S7 A16 130 A17 A18A19 A20A21 190 260 100 (3)讨论管道为树形图的情形问题 1的基本模型和解法总费用最小的优化问题总费用:订购,运输(由各厂 S i经铁路、公路至各点 A j, i=1, … 7; j=1, …15), 铺设管道 A j A j +1( j=1, …14) 由S i至A j的最小购运费用路线及最小费用 c ij 由S i至A j的最优运量 x ij由A j向A j A j -1段铺设的长度 z j及向A j A j +1段铺设的长度 y j 最优购运计划约束条件钢厂产量约束:上限和下限(如果生产的话) 运量约束: x ij对i求和等于 z j 加y j; y j与z j +1之和等于 A j A j +1段的长度 l j 基本模型由A j向A j A j -1段铺设的运量为 1+ …+z j= z j(z j +1)/2 由A j向A j A j +1段铺设的运量为 1+ …+y j= y j(y j +1)/2 )6( 0,0 )5( 15 ,,2,1,7,,2,10,0,0 )4( 14 ,,2,1 )3( 15 ,,2,1 )2(7,,2,1], 500 [}0{.. )1( ))1()1((2 min 15 1 1 71 151 71 151 151??????????????????????????????? yz jiyzx jlzy jyzx isxts yyzzxcjj ij jjj jji ij i j ij ijj jjjj ij ij?????二次规划求解步骤 1)求由 S i至A j的最小购运费用路线及最小费用 c ij 难点:公路运费是里程的线性函数,而铁路运费是里程的分段阶跃函数,故总运费不具可加性。因而计算最短路常用的 Dijkstra 算法、 Floyd 算法失效。 7010 8810 7062 7030 20 20 30 300 220 210 420 500 170 690 462 160 320 160 110 290 A10 A11 A12 A13 A14 A15 S4S5 S6 S7 需要对铁路网和公路网进行预处理,才能使