《钢管订购和运输优化模型.ppt》由会员分享,可在线阅读,更多相关《钢管订购和运输优化模型.ppt(21页珍藏版)》请在金锄头文库上搜索。
1、钢管订购和运输优化模型主讲人: 廖海涛(实验动09) 谭良红(实验动09) 问题的提出:要铺设一条 的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有 。图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。A132580101031201242701088107062703020203045010430175060619420520168048030022021042050060030601952027206905201706904621
2、60320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7 钢管运输问题(CUMCM-2000B)为方便计,1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂 在指定期限内能生产该钢管的最大数量为 个单位,钢管出厂销价1单位钢管为 万元,如下表:1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表:里程里程(km)300301 350351 400401 450451 500运价运价
3、(万元万元)2023262932里程里程(km)5016006017007018008019009011000运价运价(万元万元)37445055601000km以上每增加1至100km运价增加5万元公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)钢管可由铁路、公路运往铺设地点(不只是运到点 ,而是管道全线)问题:(1)请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。(2)请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。(3)如果要铺设的管道不是一
4、条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并对图二按(1)的要求给出模型和结果。基本假设:1. 沿铺设的主管道已经有公路或者有施工公 路2. 1km主管道钢管称为1单位钢管,在主管道上每千米卸1单位的钢管3. 公路运输费用为1单位钢管0.1万元每千米(不足整千米部分按整千米计算)4. 在计算总费用时只考虑运输费和购买钢管的费用5. 钢管在铁路运输路程超过 1000km以上每增加1至100km运价增加5万元符号说明:Aj:主管道与公路的第i个交点,称为结点结点; Si :第i个钢厂; si :钢厂Si在指定期限内生产钢管的最大数量; pi :由钢厂Si
5、 生产的单位钢管的出厂销价; Xij :从钢厂Si运到主管道结点Aj的钢管数量; Cij :从钢厂Si运一单位钢管到主管道结点Aj的最小费用;Ti1 :从主管道结点Ai向左端铺管道所用钢管的数量; Ti2 :从主管道结点Ai向右端铺管道所用钢管的数量; Ti,j :从主管道结点Ai向Aj方向铺管道所用钢管的数量; H :公路单位运费; Mat(i,j): 结点i到结点j的距离。 钢管的铺设是全线的,而不只是运到点A1,A2, A15 。 v常用解法常用解法: 二次规划二次规划v先计算最小运费矩阵先计算最小运费矩阵两种运输方式(铁路公路)混合最短路问题两种运输方式(铁路公路)混合最短路问题是普通
6、最短路问题的变种,需要自己设计算法是普通最短路问题的变种,需要自己设计算法 钢管运输问题(CUMCM-2000B)问题分析:问题一,首先,所有钢管必须运到天然气主管道铺设路线上的节点 ,然后才能向左或右铺设。必须求出每个钢管厂 到每个节点 的每单位钢管的最小运输费用。表1 单位钢管从 运输到 的最小运输费用(单位:万元)S1S2S3S4S5S6S7A1170.7 170.7 215.7 215.7 A2160.3 160.3 205.3 205.3 A3140.2 140.2 190.2 190.2 A498.6 98.6 171.6 171.6 A538.0 38.0 111.0 111.0
7、 A620.5 20.5 95.5 95.5 A73.1 3.1 86.0 86.0 A821.2 21.2 71.2 71.2 A964.2 64.2 114.2 114.2 A1092.0 92.0 142.0 142.0 A1196.0 96.0 146.0 146.0 A12106.0 106.0 156.0 156.0 A13121.2 121.2 171.2 171.2 A14128.0 128.0 178.0 178.0 A15142.0 142.0 192.0 192.0 fi表示钢厂表示钢厂i是否使用;是否使用;xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是
8、从节点是从节点j向左铺设的钢管量;向左铺设的钢管量;zj是向右铺设的钢管量是向右铺设的钢管量 钢管运输问题(CUMCM-2000B)LINDO/LINGO得到的结果比matlab得到的好cumcm2000b.lg4问题三如果要铺设的管道不是一条线,而是一个树如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并这种更一般的情形给出一种解决办法,并对图二按(对图二按(1)的要求给出模型和结果。)的要求给出模型和结果。 对于问题三的一般模型设有m个钢厂,S1,S2,Sm,以si,pi表示钢厂Si的生产的数量
9、和销售价格,n个管道节点分别是A1,A2An。若Ai与Aj关联(设ij),设置变量 其中dij表示结点Ai与Aj的距离,yij表示由结点Ai向结点Aj方向铺设的距离,若Ai与Aj不关联,则yij=0,dij=0。运往结点Aj处的钢管数量Nj得到问题三的一般非线性规划模型问题三需要求解的图与图(1)的比较A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7问题三的数学模型钢厂数m=7,结点数n=21建立非线性规划模型:谢谢