• 2.利用题中的铁路运价表将T中的每个元 素(即最短距离)转化为运输费用,将运输费用表 记为C
• 3.将公路的长度换算为运输费用,由公路路 程图(包括要沿线铺设管道的公路)得出公路费 用图G,若i,j不连通,则令Gij=+∞.
• 4.对于一组(i,j)∈{1,2, …,n}×{1,2, …,m}, 如果Cij<+∞,且小于Gij,那么就在公路费用图中 加一条边,即令Gij=min{Cij,Gij}.
• 关键词 运输问题;网络流;树形网络;分支定界
• 1.问题的提出(略) • 2.基本假设和符号说明 • 2.1 基本假设 • 1.原图是一个连通的简单图; • 2.铁路、公路的运量没有限制; • 3.为了满足费用最小的要求,允许出现生产过剩现
象; • 4.工厂的数目(图中S点的个数)不太多,约在10个
AAQjk+AAQkj=Pjk; • 9.下文所有费用的单位均为千元.
• 3.2 问题的简化
• 求SAP矩阵的基本思路是图的最短路算法.
• 由于铁路的运输费用与线路的的长度不是 线性关系,必须对铁路网做一些预处理才能套 用图的标准最短路算法.
• 下面叙述求SAP矩阵的过程:
• 1.利用图的标准最短路算法,从铁路网得出 图中任两个点之间的最短路径表T(如果两个点 之间不连通,认为它们之间的最短路长度为+∞).
全国大学生数学建模竞赛 培训班练习题评讲
钢管的订购和运输
• 钢管的订购和运输解答模型
• 摘要 首先通过最短路算法简化了供需距离网络, 去掉了铁路、公路等边的性质,使供需距离网络 简化为一个供需运输价格表.在此基础上构造了 三个模型:线性费用的网络流模型和具有非线性 费用的网络流模型.通过改进传统的最小费用最 大流算法,解决了本题的非线性费用网络流模型, 并给出了算法的正确性证明与复杂度分析.
4 2607 2503 2352 2166 1560 1405 1310
5 2557 2453 2252 2066 1460 1305 1210
6 2657 2553 2352 2166 1560 1405 1310
7 2757 2653 2452 2266 1660 1505 1410
表1续
8
9 10 11 12 13 14 15
• 3.待铺设线路的端点(图中A点,以后简称关节 点),设有m个,记作A1,A2, …,Am;
• 4.在不至于混淆的情况下,Aj同时用来表示从各 个工厂运到Aj的钢管总数量,j=1,2, …,m;
• 5.待铺设的管道,记作Pjk(j≠k),表示Aj与Ak之间 有一条待铺设的管道,它的长度也用Pjk来表示, 如果Aj与Ak之间没有待铺设的管道,则Pjk=0;
• 6.SAQij表示从Si 到Aj的运输量, i=1,2, …,n, j=1,2, …,m;
• 7. SAPij表示从Si到Aj运输单位长度钢管的最小 费用,i=1,2, …,n, j=1,2, …,m;
• 8.AAQjk表示Aj提供的用于铺设Aj与Ak之间管道 的长度, j,k=1,2, …,m,.显然有:
• Source层
Source
•
(Li,Ri)
• S层
S1
S2
S3 …
• (+∞,SAPij)
• A层
A1
A2
• (1,1),(1,2),(1,3)
…
A3
• P层
…
•
P11
P12 P13 P21 P22
以下; • 5.待铺设的钢管长度不太长,约在10000公里以下; • 6.待铺设的线路的段数不太多,约在40段以下; • 7.公路运输不足整公里部分按整公里计算.
• 2.2 符号说明
• 1.工厂(图中S点)设有n个,记作S1,S2, …,Sn; • 2.在不至于混淆的情况下,Si同时用来表示每个
工厂的产量,i=1,2, …,n;
212 642 712 1142 862 482 1162 842 1112 792 1212 842 1312 992
920 1420 820 620 570 620 760
960 1460 860 510 330 510 660
1060 1560 960 610 510 450 560
1212 1712 1112 762 712 262 382
• A.假设工厂的产量只有上限,下面的三个流网 络模型都是针对这种情况的.
• B.假设工厂的产量有上下限,“产量有下限的模 型”一节讨论这种情况.
• C.工厂的产量∈{0,[500,Li]},“基于分支定界搜 索的求解过程”一节讨论这种情况.
• 4.1 线性费用流网络模型一
• 下面建立一个线性费用流网络的模型(图1):
1280 1780 1180 830 730 110 260
1420 1920 1320 970 870 280
20
• 经过这一变换,问题大大简化,下面将原问 题用纯数学语言作一个描述,即建立问题的数 学模型.
• 3.3 问题的数学描述
• 常量:Ri:第i个工厂的钢管单价,Li:第i个工厂 的产量上限.
SAQ ij
j1
n
A j
SAQ ij
i1
m
A j
AAQ jk
k 1
AAQ jk AAQ kj P jk
S i L i
S i 0 orS i 500
• 4 问题的求解
• 上面的数学描述中,最难处理的是 Si=0orSi>=500这个条件.求解过程分为三步:
• 5.利用图的标准最短路算法,求公路费用图 中任一个S点到任一个A点的最小费用路径,得 出SAP矩阵.如表1所示:
表1 图1的SAP矩阵(待续)
A1
2
3
4
5
6
7
S
1 1707 1603 1402 986 380 205 31
2 2157 2053 1902 1716 1110 955 860
3 2307 2203 2002 1816 1210 1055 960
• 变量表:Si,SAQij, Aj,AAQjk • 模型为:
• min(c1+c2+c3)
• S.t.
n
c1 Si Ri i 1
nm
c2
SAQij SAPij
i1 j 1
mm
c3
( AAQjk ( AAQjk 1) / 2)
Hale Waihona Puke j 1 k 1m S i