数学建模——最大流问题(配合例子说明)

这篇具有很好参考价值的文章主要介绍了数学建模——最大流问题(配合例子说明)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、最大流有关的概念

例1

1、容量网络的定义

2、符号设置

3、建立模型

3.1 每条边的容量限制

3.2 平衡条件

3.3 网络的总流量

4、网络最大流数学模型

5、计算

二、最小费用流

例2

【符号说明】

 【建立模型】

(1)各条边的流量限制

(2)网络总流量

(3)网络总费用

(4)中间点的流量平衡

【数学模型】

【模型求解】

 三、最大匹配问题

例3

 【问题假设】

【问题分析】

【符号设置】

 【数学模型】

【模型求解】


一、最大流有关的概念

最大流是应用广泛的一类问题,例如交通运输网络中的人流、车流、物流;供水网络中的水流、金融系统中的资金流;通讯系统中的信息流。上世纪50年代Ford,Fulkerson建立的《网络流理论》是网络应用的基础。

例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:
c=4 3 4 2 1 2 4 2 3 2 3;
enddata
max=w;
w=@sum(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(dij>0),记为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:
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 最小费用的流量分布

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)流量网络图,如图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))); 

数学建模——最大流问题(配合例子说明),数学建模文章来源地址https://www.toymoban.com/news/detail-754075.html

到了这里,关于数学建模——最大流问题(配合例子说明)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数学建模】面包店老板使日均收入最大化的诀窍

    1 问题描述 面包店每天烘烤一定数量的面包出售,每个成本3元,以8元的价格卖出,晚间关门前将未卖完的面包无偿处理掉,若已知每天面包需求量的概率分布如下表所示。从长期看,面包店老板为了能得到最高的日均收入,他每天要烘烤多少个面包?这个最高日均收入是多

    2024年02月04日
    浏览(62)
  • 2022 年数学建模竞赛题目A 题波浪能最大输出功率设计(解析及Matlab代码)

    目录 问题一: 问题二: 问题三: 问题四: 随着经济和社会的发展,人类面临能源需求和环境污染的双重挑战,发展可再生能源产业 已成为世界各国的共识。波浪能作为一种重要的海洋可再生能源,分布广泛,储量丰富,具有 可观的应用前景。波浪能装置的能量转换效率是波浪

    2024年02月13日
    浏览(46)
  • 数学建模 优化问题——数学规划

    优化问题 :在一系列客观或主观限制条件下,寻求使所关注的某个或多个指标达到最大(或最小)的决策 结构设计、资源分配、生产计划、运输方案中经常可见 通常的解决手段: 经验积累、主观判断 做试验、比优劣 建立数学模型,求解最优策略 解决优化问题的数学方法: 数

    2024年02月06日
    浏览(47)
  • 2023年数学建模:旅行商问题:数学建模与MATLAB实现

    目录 引言 问题定义 解决策略 MATLAB实现 数学建模案例

    2024年02月11日
    浏览(43)
  • 【数学建模】2018年数学建模国赛C题 问题一代码

    本文从购买力、购买时间偏好两个维度分析会员的消费特征。 以会员消费总金额、消费次数、商品购买数量代表会员购买力; 同时按季节和天对会员消费行为进行消费时间偏好分析。 同时对会员及非会员的消费次数和消费金额进行对比分析。 导入包及数据 数据探索与预处

    2024年02月14日
    浏览(39)
  • 数学建模学习(100):交通运输问题建模

    运输问题是一种特殊类型的线性规划问题,其目标是最小化将产品从多个来源分发到多个目的地的成本。 运输问题处理一类特殊的线性规划问题,其目标是以最低的总成本将在多个工厂(原产地)生产的同质产品运输到多个不同的目的地。问题陈述中给出了始发地可用的总供

    2024年02月07日
    浏览(85)
  • 【数学建模】钻井问题

    已知 12口井的坐标位置如下: x=[0.50,1.41,3.00,3.37,3.40,4.72,4.72,5.43,7.57,8.38,8.98, 9.50]; y=[2.00,3.50,1.50,3.51,5.50,2.00,6.24,4.10,2.01,4.50,3.41,0.80]; 设平面有n个点 P i P_i P i ​ (表旧井井位),其坐标为 ( a i , b i ) , i = 1 , 2 , … , n (a_i,b_i),i=1,2,…,n ( a i ​ , b i ​ ) , i = 1 , 2 , … , n 。新置的井位是一

    2024年04月26日
    浏览(137)
  • 数学建模——规划问题

     运筹学对于线性规划问题直接使用图解法,单纯形法利用求解。在python中可以直接使用scipy.optimize模块的linprog函数求解。   linprog 函数的调用方式: 常用参数解释 : (1)  c:价格向量 (2)  A_ub:不等式约束技术系数矩阵 (3)  b_ub:不等式约束资源向量 (4)  A_eq:等式约束技

    2024年02月13日
    浏览(61)
  • 数学建模优化问题

    一、选修课程策略问题 某学校规定,运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属类别和先修课要求如表1所示。那么,毕业时学生最少可以学习这些课程中哪些课程。 如果某个学生既希望选修课程

    2024年04月26日
    浏览(46)
  • 【数学建模暑期培训】配送中心选址问题

    某省共有92个城市,城市位置、标号,公路交通网数据见附件1。 某企业在该省标号前20位的城市建立了直销中心,各直销中心负责所在城市的销售,销售量见附件1。该企业欲在该省设立一个配送中心负责给直销中心配送产品,配送中心建设成本为30万元。每吨公里运费2元,每

    2024年02月06日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包