2000B-钢管订购和运输

2000B钢管订购和运输由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km）（沿管道建有公路）钢厂i1234567产量上限is80080010002000200020003000销价ip（万元）160155155160155150160钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管里程(km)≤300301～350351～400401～450451～500运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)37445055601单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（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)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((21.0min15117115171151151yzjiyzxjlzyjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij二次规划求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。（P68,P76）如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76（万元）的处理约束条件)7,,2,1(],500[}0{)2151isxijij问题求解。，分解为上述形式的子的那些求解，再对解中满足先松弛为ixisxbjijijij5000)7,1(0)151151个子问题共和分解为71511512)7,1(5000)isxxaijijjij实际上只有S4和S7需要分解成子问题求解(P96)3)每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。0,0,,,,,0..)(05.0min1511711512151271151yzzyxlzyzyxsxtsyyzzxcjjijjjjjijijjiijjjjjjijijij问题1的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题(P60,P92)5171,1,7,1},1,0{5171,1,17,1]},,500[,0{..min71517117151711jixjxisxtsxcijiijijijijijijcij为从供应点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)得到的结果应加上iiipr才是最小费用的处理同前约束条件)7,,2,1(],500[}0{151isxijijS1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型（P84）A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作图：Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用在产量约束下找面积最小的折线论文中发现的主要问题1）针对题目给的数据用凑的方法算出结果，没有解决这类问题的一般模型2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）的处理不正确约束条件],500[}0{)3151ijijsx4）由Si至Aj的最小购运费用路线及最小费用cij不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)问题2：分析对购运计划和总费用影响（哪个钢厂销价的变化影响最大；哪个钢厂产量上限的变化影响最大）规划问题的灵敏度分析（P76,P85,P97）问题3：管道为树形图701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100,0,,,,]},500[,0{..)(05.0min71)(2112211)(71211jkijjkkjjkijkEjkijjiijjkjkjEjkijijijyxlyyyxsxtsyyxc(jk)是连接Aj,Ak的边，E是树形图的边集，ljk是(jk)的长度，yjk是由Aj沿(jk)铺设的钢管数量