《运筹学》课件--网络规划问题.ppt

运筹学—网络规划问题
主讲:经济与工商管理学院肖智
版权所有肖智重庆大学经济与工商管理学院
1
一、本讲的目的: 理解网络规划基本概念、特征、应用,掌握最小树与最短路等典型问题的网络模型建立、分析思路、求解方法,了解最小树与最短路等典型问题的应用。二、主要内容: 1、网络规划概述 2、最小树问题 3、最短路问题 4、案例讨论三、本讲的重点与难点: 1、重点:掌握网络模型基本要素、特征,网络模 型建立,求解思路与方法,其作用与应用。 2、难点:模型建立、分析思路
版权所有肖智重庆大学经济与工商管理学院
2
第二章运筹决策 第一节网络规划问题一、网络规划概述1、基本概念 1)图:由点和边组成的集合。常记为:G=(V,E);其中:V={v1,v2,…,vn}表示点的集合,E={e1,e2,…,em}表示边的集合。 -1为无向图,-2为有向图。   -1 -2
v1
e2
e1
v2
v3
v1
e2
e3
e1
v2
v3
版权所有肖智重庆大学经济与工商管理学院
3
2)网络:带有某种数量指标的图(即:赋权图)-3为无向网络,-4为有向网络。 -3 -43)链:无向图G=(V,E)中与边依次交替出现的序列{vi0,ei1,vi1,ei2,vi2,…,vik-1,eik,vik}, 且eit=(vit-1,vit),t=1,…,k,则称这个点边序列为连接vi0到vik的一条链,链长为k。4)圈:链{vi0,ei1,vi1,ei2,vi2,…,vik-1,eik,vik}中当vi0=vik时, 该链称为圈。-7中{v1,e1,v2,e3,v3,e2,v1}为圈。
v1
5
3
v2
v3
v1
3
2
8
v2
v3
版权所有肖智重庆大学经济与工商管理学院
4
-7 -8 5)路:有向图中当链(圈)上的边方向相同时,称为路(回路)。-8中{v1,e3,v4,e4,v2,e7,v5}为路; {v3,e5,v4,e6,v5,e8,v3}为回路。 6)连通图:图中任意两点间至少有一条链相连,称此图为连通图。-7、-8。 7)网络模型:对所关心的问题确定研究对象以及这些对象之间某种性质的联系,并用网络图及其图解的形式表示出来,这就是对问题建立网络模型。
v1
e1
v2
v3
v1
v2
v5
v4
v3
v4
e2
e3
e4
e5
e1
e2
e3
e4
e5
e6
e7
e8
版权所有肖智重庆大学经济与工商管理学院
5
2、网络基本特征:1)三要素——点、边、权。2)一般将研究“对象”作为“点”,“对象”之间关系作为“边”,“对象”之间关系程度作为“权”二、网络规划应用::节目排序问题 一场文艺演出共有8个节目,全体演员中有10人须参加两个以上的节目,-1中符号所示。若节目主办者希望首尾两个节目为A和H,或为H和A,还希望每个演员不连续参加两个节目的演出,则应如何安排节目表。
版权所有肖智重庆大学经济与工商管理学院
6
-1
演员
节目
1
2
3
4
5
6
7
8
9
10
A






B



C



D


E


F


G



H





版权所有肖智重庆大学经济与工商管理学院
7
分析: 把节目作为研究对象,用点表示。如果两个节目无同一名演员参加,这说明二者可以紧排在一起,则给相应的两点间连结一条边,-9。这就是本例的网络模型。于是问题归结为:从图中找出一条从A到H或从H到A且通过所有结点的链,且每一个点只通过一次。不难看出,这样的路有四条:(1)AFBCGDEH(2)HEDGCBFA(3)AFGCBDEH(4)HEDBCGFA则文艺演出的节目表可按上面任一顺序安排。
版权所有肖智重庆大学经济与工商管理学院
8
-9
H
A
G
F
E
D
C
B
版权所有肖智重庆大学经济与工商管理学院
9
:电话线架设问题 -10所示,边旁数字为各村镇之间道路的长度。现要沿交通道路架设电话线,使各村之间均能通话。应如何架线使总长最短?  -10
1
4
2
3
7