1 问题重述2 基本假设 (1)只考虑订购费用和运送费用，不考虑装卸等其他费用． (2)钢管单价与订购量、订购次数、订购日期无关．(3)订购汁划是指对每个厂商的定货数量；运送方案是指具有如下属性的一批记录：管道区间，供应厂商，详细运送路线． (4)将每一单位的管道所在地当作一种需求点，向一单位管道的所在地运送钢管即为向一种点运送钢管．3 符号阐明 M：钢厂总数. n：单位管道总数.第 i 个钢厂 第 i 个钢厂的产量上限。第 i 个钢厂单位钢管的销售价 管道线上第 i 个站点。管道线上第 i 个单位管道的位置。 F：总费用。从钢厂到点的最低单位费用。4 问题的简化求 S AP 矩阵的基本思绪是图的最短路算法 . 由于铁路的运送费用与线路的长度不是线性关系 ,必须对铁路网做某些预处理才能套用图的原则最短路算法 . 下面论述求 S AP 矩阵的过程:1.运用图的原则最短路算法 ,从铁路网络得出图中任两个点之间的最短途径表 T (如 果两个点之间不连通 ,认为它们之间的最短路长度为+ ∞ ) .2.运用题中的铁路运价表将 T 中的每个元素 (即最短距离 )转化为运送费用 ,将运送费 用表记为 C.3.将公路的长度换算为运送费用 ,由公路旅程图 (包括要沿线铺设管道的公路 )得出公路费用图 G,若 i, j 不连通 ,则令 Gij = + ∞ .4.对于任一组 ( i , j)∈ { 1,… n }× { 1,… m } 假如 Cij <+ ∞ ,且不大于 Gij ,那么就在公路费 用图中加一条边. 即令 Gij = min{Cij , Gij } .5.运用图的原则最短路算法 ,求公路费用图中任一种 S 点到任一种 A 点的最小费用 途径 ,得出 S AP 矩阵. 如表 1 所示:SAP 矩阵A123456789101112131415S11707 1603 140298638020531212642920960 1060 1212 1280 142022157 2053 1902 1716 1110955860712 1142 1420 1460 1560 1712 1780 192032307 22031816 1210 1055960862482820860960 1112 1180 132042607 2503 2352 2166 1560 1405 1310 116284262051061076283097052557 2453 2252 2066 1460 1305 1210 111279257033051071273087062657 2553 2352 2166 1560 1405 1310 121284262051045026211028072757 2653 2452 2266 1660 1505 1410 1312992760660560382260205 问题分析 运送费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转换为公路线．对于铁路线上的任意两点...
