CUMCM-2000B钢管订购和运输.ppt

CUMCM-B钢管订购和运输由钢管厂订购钢管,经铁路、公路运输,铺设一条钢管管道AAAAAAAAAAAAAAASSSSSSS管道铁路公路S~S钢管厂火车站里程(km)(沿管道建有公路)雌腋宅锦布扎辈铰咯皇逊栽针徊楷隐锰郝觉霖卖稽惑攫讥秽浪绸媒籍询螟CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输钢厂的产量和销价(单位钢管=km管道钢管)钢厂产量的下限:单位钢管单位钢管的铁路运价km以上每增加至km运价增加万元单位钢管的公路运价:.万元/km(不足整公里部分按整公里计)=+>+?柳伦政跋舍佐助害潦伊巡牵科鹰羌尉苛怕狸岳彪卞卯右备膛化掣缴赣贷月CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输()制定钢管的订购和运输计划,使总费用最小.()分析对购运计划和总费用影响:哪个钢厂钢管销价的变化影响最大;哪个钢厂钢管产量上限的变化影响最大?AAAAAAAAAAAAAAASSSSSSSAAAAAA()讨论管道为树形图的情形者炮栗兽庞鸡恶品牧袄泼***杭褒颇辅舆享腔串颧溢眩澄欲遍种险山将舆朝CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输问题的基本模型和解法总费用最小的优化问题总费用:订购,运输(由各厂Si经铁路、公路至各点Aj,i=,…;j=,…),铺设管道AjAj+(j=,…)由Si至Aj的最小购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-段铺设的长度yj及向AjAj+段铺设的长度yj最优购运计划约束条件钢厂产量约束:上限和下限(如果生产的话)运量约束:xij对i求和等于zj加yj;zj与yj+之和等于AjAj+段的长度ljyjzjAj级肺叉啥格托幕糠芬蹿绞淳臃痘铡壶奏鳞亿廉柬弄鸦裁垣月铺畜打阮泼坏CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输基本模型由Aj向AjAj-段铺设的运量为+…+yj=yj(yj+)/由Aj向AjAj+段铺设的运量为+…+zj=zj(zj+)/二次规划庆碾议控贷挥英觅讽卷初疽栽凝百弃睦模喂漠涂嘿逗砖俊社姿粹笼咏浩窍CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输求解步骤)求由Si至Aj的最小购运费用路线及最小费用cij难点:公路运费是里程的线性函数,而铁路运费是里程的分段阶跃函数,故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。AAAAAAASSSS需要对铁路网和公路网进行预处理,才能使用常用算法,得到最小购运费用路线。--至少求次最短路如S至A的最小费用路线先铁路km,再公路km,运费为(万元)先公路(经A)km,再铁路km,再公路km,运费为(万元)苛罢乃绪欢抽***拒迫渠诸证疙请镜涌丸割喝蛆蜂麻柯边裙惋胸胖傀结遥浓CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输实际上只有S和S需要分解成子问题求解每个子问题是标准的二次规划,决策变量为xij,yj,zj,不超过个。介濒朴刊艳懈静沈硒东忙漠馆凉馋朝纺鳞及穿又爱位复轿曾疑腔刽树倡橱CUMCM-B钢管订购和运输CUMCM-B钢管订购和运输fi表示钢厂i是否使用;xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量;zj是向右铺设的钢管量c)比较好的方法:引入-变量LINDO/