钢管订购与运输

1、2000B 2000B 钢管订购和运输钢管订购和运输由钢管厂订购钢管，经铁由钢管厂订购钢管，经铁路、公路运输，铺设一条路、公路运输，铺设一条钢管管道钢管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（

2、km）（沿管道建有公路）钢 厂 i1234567产 量 上 限 is80080010002000200020003000销 价ip（ 万 元 ）160155155160155150160钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计

3、）（1）制定钢管的订购和运输计划，使总费用最小）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A

4、8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形）讨论管道为树形图的情形问题问题1的基本模型和解法的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,7; j=1, 15 ），铺设管道Aj Aj+1 （j=1, 14)由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij由Aj向Aj Aj-1段铺设的长度zj及向Aj Aj+1段铺设的长度yj最优购运计划最优购运计划约束条件约束条件钢厂产量约束：上限和下限（如果生产的

5、话）运量约束：xij对i求和等于zj 加yj； yj与 zj+1之和等于Aj Aj+1段的长度lj基本模型基本模型由Aj向Aj Aj-1段铺设的运量为 1+ +zj= zj( zj+1)/2由Aj向Aj Aj+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,5000.) 1 ()1() 1(21 . 0min15117115171151151 yzjiyzxjlzyjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjj

6、ijij二次规划求解步骤求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij 难点：公路运费是里程的线性函数，而铁路运费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。7010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。算法，得到最小购运费用路线。如S7至A10的最小费用路线先铁路1130km，再

7、公路70km, 运费为77（万元）先公路（经A15）40km, 再铁路1100km，再公路70km, 运费为76（万元）的的处处理理约约束束条条件件)7 , 2 , 1(,5000)2151 isxijij问问题题求求解解。，分分解解为为上上述述形形式式的的子子的的那那些些求求解解，再再对对解解中中满满足足先先松松弛弛为为ixisxbjijijij5000)7, 1(0)151151 个个子子问问题题共共和和分分解解为为71511512)7, 1(5000) isxxaijijjij实际上只有S4和S7需要分解成子问题求解 3) 每个子问题是标准的二次规划，决策变量为xij,yj,zj, 不超

8、过135个 。0,0,0.)(05.0min1511711512151271151 yzzyxlzyzyxsxtsyyzzxcjjijjjjjijijjiijjjjjjijijij问题问题1的其它模型和解法的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题 5171,1,7,1,1,05171,1,17,1,500,0.min71517117151711 jixjxisxtsxcijiijijijijijijcij为从供应点i到需求点j的最小购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻

9、求改进算法2）最小费用网络流模型）最小费用网络流模型SourceS1S2S7A1A2A15P11P1l1P21Sink(si, pi)(+, cij)(1,1),(1,li)(1,0)SourceS1S2S7A1A2A15P1P2Sink(si, pi)(+, cij)(li, f(f+1)/2)(li,0)线性费用网络线性费用网络(只有产量上限只有产量上限)非线性费用网络非线性费用网络(只有产量上限只有产量上限)边的标记（流量上限，单位费用）用标准算法(如最小费用路算法)求解无单位费用概念(f(f+1)/2), 需修改最小费用路算法2）最小费用网络流模型）最小费用网络流模型产量有下限ri时的

10、修正SourceSiSi(si -ri, pi)(ri, 0)(+, 0)得到的结果应加上 iiipr 才是最小费用的的处处理理同同前前约约束束条条件件)7 , 2 , 1(,5000151 isxijijS1S2S3S6S5S1S2S2S3S3S5S5S63) 最小面积模型A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作图：Si到管道x单位钢管的最小购运费用c由各条Si首尾相连(横坐标)组成的一条折线对应一个购运方案，折线下面的面积对应方案的费用在产量约束下找面积最小的折线论文中发现的主要问题论文中发现的主要问题1）针对题目给的数据用凑的方法算出结果，没有解决这

11、类问题的一般模型2）局部最优，如将管道分为左右两段，分别寻求方案；如将问题分为购运和铺设两部分，分别寻优（会导致每段管道都从两端铺到中点）的的处处理理不不正正确确约约束束条条件件,5000)3151ijijsx 4）由Si至Aj的最小购运费用路线及最小费用cij 不对5）数字结果相差较大(如最小费用应127.5至128.2亿元)问题问题2：分析对购运计划和总费用影响（哪个钢厂销价：分析对购运计划和总费用影响（哪个钢厂销价的变化影响最大；哪个钢厂产量上限的变化影响最大）的变化影响最大；哪个钢厂产量上限的变化影响最大）规划问题的灵敏度分析问题问题3：管道为树形图：管道为树形图701088107062300220210170690462160320160A10A11A12S