2000年数学建模B题钢管订购和运输资料

管道订购与运输问题1 问题重述2 基本假设(1)只考虑订购费用和运输费用，不考虑装卸等其它费用． (2)钢管单价与订购量、订购次数、订购日期无关．(3)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的一批记录：管道区间，供应厂商，具体运输路线．(4)将每一单位的管道所在地看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管．3 符号说明M ：钢厂总数. n ：单位管道总数.:i S 第i 个钢厂 :i S 第i 个钢厂的产量上限。

:i p 第i 个钢厂单位钢管的销售价 i A 管道线上第i 个站点。

i d 管道线上第i 个单位管道的位置。

F ：总费用。

:ij C 从钢厂(1,2,,)i S i m =到点(1,2,,)j d j n =的最低单位费用。

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 矩阵A123 4 5 6 7 8 9 10 11 12 13 14 15 S1 170716031402986 380 205 31 212 642 920 960 1060 1212 1280 14202 215720531902 1716 1110 955 860 712 1142 1420 1460 1560 1712 1780 19203 230722032002 1816 1210 1055 960 862 482 820 860 960 1112 1180 13204 260725032352 2166 1560 1405 1310 1162 842 620 510 610 762 830 9705 255724532252 2066 1460 1305 1210 1112 792 570 330 510 712 730 8706 265725532352 2166 1560 1405 1310 1212 842 620 510 450 262 110 2807 275726532452 2266 1660 1505 1410 1312 992 760 660 560 382 260 205问题分析运输费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转换为公路 线．对于铁路线上的任意两点,i j V V ，用F1oyd 算法找出两点间最短铁路路线的长度ij L 查铁路运价表求得ij L ，对应的铁路单位运费ij f ;又设与该段铁路等费用的公路长度为ij l ，则：0.1ij ij f l =⨯由此，我们就在,i j V V 之间用一条等价的公路线来代替,i j V V 间的最短铁路线．如果,i j V V 之间原来就有公路，就选择新旧公路中较短的一条．这样，我们就把铁路运输网络转换成了公路运输网络．销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为公路单位运价．对于钢厂S i 的销售单价P i ，我们可以虚设一条公路线，连接钢厂S i 及另一虚拟钢厂'i s ，其长度为i l ，并且满足0.1i i l p =⨯；从而将钢厂的销售单价转换成公路运输单价，而新钢厂'i s 的销售价为0.将铁路和销价转换为公路的过程可以由计算机编程实现． 通过上述的分析，我们可以将原问题化为一个相对简单的产量未定的运输问题，利用115A A 到之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模型．但是由于1215,A A A ,并不能代表所有的实际需求点(实际需求点是n 个单位管道)，因此，我们可以用F1oyd 算法进一步算出7个钢厂到所有实际的n 个需求点(对于问题一，n ＝5171;对于问题三，n ＝5903)的最短路径，并由此得出一个具有7个供应点、n 个需求点的产址未定的运输模型．6 模型的建立产量未定的运输模型根据假设4，我们可以将每一单位的管道看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管．对每个点，我们可以根据该点的位置和最短等价公路距离，求出各钢厂与该点之间最小单位运输费用ij C (销价已经归人运输费用之中了)．设总共有m 个供应点(钢厂)，n 个需求点，我们就可以得到一个产量未定的运输模型：有m 个供应点、n 个需求点，每个供应点的供应量{0}{500,}i i u s ∈；每个需求点需要1单位，运输单价矩阵为C ，求使得总运输费用最小的运输方案．其数学规划模型： 11minmnij ij i j F C x ===∑∑11{0}{500,}1,2,,..11,2,01nij i j mij i ij x S i ms tx j n x ==⎧∈=⎪⎪⎪==⎨⎪⎪=⎪⎪⎩∑∑或其中： 1112112n m m mn C C C C CC C ⎛⎫⎪=⎪ ⎪⎝⎭为单位费用矩阵 1112112n m m mn x x x X x x x⎛⎫⎪=⎪ ⎪⎝⎭为决策矩阵，也为0-1矩阵 代码如下7 模型的求解对于本题，上述0-1规划规模宏大，现有的一些算法不能胜任，我们必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法．(1)初始方案的改进的最小元素法和改进的伏格尔法 *改进的最小元素法改进的最小元素法又称为贪婪法或瞎子爬山法，它的宗旨是每一步都取当前的最优值算法步骤为，对费用矩阵C 作n 次下列循环：①C 中找一个最小值ij C ； ②令1;ij x =③C 的第j 的所有数据改为+∞；④如果1nij i j x s ==∑，第i 个供应点的供应量已达上限，将C 的第i 行数据全改为+∞。

数学建模钢管订购和运输(总32页)-CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除钢管的订购和运输优化模型摘要本文建立的多元非线性优化模型。

问题一在保证天然气管道铺设可以顺利实施的情况下，给出了钢管的订购与运输总费用最小的方案。

在求钢管由钢厂运输到站点的费用和铺设钢管时产生的运输费，根据图一，我们通过深度优先遍历的方法对整个图一进行路径搜索，然后根据每条搜索到的路径上的铁路和公路上的不同权重，找到了各个钢厂到各个天然气管道上的站点的最佳路径。

对于整个优化过程我们给出了相关的算法，并用matlab软件编程，经过一系列计算之后，得出了最优的订购与运输方案。

对于问题 1，我们求得的最优解为S钢管销价的变化对购运计划和总费对于问题2我们经过计算比较得出：6S的生产上限的变化购运计划和总费用影响最大。

用影响最大。

1对于问题 3，当天然气管道呈现的是一个树状图的时候，我们得到的最优关键字：非线性优化深度优先遍历最佳路径一、问题重述要铺设一条1521A A A →→→ 的输送天然气的主管道, 如图一所示(见下页)。

经筛选后可以生产这种主管道钢管的钢厂有721,,S S S 。

图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

为方便计，1km 主管道钢管称为1单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。

钢厂i S 在指定期限内能生产该钢管的最大数量为i s 个单位，钢管出厂销价1单位钢管为i p i 1 2 3 4 5 6 7 i s80080010002000 2000 2000 3000 i p160 155 155160 155150160 1里程(km) ≤300 301～350351～400 401～450 451～500 运价(万元) 2023262932里程(km) 501～600601～700 701～800 801～900 901～1000 运价(万元)37445055601000km 以上每增加1至100km 运价增加5万元。

B 题 钢管订购和运输
要铺设一条1521A A A →→→ 的输送天然气的主管道, 如图一所示(见下页)。

经筛选后可以生产这种主管道钢管的钢厂有721,,S S S 。

图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

为方便计，1km 主管道钢管称为1单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。

钢厂i S 在指定期限内能生产该钢管的最大数量为i s 个单位，钢管出厂销价1单位钢管为i p 万元，如下表：
1单位钢管的铁路运价如下表：
1000km 以上每增加1至100km 运价增加5
公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。

钢管可由铁路、公路运往铺设地点（不只是运到点1521,,,A A A ，而是管道全线）。

（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。

（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。

（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。

7
7。

真实路网示例：节点5696 到节点3006 有三条最短路径。

黑线为第一条，兰线为第二条，红线为第三条，共享部分路段。

利用最短路算法可得最短路(途中红线表示的路径)为：v1→v3→v5→v7。

利用最短路算法可得最短路(途中红线表示的路径)为：v→v→v。

图中各边权值表示相应网线的传输能力。

例如，计算机1与2之间传输信息需要但通过枚举的方法来求解已经很困难了！完整构图为：上图展示了从起点(8,0,0)到终点(4,4,0)不同路径。

两相邻节点之间的边代表一次转移，因此可假设每条边的权值为1。

问题就化成利用最短路算法求得最优解如红线所示。

思考：这个问题仅仅是一个游戏吗？钢厂S 1~S 7节点A 1~A 15铁路公路火车站原有公路施工公路铺设地点管网节点S1→S2的最短距离为1402，路径为S1→S15→S2。

从而S1→S2 的最低运费为85。

S20→S5的最短距离为710，路径为S20→S18→S19→S5。

从而S20→S5 的最低运费为50。

858550铁路线上各节点之间的最低运费示意图新图1.24.21.03.17.01.0于是，我们可以构造出一个新的赋权图 G(V, E)，这是一个运输费用图，其中 V 为原图 的顶点集合，E 中每一条边的权值为前面求出 的运费。

图 G 的示意图如下。

对运输费用图 G 再次使用 Floyd 算法，求出 图 G 的最短路。

各 Si 到每个 Aj 的最短路值，就是一个单位 的钢管从钢厂 Si 到管网各个节点 Aj 的最小运输 费用 cij。

最小运价表如表 1 所示。

新图表 1 单位钢管从 Si 到 Aj 的最小运价(单位：万元)S1S2S3S4S5A1170.7000 215.7000 230.7000 260.7000 255.7000A2160.3000 205.3000 220.3000 250.3000 245.3000A3140.2000 190.2000 200.2000 235.2000 225.2000A498.6000171.6000 181.6000 216.6000 206.6000A538.0000111.0000 121.0000 156.0000 146.0000A620.500095.5000105.5000 140.5000 130.5000A73.100086.000096.0000131.0000 121.0000A821.200071.200086.2000116.2000 111.2000A964.2000114.200048.200084.200079.2000A1092.0000142.000082.000062.000057.0000A1196.0000146.000086.000051.000033.0000A12106.0000 156.000096.000061.000051.0000A13121.2000 171.2000 111.200076.200071.2000A14128.0000 178.0000 118.000083.000073.0000A15142.0000 192.0000 132.000097.000087.0000S6 265.7000 255.3000 235.2000 216.6000 156.0000 140.5000 131.0000 121.2000 84.2000 62.0000 51.0000 45.0000 26.2000 11.0000 28.0000S7 275.7000 265.3000 245.2000 226.6000 166.0000 150.5000 141.0000 131.2000 99.2000 76.0000 66.0000 56.0000 38.2000 26.00002.00001.2 整数约束的处理 由于给出的模型是非线性整数规划模型， 因此尚无合适的求解方法。

管道订购与运输问题摘要：本文通过研究了题目所给图并结合题目所给条件信息，理解到钢管的订购与运输问题可通过合理假并简化为单一的公路运输问题，构架了产量未定的单一运输优化模型。

运用运筹学原理求得钢管厂到铺设点的最小距离，通过线性规划的思想列出目标函数，在求得目标函数的同时，我们要考虑到目标最小费用函数中管道的铺设费用，在从铺设点向两边铺设的过程两端开始的1千米是不需要铺设费的，运用等差数列的思想构造一个子函数作为目标函数的一部分，从而得到优化的数学模型，运用lingo软件求得最小运费为1274296。

我们的数学模型是综合考虑运费与钢管单价及铺设费用问题，是整个钢管订购铺设总费用最小。

关键词：管道订购与运输；运筹学；LINGO软件；产量未定的运输模型；线性规划（一）问题重述：要铺设一条1521A A A →→→ 的输送天然气的主管道, 如图一所示(见附录一)筛选后可以生产这种主管道钢管的钢厂有721,,S S S 。

图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。

为方便计，1km 主管道钢管称为1单位钢管。

一个钢厂如果承担制造这种钢管，至少需要生产500个单位。

钢厂i S 在指定期限内能生产该钢管的最大数量为i s 个单位，钢管出厂销价1单位钢管为i p 万元，如下表：i1 2 3 4 5 6 7 i s800 800 1000 2000 2000 2000 3000 i p1601551551601551501601单位钢管的铁路运价如下表：里程(km) ≤300 301～350 351～400 401～450 451～500 运价(万元) 2023262932里程(km) 501～600 601～700 701～800 801～900 901～1000运价(万元)37445055601000km 以上每增加1至100km 运价增加5万元。

221案例10 订购和运输一、问题重述和分析要铺设一条1521A A A →→→ 的输送天然气的主管道，如图1所示,经筛选后可以生产这种主管道的钢厂有721,,,S S S . 图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位km ）.图1为了方便，1km 主管道称为1单位钢管. 一个钢厂如果承担制造这种钢管，至少需要生产500个单位. 钢厂i S 在指定期限内能生产该钢管的最大生产数量为i s 个单位，钢厂出厂销价为i p 万元，如下表：72221单位钢管的铁路运价如下表：表21000以上每增加1至100运价增加5万元. 公路运输费用为1单位管道每公里0.1万元（不足整公里的按整公里计算）. 管道可由铁路、公路运往铺设地点（不只是运到点1521A A A →→→ ，而是管道全线）.问题1. 制定一个主管道钢管的订购和运输计划，使总费用最小，并给出总费用. 问题2. 就（1）的模型进行分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果.二、基本假设1． 在计算运费时，沿管道铺设路线上的公路与其它普通公路相同（1单位钢管每公里0.1万元）；2． 订购的钢管数量刚好等于需要铺设的钢管数量；3． 管道可由铁路、公路、管道全线运往铺设地点（不只是运到点1521,,,A A A ）； 4． 模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如不计换车、转站的时间和费用，不计装卸费用等；5． 不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失； 6． 销售价和运输价不受市场价格变化的影响.三、符号说明i S ： 第i 钢管厂i s ：表示i S 的最大生产能力j A ： 表示需要铺设管道路径上的车站 i j x ：从所有i S 运往j A 的钢管数223c i j ：表示单位钢管从i S 地运往j A 地的最小费用 i p ：从i S 订购钢管的单位价格Q ： 订购的所有钢管全部运到)15,,2,1( =j A j 点的总运费 T ： 当钢管从钢厂i S 运到点j A 后，钢管向j A 的左右两边运输（铺设）管道的运输费用Z ：用于订购和运输的总费用j y ： 运到j A 地向左铺设的数目 j z ： 运到j A 地向右铺设的数目d ： 单位钢管1公里的公路运输费用1 ,+j j A ： 表示1+j j A A 和之间需要铺设的管道长度四、模型的建立与求解问题1.1、 模型的建立钢管的订购和运输方案是直接影响工程费用的主要原因，因此，选取费用最小的路线运送货物，合理的订购计划是决定该工程费用的重要因素，首先利用图论的方法，来确定从钢管生产厂家到施工结点的费用最小路线，然后建立工程费用的优化模型，从中优化出最佳购运方案.对本问题而言，实际上是一个要求制定订购和运输计划，使总费用最小的优化问题. 本模型的总费用包括钢管的销价和运输总的费用. 首先，向某厂订购钢管，然后将在每个厂订购的钢管运往需要铺设的全路段. 欲解决本问题可以按以下方案进行思考：首先，需要确定将货物从i 地运往j 地的最优路线（费用最小）；然后，求出向每个钢管厂的订购计划，并确定出运输计划；最后计算将运往j 地的钢管铺到各个管道上的运输费用，我们不妨假设运往以j 为终点的钢管只铺到与j 点相邻的两段管道上. 因此，本问题可以按以下步骤求解.第一步：确定从i 地到j 地的最优路径，从而确定出单位钢管从i 地运往j 地的最小运费.)7,2,1( =i s i 表示钢管厂)7,2,1( =i S i 的最大生产能力，)15,,2,1( =j A j 表示需要铺设钢管路径上的车站. 假设从i S 运往j A 的钢管用于铺设j A 点左右侧的钢管数为j i x ,单位，单位产品从i S 到j A 地的运费为j i F ,万元，用j i ,c 表示单位钢管从i S 地224 运往j A 地的最小费用，则：j c min ij i F =（1）第二步：建立从i S 厂运送j ,i x 单位钢管到j A 点的运费的模型： 用Q 表示订购的所有钢管全部运到)15,,2,1( =j A j 点的总运费，则：15711Q c i j i j j i x ===∑∑；（2）第三步：将运到j A 处的钢管铺到相邻两段路上的运输费用对于运到j A 的钢管，它向左运输的总量j y ，它向左运输的总费用为：(1)(2)1j j j y d y d y dd ⨯+-⨯+-⨯⨯＝()0.1(12)0.051j j j y y y ⨯+++=+（万元）； 同理它向右运输的总费用为j j z z d2)1(+＝()0.051j j z z +用T 表示当钢管从钢厂i S 运到点j A 后，钢管向j A 的左右两边运输（铺设）管道的运输费用，得()()15j j j 1T 0.051y y 1j j z z =⎡⎤=+++⎣⎦∑（3）j z j y 和之间存在的关系为7i j i 11,1x ;(1,2,,15);(1,2,,14)j j jj j j y z j z y A j =++⎧=+=⎪⎨⎪+==⎩∑ （4）（1 ,+j j A 表示1+j j A A 和之间需要铺设的管道长度）第四步：建立订购费用的模型设W 表示订购管道的总费用，则可建立如下模型：225715, 1j 1W i i j i p x ===∑∑（5）又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂i S 在指定期限内最大生产量为i s 个单位，故i j ijs x≤≤∑=152500 或0152=∑=j ij x ， 用Z 表示订购和运输的总费用，由（2）、（3）、（4）、（5），本问题可建立如下的非线性规划模型：目标函数()()71515i 111min W Q T ()0.0511i i j i j j j j j j j Z p c x y y z z ===⎡⎤=++=+++++⎣⎦∑∑∑约束条件7i j i 11,1151522x ;(1,2,,15);(1,2,,14)5000;(1,2,,7)0 1,,7,2,,15j j j j j j ij i ij j j ij y z j z y A j x s x i x i j =++==⎧=+=⎪⎪+==⎪⎪⎨⎪≤≤==⎪⎪≥==⎪⎩∑∑∑或 （6）其中1 ,+j j A 表示1+j j A A 和之间需要铺设的管道长度.2、模型的求解（1）首先求解 i j c 由于钢管从钢厂i S 运到运输点j A 要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关. 又由于钢厂i S 直接与铁路相连，所以可先求出钢厂i S 到铁路与公路相交点j b 的最短路径. 依据钢管的铁路运价表，算出钢厂i S 到铁路与公路相交点j b 的最小铁路运输费用，并把费用作为边权赋给从钢厂i S 到j b 的边. 再将与j b 相连的公路、运输点i A 及其与之相连的要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一段公路的运费，并把此费用作为边权赋给相应的边. 这样就转换为以单位钢管的运输费用为权的赋权图，再利用E.W.Dijkstra 的最短路算法计算出一个单位钢管从钢厂运到工地的最少费用系数阵()ij c ，MA TLAB 程序(略).226(2)根据以上结果, 继续求解非线性规划模型：()()71515i 111min ()0.0511i i j i j j j j j j j Z p c x y y z z ===⎡⎤=+++++⎣⎦∑∑∑7i j i 11,1151522x ;(1,2,,15);(1,2,,14).5000;(1,2,,7)0 1,,7,2,,15j j j j j j ij i ij j j ij y z j z y A j s t x s x i x i j =++==⎧=+=⎪⎪+==⎪⎪⎨⎪≤≤==⎪⎪≥==⎪⎩∑∑∑或由于不能直接处理约束条件：i j ijs x≤≤∑=152500或0152=∑=j ij x ，我们可先将此条件改为i j ijs x≤∑=152，得到如下模型：()()71515i 111min ()0.0511i i j i j j j j j j j Z p c x y y z z ===⎡⎤=+++++⎣⎦∑∑∑2277i j i 11,1152x ;(1,2,,15);(1,2,,14).;(1,2,,7)0 1,,7,2,,15j j j j j j ij i j ij y z j z y A j s t x s i x i j =++=⎧=+=⎪⎪+==⎪⎪⎨⎪≤=⎪⎪≥==⎪⎩∑∑用LINGO 求解（程序略）. 分析结果后发现购运方案中钢厂7S 的生产量不足500单位，下面我们采用不让钢厂7S 生产和要求钢厂7S 的产量不小于500个单位两种方法计算：1）不让钢厂7S 生产,程序略.计算结果：1Z =1278632（万元）（此时每个钢厂的产量都满足条件）. 2）要求钢厂7S 的产量不小于500个单位，程序略.计算结果：2Z =1285281（万元） （此时每个钢厂的产量都满足条件）. 比较这两种情况，得最优解为，121min min(,)Z Z Z Z ===1278632（万元）. 所以根据上述的模型，得运输总费用最小为1278632（万元）. 具体的购运计划和铺设方案如表4，表5.228问题2. 针对问题一的求解模型，讨论钢厂钢管的销售价格变化对购运计划和总费用影响及钢厂钢管产量的上限变化对购运计划和总费用的影响．定义 方案中运往各点i A 的运输量的变化量的绝对值之和称为运输方案变化量． 1、讨论钢厂钢管的销售价格变化对购运计划和总费用的影响当钢厂钢管销售价格变化时，会对购运计划和总费用造成影响. 为了更好地观察每一个钢厂钢管销售价格所造成的影响，采用比较法，即每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化.我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元，借助LINGO 软件得出相应的总费用、运输方案、订购方案变化情况如表6、表7所示由上述表格观察分析可得： 6S 钢厂销价变化对总费用影响最大，56,S S 钢厂钢管的销价的变化对购运计划影响最大.2、讨论钢厂钢管产量的上限的变化对购运计划和总费用的影响同样采用比较法，即每次只让一个钢厂钢管产量的上限的发生相同的变化，其余钢厂钢管产量的上限不发生变化. 将各个钢厂的产量的上限分别增加100个单位和减少100个单位，分别计算，得到购运计划和总费用变化情况如表8、表9所示.S钢厂钢管的产量的上限的变化对总费用影响最大，由上述表格观察分析可得：1购运计划影响较小.五、模型的评价及改进由于总费用由订购费用和运输费两部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成. 利用求网络中最短路径的Dijkstra算法，进行改进得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径），算出两点之间的最优路径，进而根据非线性规划，借助于Lingo软件求解即可求出相应的结果.1．优点1）本问题中运用了求网络中最短路径的Dijkstra算法的思想，进行改进和修改得到新的算法，可对含多种权重计算方式的网络进行搜索，算出两点之间的最优路径，计算结果准确，从而得出相应的购运单价的矩阵.2）本问题构造出的模型算法较简单，也可以运用相应的其他编程软件来得到比较满意的结果.3）本模型计算步骤清晰，借助于Lingo软件求解，可靠性较高.2．缺点1）由于题意中不考虑铁路公路间转运的中转费用，也不限制转运次数，因此在算法设计中存在着考虑不周全的缺限，如我们考虑是先通过铁路再通过公路到铺设点，但这不一定是最小费用路径，有可能先通过公路，然后经铁路再经公路运到铺设点，费用更少，这里没有理论证明.2292) 问题二要求根据问题一的分析,指出哪家钢厂销价的变化对购运计划和总费用影响最大，哪家钢厂钢管产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果. 这个问题属于规划问题的灵敏度分析，一般来说，应该对于销价的变化△p 和产量上限的变化△s求出相应的总费用的变化△w，但要得到△w关于△p和△s的函数关系，几乎是不可能的，只对每个钢厂进行单独讨论.3．模型改进这个数学模型可以应用于西部开发中"天然气东送”问题，当然，西部开发中"天然气东送”问题远比我们的假设还要复杂的多，但无论如何，他们的本质一样，我们可将本问题运用于时间的变化等范围的推广. 本文还可以把问题1归结为网络最小费用流问题，建立了线性和非线性最小费用流模型，并运用相应的解法和分支定界法求解，简洁，层次分明.参考文献：[1] 甘应爱，田丰等等. 运筹学.清华大学出版社,北京,1994.[2] 袁亚湘.孙文瑜著. 最优化理论与方法.科学出版社，北京，1997.[3] 徐俊明著. 图论及其应用.中国科学技术大学出版社，合肥，1997.[4] 赵静，但琦. 数学建模与数学实验[M].北京：高等教育出版社，2003.习题1. 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络（图2），请就这种更一般的情形给出一种解决办法，制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用).230231图217。