运筹学 网络最优化问题ppt课件.ppt

《运筹学 网络最优化问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学 网络最优化问题ppt课件.ppt（39页珍藏版）》请在三一办公上搜索。

1、第5章 网络最优化问题,课时：12学时5.1图的基本概念5.2最短路问题5.3最大流问题5.4最小生成树问题5.5 旅行商问题5.6最小费用流运输问题,5.1 图的基本概念,例6.11734年,七桥问题(德国哥尼斯堡),民间流传难题:一个人如何一次走遍七座桥且每座桥只走一次?,1736年数学家欧拉证明了鉴别准则:一笔划问题(欧拉定理),例6.219世纪,四色问题四色问题的内容是“任何一张地图只用四种颜色就能使有共同边界的国家着上不同的颜色。” 1852年，英国搞地图着色工作的格思里，首先提出了四色问题。 1872年，英国数学家凯利正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的

2、问题。 美国数学教授哈肯和阿佩尔于1976年6月,使用伊利诺斯大学的电子计算机计算了1200个小时，作了100亿个判断，终于完成了四色定理的证明。 不过不少数学家认为应该有一种简捷明快的书面证明方法。,其他例子.电路图、管道图等。,20世纪,与优化问题结合起来.最短路问题、最大流问题、最小支撑树问题等等。,1.图(Groph):点(vertex)和连线的集合.不带箭头的连线称为边(edge).带箭头的连线称为弧(Arc).2.无向图：连线不带箭头的图,用为:G=V,E式中：V=v1,v2,，E=e1,e2, 表示.（如图a） e=（vx,vy）.3.有向图(Divected graph)：连线

3、带箭头的图,用D=V,A表示,（如图b） a=4.起点、终点、弧头、弧尾：弧的端点。5.点的关联：若点vx,vy之间有 边相连，则称这两点是关联的。,6. 边相邻:两条边有公共的顶点,如图a中e1,e2,e3,e4有公共顶点v2.7.环:起点和终点相重的边.如图a中e6.8.多重边:两条以上边所连的顶点相重,如图a中e1,e2.9.简单图:无环、无多重边的图(如图b).10.赋权图(也称为网络)：给图G的每一条边(vi,vj),相应地赋予一个数cij,则称这样的图G为赋权图或网络,cij称为(vi,vj)的权.11.阶和度:图G的顶点个数称为它的阶数，与某顶点关联边的数称为该顶点的度(也称为次

4、)(degree）,如图a的阶为5，其中d(v1)=3.d(v4)=4(环包括入次与出次)12.孤立点:度为“0”的点,如图a中v5;13.悬挂点:度为“1”的点,如图a中v3;14.悬挂边:与悬挂点相连的边,如图a中e3.15.奇点:度为奇数的点,如图a中v1和v316.偶点:度为偶数的点;,定理:图中所有点的次之和是边数的2倍.如图a中所有点的次之和d(v)=d(v1)+d(v2)+d(v3)+d(v4)+d(v5)=3+4+1+4+0=12边数=6定理:图中奇点的个数为偶数.如图a中奇点为v1,v3. 17.完全图：对无向图的任意两点之间都有边相连，对有向图的任意两点之间都有方向相反的弧

5、相连。18.子图：设G=V,E，G=V,E,若V V,E E,则称G是G的子图。19.道路（或称链）:点、边的交错序列.如图a中(v1,e2,v2,e3,v3)即为一条链.20.回路 (或称圈):封闭的道路.如图a中(v1,e2,v2,e4,v4,e5,v1)即为一个回路.21.连通图:对无向图任两点至少存在一条道路.如图b为连通图,而图a存在孤立点v5,为非连通图.22.强连通图:对有向图的任意两点之间都有一条有向道路。23.基础图:有向图去掉箭头就变成了无向图,此无向图称为该有向图的基础图.,图的存储结构,邻接矩阵：,关联矩阵,5.2 最短路问题,1 两点间最短路及Dijkstra标号算法

6、,例求从点S(发点)到点T(收点)的最短路线.,0,1,2,4,5,4,Dijkstra标号算法计算步骤:(1)给发点标号Lss=0,记在该点旁边;(2)将标号的点与未标号的点分成两个集合 在与V有直接连线的各点中找出minLsr+drp,对于p点标号,Lsp=Lsr+drp记在该点旁边;(3) ,回到第(2)步,重复进行一直到目的地标号为止.,例单线程最短路问题.求v1到各点的最短路.,0,2,3,6,8,13,11,14,15,在所有弧的权都非负的情况下，目前公认最好的求最短路的方法是Dijkstra标号法。用实例介绍如下：,2.Floyd算法 某些问题中，要求网络上任意两点间的最短路。这

7、类问题可以用Dijkstra算法一次改变起点的办法计算，但比较繁琐。这里介绍的Floyd方法（1962）可直接求出网络中任意两点间的最短路。算法基本步骤为：,求图中任意两点间的最短有向路的长度？,2,V1,V6,V2,V3,V5,V4,1,2,7,1,3,33,1,6,2 Floyd算法,例求各点间最短路线.,从ij不一定是最短路,可能是ikj,也可能是ikmj.如从S到D先考虑只有一个中间点,有如下方案:,邻接矩阵:,SSD;SAD;SBD;SCD;SDD;SED;SFD;STD;,一般地有:,再构造由两个中间点的矩阵:,所以A(2)即得到了最短路矩阵.,计算步骤:(1)构造邻接矩阵A(2)

8、依次求最多k个中间点的可达矩阵A(k), (k=1,2,n),最短路问题的数学模型,出发点出发一次,目的地到达一次,中间点到达一次离开一次,因此，它也可用作为线性规划问题求解，只不过用Excel求解时表格应象运输问题一样作特殊设计。,例 P167例5.6某人从v1开车到v7上班，开车上班路线如右图所示，求行驶总旅程最短的路线。,解：由图可得其邻接矩阵表如下,用Excel求解得,5.3 最大流问题,例(P155例5.2)：产销地运输线及各段路线最大负载能力如下图,求从v1到v7的最大运输能力.,v1,50,v2,v3,v4,v5,v6,v7,40,70,60,40,50,30,80,70,最大流

9、问题有关概念如下:容量(Capacity):各弧最大负载能力称为该弧的容量,用C(vi,vj)表示.(注意C(vi,vj)与C(vj,vi)不同),8.4.1 .基本概念,可行流:满足下述条件 的流f称为可行流(1)容量限制:0fijcij;(2)平衡条件:式中:s为发点;t为收点;v(f)为可行流的流量.,发点、收点、中间点.,流量(flow):给弧赋予的实际负载量.,饱和弧非饱和弧零流弧,最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通讯系统中有信息流，等等。50年代福特（Ford）、富克逊（Fulkerson）建立的“

10、网络流理论”，是网络应用的重要组成部分。,增广链(agument chan):设f是一个可行流,是从vs到vt的一条链,若满足下列条件,则称为一条增广链:（1）所有前向弧都是非饱和弧.（2）所有后向弧都是非零流弧.,割:将网络中的发点和收点分割开,使st的流中断的一个弧的集合.,最小割定理:网络中st的最大流量等于它的最小割集的容量.,前向弧:如果在网络的发点和收点之间能找出一条链,在这条链上所有指向为st的弧,称为前向弧,记为+,后向弧:所有指向ts的弧(称为后向弧,记作-,若ff(vi，vj)是网络G（V，A，C）的可行流，v(f)为该可行流的流量，那么从发点vs到收点vt的最大流问题可转

11、化为如下形式的线性规划模型：,最大流问题的数学模型与求解,因此，它也可用作为线性规划问题求解，用Excel求解时表格也要作特殊设计。,例5.2由图可得其容量矩阵表如下,最大流问题的Ford-Fulkerson标号法最大流问题是一类特殊的线性规划问题，可用单纯形法进行求解。但是，在没有相关计算机软件帮助求解的情况下，用单纯形法求解最大流问题是比较复杂的，对大型问题即使让计算机单纯形法进行求解也很难，为此，这理我们将介绍求解网络最大流问题的另一种方法标号法。,标号算法于1956年由Ford和Fulkerson提出.其实质是判断是否存在增广链,并设法将其找出.如果没有增广链,则为最优方案.,用Exc

12、el求解得,算法步骤,例：求解下图所示有向网络中自点1到点6的最大流。其中每条弧上的数表示其容量。,(0,+),(v1,13),(v2,5),(v5,5),(0,+),(v1,9),(v3,5),(v6,5),(0,+),(v1,8),(v4,4),(v2,6),1,例：产销地运输线及各段路线最大负载能力如下图,求从v1到v7的最大运输能力.,2,3,(0,+),(v1,4),(v4,4),(v5,4),(v3,4),(0,+),(v1,4),(v4,2),(v6,2),(v2,2),(0,+),(v1,2),最小割=最大流=20,4,5,6,5.4 最小费用流问题,5.4.1最小费用流问题的

13、数学描述,最小费用流问题是网络优化中的一个重要概念，它在交通网、电力网、电信网和各种各样的管道网的管理中均有广泛的应用。,模型,其对偶规划模型为,利用增广路求解的算法步骤,例,运筹学课件,网络分析,运筹学课件,网络分析,1，2，0 3,4,0 1,2,0 3,1,0 1,2,0,1,2,2 3,4,0 1,2,2 3,1,0 1,2,2,(+s,2),(+a,2),(+b,2),(-b,1),(+s,1),返回,(-b,1),(+s,1),(+a,1),运输问题,运筹学课件,网络分析,其对偶规划模型为,第四章运输问题的表上作业法就是把运输问题用最小费用流问题算法设计出来的。,5.5 最小生成树

14、,8.6.1 最小生成树的概念,最小树是网络优化中的一个重要概念，它在交通网、电力网、电信网和各种各样的管道网的设计中均有广泛的应用。,即，每个树至少有一个树稍和一个树根。而且恰有一个树稍和一个树根的树是一条路。,支撑树的求法破圈法:在G中任取一个回路（俗称“圈”），从中任意删除一条边，即可将这个“圈”破掉，重复这个过程，直到图G没有“圈”为止。,8.6.1 最小生成树的算法,1、求最小树的Kruskal（库鲁斯卡尔）算法,基本思路：从G的m条边中选取n-1条权尽可能小的边，并使它们不构成回路，从而构成一最小树。,应用实例：一个乡镇有9个自然村，其间道路如下图所示，要以v0为中心建设有线电视网

15、络，问若沿道路架线，应如何架设最经济。,W（T）=13,2、求最小树的Dijkstra（狄克斯特洛）算法,例,5.5货郎担问题与中国邮路问题,有一推销员，从城市v0出发，要遍访城市v1,v2,vn各一次最后返回v0。已知vi到vj的旅费为cij问他应按怎样的次序访问这些城市，使得总费用最少？这个问题可抽象为：在网络N上找一条从v0点出发，经过v1,v2,vn各一次最后返回v0的最短路线和路程。,建立模型,变量xij是否从i第个城市到第j个城市约束 每个城市只能到达一次、离开一次,整数规划,运筹学,任何K（kn-1)个城市之间不能有回路:,任何2个城市之间不能有回路xij + xji =1,ij任何3个城市之间不能有回路xij + xjk + xki =2,ijk任何n-2个城市之间不能有回路,可证：以上条件等价于,其中，uj，ui为任意实数。,B,A,C,如列5.10中考虑A、B、C三个点是否有回路，这时n=5，,代入上述等价条件得：,目标总费用最小,整数规划,运筹学,模型,本章小结,一、基本概念图、点、边、相邻、环、多重边、简单图、次、悬挂点、悬挂边、孤立点、链、圈。二、计算要求最小支撑树：避圈法、破圈法最短路问题：Dijdstra标号算法网络最大流：Ford-Fulkerson标号算法三、应用技能两点间最短路、网络最大流电子表模型、数学模型及解法。,