当前位置:
文档之家› 运筹学PPT 第五章图与网络分析
运筹学PPT 第五章图与网络分析
C
2
G
4
2 D 2 F
5 2
B
6
J
2013-6-23
[例]今有煤气站A,将给一居民区供应煤气,居民区各 用户所在位置如图所示,铺设各用户点的煤气管道所需 的费用(单位:万元)如图边上的数字所示。要求设计 一个最经济的煤气管道路线,并求所需的总费用。
A 2 E 3.5 I 2 5 2 D 2 F 2 2 H 4 3 3 5 K 1 S
v2
5.5
5 v4
2013-6-23
1. 破圈法: 在图中找圈,并删除其中最大边。如此进行下去,直 至图中不存在圈。 v1
v2
5 4
3
v5
2
v3 3.5 v4
2013-6-23
1. 破圈法: 在图中找圈,并删除其中最大边。如此进行下去,直 至图中不存在圈。 v1
v2
5
3
v5
1 2 1 2 1 2
3 . 链与圈
链:由G中的某些点与边相间构成的序列 e v e e v v ,
1 1 2 2 1
若满足e [v ,v ], 则称此边点序列为G中的一条链。
1
圈:封闭的链。
连通图:图G中任二点间至少存在一 条链。
2013-6-23
4. 有向图与无向图
图G = (V, E), 也可记G = (vk , [v i , v j ]).若点对[v i , v j ]无序, 称G为无向图;否则称G为有向图。 称有向图的边为弧,记(v i , v j ), 在图上用箭线表示。
5. 树
例1 已知有5个城市,要在它们之间架设电 话线网,要求任2城市都可通话(允许通过其它 城市),并且电话线的根数最少。
v1 v2 v3 v4 v5
特点:连通、无圈。 树:无圈的连通图,称为树,记为T。
2013-6-23
v1
v2 v3 v4
v5
树的性质:(1)树的任2点间有且仅有1链;
(2)在树中任去掉1边,则不连通;
(容量约束) 0 f c v ( f ), i s 约束条件: i s , t (平衡条件) f f 0, v ( f ), i t
2013-6-23
3. 基本概念与定理
f 饱和弧: c (1) 弧按流量分为未饱和弧:f c 零流弧:f 0
1 1 1
为D的一个截集,记为(V ,V )。
1 1
截量:截集上的容量和,记为 C(V ,V ) 。 例4 对于下图,若V1={vs,v1},请指出相应的截 集与截量。 v v
2
(4,3)
4
2013-6-23
(5,3) (1,1) (3,0) vs vt (1,1) (2,1) (5,1) v1 v3 (2,2)
如 G:
e5
e7 v4
e5
v4
简单图:无环、无多重边的图。
2013-6-23
2 . 关联与相邻
关联(边与点关系):若e是v ,v 二点间的边,
1 2
记e [v ,v ], 称v (或v )与e关联。
1 2 1 2
相邻(边与边、点与点):点v 与v 有公共边,
1 2
称v 与v 相邻; e 与e 有公共点,称e 与e 相邻。 边
7 v3 5 [4,v2] 1 3 2 5
[8,v5] v6 1 7
5
[13,v6] v7
v4 [3,v1]
v5 [7,v3]
其中3=min{0+3,0+5,2+2,2+7}
最短距为13;
最短路为v1-v2-v3-v5-v6-v7。
2013-6-23
三. 最大流问题
1. 问题 已知网络D=(V,A,C),其中V为顶点 集,A为弧集,C={cij}为容量集, cij 为弧(vi,vj ) 上的容量。现D上要通过一个流f={fij},其中fij 为弧
比较:
无向图:边[v i ,v j ],链 有向图:弧(v i ,v j ),路
,圈 ,回路
2013-6-23
链与路、圈与回路 无向图:
链 点边交错的序列 圈
起点=终点的链
有向图:
路 点弧交错的序列 回路 起点=终点的路
v5
v5 v4 v1
v1
v4
2013-6-23
v2
v3
v2
v3
2013-6-23
用避圈法解例2
v2
2
v1• 3 5 1
v3
2
7 5 3 5 v5
v6 1 7
5
v7
v4
最小部分树如图上红线所示; 最小权和为14。
2013-6-23
二. 最短路问题
1. 问题:求网络D中一定点v1到其它点的最短路。 例3 求如图网络中v1至v7的最短路,图中数字 为两点间距离。
v2 (3,3)
(4,3)
v4
(5,3) (1,1) (3,0) vs vt (1,1) (2,1) (5,1) v1 v3 (2,2)
2013-6-23
(3) 截集与截量
使v V ,v V 。称弧集 v ,v ) V ,v V ( v
1 1 1
截集(割集):将V 分为二非空互补集V 与V ,
C
2
G
B
6
2013-6-23
[例]今有煤气站A,将给一居民区供应煤气,居民区各 用户所在位置如图所示,铺设各用户点的煤气管道所需 的费用(单位:万元)如图边上的数字所示。要求设计 一个最经济的煤气管道路线,并求所需的总费用。
A 2 E I 2 4 3 2 D 2 F 2 2 H 3 J 5 K 1 S
(vi,vj )上的流量。问应如何安排流量fij可使D上
通过的总流量v最大?
v2 4 1 5 2 1 v4
例如:
vs
3
3
5
vt 2
v1
2013-6-23
v3
2. 数学模型
问题:最大流问题的决策变量、目标函数、约束条件各是什么?
决策变量: 各弧(v ,v )上的流量f ,
目标函数: Maxv v ( f )
2
v3 3.5 v4
2013-6-23
[例]今有煤气站A,将给一居民区供应煤气,居民区各 用户所在位置如图所示,铺设各用户点的煤气管道所需 的费用(单位:万元)如图边上的数字所示。要求设计 一个最经济的煤气管道路线,并求所需的总费用。
A 2 E 3.5 I 2 4 3 2 H 3 5 K 1 S
C 5
2
A 4 D
2013-6-23
B 2
7
5
G
5
C 1 4 3
4
E 7 1 F
图1 光缆铺设费用图
案例分析:默登公司的联网问题
2 A
B
2
C 1 D 3 E 1 F
5
G
图 1 光缆铺设最小费用图
2013-6-23
应用例
已知有A、B、C、D、E、F六个城镇间的道路网络 如图,现要在六个城镇间架设通讯网络(均沿道路架 设),每段道路上的架设费用如图。求能保证各城镇均
2 D
2
G
4
2 F
5 2
B
6
J
2013-6-23
[例]今有煤气站A,将给一居民区供应煤气,居民区各 用户所在位置如图所示,铺设各用户点的煤气管道所需 的费用(单位:万元)如图边上的数字所示。要求设计 一个最经济的煤气管道路线,并求所需的总费用。
A 2 E 3.5 I 2 4 3 2 H 3 5 K 1 S
例 1 求如图网络的最小部分树。
v2 2 v1 3 5 1 v4 5 v3 2 7 5 3 v5 v6 1 7 5 v7
2013-6-23
1. 破圈法: 在图中找圈,并删除其中最大边。如此进行下去,直 至图中不存在圈。 v1
v2
5.5
5 7.5 4
3
v5
2
v3 3.5 v4
2013-6-23
1. 破圈法: 在图中找圈,并删除其中最大边。如此进行下去,直 至图中不存在圈。 v1
B
J
此即为最经济的煤气管道路线,所需的总费用为25万元
2013-6-23
案例分析:默登公司的联网问题
默登(Modern)公司的管理层决定铺设最先进 的光纤网络,为它的主要中心之间提供高速通信。图 1中的节点显示了该公司主要中心的分布图。虚线是 铺设光缆可能的位置。每条虚线旁边的数字表示成本 (单位:百万美元)。 问:需要铺设哪些光缆使得总成本最低?
如:在前面例举的网络流问题中,若已给定一个可行流 (如括号中后一个数字所示),请指出相应的弧的类型。
v2 (4,3) v4
(5,3) (1,1) (3,0) vs vt (1,1) (2,1) (5,1) v1 v3 (2,2)
2013-6-23
(3,3)
(2)可增值链(增广链)
:中的正向弧集 D中由v 至v 的链,记 , :中的反向弧集 中弧皆未饱 若 ,则称为D中关于可行流f 的 中弧皆非零 一条可增值链。
C
2
G
B
2013-6-23
[例]今有煤气站A,将给一居民区供应煤气,居民区各 用户所在位置如图所示,铺设各用户点的煤气管道所需 的费用(单位:万元)如图边上的数字所示。要求设计 一个最经济的煤气管道路线,并求所需的总费用。
A 2 E I 2 4 3 2 D 2 F 2 2 H 3 K 1 S
C
2
G
第五章 图与网络分析
第一节 图的基本概念 第二节 网络分析
2013-6-23
第一节