§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题

Slides:



Advertisements
Similar presentations
软饮料概述 人文艺术系 石惠舟. 什么是饮料? 饮料概述 饮料是指以水为基本原料,由 不同的配方和制造工艺生产出 来,供人们直接饮用的液体食 品。 饮料 饮料除提供水分外,由于在不 同品种的饮料中含有不等量的 糖、酸、乳以及各种氨基酸、 维生素、无机盐等营养成分, 因此有一定的营养。
Advertisements

2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
课件说明 课题 : 国歌 课型 : 综合 课时 : 一课时 突破口 : 通过不同国家国旗的竞猜游戏, 导入我 国的国旗国歌, 并以器乐和声乐两种不同形式 的作品达到体会歌曲内涵的目的, 从而更好地 演唱歌曲.
第五单元 酒水知识与酒吧服务 主题三 蒸 馏 酒 —— 中国蒸馏酒. 蒸馏酒是把经过发酵的酿酒原料,经过一次或多次的蒸馏过 程提取的高酒度酒液。
Chapter6 图与网络分析 ( Graph Theory and Network Analysis )
EVOLVE…… 进化 包装设计.
管理运筹学 -管理科学方法 谢家平 博士 教授 博士生导师 研究领域:管理科学、运营管理、供应链管理
食品安全小常识 目 录 下一页 封 底.
鬼太郎 身為幽靈族後裔一員的鬼太郎,他出生的時候,父母便雙亡,不過他的爸爸化身為眼珠,陪伴著他。而鬼太郎與他的同伴貓女、臭鼠人等,為了維持妖怪與人類間的和平,他們將一一消滅邪惡的妖怪,守護這世界的和平。
关于市场营销的分析 ——以九阳豆浆机为例 品牌经营——让每一个家庭都拥有一台九阳豆浆机 营销管理——采取文化、概念、网络等营销组合
政府採購法規概要 報告人:杜國正 行政院公共工程委員會企劃處.
國中基本能力測驗 (基測) 報告人:魏麗琴老師.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
一、能线性化的多元非线性回归 二、多元多项式回归(线性化)
之 魔 析 妖 鬼 解 怪 大 沈家仪小组出品.
励步英语授权流程.
第四章 运筹学模型 本章重点: 线性规划基础模型、目标规划模型、运输模型 及其应用、图论模型、最小树问题、最短路问题.
数学建模方法及其应用 韩中庚 编著.
正确保养皮肤的原则 皮肤的保养要依肤质进行 皮肤保养要分区进行 根据季节变化适时调整保养计划 依据年龄进行皮肤保养 肌肤保养还要分时进行
如何用合適的書報和新人一起追求 初信餵養-365 屬靈問答-500.
授课教师简历 刘付才,男,中学高级教师,亳州一中南校体 育教研组长,全国体育优质课一等奖获得者,华佗 五禽戏第五十八代传承人;长期从事五禽戏教学和 研究工作,参与创编了国家级课题“校园五禽戏”; 2014年全国学生运动会展示中获得优秀表演奖; 2015年指导的五禽戏传人进行的五禽戏教学获得全 国一等奖,编著的《华佗五禽戏之简易健身操》即.
洪涝灾害重点传染病的预防 江苏省疾病预防控制中心 汪华.
数据结构与算法(B) 期中后MOOC课程小测
Statistical Thermodynamics and Chemical Kinetics
第七章 固定资产 第一节 固定资产概述 第二节 固定资产的确认和初始计量 第三节 固定资产的后续计量 第四节 固定资产清查与期末计价
第九章 长期资产及摊销 2017/3/21.
小 桔 灯 市场赢利能力与战略 主讲:杨贤耀.
第17章 实现路由器.
第7讲:网络模型 上次图论课我们重点关注的是图中顶点之间静态的关系,如距离,连接关系 这节课我们来关注对边的限制和边与顶点之间的关系.
第七章 证券投资.
《7.1 力》说课稿 丰城中学 杨青青.
講師:聯捷聯合會計師事務所 張志勝會計師(所長)
崇拜即將開始,請大家安靜片刻, 預備心靈敬拜上帝。
恩典更新 羅15:1-13.
践行新时期广东精神 推进广东公路文化繁荣与发展 ——关于广东省公路文化建设与实践的思考
商 业 空 间.
物流运输管理.
1.图的基本概念 2.树 3.最短路 4.最大流问题 5.最小费用最大流 6.中国邮递员问题
成员名单 陈丽 陈敏 杨娇 高丽莉 李亚金 吴沅娟 任津沙 张舒蓉.
实验3.2 电场描绘 实验简介 实验目的 实验原理 实验仪器 实验内容 注意事项 数据处理.
第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法.
Hub Web System 主要功能: 1.查询库存(Query Current Storage) 2.创建PL(Create PL) 3.查询、打印PL单(Query & Print PL) 4.查询允交量、在途量 5.修改用户的基本信息(Update Password) 6.查询GR(Query.
第4章 非线性规划 一维搜索方法 2011年11月.
数学模型实验课(三) 插值与三维图形.
六、图与网络分析 第11章 图与网络优化 第12章 网络计划.
第二章 静电场(3) §2.3 电像法 教师姓名: 宗福建 单位: 山东大学物理学院 2016年10月18日
运筹学 图与网络分析 1.
網路遊戲版 幸福農場168號.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
知识点回顾 拓扑排序 关键路径 应用领域、求解步骤、算法实现过程 应用领域 求解步骤
北师大版三年级数学下册 电 影 院.
§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题
第二章 静电场(2) §2.2 唯一性定理 教师姓名: 宗福建 单位: 山东大学物理学院 2015年10月16日
3.3 垂径定理 第2课时 垂径定理的逆定理.
单元17 钢 结 构 学习目标 (1)了解钢结构的特点。 (2)了解钢结构的发展现状。 (3)掌握钢结构的链接方式。
第4章 Excel电子表格制作软件 4.4 函数(一).
參考資料來源:上網逛逛圖書館台北市立圖書館
树和图 tree and graph 蔡亚星.
网络模型 Network Modeling Operations Research 运 筹 学
1.非线性规划模型 2.非线性规划的Matlab形式
第七、八次实验要求.
Models and Software Practice of the Operations Research
本章要点 了解图论的基本思想 掌握相关的基本概念 学会最短路、最大流、最小费用 最大流的解法 学会用图的工具表达思想和研究问题
实验一 原子发射光谱定性半定量分析 一、概述 二、仪器装置 三、实验步骤.
汽车电器与控制设备 第0章 绪论.
圖形結構 Graph Structure chapter 9 德明科技大學資訊科技系.
第四部分 图论 主要内容 图的基本概念:图、通路和回路、图的连通性、图的矩阵表示 图的可行遍性:欧拉图、哈密顿图、带权图及其应用
最小生成树 最优二叉树.
第三章 图形的平移与旋转.
第六章 波 6-1 波速、頻率與波長 6-2 波的特性 6-3 都卜勒效應 6-4 光 6-5 電磁波
Presentation transcript:

§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题 第7章 图与网络模型 §1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题

§4 最大流问题 最大流问题: 给了一个带收发点的网络,其每条弧的赋权称之为容量,在不超过每条弧的容量的前提下,求出从发点到收点的最大流量。

4.1 最大流的数学模型 例:某石油公司拥有一个管道网络,使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化,他的各段管道(vi,vj)的流量cij也不一样,如下图所示。cij的单位为万加仑/小时。如果使用这个网络系统从开采地v1向销地v7运送石油,问每小时能运送多少加仑石油? v2 3 v5 5 2 2 6 2 v6 4 v3 v7 v1 6 3 1 2 v4

设弧(vi,vj)上的流量为fij,网络上的总的流量为F,则上述问题的线性规划模型为: 目标函数:max F=f12+f14 约束条件:f12=f23+f25 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14 fijcij,(i=1,2,...,6;j=2,...,7) fij0,(i=1,2,...,6;j=2,...,7)

4.2 最大流问题网络图论的解法 对一条弧(vi,vj)的容量用一对数(cij,0)标在弧(vi,vj)上,cij表示从vi到vj容许通过的容量,0表示从vj到vi容许通过的容量。 cij cij vi vj vi vj cij cij cji vi vj vj vi cji

注意: 求最大流的基本算法 找出一条从发点到收点的路,在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路,则已求得最大流。 找出这条路上各条弧的最小的顺流的容量pf,通过这条路增加网络的流量pf。 在这条路上,减少每一条弧的顺流容量pf,同时增加这些弧的逆流容量pf,返回步骤①。 注意: 在步骤①中尽量选择包含弧数最少的路。

引例的Ford-Fulkerson标号算法:(贝尔曼-福特算法 ) 第一次迭代: 选择路为:v1v4 v7.弧(v4,v7)的顺流容量为2,决定了pf=2,改进的网络流量如图所示: v2 v5 3 5 2 2 6 2 v6 4 v3 v7 v1 2 6 2 4 3 1 2 2 v4

选择路为:v1v2 v5 v7.弧(v2,v5)的顺流容量为c25=3,决定了pf=3,改进的网络流量如图所示: 第二次迭代: 选择路为:v1v2 v5 v7.弧(v2,v5)的顺流容量为c25=3,决定了pf=3,改进的网络流量如图所示: 3 v2 v5 2 3 3 5 2 3 3 2 6 2 v6 4 v3 v7 v1 2 2 5 4 3 1 2 v4

选择路为:v1v4 v6 v7.弧(v4,v6)的顺流容量为c46=1,决定了pf=1,改进的网络流量如图所示: 第三次迭代: 选择路为:v1v4 v6 v7.弧(v4,v6)的顺流容量为c46=1,决定了pf=1,改进的网络流量如图所示: v2 v5 3 2 3 2 2 3 3 2 v6 3 4 v3 1 v7 1 v1 5 2 6 4 3 3 1 2 3 v4

选择路为:v1v4 v3 v6 v7.弧(v3,v6)的顺流容量为c36=2,决定了pf=2,改进的网络流量如图所示: 第四次迭代: 选择路为:v1v4 v3 v6 v7.弧(v3,v6)的顺流容量为c36=2,决定了pf=2,改进的网络流量如图所示: v2 v5 3 2 3 2 2 2 1 3 2 v6 3 4 v3 3 v7 2 v1 6 1 2 8 3 1 1 3 3 5 v4

选择路为:v1v2 v3 v5 v7.弧(v2,v3)的顺流容量为c23=2,决定了pf=2,改进的网络流量如图所示: 第五次迭代: 选择路为:v1v2 v3 v5 v7.弧(v2,v3)的顺流容量为c23=2,决定了pf=2,改进的网络流量如图所示: v2 v5 3 5 2 2 3 2 1 2 5 3 2 v6 3 2 1 v3 3 v7 v1 2 8 1 2 10 1 1 5 v4

最大流如图所示: v2 v5 3 2 2 5 5 v6 2 3 v3 v7 v1 10 1 2 2 5 v4