当前位置：文档之家 › 运筹学PPT 第五章图与网络分析

运筹学PPT 第五章图与网络分析

  • 格式：ppt
  • 大小：673.50 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

运筹学胡运权第五版课件

运筹学胡运权第五版课件

V5 12 7
5
4
3
2
0
1 3
1
0 4
3
4 0
v7 ∞ 10 10 8
⑶ 构造任意两点间最多可经过3个中间点到达 的最短距离矩阵 D（2）= dij（2） 其中 dij（2）= min { dir（1）+ drj（1）}
r
i
dir
（1）
r
drj（1）
j
v1 v2 v3 v4 v5 v6 v7
• • •
悬挂边 孤立点 偶点 奇点
悬挂点的关联边，如 e8 次为0的点 次为偶数的点，如 v2 次为奇数的点, 如 v5
5、链：图中保持关联关系的点和边的交替序列，其 中点可重复，但边不能重复。 路：点不能重复的链。 圈：起点和终点重合的链。 回路：起点和终点重合的路。 连通图：任意两点之间至少存在一条链的图。 完全图：任意两点之间都有边相连的简单图。 n(n 1) 2 n阶完全图用Kn表示，边数= C n
狄克斯屈拉算法
既可以求两点之间的最短 距离，又可以确定最短路
求某两点之间的最短距离
（0）= V2 D
5
2
∞ ∞ ∞ ∞
5
0
∞ 2
7 0 2 7
7
6
∞ ∞
∞ ∞ 2
V3 2
∞ 0
∞ 4
V4 ∞ 2
V5 ∞ 7
∞ 6
0
1
1
0 6
3
6 0
V6 ∞ ∞ 4
v7 ∞ ∞ ∞ ∞ 3
注意：D(0)是一个对称矩阵，且对角线上的元素全是0.
⑵ 构造任意两点间直接到达、或者最多经过1 个中间点到达的最短距离矩阵D（1）= dij（1） 其中

运筹学 图与网络分析PPT学习教案

运筹学 图与网络分析PPT学习教案

ij
min{ V1到Vj中间最多经过t-2个点 P1j（t-1）=
P1j（t-2）
+wij}
终止原则：
1）当P1j（k）= P1j（k+1）可停止，最短路P1j*= P1j（k） 2）当P1j（t-1）= P1j（t-2）时，第1再9页多/共迭59页代一次P1j（t） ，若P1j（t） =
P1j（t-1） ，则原问题无解，存在负回路。
图与网络模型Graph Theory
最短路问题
v1，u1 =（M，W，G，H）； v2，u2 =（M，W，G）；
v3，u3 =（M，W，H）；
v4，u4 =（M，G，H）；
v5，u5 =（M，G）。
此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
v1
v2
v3
v4
v5
u5
u4
例： 求下图所示有向图中从v1到各点 的最短路。
2 v1
v2
4
5 -2 v3 6
-3 4
v4
7
v6 -3 2
v5
3
4
v8
-1
v7
第20页/共59页
wij
d(t)(v1,vj)
v1 v2 v3 v4 v5 v6 v7 v8 t=1 t=2 t=3 t=4 t=5 t=6
v1 0 2 5 -3
0 0 0 00 0
参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加
此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此
问题。很快，各办事处将其已订购机票的情况传到了总社。根据此
资料，总社要作出计划，最多能将多少游客从成都送往北京以及如
何取道转机。下面是各办事处已订购机票的详细情况表：

【经营管理】企业运筹学--图与网络理论讲义(ppt 81页)

【经营管理】企业运筹学--图与网络理论讲义(ppt 81页)
e3 [1,4] e5 [1,3] e7 [3,4] e9 [4,5]
e2 [1,2] e4 [1,3]
e6 [2,4]
e8 [4,4]
v1
e1 e2 e3 e4 e5
v2
v3
e6
e7 e9 v5
v4
e8
v6
图的概念 点与边
顶点数 集合V中元素的 个数，记作p(G)。
边数 集合E中元素的 个数，记作q(G)。
子图的定义 设，
G1=(V1,E1), G2=(V2,E2)， v2
如果V1V2 ，又E1E2 ，
v1
v3
则称G1是G2的子图。
e1 e2 e3 e4 e5
必须指出，并不是从图
G2中任选一些顶点和边 v2
在一起就组成G2的子图 G1，而只有在G2中的一 条边以及连接该边的两 个端点均选入G1时，G1 才是G2的子图。
• 在画图时，顶点的位置、边和长短形状都是无 关紧要的，只要两个图的顶点及边是对应相同 的，则两个图相同。
图的概念 图的表示
( 1 ,2 ,3 ,4 ,5 ,6 ) E , ( e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 , e 8 , e 9 )
e1 [1,2]
若点u和v与同一条边
相关联，则u和v为 相邻点；若两条边
v1
例e则如i和称在e图ej有i与5同－ej一为1中个相v端邻1和点边，。v2e1
e2 e3 e4
e5 v3
v2为相邻点， v1和 v5不相邻；e1与e5为
e6
e7 e9 v5
相邻边，e1和e7不相
简单图
若一条边的两个端点是同
v6
图的概念 连通的意义

管理运筹学 图与网络分析PPT教案

管理运筹学 图与网络分析PPT教案

v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
第27页/共83页
支撑树的权：如果T=(V,E)是G的一个支撑树，则称E中所 有边的权之和为支撑树T的权，记为w(T)。即
w(T )
wij
[vi ,v j ]T
v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
上例中支撑树的权为 3+7+5+2+2+3+4=26
第34页/共83页
v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
第35页/共83页
课堂练习：1.分别用三种方法求下图的最小支撑树
v2
7
v5
5
2
3
4
v1
4
5
v4 3
1
1
v7
7
4
v3
v6
第36页/共83页
2. 某农场的水稻田用堤埂分割成很多小块。为了 用水灌溉，需要挖开一些堤埂。问最少挖开多少条 堤埂，才能使水浇灌到每小块稻田？
水源
第37页/共83页
作业 P221： 第3题
第38页/共83页
§3 最短路问题
1. 问题的提出 2. 最短路问题的Dijkstra算法 3. 求任意两点之间最短距离的矩阵算法

运筹学图与网络分析-最短路

运筹学图与网络分析-最短路

(P0
)
min P
(P)
路P0的权称为从vs到vt的距离，记为d(vs,vt)。
求网络上的一点到其它点 的最短路
Dinkstra标号法
这是解决网络中某一点到其它点的最 短路问题时目前认为的最好方法。
适用于有向图权值非负的情况
有向图权值非负---- Dijkstra算法
Dijkstra算法的基本步骤（权值非负） 1、给顶点v1标号（0），v1称为已标号点，记标号点集为
(1,2)
2
2
0
1
2
5
7
(2,4)
3 5 55
7
3
1 (4,4) 3 1
4
6
7
(1,3)
5
④重复上述步骤，直至全部的
点都标完。
(1,2)
2
2
0
1
2
5
7
(2,4)
3 5 55
7
1
3
3
1
4
6
7
(1,3)
5
7
(1,2)
2
2
0
2
7
1
5
(2,4)
35
55
7
1
3
3
1
4
6
7
(1,3)
5
(3,7)
(1,2)
2
2
0
2
7
1
5 3 5 55 7
3
1
3 1
34 5 6
7
④重复上述步骤，直至全部的
(1,2)
点都标完。
2
2
0
2
7
1
5 3 5 55 7

运筹学第五章 图与网络分析

运筹学第五章 图与网络分析

v6
v7
v8
考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)
计算 min{0+2, 0+3, 1+10, 1+2}=min {2,3,11,3} =2
v2:[2,v1]
（4）A={v1,v2,v4}
[0,v1] [2,v1] 2 1 10 [1,v1] v4 5 v6 [3,v1] 4 2 v7
最短．
最小支撑树的求法
1 破圈法 2 避圈法
5.2.1 求解最小支撑树问题的破圈法
方法：去边破圈的过程。 步骤：1）在给定的赋权的连通图上任找 一 个圈。 2）在所找的圈中去掉一条权数最 大的边。 3）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑
树，否则返回 1）。
例１：用破圈法求右图
v1 1 5 4 v2 2 v4 3 v6
权和＝１５
5.3 最短路问题
问题：求网络中一定点到其它点的最短路。
5.3.1 最短路问题的Dijstra解法 方法：给vi点标号[αi,vk] 其中：αi：vi点到起点vs的最短距离 vk: vi的前接点
方法：(1) 给起点vs标号[0，vs]。 （2）把顶点集v分为互补的两部分A和Ā 其中：A：已标号点集 Ā：未标号点集 （3）考虑所有这样的边[vi, vj], 其中vi ∈A,vj ∈ Ā 挑选其中与vs距离最短的点vj标号 [min{αi+cij},vi]
[3，V1]
考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)
计算 min { 2+6, 2+5, 1+2, 3+4}=min {8,7,3,7}=3
v7:[3,v4]

第5章图与网络分析163页PPT


bi j 0wi j
(vi ,vj)E (vi ,vj)E
例6.4 下图所表示的图可以构造权矩阵B如下:
v1 4
v2
36
72
v6 4
3
3
v3
5
2
v5
v4
v1 0 4 0 6 4 3
v
2

4
0
2
7
0
0

B

v3
0
2
0
5
0
3
v4 6 7 5 0 2 0
v
5
4
17
v4
树与图的最小树
v1 23 v6
20
v2
1
4
v7
9
15 v3
28 25
16 3
v5
17
v4
v1
v2
23 v6
1
4
v7
9
15 v3
28
25
16 3
v5
17
v4
v1
v2
23 v6
1
4
v7 9
15 v3
28
25
16 3
v5
17
v4
v1
v2
23
1
4
v7
v6
9
v3
28
25
16 3
v5
17
v4
v1
②
15
9
7 ④ 14
⑤
①
10
19
20
6 ⑥
③
25
图的矩阵描述： 邻接矩阵、关联矩阵、权矩阵等。
1. 邻接矩阵 对于图G=（V，E），| V |=n， | E |=m，有nn阶方矩阵

运筹学图论 ppt课件

• “不怕太阳晒，也不怕那风雨狂，只怕先生骂我 笨，没有学问无颜见爹娘 ……”
• “太阳当空照，花儿对我笑，小鸟说早早早……”
什么是图？
图论中所谓的图是由一些点(vertices)，和一 些连接兩点的边(edges)所形成的
5.1 图的基本概念与基本定理
图论是应用非常广泛的运筹学分支，它已经广 泛地应用于物理学控制论、信息论、工程技术、交 通运输、经济管理、电子计算机等各项领域。对于 科学研究、市场和社会生活中的许多问题，可以同 图论的理论和方法来加以解决。例如：各种通信线 路的架设，输油管道的铺设，铁路或者公路交通网 络的合理布局等问题，都可以应用图论的方法，简 便、快捷地加以解决问题。
矩阵A的元素全为0的行所对应的点称为汇 点 上图v8
图，记作D=(V, A)，其中V表示有向图D的点集合，A表 示有向图D的弧集合。一条方向从vi 指向vj 的弧，记作(vi , vj)。
图5.4是一个无向图G=（V，E），
其中V={v1 , v2 , v3 , v4}
v1
v2
E={[v1 , v2],[v2 ,v1],[v2 ,v3],
[v3 ,v4],[v1 ,v4],
郑州
济南 徐州
青岛 连云港
重庆
武汉 南京
上海
图5.3
例5.2 有六支球队进行足球比赛，我们分别用
点v1 ，…，v6表示这六支球队，它们之间的比赛情 况，也可以用图反映出来，已知v1队战胜v2 队，v2 队战胜v3 队，v3 队战胜v5队，如此等等。这个胜负
情况，可以用图5.3所示的有向图反映出来
v2 v
(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)

运筹学图与网络分析.pptx

{a12,a14,a34}
{a26,a46 } φ
min{ li Wij | Vj J } lh Whk
iI
min{l1+W12, l1+W13, l1+W14}= min{0+3,0+2,0+5}=2= l1+W13 min{l1+W12, l1+W13, l3+W34}= min{0+3,0+5,2+1}=3= l1+W12, l3+W34 min{l2+W26, l4+W46}= min{3+7,3+5}=8= l4+W46
{ a57,a68 }
min{ li Wij | Vj J } lh Whk
iI
min{l1+W12, l1+W13, l1+W14}= min{0+2,0+6,0+3}=2= l1+W12 min{l1+W13, l1+W14, l2+W23, l2+W26}= min{0+6,0+3,2+3, 2+7}=3= l1+W14 min{l1+W13,l2+W23, l2+W26, l4+W45}= min{0+6,2+3,2+7,3+6}=5= l2+W23 min{l2+W26, l3+W35, l3+W36, l4+W45}= min{2+7,5+3,5+7,3+6}=8= l3+W35 min{l2+W26, l3+W36, l5+W56, l5+W57}= min{2+7,5+7,8+1,8+6}=9= l2+W26, l5+W56 min{ l5+W57, l6+W68}= min{8+6,9+4}=13= l6+W68

《运筹学》全套课件(完整版)

负指数分布、几何分布、爱尔朗分布等。
服务时间分布
负指数分布、确定型分布、一般分布等。
顾客到达和服务时间的独立性
假设顾客到达和服务时间是相互独立的。
单服务台排队系统
M/M/1排队系统
顾客到达服从泊松分布，服务时间服从负指 数分布，单服务台。
M/D/1排队系统
顾客到达服从泊松分布，服务时间服从确定 型分布，单服务台。
投资组合优化
确定投资组合中各种资产的最 优配置比例，以最大化收益或
最小化风险。
03
整数规划
整数规划问题的数学模型
01
整数规划问题的定 义
整数规划是数学规划的一个分支 ，研究决策变量取整数值的规划 问题。
02
整数规划问题的数 学模型
包括目标函数、约束条件和决策 变量，其中决策变量要求取整数 值。
03
Edmonds-Karp算法
介绍Edmonds-Karp算法的原理、步骤和实现方法，以及其与FordFulkerson算法的比较。
网络最大流问题的应用
列举网络最大流问题在资源分配、任务调度等领域的应用案例。
最小费用流问题
最小费用流问题的基本概 念
介绍最小费用流问题的定义、 分类和应用背景。
Bellman-Ford算法
优点是可以求解较大规模的整数规划问题，缺点是计算量较大，需 要较高的计算精度。
割平面法
割平面法的基本思想
通过添加新的约束条件（割平面）来缩小可行域的范围，从而逼 近最优解。
割平面法的步骤
包括构造割平面、求解子问题和更新割平面三个步骤，通过不断 迭代找到最优解。
割平面法的优缺点
优点是可以处理较复杂的整数规划问题，缺点是构造割平面的难 度较大，需要较高的数学技巧。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
比较：
无向图：边[v i ,v j ]，链 有向图：弧（v i ,v j ），路
，圈 ，回路
2016/3/2
链与路、圈与回路 无向图：
链 点边交错的序列 圈
起点=终点的链
有向图：
路 点弧交错的序列 回路 起点=终点的路
v5
v5 v4 v1
v1
v4
2016/3/2
v2
v3
v2
v3
5. 树
第五章 图与网络分析
第一节 图的基本概念 第二节 网络分析
2016/3/2
第一节
1.图
图的基本概念
图由点和边组成， 记成G (V , E )，其中V v1 ,, vm 为顶点集，
E e1 , , en 为边集， 点表示研究对象，边表示研究对象之间的关系。
e1 v1 e2 e3 e4 v2 e6 v3 v1 e2 e3 e4 v2 e6 v3
C 5
2 D
G
4
2 F
5 2
B
6
J
2016/3/2
[ 例 ] 今有煤气站 A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。
A 2 3.5 E I 2 2 4 3 2 H 3 5 K 1 S
如：在前面例举的网络流问题中，若已给定一个可行流 （如括号中后一个数字所示），请指出相应的弧的类型。
v2 （4，3） v4
（5，3） （1，1） （3，0） vs vt （1，1） （2，1） （5，1） v1 v3 （2，2）
2016/3/2
（3，3）
（2）可增值链（增广链）
：中的正向弧集 D中由v 至v 的链，记 ， ：中的反向弧集 中弧皆未饱 若 ，则称为D中关于可行流f 的 中弧皆非零 一条可增值链。
C
G
B
6
J
2016/3/2
[ 例 ] 今有煤气站 A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。
A 2 3.5 E I 2 2 4 3 2 D 2 F 2 2 H 3 J 5 K 1 S
2
4 D
2016/3/2
B 2
7
5
G
5
C 1 4 3
4
E 7 1 F
图1 光缆铺设费用图
案例分析：默登公司的联网问题
2 A
B
2
C 1 3 E 1 F
5
G
D
图 1 光缆铺设最小费用图
2016/3/2
应用例
已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设通讯网络（均沿道路架 设），每段道路上的架设费用如图。求能保证各城镇均
1 1
挑选其中与v 距最短（mind c )的v 进行标号。
1
1
1
4. 重复3，直至终点（本例即v ）标上号[d ,v ]，则
7 7
d 即最短距，反向追踪可求出最短路。
7
2016/3/2
用标号法解例3
[2，v1] v2 [0，v1] v1 2 5 3
其中2=min{0+2,0+5,0+3}
2016/3/2
用避圈法解例2
v2
2
v1• 3 5 1
v3
2
7 5 3 5 v5
v6 1 7
5
v7
v4
最小部分树如图上红线所示； 最小权和为14。
2016/3/2
二. 最短路问题
1. 问题：求网络D中一定点v1到其它点的最短路。 例3 求如图网络中v1至v7的最短路，图中数字 为两点间距离。
v2
（3，3）
例4 对于下图，若V1={vs，v1}，请指出相应的截 集与截量。 v v
2
（4，3）
4
（5，3） （1，1） （3，0） vs vt （1，1） （2，1） （5，1） v1 v3 （2，2）
解： （V
（3，3）
v ,v ），（v ,v ） ， ,V ） （
C（V ,V ） 32 5
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。
2016/3/2
三. 最大流问题
1. 问题 已知网络D=（V，A，C），其中V为顶点 集，A为弧集，C={cij}为容量集， cij 为弧（vi，vj ） 上的容量。现D上要通过一个流f={fij}，其中fij 为弧
（vi，vj ）上的流量。问应如何安排流量fij可使D上
通过的总流量v最大？
v2 4 1 5 1 2 v4
例如：
vs
3
5
3 2 vt
v1
2016/3/2
v3
2. 数学模型
问题：最大流问题的决策变量、目标函数、约束条件各是什么？
决策变量： 各弧（v ,v ）上的流量f ,
目标函数： Maxv v ( f )
C
G
B
J
此即为最经济的煤气管道路线，所需的总费用为25万元
2016/3/2
案例分析：默登公司的联网问题
默登（Modern）公司的管理层决定铺设最先进 的光纤网络，为它的主要中心之间提供高速通信。图 1中的节点显示了该公司主要中心的分布图。虚线是 铺设光缆可能的位置。每条虚线旁边的数字表示成本 （单位：百万美元）。 问：需要铺设哪些光缆使得总成本最低？
（3）在树中不相邻2点间添1边，恰成1圈；
（4）若树T有m个顶点，则T有m-1条边。
2016/3/2
6.图的部分（支撑）树
若图G=（V，E）的子图T=（V，E’）是树， 则称T为G的部分树或支撑树。 特点——边少、点不少。
性质：G连通，则G必有部分树。
2016/3/2
第二节 网络分析
图的每条边都有一个表示一定实际含义的权数，称为赋权图。 记作D=(V，E，C)。又称为网络。
2
v1 3 5 1
v3
2
7 5 3
v6 1 7
5
v7
v5 5 2. 方法：标号法（Dijkstra，1959）
v4
给每点vj标号[dj，vi]，其中dj为v1至vj的最短距，vi为 最短路上的前一点。
2016/3/2
标号法步骤：
1. 给v 标号[0，v ];
1 1
V :已标号点集， 2. 把顶点集V 分为互补的两部分 V : 未标号点集； 3. 考虑所有这样的边[v ,v ], 其中v V ,v V ,
v2
5.5
5 4
3
v5
2
v3 3.5 v4
2016/3/2
1. 破圈法： 在图中找圈，并删除其中最大边。如此进行下去，直 至图中不存在圈。 v1
v2
5 4
3
v5
2
v3 3.5 v4
2016/3/2
1. 破圈法： 在图中找圈，并删除其中最大边。如此进行下去，直 至图中不存在圈。 v1
v2
5
3
v5
2
C
G
B
2016/3/2
[ 例 ] 今有煤气站 A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。
A 2 E I 2 2 4 3 2 D 2 F 2 2 H 3 K 1 S
C
G
B
6
2016/3/2
[ 例 ] 今有煤气站 A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。
A 2 E I 2 2 4 3 2 D 2 F 2 2 H J 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
2016/3/2
1. 破圈法： 在图中找圈，并删除其中最大边。如此进行下去，直 至图中不存在圈。 v1
v2
5.5
5 7.5 4
3
v5
2
v3 3.5 v4
2016/3/2
1. 破圈法： 在图中找圈，并删除其中最大边。如此进行下去，直 至图中不存在圈。 v1
如 G：
e5
e7 v4
e5
v4
简单图：无环、无多重边的图。
2016/3/2
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 相邻。
1 1 1

为D的一个截集，记为（V ,V ）。
1 1
截量：截集上的容量和，记为 C（V ，V ） 。 例4 对于下图，若V1={vs，v1}，请指出相应的截 集与截量。 v v
2
（4，3）
4
2016/3/2
（5，3） （1，1） （3，0） vs vt （1，1） （2，1） （5，1） v1 v3 （2，2）