文档介绍：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)SourceSSSAAAPPlP…