当前位置: 首页 > news >正文

网络优化问题

 

一、基本概念

【发点和收点】设点 v 是有向图 D (带箭头)的一个顶点:

1、发点:如果不存在以v为终点的弧,则称v是D的一个发点(源),通常称为vs;

2、收点:如果不存在以v为始点的弧,则称v是D的一个收点(汇),通常称为vt。

【容量和流量】

1、容量:网络中某条弧(vi,vj)的最大通过能力称为该弧的容量,记做 cij ;

2、流量:通过弧 (vi,vj)的某种流的实际数量称为该弧的流量,记做 fij 。

【可行流和最大流】

发点 vs流出的流量为 f ,则汇入收点vt的流量为 -f。这个f,就是可行流。如果一个网络图中,有n个发点,n个收点,那么可行流就是所有发点发出流量的和,也就是所有收点收到流量的和。
 
可行流具备以下两个特征:
1、可行性条件:对每一条弧 (vi , vj )∈ A ,均应有,0 ≤ fij ≤  cij。即每条弧的流量,都应该是非负的,是大于等于0,且小于这条弧的容量的;
2、平衡条件:除了发点和收点,其余点都是中间点,可以理解为中转站。流入任何一个中间点的流量必等于流出该顶点的流量,即对 vi ≠ vs , vt时:
 image
 
 
因此对于可行流 f 来说,对发点,它的公式就是如下形式。对于收点就是 -f :

image

 

 示例:下面的网络图,每个弧,弧旁第一个数字为容量,第二个数字为流量,即 cij, fij。每条弧都满足非负性和中间点的平衡条件,因而为一可行流,且可行流 f = 6(发流量为2+4)。这里有一个特殊的情况,即,可能存在某条弧完全没有启动,或者整个网络为初始状态,这时候就会有零流 fij= 0,它一定是一个可行流。因而在一个网络图中,可行流总是存在的,至少有零流。

image

 

 【网络的最大流】

在一张网络中,每条弧容量不同,走每条弧的成本不同,因此,不同的规划,得到的可行流的流量,并不相同。找到最大的可行流,也就是找到网络的最大流,是很多实际问题需要的。这也是一个线性规划问题,可描述为:

image

 

 

 

 

 

 

 

http://www.hskmm.com/?act=detail&tid=28168

相关文章:

  • Java环境安装备忘录
  • 深入解析:【Spring MVC终极指南】一文掌握请求处理与响应!从Servlet原生方式到SpringMVC高效优雅写法
  • foobar2000 v2.25.2 汉化版
  • 比特币地址投毒攻击深度剖析
  • 为什么大家都爱用微擎?这几点真的太香了
  • 【JS逆向百例】某坤行 1101,雪球 1038,新 acw_sc__v2 逆向分析
  • JAVA 的模板方法模式解析
  • 《构建之法-现代软件工程》 -阅读和提问作业1
  • 计算机视觉与AI在人体成分分析中的技术突破
  • 2024-网鼎杯web-PyBlockly
  • 关于微信小程序申请地理位置接口申请
  • c++学习总结
  • 2025 年大闸蟹蟹卡 / 大闸蟹礼盒 / 大闸蟹礼券 / 好蟹汇大闸蟹选择指南:生态养殖与全国服务双保障解析
  • 分享一个超级耐玩的游戏 转载 植物大战僵尸融合版最新版(v3.0.1)支持安卓版+PC电脑版
  • 【Go 语言神器】iota 到底是什么?为什么高手都爱用它?
  • 2025 年模具生产厂家最新推荐榜单:聚焦优质源头企业,助力工程采购精准选型框格梁模具/框格梁模板/混泥土模具厂家推荐
  • 2025 年最新推荐仿石漆厂家实力厂家口碑排行榜:精选优质环保外墙内墙涂料企业权威揭晓
  • oracle查询存储过程和函数中是否包含某个字符串
  • Qoder 负责人揭秘:Qoder 产品背后的思考与未来发展
  • 2025 年半导体晶片生产厂家最新推荐榜单:专利技术与规模化供货能力双维度深度解析
  • 2025 年水产养殖降氨氮亚盐厂家最新推荐排行榜 ,助力北方对虾鱼塘螃蟹池塘养殖户轻松选购优质产品
  • CS:APP学习笔记之程序的机器级表示(三) - Invinc
  • EHOME视频平台EasyCVR构建全协议、全场景融合的视频监控中枢
  • GA/T 1400视图库平台EasyCVR平台GB28181与1400级联方式全解析
  • 2025 年玻璃钢水箱生产厂家最新推荐榜单:含 30 吨 / 订做 / 消防 / 方形 / 拼装式 / 屋顶 / 大型产品,从产能与服务双维度精选优质企业
  • linux 修改本地时区
  • crontab 定时执行python脚本失败,但手动执行却成功问题处理 - hello-*
  • 2025 年不锈钢水箱厂家最新推荐榜:优质厂家实力对比与选购指南,助您选到适配设备矩形/屋顶/定做方形不锈钢水箱厂家推荐
  • 实用指南:Java 后端面试技术文档(参考)
  • 2025 年钢结构厂家最新推荐榜:优质企业全面解析,助力客户精准选择可靠合作伙伴