钢管的订购和运输解吝模型 9.下文所有费用的单位均为千元 3问题的分析与简化 3.1问题的分析 整个铺设管道的工程看似错综复杂,其实可分为三个部分 各个工厂(S点)生产一定数量的钢管 2.把钢管从工厂(S点)运送到铺设管道的关节点(A点) 3.从关节点(A点)将管道运至铺设地点 这三个部分是相互依赖的,不能简单地把三个部分孤立开来讨论.但是通过仔细观察 我们发现第二部分中的运费事实上只与出发点(S点)、目标点(A点)和运量有关,并且是 运量的线性函数,具备可叠加性 运输总费用:W=∑∑SAQn×SAP 因此,我们可以简化第二部分的计算,即先从铁路与公路网络得出SAP矩阵 3.2问题的简化 求SAP矩阵的基本思路是图的最短路算法 由于铁路的运输费用与线路的长度不是线性关系,必须对铁路网做一些预处理才能套 用图的标准最短路算法 下面叙述求SAP矩阵的过程: 1.利用图的标准最短路算法,从铁路网络得出图中任两个点之间的最短路径表T(如 果两个点之间不连通,认为它们之间的最短路长度为+∞) 2.利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输 费用表记为C. 3.将公路的长度换箅为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公 路费用图G,若i,j不连通,则令Ga=+∞ 4.对于任一组(i,j)∈1,n}×,…m}如果C<+∞,且小于G,那么就在公路 费用图中加一条边.即令G= min Ci,G 利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用 路径,得出SAP矩阵.如表1所示: 表1图1的SAP矩阵 5 6 10 1170716031402986380205312126429209601060121212801420 2215720531902171611109558607121142142014601560171217801920 3230722032002181612101055960862482820860960111211801320 420532610110510608970 5257245322522066146013051210111279257030510712730870 626572553235221661560140513101212842620510450262110280 727572653245222661660150514101312992760660560382260