学号：                           姓名：                        

实验七：图论3

1. 某产品从仓库运往市场销售，已知各仓库的可供量、各市场需求量及从i仓库至j市场的路径的运输能力如下表所列(表中数字0代表无路)，试求从仓库可运往市场的最大流量，各市场需求能否满足？

仓库i

将仓库（A,B,C）到市场j(j=1…4)，按交通图用弧连接，并标上容量，再虚设一个发点s和一个收点t，形成以下网络流。问题转化成求S到T的最大流，

Lingo程序如下

model:

sets:

nodes/s,a,b,c,1,2,3,4,t/;

arcs(nodes,nodes)/s a,s b,s c,a 1,a 2,a 4,b 3,b 4,c 1,c 2,c 3,c 4,1 t,2 t,3 t,4 t/:c,f;

endsets

data:

c=20 20 100 30 10 40 10 50 20 10 40 5 20 20 60 20;

enddata

n=@size(nodes);!顶点的个数;

max=flow;

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

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

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

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

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

end

结果分析：

最大流为110，不满足C的供求量。其中市场 3 只能满足 50 单位，差 10 单位。

2. 某单位招收懂俄、英、日、德、法文的翻译各一名，有5人应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书？最多几个得到聘书，招聘后每人从事哪一方面翻译工作？

解答： 将 5 个人与 5 个语种分别用点表示，把各个人与懂得的外语语种之间用

弧相连。为了求单源和单汇网络的最大流，再加一个虚拟的单源 vs,vs 与 5 个人

之间各有一条弧，再加一个虚拟的单汇 vt，在 5 个外语语种和 vt 之间各有一条

弧。规定每条弧的容量为 1，求出上述网络的最大流数字即为最多能得到招聘的

人数。计算时把源点 vs,甲乙丙丁戊 5 个人，俄英日德法 5 个外语语种和汇点 vt

分别编号为 1,2,...,12.

Matlab程序如下

clc,clear

a=zeros(12);

a(1,[2:6])=1;

a(2,[8,9])=1;

a(3,[7,8,10])=1;

a(4,[8,9])=1;

a(5,[8,9])=1;

a(6,[10,11])=1;

a([7:11],12)=1;

a=sparse(a);

[b,c]=graphmaxflow(a,1,12)

运行结果:

b =4

c =

(1,3) 1

(1,4) 1

(1,5) 1

(1,6) 1

(3,7) 1

(5,8) 1

(4,9) 1

(6,10) 1

(7,12) 1

(8,12) 1

(9,12) 1

(10,12) 1

结果分析

求得只有 4 个人得到招聘，乙—俄,丁—英,丙—日,戊—德,甲未能得到应聘.

3. 将下表所列的某运输问题的相关数据转化为最小费用最大流问题，画出网络图并求解。

产地

Matlab程序如下：

n=7

C=zeros(7)

C(1,[2,3])=[8,7]

C(2,[4,5,6])=[8,8,8]

C(3,[4,5,6])=[7 7 7]

C(4,7)=4

C(5,7)=5

C(6,7)=6

运行结果

wf =

15

No =

8 0 0 0 0 0 0

结果分析

得到最大流为15

再建立求最小费用的线性规划模型，求最小费用的Lingo程序如

下：

model:

sets:

nodes/s,a,b,1,2,3,t/:d;

arcs(nodes,nodes)/s a,s b,a 1,a 2,a 3,b 1,b 2,b 3,1 t,2 t,3 t/:b,c,f;

endsets

data:

b=0 0 20 24 5 30 22 20 0 0 0;

c=8 7 8 8 8 7 7 7 4 5 6;

d=15 0 0 0 0 0 -15; !最大流为 15;

enddata

n=@size(nodes); !顶点的个数;

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

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

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

end

结果分析：

求得最小费用为240。