下载此文档

2000b题钢管订购和运输(南昌大学全国一等奖).doc


文档分类:论文 | 页数:约16页 举报非法文档有奖
1/16
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/16 下载此文档
文档列表 文档介绍
钢管订购和运输
刘德元吴晓欣周明宇
指导教师:马新生
(南昌大学 330029)
摘要
本文建立了一个运输问题的最优化模型。
通过对图(一)的分析,我们首先直观地将路线分成两段,将图分为两个子图建立了模型一, 利用分支定界法求得总费用最优解为1279496万元。然后对模型一进行优化,得到全线的最优模型二,求得总费用最优解为1278632万元。
通过对最优模型二的分析,我们得出钢厂S1的上限产量和钢厂S6的销价的的变化对运购计划和总费用的影响最大,并给出了数据结果。
我们利用截取和连接的方法将树形图转化成为对线性图进行分析,并给出了一般的解决方法。对图(二)给出的具体模型,类似与问题一,分别建立了模型三和模型四,.
问题的提出
已知有7个钢厂,可生产输送天然气主管道的钢管,用Si表示(i=1,2,…,7)。现有15个地点(A1,A2,…,A15),沿着这15个地点铺设一条输送天然气的主管道。为方便计,1km主管道称为1单位钢管。
一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位,钢管出厂销价1单位钢管为万元,如下表:
1
2
3
4
5
6
7
800
800
1000
2000
2000
2000
3000
160
155
155
160
155
150
160
1单位钢管的铁路运价如下表:
里程(km)
≤300
301~350
351~400
401~450
451~500
运价(万元)
20
23
26
29
32
里程(km)
501~600
601~700
701~800
801~900
901~1000
运价(万元)
37
44
50
55
60
1000km以上每增加1至100km运价增加5万元。
(不足整公里部分按整公里计算)。
钢管可由铁路、公路运往铺设地点(不只是运到点,而是管道全线)。
(1)请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。
(2)请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。
(3)如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并对图二按(1)的要求给出模型和结果。
二、问题的分析
该问题是图论中运输问题的最优化问题。
经过分析,我们认为总费用可分为两种费用进行求解,分别为:
(1)销价和运输钢管至管道结点Ai(i=1,2,…,15)的总费用(称为成本费用)
(2)铺设过程中的运输费用;
要解决此问题,我们认为有两点关键:
(1)如何求出Ai(i=1,2,…,15)至Si(i=1,2,…,7)的最小成本费用;
(2)如何调整使得各路径满足题中的最优指标。
针对上述问题,我们分别运用了图上作业法、枚举法、逐次修正法、重绕最小生成树法等方法,在综合考虑算法的精度和算法的复杂度后,我们选择了图上作业法、枚举法、逐次修正法对模型进行逐次优化,直至求得最优解。
三、模型的基本假设及符号说明
基本假设:
(1)运输方式的改变所花费用包含在运费中;
(2)铁路线上任意两点可以直达,不需中途转车,即铁路线上两点
间运费按线路总长计算;
(3)假设一单位钢管可由任意长度钢管组成,购买钢管可以非整数单位购买;
(4)不考虑其它外界因素对费用的影响;
(5) 钢管在铺设时,先将钢管运到结点处,再由结点处向左右两方相邻结点铺设;
(6) 在Si厂购买钢管要么为零,要么至少为500单位。
(二)符号说明:
xij:从钢厂Si运到结点Aj的单位钢管数;
fij:单位钢管从钢厂Si运到结点Aj的的最少成本费用;
tj:第Aj点与Aj+1点间的路线长度,j=1,2,…,14;
yj:从结点Aj开始沿管道向右铺设的路线长度, j=1,2,3,…,15;
w:钢管订购和运输的总费用;
mi: 钢厂Si的最小产量,mi=500,i=1,2,3,4,5,6,7
ni: 钢厂Si的产量上限,ni=si,i=1,2, …,7
bi: 图一中各节点(见附录七)
Vi: 图二中各节点(见附录八)
四、模型的建立与求解
(一)问题一及其求解:
针对图(一),我们首先采用图上作业法对所给图进行分析,利用枚举法,我们求出一单位钢管由钢管厂Si运输至管道结点Ai的最小成本费用,具体数据如下表:

2000b题钢管订购和运输(南昌大学全国一等奖) 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数16
  • 收藏数0 收藏
  • 顶次数0
  • 上传人文库旗舰店
  • 文件大小166 KB
  • 时间2018-06-09