数学建模社区-数学中国

标题: 国赛前期培训成果（请抱有客观的态度欣赏哦） [打印本页]

作者: X12345B 时间: 2015-7-17 23:44
标题: 国赛前期培训成果（请抱有客观的态度欣赏哦）
钢管订购和运输
摘要
本文针对钢管订购和运输问题建立数学模型，运用MATLAB和lingo软件，求解出得出最小总费用及分别分析了哪个钢厂钢管的销价变动、产量上限的变动对购运计划和总费用影响最大。
问题一，单一变量的优化问题。首先研究所给图形的性质并对其进行编号，得到将铁路与销价转换为公路运费的思想，然后通过Floyd算法，用MATLAB求出各钢厂到各站点的最短运费路线。然后通过相关理论建立优化模型，再利用lingo软件求解，得到所需最小的总费用为1281354万元。
问题二，模型灵敏度分析问题，用规划论中的灵敏度分析可得到所需的结论。在模型一的基础之上，把各个钢厂的单位钢管销价作为单一变量，通过对每一个单一变量的适当增加，得到每个钢厂钢管的销价变化后的最小总费用。比较其与第一问中结果。得到钢厂 S_6钢管的销价变化对购运计划和总费用的影响最大。
问题三，单一变量的优化问题。在问题一的基础上，把钢管的铺设路线变为树形。同样是对路线结点进行编号，然后用Floyd算法，并通过改进问题一中MATLAB程序算出最小运费路线。通过相关理论建立优化模型，用lingo软件求解出最小总费用为1366294万元。
在一定的理论基础上，我们对模型进行了优缺点评价。

关键词：MATLAB lingo Floyd算法  最小总费用
一、问题重述
要铺设一条A_1→A_2→⋯A_15送天然气的主管道,经过筛选后可以生产这种主管道钢管的钢厂有S_1,S_2,S_(3⋯) S_7。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）。为方便计，1km主管道钢管称为1单位钢管。题目中给出了整个的路线分布图。
一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂S_i在指定期限内能生产该钢管的最大数量为s_i个单位，钢管出厂销价1单位钢管为p_i,题目中给出了各钢厂产量和销假表。1单位钢管的铁路运价如题目中所示，1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（管道全线）。我们需要建立模型研究以下问题：
（1）请制定一个主管道钢管的订购和运输计划，使总费用最小并给出总费用。
（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大？哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大？并给出相应的数字结果。
（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对题目中给出的第二幅图按（1）的要求给出模型和结果。
二、问题分析
本题是一个制定一个主管道钢管的订购和运输计划的最优化问题。就是根据钢厂生产情况和钢管的铁路运价以及公路运输费用，制定各钢厂的生产产量和运输路线，使铺设管道的总费用最低。即建立以总费用为目标函数来寻求最优解。
问题一的分析：总费用W为订购费用Q及从钢厂到各管道关节点的运输费用P和从管道的关节点到铺设点的运输费用T,钢管的订购费可由在每个厂的购买量与每个厂的出厂销价的线性运算得到。从钢厂到各管道关节点的运输费用可变换为求最短路径，由于铁路运输费用函数不具有可加性，所以不能直接应用现有的最短路径算法来求解铁路和公路网中任意两点间最小费用问题。根据题目可先运用Floyd算法，得出公路和铁路各自的局部最短路径。然后将两种局部最短路径互相转化统一求得两者最小值后，再次运用Floyd算法得到全局的最短每两点间最小运费矩阵。对于从管道的关节点到铺设点的运输费用，我们假设一1km为单位进行铺设，即铺设中车每向前开1km边将1km的钢管放下。由于铺设管道式线型的，除了两个端点外，每个站点需要往两边进行铺设管道。所以，假设第j个站点往左、右两边铺设管道为R_j和L_j公里,则由站点到铺设地点的运输费就可以通过等差数列求和得到。最后根据约束条件和以总费用为目标函数运用数学软件Lingo编程求解最小值。
问题二的分析即为对问题一中模型的灵敏度分析。首先，要确定哪个钢厂钢管的销价变化对购运计划和总费用影响最大以及哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，就要对模型一进行灵敏度分析。然后，分别确定钢管的销价变化与钢管的产量上限为单一变量，求出各因变量（总费用）的值。最后，将各因变量（总费用）与最初总费用进行比较，得出最后结果。
问题三的分析：如果要铺设的管道不是一条线，而是一个树形图，我们可以在问题一的基础上稍作改动。依旧是先计算出钢厂到在此假设各站点向三方向铺设，k_j代表第j站点向第k方向铺设的钢管量（k=1,2,3）。则模型建立如下：
目标函数：
min⁡∑_(i=1)^7▒∑_(j=1)^21▒〖c_ij x_ij+d∑_(i=1)^7▒〖∑_(j=1)^21▒〖p_i x_ij 〗+〗 d∑_(j=1)^21▒((y_j (y_j-1))/2+(z_j (z_j-1))/2+(m_j (m_j-1))/2) 〗
s.t.{█(500×t_i≤∑_(j=1)^21▒〖x_ij≤s_i×t_i 〗 (i=1,⋯,7)(t_i=0or1)@∑_(i=1)^7▒〖x_ij=〗 y_j+z_j+m_j          (j=1,⋯,21)@y_j+z_j+m_j=b_j       (j=1,2,⋯,20)@x_ij≥0,y_j≥0,z_j≥0,m_j≥0 (i=1,⋯,7)(j=1,⋯,21))┤
编号图如下：

（模型一对应结点的编号和该图中的编号一样）

模型假设
1）运送钢管的过程中若用火车则可直接把钢管与铁路交接处，即下了火车不上火车。
2）沿需要铺设的管道或原有公路，或有施工公路，可运送所需钢管；因此，在主管道上铺设钢管时的单位钢管运费可按公路运输计算。
3）钢管在运输中由铁路转为公路运时不及换车费。
4）所需钢管均由钢厂S_i    (i=1,⋯,7)提供。
5）在具体铺设每公里路时，只把钢管运输到每公里起点，沿运输方向向前铺设的费用不予考虑。
6）假设运输单位可提供足够的火车与汽车。
7）路中铺设的钢管只允许由其相邻点提供。
8）运费中不足整公里部分按整公里计算，设1Km主管道钢管为1单位钢管。

四、符号说明
符号意义
S_i 第i个钢厂
s_i 钢厂S_i的最大生产能力
p_i 钢厂S_i钢管单位价格
d 公路上每公里1单位钢管的运费
e 铁路上每公里1单位钢管的运费
c_ij 1单位钢管从钢厂S_i运送到A_j的最小费用
b_j 从A_j到A_(j+1)之间的距离
x_ij 从钢厂S_i运到A_j的钢管数
z_j 运送到A_j的钢管向左铺设的数目
y_j 运送到A_j的钢管向右铺设的数目
t_i={█(1 @0 )┤ 钢厂S_i提供钢管
钢厂S_i不提供钢管
W 总费用
Q 钢管购买总费用
P 运输到A_j的总费用
T 铺设过程中，将钢管运输到每公里起点处的总费用
五、模型建立与求解
（一）模型一：铺设道路是一条线的情况
①模型建立：
总费用由钢管订购费用Q、钢管运输费用P和钢管铺设过程中，将钢管运输到每公里起点处的总费用T三部分组成，即：
W=Q+P+T
所以可以分为三方面考虑：钢管订购、钢管运输和钢管铺设。
（1）钢管订购：
钢管订购总长度应该与主管道长度相等，各钢厂S_i生产的总钢管数量或者不生产为0，或者不小于500个单位，并且不会超过产量上限。
一共需要铺设的钢管长度为5171km，即
∑_(i=1)^7▒∑_(j=1)^15▒x_ij =5171
各钢厂S_i生产的总钢管数量为：
∑_(j=1)^15▒x_ij
满足条件：
∑_(j=1)^15▒x_ij =0或者500≤∑_(j=1)^15▒x_ij ≤s_i    (i=1,⋯,7)
即：
{█(∑_(j=1)^15▒x_ij (∑_(j=1)^15▒x_ij -500)≥0@0≤∑_(j=1)^15▒x_ij ≤s_i )┤
则钢管订购总费用Q为：
Q=∑_(i=1)^7▒〖(p_i ∑_(j=1)^15▒x_ij )=〗 ∑_(i=1)^7▒∑_(j=1)^15▒〖p_i t_i x_ij 〗
（2）钢管运输：
钢管运输由公路和铁路运输两种形式，不同的运输方式计价方式也不同。因此，需要首先确定1单位钢管从钢厂S_i运输到A_i的最小费用c_ij，再计算所有钢管的费用P,即：
P=∑_(i=1)^7▒∑_(j=1)^15▒〖c_ij t_i x_ij 〗
（3）钢管铺设：
从A_j开始向左右两个方向铺设，铺设数量分别为z_j和y_j，又因为公路上每公里1单位钢管的运费为d，则：
I从A_j向左铺设的费用为：
d∙0+d∙1+d∙2+⋯+d∙(y_j-1)=d (y_j (y_j-1))/2
II从A_j向右铺设的费用为：
d∙0+d∙1+d∙2+⋯+d∙(z_j-1)=d (z_j (z_j-1))/2
所以，钢管铺设过程中，将钢管运输到每公里起点处的总费用T为：
T=d∑_(j=1)^15▒〖((y_j (y_j-1))/2+(z_j (z_j-1))/2)〗
针对具体问题，有以下约束限制：
⑴生产能力的限制：
500∙t_i≤∑_(j=1)^15▒x_ij ≤s_i∙t_i       (i=1,⋯,7) (t_i=0or1)
⑵运到A_j的钢管需要正好全部用完，即：
∑_(i=1)^7▒〖t_i x_ij 〗=y_j+z_j       (j=1,2,⋯,15)
⑶A_j到A_(j+1)之间铺设的管道长度应该等于A_j到A_(j+1)之间的距离，即：
y_j+z_(j+1)=b_j       (j=1,2,⋯,14)
⑷端点限制：
y_1=0 ，z_15=0
⑸变量非负性限制：
x_ij≥0，y_j≥0，z_j≥0 (i=1,⋯,7) (j=1,2,⋯,15)
※综上所述，要求总费用最小属于优化问题，总体关系式如下：
min⁡W=∑_(i=1)^7▒∑_(j=1)^15▒〖p_i x_ij 〗+∑_(i=1)^7▒∑_(j=1)^15▒〖c_ij x_ij 〗+d∑_(j=1)^15▒〖((y_j (y_j-1))/2+(z_j (z_j-1))/2)〗
s.t.{█(500∙t_i≤∑_(j=1)^15▒x_ij ≤s_i∙t_i    (i=1,⋯,7) (t_i=0or1)@∑_(i=1)^7▒〖t_i x_ij 〗=y_j+z_j    (j=1,2,⋯,15)@y_j+z_(j+1)=b_j    (j=1,2,⋯,14)@z_1=0 ,y_15=0@x_ij≥0,y_j≥0,z_j≥0       (i=1,⋯,7) (j=1,2,⋯,15)@t_i={█(1 @0 )┤ )┤
模型二：铺设道路是树形的情况
该问题是在模型一的基础上建立的，钢管的订购、运输、铺设所需要的费用和模型一的一样通过题意和铺设路线图建立该优化模型关系式如下：
min⁡W=∑_(i=1)^7▒∑_(j=1)^15▒〖p_i x_ij 〗+∑_(i=1)^7▒∑_(j=1)^15▒〖c_ij x_ij 〗+d∑_(j=1)^15▒〖((y_j (y_j-1))/2+(z_j (z_j-1))/2)〗+d[(m_9 (m_9-1))/2+(m_11 (m_11-1))/2+(m_17 (m_17-1))/2]
s.t.{█(500∙t_i≤∑_(j=1)^21▒x_ij ≤s_i∙t_i    (i=1,⋯,7) (t_i=0or1)@∑_(i=1)^7▒〖t_i x_ij 〗=y_j+z_j    (j=1,2,⋯,21,但j≠9,11,17)@∑_(i=1)^7▒〖t_i x_ij 〗=y_j+z_j+m_j       (j=9,11,17)@y_j+z_(j+1)=b_j    (j=1,2,⋯,14)@m_9+y_16=42,y_17+z_18=130,m_17+z_19=190,m_11+y_17=10,y_19+z_20=260,y_20+z_21=100@z_1=0 ,y_15=0,z_16=0 ,y_18=0,y_21=0@x_ij≥0,y_j≥0,z_j≥0       (i=1,⋯,7) (j=1,2,⋯,21)@t_i={█(1 @0 )┤ )┤
②模型求解：
问题一：
模型求解的关键在于合理的处理决策变量t_i和求出目标函数中系数c_ij。〖（c_ij）〗_(7×15)中每一个c_ij都表示1单位钢管从钢厂 S_i到A_j的最小运输费用，因而，求解c_ij实际上是一个求最短路径的问题。
求出铁路和公路的最短路径矩阵：
A_(39×39)=〖(a_ij)〗_(39×39)
其中a_ij表示从A_i到A_j的最短路程，若不能直接相连用a_ij=∞表示。
铁路和公路自身分别构成权矩阵，记为A^1和A^2。运用Floyd算法，得出局部最短路径矩阵。
求出铁路和公路整体的最短路径矩阵：
对于公路，将0.1×A^2=A^2'为公路局部最小运费矩阵；对于铁路，用铁路的费用e进行转换，得到铁路局部最小运费矩阵A^1'。
令
A=min⁡〖(〖A^1〗^',A^2')〗
求最小费用矩阵：
对得到的A，使用Floyd算法，并用matlab软件编程（程序见附录1-1），得到全局的每两点间最小运费矩阵，从中抽取出S_i到A_j之间的子矩阵，即为所需的〖（c_ij）〗_(7×15)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 170．7 160．3 140．2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121．2 128 142
2 215．7 205．3 190．2 171．6 111 95.5 86 71.2 114．2 142 146 156 171．2 178 192
3 230.7 220．3 200．2 181．6 121 105．5 96 86．2 48．2 82 86 96 111．2 118 132
4 260．7 250．3 235．2 216．6 156 140．5 131 116．2 84．2 62 51 61 76．2 83 97
5 255．7 245．3 225．2 206．6 146 130．5 121 111．2 79．2 57 33 51 71．2 73 87
6 265．7 255．3 235．2 216．6 156 140．5 131 121．2 84．2 62 51 45 26．2 11 28
7 275．7 265．3 245．2 226．6 166 150．5 141 131．2 99．2 76 66 56 38．2 26 2
根据总费用最小优化模型，运用lingo软件编程（程序见附录1-2）求解：W_min=1281354万元；
所得的最优解中：
x_4j=0,∑_(j=1)^15▒x_7j <500
将钢厂S_4从供应商中除去，再将钢厂S_7的供货量改为0或不小于500另种情况重做。得出的结果中，显而易见供货量为0是总费用相对较小，从而将钢厂S_7也从供应商中除去。事实上并不需要向每个钢厂都订购，即允许
∃ i,1≤i≤7,s.t.∑_(j=2)^15▒〖X_ij=0〗
再利用lingo软件进行计算，得到当钢厂S_4和S_7都不生产时有minW=127.86亿元。
（二）模型二：铺设道路是一个树的情况
其情况类似模型一的建立，只是把折线的铺设方法改为树形铺设，管道铺设路线上的结点增加到21个。使用Floyd算法，并用matlab软件编程（程序见附录3-1），得到全局的每两点间最小运费矩阵，从中抽取出S_i到A_j之间的子矩阵〖（c_ij）〗_(7×21)。
求解出的矩阵如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
1 170．7 160．3 140．2 98.6 38 20.5 3.1 21.2 64.2 92 96 106 121．2 128 142 60 95 100 105 115 125
2 215．7 205．3 190．2 171．6 111 95.5 86 71.2 114．2 142 146 156 171．2 178 192 110 145 150 155 165 175
3 230.7 220．3 200．2 181．6 121 105．5 96 86．2 48．2 82 86 96 111．2 118 132 44 85 90 95 105 115
4 260．7 250．3 235．2 216．6 156 140．5 131 116．2 84．2 62 51 61 76．2 83 97 80 50 55 60 70 80
5 255．7 245．3 225．2 206．6 146 130．5 121 111．2 79．2 57 33 51 71．2 73 87 75 32 45 50 65 75
6 265．7 255．3 235．2 216．6 156 140．5 131 121．2 84．2 62 51 45 26．2 11 28 80 46 33 36 10 0
7 275．7 265．3 245．2 226．6 166 150．5 141 131．2 99．2 76 66 56 38．2 26 2 95 63 50 55 32 26

根据总费用最小优化模型，运用lingo软件编程（程序见附件3-2）求解：
  六、问题解答
（一）问题一：
利用模型一运用lingo软件编程得：
钢管订购计划
1 2 3 4 5 6 7
供货量 800 800 1000 0 1297 1274 0
W=128.13亿元
1 2 3 4 5 6 7
供货量 800 800 1000 0 1015 1556 0
W=127.86亿元
钢管的运输方案
A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 A_10 A_11 A_12 A_13 A_14 A_15
S_1 214 122 200 264
S_2 179 40 281 300
S_3 126 210 664
S_5 508 88 3 311 415
S_6 41 86 333 621 165
合计 179 508 468 616 200 264 300 664 352 415 86 333 621 165

A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 A_10 A_11 A_12 A_13 A_14 A_15
z_j 0 104 226 468 606 184 189 126 506 322 270 75 199 286 165
y_j 0 75 282 0 10 16 75 174 158 30 145 11 134 335 0

（二）问题二：
1）上限变化对费用的影响
利用lingo软件的分析功能，把每个钢管厂的生产上限全都改成6000，观察哪一个钢管厂提供的数量有明显的增大那么就认为它对总费用的影响最大。修改后lingo程序执行出来的结果如下：
1 2 3 4 5 6 7
供货量 2180 0 514 0 641 1205 0
W=115.07亿元
得知S_1对总W影响最大，得到minW=1150710万元。
2）销价变化对费用的影响
首先，利用问题一计算最小总费用的代码，依次以钢厂的单位钢管销价为单一变量，其余钢厂的单位钢管销价为固定量，分别对每一个单一变量增加5元和减少5元，得到费用表格如下：
S1 S2 S3 S4 S5 S6 S7
W0 1281354 1281354 1281354 1281354 1281354 1281354 1281354
W1(降5) 1277354 1277354 1276354 1281354 1274462 1273387 1281354
W2（升5） 1285354 1285354 1286354 1281354 1286242 1287317 1281354
W1-W0 4000 4000 5000 0 6892 7967 0
W2-W1 4000 4000 5000 0 4888 5963 0
W2-W1 8000 8000 10000 0 11780 13930 0
比较变化后的总费用与最初的总费用相差值，W1-W0、W2-W1。相差多的就说明此钢厂钢管的销价变化对购运计划和总费用的影响最大。
所以，S_5或S_6的销价变化对购运计划和总费用的影响最大。
（三）问题三：
利用模型二运用LINGO软件编程（程序见附录3-2）得：
钢管订购计划
1 2 3 4 5 6 7
供货量 800 800 1000 0 1303 2000 0
W=147.66亿元

钢管的运输方案
X(1，4)=123.95;X(1，5)=210.55;X(1，6)=200;X(1，7)=265.5;
X(2，2)=179;X(2，3)=79.93;X(2，4)=232.80;X(2，5)=8.28;X(2，8)=300;
X(3，3)=80.47;X(3，4)=97.53;X(3，5)=116;X(3，9)=664.5;X(3，16)=41.5;
X(5，3)=347.60;X(5，4)=13.72;X(5，5)=280.68;X(5，10)=71;
X(5，11)=380;X(5，17)=200;
X(6，10)=280;X(6，12)=111;X(6，13)=393;X(6，14)=571;X(6，15)=165;
X(6，18)=120;X(6，20)=260;X(6，21)=100;
七、模型的分析与检验
现在对假设及原则进行说明：
对于假设（1），从图形的连通性，铁路，公路的长短及多次装卸与实际不符，知其具有合理性；对于假设（7），由于两相邻站点都较远，故显然不可能从较远处运来钢管进行铺设。因此，从解的结果来看，所建的模型具有合理性。
八、模型评价
模型优点：
1）本文将问题简化为求局部最短路径问题，采用Floyd算法，简化运输网络。过程严谨，理论性强，易于理解。
求解最短路径问题时所采用得Floyd算法，减少了大量的重复计算，缩短运行时间，提高工作效率。
求解目标函数最优解时用计算机程序执行，误差较小。
4）本模型计算步骤清晰，易于推广，对相似的管道运输问题提供了很好的参考价值。
（2）模型缺点：
1.本模型变量多余100个，为了能使用lingo软件，在计算时，已经认为删去了一些变量，这就产生了一定的误差。
2.问题三中，解题时充分利用了图本身的性质，但这并不利于模型的推广。

九、参考文献
[1]张德丰，周燕，《详解MATLAB在统计与工程数据分析中的应用》，电子工业出版社，2010年。
[2]满晓宇，罗捷，《战胜MATLAB必做练习50题》，北京大学出版社。
[3] 姜启源，数学模型[M].北京：高等教育出版社，1997。
十、附录
（编程还是算啦，大神们自己试试哈）

作者: SHERE201506 时间: 2015-9-1 22:41
我也是醉了啦啦啦啦啦啦啦

作者: lingxin179 时间: 2015-9-4 10:16
哇，这个可以以pdf格式发

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)