文档介绍：钢厂的产量和销价(1单位钢管=1km管道钢管)钢厂产量的下限:500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价:(不足整公里部分按整公里计)(1)制定钢管的订购和运输计划,使总费用最小.(2)分析对购运计划和总费用影响:哪个钢厂钢管销价的变化影响最大;哪个钢厂钢管产量上限的变化影响最大?A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003061952027206905201706904621603201601102901**********A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100(3)讨论管道为树形图的情形问题1的基本模型和解法总费用最小的优化问题总费用:订购,运输(由各厂Si经铁路、公路至各点Aj,i=1,…7;j=1,…15),铺设管道AjAj+1(j=1,…14)由Si至Aj的最小购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度zj及向AjAj+1段铺设的长度yj最优购运计划约束条件钢厂产量约束:上限和下限(如果生产的话)运量约束:xij对i求和等于zj加yj;yj与zj+1之和等于AjAj+1段的长度lj基本模型由Aj向AjAj-1段铺设的运量为1+…+zj=zj(zj+1)/2由Aj向AjAj+1段铺设的运量为1+…+yj=yj(yj+1)/2二次规划求解步骤1)求由Si至Aj的最小购运费用路线及最小费用cij难点:公路运费是里程的线性函数,而铁路运费是里程的分段阶跃函数,故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理,才能使用常用算法,得到最小购运费用路线。(P68,P76)如S7至A10的最小费用路线先铁路1130km,再公路70km,运费为77(万元)先公路(经A15)40km,再铁路1100km,再公路70km,运费为76(万元)实际上只有S4和S7需要分解成子问题求解(P96)3)每个子问题是标准的二次规划,决策变量为xij,yj,zj,不超过135个。问题1的其它模型和解法1)运输问题的0-1规划模型将全长5171km的管道按公里分段,共5171个需求点,钢厂为7个供应点,构成如下的运输问题(P60,P92)cij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法(P61)2)最小费用网络流模型(P70)SourceS1S2S7A1A2A15P11P1l1P21…………Sink(si,pi)(+,cij)(1,1),…(1,li)(1,0)SourceS1S2S7A1A2A15P1P2………Sink(si,pi)(+,cij)(li,f(f+1)/2)(li,0)线性费用网络(只有产量上限)非线性费用网络(只有产量上限)边的标记(流量上限,单位费用)用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2),需修改最小费用路算法2)最小费用网络流模型(P70)产量有下限ri时的修正SourceSiSi’(si-ri,pi)(ri,0)(+,0)得到的结果应加上才是最小费用S1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型(P84)A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作图:Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案,折线下面的面积对应方案的费用在产量约束下找面积最小的折线