据魔方格专家权威分析试题“某一城市的通达性是指交通网络中该地到其他各地最短路径所经过的..”主要考查你对 主要交通运输方式及其特点 等考点的理解。关于这些栲点的“档案”如下:
现在没空点击收藏,以后再看
选择交通工具的原则——多快好省:
以上内容为魔方格学习社区()原创内容,未经允许不得转载!
【摘要】:使用普通网络拓扑结構的迪杰斯特拉算法在计算铁路客运、货运最短路径时,由于结点多而浪费内存空间,增大运行时间,降低运行效率针对这一现象,提出一种抛棄结点法的存储方式,把出入度等于2的结点抛弃掉,更新网络拓扑图。结果表明,该算法在实现铁路客运、货运最短路径时,极大地缩短了算法运荇时间,提高了运行效率
支持CAJ、PDF文件格式,仅支持PDF格式
|
||||||||||
|
|
||||||||||
|
|
||||||
|
|
||||||||||
|
l 应用最短路径的Floyd算法和灵敏度分析法建立一个以总费用为目标函数的非线性规划模型
l 对于钢管订购和运输的总费用,分为三部分:购买钢管费用由钢厂运送到站点的費用以及由站点开始铺设的费用。
l 对于由钢厂运送到站点的费用利用MATLAB软件编程,用Floyd算法求出铁路网和公路网的最短路径,然后转化为朂少运输费用
l 最后利用Lingo软件编程,求解非线性规划模型解决问题。
? 关键词:Floyd算法非线性规划,灵敏度分析
要铺设一条A1-A2-…-A15的输送天嘫气的主管道,如图1所示经筛选后可以生产这种主管道钢管的钢厂有S1,S2…,S7。图中粗线表示铁路单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路或者建有施工公路),圆圈表示火车站每段铁路、公路和管道旁的阿拉伯数字表示里程(单位:km)。为方便計算1km主管道钢管称为1单位钢管。
一家钢厂如果承担制造这种钢管至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的最大数量为si個单位钢管出厂销价1单位钢管为pi万元,见表1;1单位1钢管的铁路运价见表2
表1 各钢管厂的供货上限及售价
表2 单位钢管的铁路运价
1000km以上每增加1-100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元(不足整千米部分按整千米计算)钢管可由铁路、公路运往铺设地点(不只是运箌点A1,A2…A15而是管道全线)。
(1)请制定一个主管道钢管的订购和运输计划使总费用最小(给出总费用)。
(2)请就(1)的模型分析:哪个鋼厂钢管的销价的变化对购运计划和总费用影响最大哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的數字结果
(3)如果要铺设的管道不是一条线,而是一个树形图铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法并对图2按(1)的要求给出模型和结果。
l 钢管在运送使用过程中没有损耗
l 不考虑恶劣天气等突发情况对运输及铺设的影响
l 在求解钢厂钢管嘚销价对总费用的影响时认为钢管的销价只会在一个小范围内变化,在求解钢厂钢管的生产上限对总费用的影响时亦是如此。
Aj :输送管道(主管道)上的第j个点; j=1,..15
pi:第i个钢厂1单位钢管的销价;i=1,..7
cij:1单位钢管从Si钢厂到铺设节点Aj的最小购运费
lj:管道第Aj段需要铺设的钢管量
xij:钢厂Si運到节点Aj的钢管量
yj:从节点Aj向左铺设的钢管量
zj:从节点Aj向右铺设的钢管量
1、订购运输铺设计划及总费用:
先计算从Si到Aj的最小购运费cij(即订購费用与运输费用之和)再根据cij求解最小总费用W(即订购费用、运输费用、铺设费用之和)
① 构造铁路费用赋权图
l 用Floyd算法来计算铁路任意相邻两点间的最短距离值。
l 再根据题中的铁路运价表求出铁路任意两点间的最少运费。
l 用Floyd算法来计算公路任意相邻两点间运输的最少運费4
③ 构造铁路公路费用的混合赋权图
l 由于可以铁路公路交叉运输所以任意相邻两点间的最小运输费用为铁路、公路两者最小运输费用嘚最小值。即c=min(v,w)
l 用Floyd算法来图中任意相邻两点间运输的最少运费
④ 从运行结果中提取所需要的Si到Aj的最小运输费用见表3
表3 最优路径单位钢管运輸费用
任意两点间的最小运输费用加上出厂售价,得到单位钢管从任一个Si到Aj的最小购运费cij
① 分析题目可以知道约束条件应包括以下几方媔
将上式转化成线性约束:
记:xij:钢厂Si运到节点Aj的钢管量
② 根据以上条件可以建立如下数学规划模型
③ Lingo程序见附录2,由运行结果分析可得表4
表4 问题一订购和运输方案及最小总费用
1)钢厂钢管的销售价格变化对购运计划和总费用的影响
当钢厂钢管销售价格变化时,会对购运計划和总费用造成影响. 为了更好地观察每一个钢厂钢管销售价格所造成的影响采用比较法,即每次只让一个钢厂钢管的销售价格发生相哃的变化其余钢厂钢管的销售价格不发生变化。
我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元借助Lingo软件得出相应的总费用、运输方案、订购方案变化情况如表5、表6所示
表5 各个钢厂单位钢管的销价分别增加1万元
表6 各个钢厂单位钢管的销价分别减少1万元
由上述表格观察分析可得:S6钢厂销价变化对总费用影响最大,S5S6钢厂钢管的销价的变化对购运计划影响最大。
2)、钢厂钢管产量的上限的变化对购運计划和总费用的影响
同样采用比较法即每次只让一个钢厂钢管产量的上限的发生相同的变化,其余钢厂钢管产量的上限不发生变化. 将各个钢厂的产量的上限分别增加100个单位和减少100个单位分别计算,得到购运计划和总费用变化情况如表7、表8所示.
表7 各个钢厂钢管的产量的仩限分别增加100个单位
表8 各个钢厂钢管的产量的上限分别减少100个单位
由上述表格观察分析可得:S1 钢厂钢管的产量的上限的变化对总费用影响朂大购运计划影响较小。
问题(3)要铺设的管道不是一条线而是一个树形图。铁路、公路和管道构成的网络时只是在路线图中增加叻四条公路,与问题(1)没有本质的区别
因此,我们同样运用Floyd最短路径算法求得最小费用矩阵及最小费用路线矩阵在模型上,第(3)問的模型只是第(1)问模型的扩展延伸本质上是一样的。因此可得模型为:
1)本问题中运用了求网络中最短路径的Foyld思想,改进和修改嘚到新的算法可对含多种权重计算方式的网络进行搜索,算出两点之间的最优路径计算结果准确,从而得出相应的购运单价的矩阵.
2)夲问题构造出的模型算法较简单也可以运用相应的其他编程软件来得到比较满意的结果.
1)由于题意中不考虑铁路公路间转运的中转费用,也不限制转运次数因此在算法设计中存在着考虑不周全的缺限,如我们考虑是先通过铁路再通过公路到铺设点但这不一定是最小费鼡路径,有可能先通过公路然后经铁路再经公路运到铺设点,费用更少这里没有理论证明。
2) 问题二要求根据问题一的分析,指出哪家钢廠销价的变化对购运计划和总费用影响最大哪家钢厂钢管产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果. 这個问题属于规划问题的灵敏度分析在此模型中,只是通过说明销价增加一万元减少一万元来说明,并没有给出一般的理论说明
这个數学模型可以应用于西部开发中“西气东送”问题,当然西部开发中“西气东送”问题远比我们的假设还要复杂的多,但无论如何他們的本质一样。
%用Floyd算法来计算任意两点间的最短铁路距离值 u=u+u';%与其转置矩阵相加得到对称矩阵 %将最短铁路距离转换成最少铁路费用 %用Floyd算法來计算任意两点间的最短公路距离值 w=w+w';%与其转置矩阵相加,得到对称矩阵 %将最短公路距离转换成最少公路费用 %用Floyd算法来计算任意两点间的最尐费用 path=zeros(n);%矩阵path用来存放每对顶点之间最短路径上所经过顶点的序号!钢管购买与运输铺设; !cj表示厂家,md表示目的地;
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。