资源描述：
《CUMCM-2000B钢管订购和运输.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、CUMCM-2000B钢管订购和运输由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1~S7钢管厂火车站450里程（km)（沿管道建
2、有公路）钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管1单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）601=300+30144>20+23?（1）制定钢管的订购和运输计划，使总费用最小.（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的变化影响最大；哪个钢厂钢管产量上限的变化影响最大？A1325801010312012427010881070627030202030450104301750606194205
3、201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）讨论管道为树形图的情形问题1的基本模型和解法总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,…7;j=1,…15），铺设管道AjAj+1（j=1,…14)由Si至Aj的最小购
4、运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度yj及向AjAj+1段铺设的长度yj最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj加yj；zj与yj+1之和等于AjAj+1段的长度ljyjzjAj基本模型由Aj向AjAj-1段铺设的运量为1+…+yj=yj(yj+1)/2由Aj向AjAj+1段铺设的运量为1+…+zj=zj(zj+1)/2二次规划求解步骤1）求由Si至Aj的最小购运费用路线及最小费用cij难点：公路运费是里程的线性函数，而铁路运
5、费是里程的分段阶跃函数，故总运费不具可加性。因而计算最短路常用的Dijkstra算法、Floyd算法失效。A17010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要对铁路网和公路网进行预处理，才能使用常用算法，得到最小购运费用路线。--至少求3次最短路如S7至A10的最小费用路线先铁路1130km，再公路70km,运费为77（万元）先公路（经A15）40km,再铁路1100km，再公路70km,运费为76
6、（万元）实际上只有S4和S7需要分解成子问题求解每个子问题是标准的二次规划，决策变量为xij,yj,zj,不超过135个。fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量c)比较好的方法：引入0-1变量LINDO/LINGO得到的结果比matlab得到的好exam1202d.lg4yjzjj问题1的其它模型和解法1）运输问题的0-1规划模型将全长5171km的管道按公里分段，共5171个需求点，钢厂为7个供应点，构成如下的运输问题cij为从供应点i到需求点j的最小
7、购运费xij=1表示从点i到点j购运1单位钢管求解时要针对规模问题寻求改进算法2）最小费用网络流模型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),需修改
8、最小费用路算法2）最小费用网络流模型产量有下限ri时的修正SourceSiSi’(si-ri,pi)(ri,0)(+,0)得到的结果应加上才是最小费用注：该模型获当年的惟一最高奖（网易杯）S1S2S3S6S5S1S2S2S3S3S5S5S63)最小面积模型A1A2A3A4A
