北交大LINGO考试2旅行商问题,最大流问题等

《物流软件》实验报告

实验编号：实验2

学号：序号：

姓名：

班级：

2015年10月

一、 旅行商问题

（1） 数学模型

设di是两点i与j之间的距离，Xij=0或1（1表示连接，0表示不连接）则有

Mindij*Xij

jV

s.t. （每个点只有一条边出去），iV Xij =1 ，

jV

（每个点只有一条边进入），iV Xji =1，

jV

(除起点与重点外，个边不构成圈)

（2） LINGO程序

MODEL:

SETS:

CENTERS/1..8/:LEVEL;

LINK(CENTERS,CENTERS):DISTANCE,X;

ENDSETS

DATA:

DISTANCE = 0 3 2 3 4 3 5 6

3 0 2 3 2 3 1 4

2 2 0 1 4 3 2 5

3 3 1 0 1 14 3 4

4 2 4 1 0 2 2 3

3 3 3 14 2 0 8 4

5 1 2 3 2 8 0 3

6 4 5 4 3 4 3 0;

ENDDATA

N=@SIZE(CENTERS);

MIN=@SUM(LINK(I,J)|i #ne# j :distance(i,j)*x(i,j));

@for(centers(i):

@sum(centers(j)|j #ne# i:x(j,i))=1;

@SUM(CENTERS(J)|J #NE# I:X(I,J)) = 1;

@FOR(CENTERS(j)|J #GT# 1 #AND# J #NE# I :

LEVEL(J)>=LEVEL(I)+X(I,J)-(N-2)*(1-X(i,J))+(N-3)*X(J,I););); @FOR(LINK:@BIN(X));

@FOR(CENTERS(I)|I #GT# 1:

LEVEL(I)

LEVEL(I)>=1+(N-2)*X(I,1););

END

CENTERS/1..8/是基本集合名字，元素为1到8。LEVEL为其元素。 LINK是派生集合

（3） 运行结果

Global optimal solution found.

Objective value: 17.00000

Extended solver steps: 0

Total solver iterations: 56

X( 1, 2) 1.000000 3.000000

X( 2, 7) 1.000000 1.000000

X( 3, 1) 1.000000 2.000000

X( 4, 3) 1.000000 1.000000

X( 5, 4) 1.000000 1.000000

X( 6, 5) 1.000000 2.000000 X( 7, 8) 1.000000 3.000000

X( 8, 6) 1.000000 4.000000

从以上结果可以看出，最短的经过距离是17.路径为

1 2 7 8 6 5 4 3 1

二、最大流问题

（1）数学模型

Max vf;

s.t.

jV(i,j)Avf(is);fijfij=-vf(it); jV0(is,t)(j,i)A

0

（2）LINGO程序

MODEL:

SETS:

NODES/1,2,3,4,5,6,7/;

arcs(nodes,nodes)/1,2,1,3,1,4,2,5,3,6,4,3,4,6,5,7,6,5,6,7/:c,f;

endsets

data:

c =40 13 15 25 20 26 12 32 18 42;

enddata

max=flow;

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):

@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);

@sum(arcs(i,j)|i #eq# 1:f(i,j))= flow;

@for(arcs:@bnd(0,f,c));

End

NODES是基本集合名字，1到7为元素，

acrs是派生集合，各个路径是其元素。Cf为属性

（3）运行结果

Global optimal solution found.

Objective value: 53.00000

Total solver iterations:

Variable Value Reduced Cost

FLOW 53.00000 0.000000

F( 1, 2) 25.00000 0.000000

F( 1, 3) 13.00000 -1.000000

F( 1, 4) 15.00000 -1.000000

F( 2, 5) 25.00000 -1.000000

F( 3, 6) 16.00000 0.000000

F( 4, 3) 3.000000 0.000000

F( 4, 6) 12.00000 0.000000

F( 5, 7) 25.00000 0.000000

F( 6, 5) 0.000000 0.000000

F( 6, 7) 28.00000 0.000000

从以上结果可以看出各个线路的流量，如第一行表示点1到点2流 25，第二行表示点1到点3流13,依此类推。得到

v1，v2，v5，v7=25

V1，v4，v6，v7=12

V1，v3，v6，v7=13

V1，v4，v3，v6，v7=3.

最大流为53

二、 最小费用最大流问题

（1） 数学建模

Min

s.t.(i,j)ACijFij;

jV(i,j)AFijjV(j,i)AFji=di,

0

di=vf(i=s);-vf(i=t);0(i≠s,t)

（当vf为网络的最大流时，就为最大费用最小流问题。）

（2） LINGO程序

MODEL:

SETS:

NODES/1,2,3,4,5,6,7/:d;

arcs(nodes,nodes)/1,2,1,3,1,4,2,5,3,6,4,3,4,6,5,7,6,5,6,7/:c,u,f; endsets

data:

d = 53 0 0 0 0 0 -53;

c = 3 1 2 4 3 3 1 1 1 2;

u = 40 13 15 25 20 26 12 32 18 42;

enddata

min=@sum(arcs:c*f);

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):

@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=d(i));

@sum(arcs(i,j)|i #eq# 1:f(i,j))=d(1);

@for(arcs:@bnd(0,f,u));

end

NODES为基本集合名，1到7为元素，d为属性

arcs为派生集合名，各个路径为元素，c，u，f为属性

（3） 运行程序

Global optimal solution found.

Objective value: 368.0000

Total solver iterations: 0

Variable Value Reduced Cost U( 1, 2) 40.00000 0.000000

U( 1, 3) 13.00000 0.000000

U( 1, 4) 15.00000 0.000000

U( 2, 5) 25.00000 0.000000

U( 3, 6) 20.00000 0.000000

U( 4, 3) 26.00000 0.000000

U( 4, 6) 12.00000 0.000000

U( 5, 7) 32.00000 0.000000

U( 6, 5) 18.00000 0.000000

U( 6, 7) 42.00000 0.000000

F( 1, 2) 25.00000 0.000000

F( 1, 3) 13.00000 -4.000000 F( 1, 4) 15.00000 0.000000

F( 2, 5) 25.00000 -2.000000 F( 3, 6) 16.00000 0.000000

F( 4, 3) 3.000000 0.000000

F( 4, 6) 12.00000 -5.000000 F( 5, 7) 32.00000 0.000000

F( 6, 5) 7.000000 0.000000

F( 6, 7) 21.00000 0.000000

V，v2，v5，v7

V1，v4，v6，v7

V1，v3，v6，v7

V1，v3，v6，v5，v7

V1，v4，v3，v6，v7

由以上结果可知，最大流为53，最小费用为368

（4） 对比

v1，v2，v5，v7=25

V1，v4，v6，v7=12

V1，v3，v6，v7=13

V1，v4，v3，v6，v7=3

这是实验（2）的结果

V，v2，v5，v7

V1，v4，v6，v7

V1，v3，v6，v7

V1，v3，v6，v5，v7

V1，v4，v3，v6，v7

这个是实验（三）的结果

两个实验的路径选择是一样的，如果图更复杂，很有可能遇到有多个最大流的情况，这时候引入最小费用最大流就有了经济意义，帮助决策。