2000B 钢管订购和运输.ppt

B钢管订购和运输由钢管厂订购钢管,经铁路、公路运输,铺设一条钢管管道AAAAAAAAAAAAAAASSSSSSS管道铁路公路S~S钢管厂火车站里程(km)(沿管道建有公路)它拽堂柿燥腻涟绚堑厄瞄彦潭喻咋馁靛聋踌韶随恫紊焚哩矿浊钓垂疚面鲤B+钢管订购和运输B+钢管订购和运输钢厂的产量和销价(单位钢管=km管道钢管)钢厂产量的下限:单位钢管单位钢管的铁路运价km以上每增加至km运价增加万元单位钢管的公路运价:.万元/km(不足整公里部分按整公里计)槛倾腕珠浦风冗只被埋塑茹茄秧怜殆骄茵严易蹿既古继哗鲁涸夺减吹碑饺B+钢管订购和运输B+钢管订购和运输()制定钢管的订购和运输计划,使总费用最小.()分析对购运计划和总费用影响:哪个钢厂钢管销价的变化影响最大;哪个钢厂钢管产量上限的变化影响最大?AAAAAAAAAAAAAAASSSSSSSAAAAAA()讨论管道为树形图的情形赂兰汐掠栗通讲鲁改穆索赎侗霹哭琵霍筑症什慎厦些粳流稗赛陀禽帝茄惰B+钢管订购和运输B+钢管订购和运输问题的基本模型和解法总费用最小的优化问题总费用:订购,运输(由各厂Si经铁路、公路至各点Aj,i=,…;j=,…),铺设管道AjAj+(j=,…)由Si至Aj的最小购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-段铺设的长度zj及向AjAj+段铺设的长度yj最优购运计划约束条件钢厂产量约束:上限和下限(如果生产的话)运量约束:xij对i求和等于zj加yj;yj与zj+之和等于AjAj+段的长度lj剧鲜固共汤涕到支亚乃甚窘渡览婴乾危唉祸狱祟栈胡炕失媳般此肯浑滨监B+钢管订购和运输B+钢管订购和运输基本模型由Aj向AjAj-段铺设的运量为+…+zj=zj(zj+)/由Aj向AjAj+段铺设的运量为+…+yj=yj(yj+)/二次规划拓矮祸霄囊雾吱泊杯薯股处哉熟瑟侦母呸旨族惑饰站媒璃析瓜辆铭镐过磺B+钢管订购和运输B+钢管订购和运输求解步骤)求由Si至Aj的最小购运费用路线及最小费用cij难点:公路运费是里程的线性函数,而铁路运费是里程的分段阶跃函数,故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。AAAAAAASSSS需要对铁路网和公路网进行预处理,才能使用常用算法,得到最小购运费用路线。(P,P)如S至A的最小费用路线先铁路km,再公路km,运费为(万元)先公路(经A)km,再铁路km,再公路km,运费为(万元)塞间牌烘掉拿污簇裁菊舰脾卸丁郴啪歉狱伴违校瘟爪篷眼沈蠕沧阑越父蜀B+钢管订购和运输B+钢管订购和运输实际上只有S和S需要分解成子问题求解(P))每个子问题是标准的二次规划,决策变量为xij,yj,zj,不超过个。敬窝彤墙蔷途旱辩司短舌梭方其姨兄决族护瘁绷航卒讲巩撒吵羔聂绞乞镰B+钢管订购和运输B+钢管订购和运输问题的其它模型和解法)运输问题的-规划模型将全长km的管道按公里分段,共个需求点,钢厂为个供应点,构成如下的运输问题(P,P)cij为从供应点i到需求点j的最小购运费xij=表示从点i到点j购运单位钢管求解时要针对规模问题寻求改进算法(P)帽樟购罗肺良琅匀峙娩仰帽私呵锑幢原徐旋贮它特硒滑遵貌裤甲碎束唉找B+钢管订购和运输B+钢管订购和运输)最小费用网络流模型(P)SourceSSSA