网络分析最短路和最大流问题
- 格式:ppt
- 大小:1.00 MB
- 文档页数:56
《运筹学》重要知识点解析和例题分析第六部分一.图的基本概念 定义一个图G 是指一个二元组(V(G),E(G)).即图是由点及点之间的联线所组成。
其中: 1)图中的点称为图的顶点(vertex).记为:v2)图中的连线称为图的边(edge).记为:,i j e v v ⎡⎤=⎣⎦.,i j v v 是边 e 的端点。
3)图中带箭头的连线称为图的弧(arc).记为:(),i j a v v =.,i j v v 是弧 a 的端点。
—— 要研究某些对象间的二元关系时.就可以借助于图进行研究 分类▪ 无向图:点集V 和边集E 构成的图称为无向图(undirected graph).记为: G(V.E)—— 若这种二元关系是对称的.则可以用无向图进行研究▪ 有向图:点集V 和弧集A 构成的图称为有向图(directed graph) .记为:D(V.A)—— 若这种二元关系是非对称的.则可以用有向图进行研究▪ 有限图: 若一个图的顶点集和边集都是有限集.则称为有限图.只有一个顶点的图称为平凡图.其他的所有图都称为非平凡图.图的特点:1 图反映对象之间关系的一种工具.与几何图形不同。
2 图中任何两条边只可能在顶点交叉.在别的地方是立体交叉.不是图的顶点。
3 图的连线不用按比例画.线段不代表真正的长度.点和线的位置有任意性。
4 图的表示不唯一。
如:以下两个图都可以描述“七桥问题”。
点(vertex)的概念1 端点:若e =[u.v] ∈E.则称u.v 是 e 的端点。
2 点的次:以点 v 为端点的边的个数称为点 v 的次.记为:()d v 。
在无向图G 中.与顶点v 关联的边的数目(环算两次),称为顶点v 的度或次数.记为()d v 或 dG(v).在有向图中.从顶点v 引出的边的数目称为顶点v 的出度.记为d+(v).从顶点v 引入的边的数目称为v 的入度.记为d -(v). 称()d v = d+(v)+d -(v)为顶点v 的度或次数. 3 奇点:次为奇数的点。
第七章Operational厂§ 4网络最大流问题网络最大流冋题是网络的另一个基本冋题。
许多系统包含了流量问题。
例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。
许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。
4.1基本概念与定理1. 1.网络与流定义14 (1)网络:例1如图7-20是连结某产品产地’和销地一的交通图。
弧:1 表示从二到匚的运输线,弧旁的数字表示这条运输线的最大通过能力,.,括号内的数字表示该弧上的实际流一[。
现要求制定一个运输方案,使从一运到尸,的产品数量最多。
可行流与最大流输网络的实际问题中,我们可以看出,对于流有两个基本要求:一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力(即该弧的容量)二是起点发出的流的总和(称为流量),必须等于终点接收的流的总和,且各中间点流 入的流量之和必须等于从该点流出的流量之和, 即流入的流量之和与流出的流量之和的差为 零,也就是说各中间点只起转运作用,它既不产出新的物资,也不得截留过境的物资。
因此有下面所谓的可行流的定义。
定义14对于给定的网络 D=(V,A,C )和给定的流 』」:.「,若「满足下 列条件:(1)容量限制条件:对每一条弧 .-,有- -(7.9)(2)平衡条件: 对于中间点:流出量=流入量,即对于每一个对于出发带点T :,有SA -'K/)对于收点①,有 工二 'I(7.12)则称/ - ■为一个可行流,•-称为这个可行流的 流量。
注意,我们这里所说的出发点 r 是指只有从匚发出去的弧,而没有指向J 的弧;收点二是指只有弧指向--,而没有从它的发出去的弧。
在运i (i 丰 s,t),有(7.10)(7.11)可行流总是存在的。
例如令所有弧上的流,就得到一个可行流,(称为零流),其流量 ': 一。
如图7-20中,每条弧上括号内的数字给出的就是一个可行流 3 - f/yJ ,它显然满足定义中的条件(1 )和(2)。
《运筹学》重要知识点解析和例题分析第六部分一.图的基本概念 定义一个图G 是指一个二元组(V(G),E(G)).即图是由点及点之间的联线所组成。
其中: 1)图中的点称为图的顶点(vertex).记为:v2)图中的连线称为图的边(edge).记为:,i j e v v ⎡⎤=⎣⎦.,i j v v 是边 e 的端点。
3)图中带箭头的连线称为图的弧(arc).记为:(),i j a v v =.,i j v v 是弧 a 的端点。
—— 要研究某些对象间的二元关系时.就可以借助于图进行研究 分类▪ 无向图:点集V 和边集E 构成的图称为无向图(undirected graph).记为: G(V.E)—— 若这种二元关系是对称的.则可以用无向图进行研究▪ 有向图:点集V 和弧集A 构成的图称为有向图(directed graph) .记为:D(V.A)—— 若这种二元关系是非对称的.则可以用有向图进行研究▪ 有限图: 若一个图的顶点集和边集都是有限集.则称为有限图.只有一个顶点的图称为平凡图.其他的所有图都称为非平凡图.图的特点:1 图反映对象之间关系的一种工具.与几何图形不同。
2 图中任何两条边只可能在顶点交叉.在别的地方是立体交叉.不是图的顶点。
3 图的连线不用按比例画.线段不代表真正的长度.点和线的位置有任意性。
4 图的表示不唯一。
如:以下两个图都可以描述“七桥问题”。
点(vertex)的概念1 端点:若e =[u.v] ∈E.则称u.v 是 e 的端点。
2 点的次:以点 v 为端点的边的个数称为点 v 的次.记为:()d v 。
在无向图G 中.与顶点v 关联的边的数目(环算两次),称为顶点v 的度或次数.记为()d v 或 dG(v).在有向图中.从顶点v 引出的边的数目称为顶点v 的出度.记为d+(v).从顶点v 引入的边的数目称为v 的入度.记为d -(v). 称()d v = d+(v)+d -(v)为顶点v 的度或次数. 3 奇点:次为奇数的点。
图论与网络流问题的LINGO 求解技巧我们介绍使用LINGO 求解图论与网络问题中的一些典型问题。
如最短路问题、最大流问题、关键路径问题、最优树问题,以及TSP 问题。
这里主要介绍使用LINGO 求解的方法,重在应用和解决问题。
1 最短路问题的Lingo 求解设图共有个节点,其赋权图的邻接矩阵为n n n w ×.ij w p =表示节点i 到j 的权值为.当为有向图时,p ji w w ij =;当为无向图时,和ij w ji w 分别由图得到,通常不一样。
当,表示节点i 与节点0ij w =j 不连通。
令0ii w =。
假设图的所有权值 0ij w ≥现求节点a 到节点b 的最短路,其线性规划模型为:模型一、决策变量:设1ij i j x i j ⎧=⎨⎩节点与节点连通节点与节点不连通目标函数为寻找一条节点到节点的通路,使其上权值和最小,故目标函数为:a b 11min .nnij ij i j Z w x ===∑∑1. 对节点恰有一条路出去,却不能有路回来,故有:a 11najj j ax=≠=∑ 且10nkak k a x=≠=∑2. 对节点恰有一条路到达,却不能有路出去,故有:b 11nkbk k bx=≠=∑ 且10nbjj j bx=≠=∑3. 对除起始点a 和目标点之外,其它点进入和出去的路是一样多(可都为0),则:b 11,nnkiijk j xx i a ===≠∑∑b4. 对不通的路不取,约束为:,1,2,ij ijx w i j ≤=L n总的线性规划模型为:11111111min .,10..10,1,2,,01n nij iji j nnki ijk j naj j j a n ka k k a n kb k k a nbj j j a ij ijijZ w x x x i a b x x s t x x x w i j x =====≠=≠=≠=≠=⎧=≠⎪⎪⎪=⎪⎪⎪⎪=⎪⎪⎪⎪=⎨⎪⎪⎪=⎪⎪⎪≤=⎪⎪=⎪⎪⎪⎩∑∑∑∑∑∑∑∑L 或n示例演示。
实验六:图与网络分析-最短路问题
一、实验目的:掌握不同问题的输入方法,求解网络模型,观察求解步骤,显示并读出结果。
二、内容和要求:用WinQSB软件求解最短路问题,并对结果进行简单分析。
例:求下图的最短路。
三、操作步骤:
1.“开始”菜单→“winQSB”→“Network Modeling”(网络模型)。
2.建立新问题:File→New Problem,出现下面界面。
选择Shortest Path Problem、Minimization、输入问题标题、节点的个数,然后单击“OK”。
3.修改节点名称:菜单“Edit”→“Node Names”,编辑完点“OK”,如下图。
4.按下图输入图的权矩阵,本例是无向图,每一条边必须输入两次。
5.菜单“Solve and Analyze”→“Solve the Problem”,出现以下对话框,
6.然后选择起点v1和终点v10,点“Solve”按键,出现下图:
从图中可以看到v1到v10的最短路径为v1→v3→v7→v10,总长为6,另外从v1到其他各点的最短距离也都计算了出来。
7.实例求解:有九个城市v1,v2…,v9,其公路网如下图,弧旁数字是该段公路的长度,有一批货物从v1运到v9,试用Dijkstra方法求出走哪条路最短?
自己先用标号法求出最短路,然后用winWSB软件进行验证。
8.思考题:教育部门打算在某新建城区建一所学校,让附近七个居民区的学生就近入学。
七个居民区之间的道路如下图所示,学校应建在哪个居民区,才能使大学都方便?(图中距离单位:百米)。