2000年全国数学建模竞赛B题优秀论文.pdf

2000年论文选

管道订购与运输问题

杨志江，李国欣，张敏
指导老师：中国矿业大学数模教练组
(中国矿业大学．江苏徐州221008)

编者按：本文采用将待铺设管道按单位长度分解成n个需求点，建立运输模型的方法．避免了问题一和三
的差别．模型切合原赛题要求．并针对原问题的规模，对算法作y--定的改进，得到了较好的结果．本刊予
以摘要发表．
摘要：本文在详细分析的基础上，通过合理假设并引人等价转换原则，将管道订购与运输问题转化为单
一的公路运输问题．运用组合优化的思想和方法，给出了数学模型·——产量未定的运输模型．针对此模
型，我们设计了“改进的最小元素法”和“改进的伏格尔Ph"，先求得了—个初始解。再通过“试探法”
和“迭代法”进行调调优化．最后得出结果：对第—·问．最小总费用为1279019万元；对第三问．最小
总费用为1407383万元．

1问题的重述(略)

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

3符号说明

M：钢厂总数.n：单位管道总数.

S:第i个钢厂S:第i个钢厂的产量上限。
ii

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

d管道线上第i个单位管道的位置。F：总费用。
i

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

4问题分析
运输费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转换为公路

线．对于铁路线上的任意两点V,V，用F1oyd算法找出两点间最短铁路路线的长度L查
ijij
铁路运价表求得L，对应的铁路单位运费f;又设与该段铁路等费用的公路长度为l，则：
ijijij

f0.1l
ijij

由此，我们就在V,V之间用一条等价的公路线来代替V,V间的最短铁路线．如果
ijij

V,V之间原来就有公路，就选择新旧公路中较短的一条．这样，我们就把铁路运输网络转
ij
换成了公路运输网络．
销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为公路单位运价．

对于钢厂S的销售单价P，我们可以虚设一条公路线，连接钢厂S及另一虚拟钢厂s'，
iiii

其长度为l，并且满足l0.1p；从而将钢厂的销售单价转换成公路运输单价，而新钢
iii

厂s'的销售价为0.
i
将铁路和销价转换为公路的过程可以由计算机编程实现．
通过上述的分析，我们可以将原问题化为一个相对简单的产量未定的运输问题，利用

A到A之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模
115

型．但是由于A,A,A并不能代表所有的实际需求点(实际需求点是n个单位管道)，因
1215
此，我们可以用F1oyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一，n
＝5171;对于问题三，n＝5903)的最短路径，并由此得出一个具有7个供应点、n个需求点的
产址未定的运输模型．

5模型的建立
产量未定的运输模型
根据假设4，我们可以将每一单位的管道看成一个需求点，向一单位管道的所在地运输
钢管即为向一个点运输钢管．对每个点，我们可以根据该点的位置和最短等价公路距离，求

出各钢厂与该点之间最小单位运输费用C(销价已经归人运输费用之中了)．设总共有m个
ij
供应点(钢厂)，n个需求点，我们就可以得到一个产量未定的运输模型：

有m个供应点、n个需求点，每个供应点的供应量u{0}{500,s}；每个需求点需
ii
要1单位，运输单价矩阵为C，求使得总运输费用最小的运输方案．
其数学规划模型：

mn
minFCx
ijij
i1j1
n
x{0}{500,S}i1,2,,m
iji
j1
m
s..tx1j1,2,n
ij
i1
x0或1
ij

CCC
11121n
其中：C为单位费用矩阵

CCC
m1m2mn
xxx
11121n
X为决策矩阵，也为0-1矩阵

xxx
m1m2mn

6模型的求解
对于本题，上述0-1规划规模宏大，现有的一些算法不能胜任，我们必须具体问题具体
分析，结合本题实际情况，寻找行之有效的算法．
(1)初始方案的改进的最小元素法和改进的伏格尔法
*改进的最小元素法
改进的最小元素法又称为贪婪法或瞎子爬山法，它的宗旨是每一步都取当前的