数学建模——最大流问题（配合例子说明）（二）

【模型求解】

编写lingo求解程序，计算得个各条边的实际流量见表2和总费用为50.（总流量为7时）

sets:
dian/vs v1 v2 v3 v4 vt/:;
bian(dian,dian)/vs,v1 vs,v3 vs,v4 v1,v2 v1,v3 v2,v3 v2,vt v3,vt v3,v4 v4,v3 v4,vt/:c,x,d;
endsets
data:
c=4 3 4 2 1 2 4 2 3 2 3;
d=3 3 2 4 2 1 3 3 3 2 4;
enddata
min=@sum(bian:d*x);
w=@sum(bian(i,j)|j#eq#6:x(i,j));
@for(bian(i,j):x(i,j)<c(i,j));
@for(dian(k)|k#ne#1#and#k#ne#6:@sum(bian(i,k):x(i,k))=@sum(bian(k,j):x(k,j)));
w=7;

表2 最小费用的流量分布

三、最大匹配问题

问题来源：

 有n个人，m件工作，每个人的工作能力不同，各能胜任某几项工作。假设每个只做一件工作；一件工作只需一个人做，怎样分配才能使得尽量多的工人有工作。

转化为匹配问题：

•  x1,x2,…,xn表示工人；
• y1,y2,…,ym表示工作,
• X表示{x1,x2,…,xn}, Y表示{y1,y2,…,ym}。

这样就产生一个二部图G=(X,Y,E),其中E中的边(xi,yj)就表示xi胜任工作yj。如图4所示

匹配定义：

二部图G=(X,Y,E)，M是E的子集，M中任意两条边都没有公共端点，则称M是G的一个匹配（对集）。使得|M|达到最大的匹配称为最大匹配。

例3

设有5位待业者，5项工作，他们各自能胜任的工作情况如图5所示，设计一个就业方案，使尽量多人能就业。

【问题假设】

一人最多一工作，一工作最多一人。

【问题分析】

注意到，对xi来说，出次可能不唯一，但最多有一条边可能实现；对yj来说，入次可能不唯一，但也最多一条边实现。根据流量平衡，在xi前置vs作为发点；在yj后置vt作为汇点，将图5改造为流量网络，见图六。

如图6所示流量网络图G=(V,E,C),其中每条边的容量都为1.

【符号设置】

• G=(V,E,C)流量网络图，如图6；
• vs 发点；
• vt 汇点；
• x1,…,x5,y1,…,y5，网络中间点；
• Cij  边(i,j)的容量限制，且cij=1,(i,j)∈E；
• xij 边(i,j)的实际流量，且只取0-1；

【数学模型】

【模型求解】

  编写Lingo程序，计算得到最大匹配为4，具体安排反映在图6上，见图7.

sets:
dian/vs x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 vt/:;
bian(dian,dian)/vs,x1 vs,x2 vs,x3 vs,x4 vs,x5 
x1,y1 x1,y2 x1,y3 x2,y1 x2,y4 x3,y4 x3,y5 x4,y5
x5,y4 x5,y5 y1,vt y2,vt y3,vt y4,vt y5,vt/:x,c;
endsets
data:
c=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1;
enddata
n=@size(dian);
max=@sum(bian(i,j)|i#eq#1:x(i,j));
@for(bian:@bin(x));
@for(bian:x<c);
@for(dian(k)|k#ne#1#and#k#ne#n:@sum(bian(i,k):x(i,k))=@sum(bian(k,j):x(k,j)));