2024年4月11日发(作者：黄冈2年级数学试卷)

2000年论文选

管道订购与运输问题

杨志江， 李国欣， 张 敏

指导老师： 中国矿业大学数模教练组

(中国矿业大学．江苏徐州 221008)

编者按：本文采用将待铺设管道按单位长度分解成n个需求点，建立运输模型的方法．避免了问题一和三

的差别．模型切合原赛题要求．并针对原问题的规模，对算法作y--定的改进，得到了较好的结果．本刊予

以摘要发表．

摘 要：本文在详细分析的基础上，通过合理假设并引人等价转换原则，将管道订购与运输问题转化为单

一的公路运输问题．运用组合优化的思想和方法，给出了数学模型·——产量未定的运输模型．针对此模

型，我们设计了“改进的最小元素法”和“改进的伏格尔Ph\"，先求得了—个初始解。再通过“试探法”

和“迭代法”进行调调优化．最后得出结果：对第—·问．最小总费用为1279019万元；对第三问．最小

总费用为1407383万元．

1 问题的重述(略)

2 基本假设

(1)只考虑订购费用和运输费用，不考虑装卸等其它费用．

(2)钢管单价与订购量、订购次数、订购日期无关．

(3)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的

(4)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的一批记录：管

道区间，供应厂商，具体运输路线．

(4)将每一单位的管道所在地看成一个需求点，向一单位管道的所在地运输钢管即为

向一个点运输钢管．

3 符号说明

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

S

i

:

第i个钢厂

S

i

:

第i个钢厂的产量上限。

p

i

:

第i个钢厂单位钢管的销售价

A

i

管道线上第i个站点。

d

i

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

C

ij

:

从钢厂

S

i

(i1,2,,m)

到点

d

j

(j1,2,,n)

的最低单位费用。

4 问题分析

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

线．对于铁路线上的任意两点

V

i

,V

j

，用F1oyd算法找出两点间最短铁路路线的长度

L

ij

查

铁路运价表求得

L

ij

，对应的铁路单位运费

f

ij

;又设与该段铁路等费用的公路长度为

l

ij

，则：

f

ij

0.1l

ij

由此，我们就在

V

i

,V

j

之间用一条等价的公路线来代替

V

i

,V

j

间的最短铁路线．如果

V

i

,V

j

之间原来就有公路，就选择新旧公路中较短的一条．这样，我们就把铁路运输网络转

换成了公路运输网络．

销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为公路单位运价．

对于钢厂S

i

的销售单价P

i

，我们可以虚设一条公路线，连接钢厂S

i

及另一虚拟钢厂

s

i

，

其长度为

l

i

，并且满足

l

i

0.1p

i

；从而将钢厂的销售单价转换成公路运输单价，而新钢

厂

s

i

的销售价为0.

将铁路和销价转换为公路的过程可以由计算机编程实现．

通过上述的分析，我们可以将原问题化为一个相对简单的产量未定的运输问题，利用

\'

\'

A

1

到A

15

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

型．但是由于

A

1

,A

2

,A

15

并不能代表所有的实际需求点(实际需求点是n个单位管道)，因

此，我们可以用F1oyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一，n

＝5171;对于问题三，n＝5903)的最短路径，并由此得出一个具有7个供应点、n个需求点的

产址未定的运输模型．

5 模型的建立

产量未定的运输模型

根据假设4，我们可以将每一单位的管道看成一个需求点，向一单位管道的所在地运输

钢管即为向一个点运输钢管．对每个点，我们可以根据该点的位置和最短等价公路距离，求

出各钢厂与该点之间最小单位运输费用

C

ij

(销价已经归人运输费用之中了)．设总共有m个

供应点(钢厂)，n个需求点，我们就可以得到一个产量未定的运输模型：

有m个供应点、n个需求点，每个供应点的供应量

u

i

{0}{500,s

i

}

；每个需求点需

要1单位，运输单价矩阵为C，求使得总运输费用最小的运输方案．

其数学规划模型：

minF



C

ij

x

ij

i1j1

mn

s..t

n

x

ij

{0}{500,S

i

}i1,2,

j1

m

j1,2,n

x

ij

1

i1

x

ij

0或1

,m

C

11

C

12

其中：

C

C

m1

C

m2

x

11

X

x

m1

x

12

x

m2

C

1n

为单位费用矩阵

C

mn

x

1n

为决策矩阵，也为0-1矩阵

x

mn

6 模型的求解

对于本题，上述0-1规划规模宏大，现有的一些算法不能胜任，我们必须具体问题具体

分析，结合本题实际情况，寻找行之有效的算法．

(1)初始方案的改进的最小元素法和改进的伏格尔法

*改进的最小元素法

改进的最小元素法又称为贪婪法或瞎子爬山法，它的宗旨是每一步都取当前的最优值算

法步骤为，对费用矩阵C作n次下列循环：

①C中找一个最小值

C

ij

；

②令

x

ij

1;

③C的第j的所有数据改为+

；

④如果

x

j1

n

ij

s

i

，第i个供应点的供应量已达上限，将C的第i行数据全改为+

。

对于问题一和问题三，我们用贪婪法求得的最小总费用的初始分别为1286692.1万元和

1414515.2万元。

*改进的伏格尔法

改进的最小元素法确定的初始方案往往缺乏全局观念，即为了省节一处的费用，在其它

处要花费更多，改进的伏格尔法的主要思想：一个目的地如果不能采用最小值供应（供应点

供应不足），就必须考虑次小值供应，这里就存在一个差额，差额越大，在不能采用最小值

时，损失越大，因此，改进的伏格尔法的宗旨是每一步对当前差值最大的点取当前最小值。

算法的步骤为，对矩阵C做n次下循环：

①指出每一行最小值与最大值之差最大的一行，第i行，找出该行的最小值为

C

ij

②令

x

ij

1;

③C的第j列的所有数据改为



；

④如果

x

j1

n

ij

s

i

，第i个供应点的供应量已达上限，令C的第i行的所有数据为



。

对于问题一和问题三，我们用改进的伏格尔法求得方案的总费用分别为1279019万元和

1407383万元。

（2）调整优化

调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度．调整优

化分两个部分，第一部分是用试探法对供应点的供应量进行优化．第二部分是用迭代法对供

应点进行两两对调优化．

*试探法调整优化实际供应量在500以下的供应点

对每个实际供应量在500以·F的供应点，只存在两种合理的优化方法：一种是将其供

应量增加到500，另一种是将其供应量减少到0．试探法将分别试探进行下列两种优化：

其一是先将供应点的供应量强行提升至500，使用改进的伏格尔法的优先顺序，从其它

供应点负责供应的需求点抢夺一部分，再用对调法优化至无法更优，得出一个总费用F

1

；

其二是先将该供应点的供应量调整为0，其原供应的需求点由其它钢厂用改进的伏格尔法的

优先顺序补充，再用对调法优化至无法更优，得出一个总费用F

2

那么，就应当采取总费用

较小的方法．

例如，对于第一问，按改进的伏格尔法获得的初始方案中，S

7

的用量仅为245，优化时，

试探将其降为0和将其提升为500后的最优结果，分别为1279019万元和1280506万元，则

说明应将S，降为0．

*用迭代法进行对调优化

改进的伏格尔法给出的初始值虽然很接近最优值，但仍有不足之处，即可能存在两个需

求点，调换供应点能使总费用更小，例如，需求点a和6的供应点是x和y，费用分别是

C(x,a)和C(y,b)，如果让y供应a，x供应b的话，费用将是C(y，a)和r(c，b)，如果：

C(y，a)+r(x，b)

则说明对调后总费用更低．

因此，我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优．

2

由于一共只有m＝7个供应点，所以两两对调的可行方案一共有

C

7

21

种，因此，两

两对调供应点的方法是可行的，具体步骤如下：

Stepl 对于任意两个供应点x

i

和x

j

i＝1，2，…，m j=1，2，…，m

ij

1)找出所有由x

i

供应的需求点，构成点集A＝{a

1

,a

2

,c}

2)找出所有由x

j

供应的需求点，构成点集B＝{b

1

,b

2

,…}

3)对A中所有点，如果改用x

j

来供应，将付出的代价构成向量

A\'{a

1

,a

1

,

4)对B中所有点，如果改用x

i

来供应，将付出的代价构成向量

B\'{b

1

,b

1

,

5)对

A\'和B\'

分别按升序排序．

\'\'

6)同时对

A\'和B\'

从前向后遍历，如果

a

i

b

i

0

(表示对调供应者将降低总费用)，则对

\'\'

调其供应者，直到出现

a

i

b

i

0

为止．

\'\'

\'\'

}

}

Step2 统计这

C

m

轮对调后的总费用

F\'

是否比原来的总费用F有明显的进步，即

2

F\'F

(

为一固定的较小值)

。如果有明显的进步，则再回Stepl执行，否则结束优

化．

令人振奋的是，采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别采

用这种优化方案后，竟都达到了相同的最小费用：1279019万元．

(3)结果(略)

参考文献

[1]薛秀谦等编著．《运筹学》.中国矿业大学出版社．1998年．

[2]赵新泽著．《线性规划的新方法和应用》．世界图书出版社，1996年．

[3]王树禾著．《图论极其算法》．中国科学技术大学出版社．1990年．

[4]LUCAS W F著．《离散与系统模型3．国防科技大学出版社，1996年

钢管订购和运输策略

段晓军， 俞昌盛， 吴建德

指导老师： 张胜贵

(西北工业大学，西安 710072)

编者按：本文节选的是原沦文中模型的分析与建立以及之前的准备工作部分．该部分通过单

位钢管的最小运购费，建立了问题求解的二次规划模型．特点是思路、表述简明、清晰，尤

其是第3问的模型具有较强的般性，适用于树形结构的通常情形．值得注意的是．模型中有

关铺设费的假设和表达式与常见情形略有不同．

摘要：在铺设管道为一条线的情况下．我们建立了解决钢管订购和运输问题的非线性规划模

型．由于变量较少．约束条件大都为线性的，口标函数为二次函数．所以利用Lingo软件．可

以很快求得比较满意的订购和运输方案．我们利用Matlab软件，对所得到的数据进行拟合，

得到相应的反映销价变化对总费用影响的曲线，然后比较各个钢厂钢管销价变化对总费用影

响的大小．对于钢厂钢管产量上限变化对总费用和购运计划的影响．我们也作了类似的处

理．如果要铺设的管道是树形图，我们对树形图的每条边定向，建立了与铺设管道为·—条

线时类似的数学模型．从而大大拓广了模刑的使用范围．在论文中．我们还对所建立的模型

的优缺点和需要改进的方向进行了讨论．

1 符号说明

·

s

i

：钢厂

s

i

在指定期限内钢管的最大产量；

·

i,j

:A

i

到A

j

，之间铺设管道的里程数；

·

c

ij

:

：单位钢管从钢厂

S

i

运到

A

j

，所需最小订购和运输费用；

·

x

i

:

钢厂

S

i

是否承担制造这种钢管；

·

y

ij

:

钢厂

S

i

运抵A

j

点的钢管数量，不含路过A

j

的部分；

·

z

j

:

运到A

i

的所有钢管沿

A

j

A

j1

铺设的数量；

·

z

ij

：运抵A

i

的所有钢管沿

A

j

A

j1

铺设的数量；

·

d(A

j

)

：树中A

j

的度数；

·

d(A

j

):

树中A

j

的入度；

·

d(A

j

):

树中A

j

的出度；

·

:

单位钢管1公里的公路运输费用。

2 基本假设

根据题目的要求，并为达到简化问题的目的，我们有以下假设：

1．假设运到A

j

的钢管，只能在

A

j1

到A

j1

之间包含A

j

的某个区段内铺设,并且到达A

j

的钢管在

A

j1

到A

j1

之间包含A

j

的铺设区段和到达A

j+1

，的钢管在A

j

到A

j+2

之间包含A

j+l

的铺设区段不相交．否则的话，总可以调节铺设方案，使得总费用减少．

2．在考虑问题2时，假设钢管价格不可能有太大幅度变化．所以，我们只考虑钢管价

格在其原售价10％的范围内波动．同时，我们假定，钢厂的产量不可能成倍的增加或减少．我

们在减少300个单位，增加600个单位的范围内讨论，这意味着我们不考虑钢厂破产或者超

大规模扩大生产的情况．

3．在具体铺设每一公里时，我们只把钢管运到每一公里开始的地方，沿运送方向向前

铺，然后往前铺设的运送费用我们不予考虑．

3 模型建立

1．问题l的模型

(1)决策变量

我们首先引入一组0一1变量

x

1

,x

2

,x

7

,其中

x

i

表示钢厂S

i

是否承担制造这种钢管．如

果钢厂S

i

承担制造这种钢管，则

x

i

1

，否则

x

i

0

.

所有的钢管，都是先运用

A,A

2

,,A

15

后，或者转运到其它地方，或者在包含A

j

的一

个区段内铺设，我们设从钢厂S

i

运抵A

j

的一个区段内铺设的钢管数量为

y

ij

,这里

i1,2,,7;j1,2,15.

我们用变量Z

j

来表示从所有的钢厂运到A

j

的钢管总量中沿

A

j

A

j1

铺设的部分，这

里j=1,2, ,14.

这样，我们一共引入了三组决策变量：

x

i

(i1,2,,7);y

ij

(i1,2,,7,j

1,2,,15);

z

k

(k1,2,,14)

。

（2）目标函数

问题的目的是求好的订购和运输方案，使得总费用最小，事实上，总费用可以分成两部

分。第一部分包括钢管的订购费用和钢管从钢厂运抵

A

1

,A

2

,A

15

所需的运费；我们用

c

ij

来

表示单位钢管从钢厂

S

i

运抵A

j

所需的最小订购和运输费用，则第一部分费用为

u

1



c

i1j1

715

ij

y

ij

A

15

后，再运到具体铺设地点的费用，由假设3，从

A

j

第二部分费用是指钢管运抵

A

1

,A

2

,

到

A

j1

区段部分所需的费用为

z

j

(z

j

1)

2

(

j,j1

z

j

)(

j,j1

z

j

1)

2

,

其中

j,j1

表示

A

j

到A

j1

铺设管道的长度，这样，我们不难得知第二部分费用为

u

2

（3）约束条件

首先，由于一个钢厂如果承担制造这种钢管，则至少需要生产500个单位，而钢厂

S

i

在

指定期限内能生产钢管的最大数量为

s

i

个单位，所以，我们得到以下一组约束条件

500x

i

[(z

2

j1

14

j

1)z

j

(

j,j1

z

j

)(

j,j1

z

j

1)]

y

j1

15

ij

s

i

x

i

,i1,2,,7.

A

15

的里程数，那么 由于订购的所有钢管总量等于

A

1

A

2



y

i1j1

715

ij

5171.

很显然，我们可以设

z

j

j,j1

，因为如果

z

j

j,j1

，则相当于有

z

z

j,j1

数量的

钢管是从A

j

直接运送到

A

j1

后再送到具体铺设地点。

运抵A

j

的钢管总数量，等于向包含A

j

的区段铺设的里程数，那么

y

i1

7

ij

z

j

(

j1,j

z

j1

),j2,3,

77

,14.

并且，我们还有

y

i1

ij

z

1

和

y

i.15

14,15

z

14

i1

（4）数学模型

通过上面的分析，我们得到问题1的如下模型

min



c

i1j1

715

ij

y

ij

2

[z(z

j

j1

14

j

1)(

j,j1

z

j

)(

j,j1

z

j

1)]

15

j1,2,,7

500x

i

y

ij

s

i

x

i

j1

715



y

ij

5171

i1j1

7

j2,3,

y

ij

z

j

(

j1,j

z

j1

),

i1

(A)s.t

7

y

i1

z

1

i1

7

y

z

i,1514,1514

i1

j1,2,,14

0z

j

j,j1

i1,2,7

x

i

0.1,

y

ij

0,i1,2,,7,j1,2,

j1,2,,14

,15

可以看出，这是一个非线性规划问题。

2．问题2的模型

为了分析钢厂钢管销价的变化对购运计划和总费用的影响，对于每个钢厂，利用模型

(A)，我们分别算出它的钢管销价发生一系列的变化后，所得到的总费用和购运计划；并根

据所得到的数据，利用Matlab软件拟合出销价变化和总费用变化量关系的曲线，对所得到

的曲线进行分析和对比，找到钢管销价变化对购运计划和总费用影响最大的钢厂．类似地，

我们用同样的方法，对钢厂产量上限发生变化对购运计划和总费用的影响进行了分析．

3．问题3的模型

如果要铺设的管道不是一条线，而是一个树形图，我们首先给树形图的每条边指定一

个方向，使得所得到的有向树有一个度数为1的顶点的人度为o，而其它每个顶点的人度均

为1．与问题1一样，我们可以引入0—1变量

x

i

(i1,2,,7)

以及变量

y

ij

(i1,2,,7,j1,2,,21)

，它们的含义与问题1中的定义完全一致．类似于问题1，对

于有向树的有向边

(A

i

,A

j

),

我们用z

ij

表示运抵A

i

的所有钢管沿

A

i

A

j

，铺设的里程数．数

学模型为

min



c

ij

y

ij

i1j1

715

2

(A

i

,A

j

)E(T)

[z

ij

(z

ij

1)(

i,j

z

ij

)(

i,j

z

ij

1)]

21

j1,2,,7

500x

i

y

ij

s

i

x

i

j1

715



y

ij

5903

i1j1

7

y

ij

z

jk

(

h,j

z

hj

),其中(A

h

,A

j

)E(T)

当d(A

j

)1时,

i=1(A

j

,A

k

)E(T)

7

(B)s.t

当d(A

j

)0时,

y

i1

k,j

z

kj

,其中(A

k

,A

j

)E(t)

i1

7

当d(A

j

)0时,

y

ij

z

jk

,其中(A

j

,A

k

)E(T)

i1

(A

i

,A

j

)E(T)

0z

ij

i,j1

i1,2,7

x

i

0.1,

i1,2,,7,j1,2,,21

y

ij

0,

参考文献：

[1]甘应爱，田丰等等.运行学.清华大学出版社,北京,1994。

[2]袁亚湘.孙文瑜著.最优化理论与方法.科学出版社，北京，1997.

[3]徐俊明著.图论及其应用.中国科学技术大学出版社，合肥，1997.


更多推荐

钢管,运输,钢厂