Page 241 - 数学建模算法与应用

第八章 图与网络模型及方法应用

编号见图 14；W1= ( )39× 9

由于铁路运费不是连续的，故不能直接用 Floyd 算法来计算最小运输费用。
但可以用 Floyd 算法来计算任意两点间的最短铁路距离值，再依据题中的铁路运
价表，来计算最小运输费用。这就巧妙的避开铁路运费不是连续的问题。最终计

算出铁路任意两点间的最小运输费用 其中，路径值无穷大时的费用也为无穷大。
②计算公路任意两点间的最小运输费用

构造公路距离赋权图 G2=(V，E2 ，W2 )，其中 V 同上，

依据题中“公路运输费用为 1 单位钢管每公里 0.1 万元（不足整公里部分按
整公里计算）”，计算出公路任意两点间的最小运输费用 路径值为无穷大时的
费用也为无穷大。
③计算任意两点间的最小运输费用

由于可以用铁路、公路交叉运送，所以任意相邻两点间的最小运输费用为铁
路、公路两者最小运输费用的最小值。构 造 铁路公路的混合赋权完全图 G=(V，

E，W)， 其 中
对图 G 应用 Floyd 算法，就可以计算出 到
的最小运送费用 ( 单位：万元 ) 见表 8-7。

任意两点间的最小运输费用加上出厂售价 , 得到单位钢管从任一个 Si（i=1，
2，…，7）到 A j =（ j=1，2，…，15）的购买和运送最小费用 c ij 。
2. 总费用的数学规划模型

分析题目可以知道约束条件应包括：
①钢厂产量约束：上限和下限（如果生产的话）；

②运量约束： x ij 对 i 求和等于 zj 加 y j ；

231