全国数学建模竞赛B题论文

精品文档---下载后可任意编辑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 2203 2024 1816 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 问题分析 运输费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转换...