专做机票网站的软件公司,律所网站建设管理制度,网络营销的概念和特征,中国建设银行官网站电话目录 一、最大流有关的概念
例1
1、容量网络的定义
2、符号设置
3、建立模型
3.1 每条边的容量限制
3.2 平衡条件
3.3 网络的总流量
4、网络最大流数学模型
5、计算
二、最小费用流
例2
【符号说明】 【建立模型】
#xff08;1#xff09;各条边的流量限制
1各条边的流量限制
2网络总流量
3网络总费用
4中间点的流量平衡
【数学模型】
【模型求解】 三、最大匹配问题
例3 【问题假设】
【问题分析】
【符号设置】 【数学模型】
【模型求解】 一、最大流有关的概念
最大流是应用广泛的一类问题例如交通运输网络中的人流、车流、物流供水网络中的水流、金融系统中的资金流通讯系统中的信息流。上世纪50年代FordFulkerson建立的《网络流理论》是网络应用的基础。
例1
如图1所示网络为输油管道网络vs为起点vt为终点v1,v2,v3,v4为中转站边上的数字表示该管道的最大输油能力t/h。问如何安排各管道的输油量才能使得从vs到vt的输油量最大。
1、容量网络的定义 设有连通图G(V,E)G的每一条边(vi,vj)上有非负数cij称为容量仅有一个入次为0的点vs称为发点源一个出次为0的点vt称为收点汇其余点位中间点这样的网络G称为容量网络记为G(V,E,C)。如图1所示。
2、符号设置 Cij 边(i,j)的容量限制fij 边(i,j)的实际流量称f{fij}为网络的一个流。W 网络的总流量 3、建立模型
3.1 每条边的容量限制 3.2 平衡条件
对中间点u流入流出即
3.3 网络的总流量
称发点流量之和或汇点流量之和为网络总流量忽略损失。
4、网络最大流数学模型 5、计算 编写例1的Lingo计算程序将计算结果填入表1将数据反映如图1得到图2.
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,f;
endsets
data:
c4 3 4 2 1 2 4 2 3 2 3;
enddata
maxw;
wsum(bian(i,j)|j#eq#6:f(i,j));
for(bian(i,j):f(i,j)c(i,j));
for(dian(k)|k#ne#1#and#k#ne#6:sum(bian(i,k):f(i,k))sum(bian(k,j):f(k,j)));
表1 流量分布不唯一 fij V1 V2 V3 v4 vt Vs 3 4 V1 2 1 V2 2 V3 1 2 v4 2 3 如图2所示称形如(vs,v4),(v4,vt),(v4,v3),(v1,v2),(v1,v3)为饱和边;其余的边都是非饱和边。 要增大网络的流量必须对饱和边扩容 二、最小费用流
设G(V,E,C)为流量网络边(i,j)除了容量限制cij外还有因为流量而产生的单位费用dij(dij0)记为G(V,E,C,d)。这时如果不管流量大小而只把网络流产生的费用当产目标最优解必定是0即各条边的实际流量为0时费用最小。研究方法必须改变为保持流量一定的情况下使得流量产生的总费用最小。当网络流量保持最大而流量费用最小的网络流称为最小费用最大流。
例2
如图3所示网络G(V,E,c,d)每条边有两个数字第一个是容量限制第二个是流量产生的单位费用。求该网络的最小费用最大流最大流例1求得为7。 【符号说明】 G(V,E,c,d] 如图3所示网络图Cij 边(i,j)的管道容量限制Dij 边(i,j)的单位费用Xij 边(i,j)的实际流量W 网络G的总流量。 【建立模型】
1各条边的流量限制 2网络总流量 3网络总费用 4中间点的流量平衡 【数学模型】 【模型求解】
编写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:
c4 3 4 2 1 2 4 2 3 2 3;
d3 3 2 4 2 1 3 3 3 2 4;
enddata
minsum(bian:d*x);
wsum(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)));
w7;表2 最小费用的流量分布 fij V1 V2 V3 v4 vt Vs 2 2 3 V1 2 V2 2 V3 2 v4 3 三、最大匹配问题
问题来源 有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)流量网络图如图6vs 发点vt 汇点x1,…,x5,y1,…,y5网络中间点Cij 边(i,j)的容量限制且cij1,(i,j)∈Exij 边(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:
c1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1;
enddata
nsize(dian);
maxsum(bian(i,j)|i#eq#1:x(i,j));
for(bian:bin(x));
for(bian:xc);
for(dian(k)|k#ne#1#and#k#ne#n:sum(bian(i,k):x(i,k))sum(bian(k,j):x(k,j)));
