钢管订购与运输问题一的数学模型与求解

钢管订购与运输问题一的数学模型与求解

第32卷第3期2002年5月

数学的实践与认识

Vol132　No13　

May,2002　

建　　模

钢管订购与运输问题一的数学模型与求解

杨振华1,　胡国雷2,　郭跃华2

(11南京邮电学院应用数理系,南京　210003)(21南通工学院,南通　226007)

摘要:　本文针对2000年全国大学生数学建模竞赛B题—钢管订购与运输问题的问题,,

并给出了该数学模型的精确求解.

关键词:　数学模型,订购;运输;钢管

记铺设管道A1A15上任一点到A1,fiSi生产并运输单位钢管至x处的最小总费用.jjSAj的最小费用为qij(aj与qij1　SiAj的最小总费用(qij)表

S1

A1(0A2(104)A3(405)A4(1155)A5(1761)A6(1955)A7(2160)A8(2361)A9(3041)A10(3521)A11(3821)A12(4041)A13(4251)A14(4671)A15(5171)

S2

S3

S4

S5

S6

S7

330.7320.3300.2258.6198180.5163.1181.2224.2252256266281.2288302

370.7360.3345.2326.6266250.5241226.2269.2297301311326.2333347

385.7375.3355.2336.6276260.5251241.2203.2237241251266.2273287

420.7410.3395.2376.6316300.5291276.2244.2222211221236.2243257

410.7400.3380.2361.6301285.5276266.2234.2212188206226.2228242

415.7405.3385.2366.6306290.5281271.2234.2212201195176.2161178

435.7425.3405.2386.6326310.5301291.2259.2236226216198.2186162

　　注:表中第一列给出了Aj的坐标

若x∈AjA

j+1

,易知:

fi(x)=min(qij+0.1([x-aj]+1),qi,j+1+0.1([aj+1-x]+1)

.fi(x)(i=1,2,…,7)的图形见图1.其中[x-aj]表示取x-aj的整数部分

收稿日期:2001202216

钢管订购与运输问题一的数学模型与求解

354数　学　的　实　践　与　认　识32卷

图1

　最小费用函数fi(x)(1,2,7)

方案的区间表示

到达Aj的钢管的铺设费用,只与由j,不受其铺设中任一段使用何厂的钢管影响,,因而[ij1j1

715

1,一定存在一组可表示为∪∪[aij,bij]形式的最优解,其中

i=1j=1

715

.aij,bij均为整数(证明见[1])

f(x)dx.

∫

e

i

我们称长度为1,且端点值为整数的区间为单位区间.若e为单位区间,记fi(e)为

fi(x)在e内任一点的取值,显然fi(e)=

设Ei<[0,5171]为Si生产、运输钢管的集合,其总费用为学模型为模型1:

mins.t.

f∑∫

i=1

Ei

f(x)dx,因此原问题的数

∫

Ei

i

7

i

(x)dx

ΛEi∈{0}∪[500,si](i=1,2,…,7)

7i=1

　　Λ(Ei∩Ej)=0,(i,j=1,2,…,7,i≠j),∪Ei=[0,5171].

　　注　1)Λ(Ei∩Ej)=0,即Ei∩Ej=<,表示钢厂Si与Sj铺设的钢管无重叠部分.

2)在解集中,区间是开区间或闭区间对原问题是同一个解.

我们先取消S5,S6生产的上下限的限制,建立模型2:min

f∑∫

i=1

Ei

7

i

(x)dx

s.t.ΛEi∈{0}∪[500,si](i=1,2,3,4,7)

ΛE5≥0,ΛE6≥0,Λ(Ei∩Ej)=0,(i,j=1,2,…,7,i≠j),∪Ei=[0,5171].

i=1

7

　　命题1　若模型2的最优解是模型1的可行解,则必是模型1的最优解.

钢管订购与运输问题一的数学模型与求解

3期杨振华等:钢管订购与运输问题一的数学模型与求解355

fm

证明　由模型1的可行域为模型2的可行域的子集易得.

定理2(差价控制定理)　在Aj与Aj+1之间任一点x处Sm与Sn钢管单价之差 (x)=(x)-fn(x)一定位于两厂在Aj的差价与在Aj+1的差价之间,即令 j=fm(aj)-fn(aj),

j+1=fm(aj+1)-fn(aj+1),则x∈[aj,aj+1]时, (x)位于 j与 j+1之间.

证明　x∈[aj,aj+1]时, (x)的表达式为

(x)=min(qmj+0.1([x-aj]+1),qm,j+1+0.1([aj+1-x]+1))

-min(qnj+0.1([x-aj]+1),qn,j+1+0.1([aj+1-x]+1))

1)若

qmj+0.1([x-aj]+1)≤qm,j+1+0.1([aj+1-aj]+1)≤qn,j+1+0.1([aj+1-x]+1)x]+1)

且则　　2)若

qnj+0.1([x-

(x)=(qmj+0.1([x-aj]+1))-=qmj-qnj= j.

qmj+0.1([x-

(qnj+0.1[x-aj]+1))

aj]+1)≥qm,1.([aj-aj]+,+1ajxx]+1),

且qnj+0.1([x-

类似于情形1)可得 (=j3)j+0.1([-aj]+1)≤qm,j+1+0.1([aj+1-aj]+1)≥qn,j+1+0.1([aj+1-x]+1)x]+1)

且则

qnj+0.1([x-

(x)=(qmj+0.1([x-aj]+1)-(qn,j+1+0.1([aj+1-x]+1)

≤(qm,j+1+0.1([aj+1-x]+1))-(qn,j+1+0.1([aj+1-x]+1))

= j+1

另一方面因此

(x)≥(qmj+0.1([x-aj]+1))- j≤ (x)≤ j+1.

qmj+0.1([x-

(qnj+0.1([x-aj]+1))= j

　　4)若

aj])+1)≥qm,j+1+0.1([aj+1-aj])+1)≤qn,j+1+0.1([aj+1-x]+1)x]+1)

且qnj+0.1([x-

类似于3)的情况可证 j+1≤ ≤ j,定理2证毕.

33

记(E3.1,E2,…,E7)是模型2的一个最优解

定理3　ΛE37=0证明　否则ΛE3.7≥500

根据表1在A1,A2…A14处均有f7(x)-f6(x)≥20,由差价控制定理知,当x∈[0,4671]时,f7(x)-f6(x)≥20.当x∈[4671,5171]时,

f6(x)=f7(x)=

161+0.1([x-4671]+178+0.1([5171-x]+186+0.1([x-4671]+162+0.1([5171-x]+

1),1),1),1),

4671≤x<50065006≤x≤51714671≤x<48014801≤x≤5171

钢管订购与运输问题一的数学模型与求解

356数　学　的　实　践　与　认　识32卷

易知,当x∈[4671,4826]时,f7(x)-f6(x)≥20,当x∈[4826,5171]时,-16≤f7(x)-f6(x)≤20,且

∫(f

4826

5171

7

(x)-f6(x))dx=-2280.

设g(x)=f7(x)-f6(x)-20,则

∫g(x)dx=∫g(x)dx+∫

≥

∫g(x)dx=-20(5171-3E7

3

E7∩[0,4826]

3

E7∩[4826,5171]

g(x)dx≥

∫

3

E7∩[4826,5171]

g(x)dx

51714826

4826)-2280=-9180

从而

∫

E7

3

(f7(x)-f6(x))dx=20ΛE37+

∫g(x)dx≥20 500-3

E7

3E6

9180=820

33

取E3=E3=<(S6的产量无上限,故变化后仍为模型2可行解),则6′6∪7,E7′

f(x)dx+∫f(x)dx-f(x)+f

=

∫f(x)dx-∫f(x)dx-(=

∫(f(x)-f()dx-63

E6′

73

E7′

6

3E7

33E6∪E7

7

(x)d6

3E6

6

37

7

3E7

6,.EΛ4,j-q5,j≥10(j=1,2,…,15),根据差价控制定理,在[0,5171]上有f4(x)

-f5(x)≥10,又S5无产量上限,类似于定理3的证明可证ΛE34=0

设A1=[0,3325],A2=[3325,5171],由于当x∈A2时,

min(f5(x),f6(x))<min(f1(x),f2(x),f3(x)),我们可将模型2分解为两个模型:记{1,2,3,5,6}=J模型3:模型4:

min2

i∈J

f(x)dx

∫

Ei

i

min2

i∈J

f(x)dx∫

Ei

i

s.t.0≤ΛEi≤si(i=1,2,3)s.t.0≤ΛEi≤si(i=1,2,3)

ΛE5≥0,ΛE6≥0

Λ(Ei∩Ej)=0,(i,j∈J,i≠j)

i∈J

ΛE5≥0,ΛE6≥0

Λ(Ei∩Ej)=0,(i,j∈J,i≠j)

i∈J