运筹学-网络最优化问题

第5章网络最优化问题课时：12学时5.1图的基本概念5.2最短路问题5.3最大流问题5.4最小生成树问题5.5旅行商问题5.6最小费用流——运输问题5.1图的基本概念ACDB[例6.1]1734年,七桥问题(德国哥尼斯堡)民间流传难题:一个人如何一次走遍七座桥且每座桥只走一次?ADBC1736年数学家欧拉证明了鉴别准则:一笔划问题(欧拉定理)[例6.2]19世纪,四色问题四色问题的内容是“任何一张地图只用四种颜色就能使有共同边界的国家着上不同的颜色。”1852年，英国搞地图着色工作的格思里，首先提出了四色问题。1872年，英国数学家凯利正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的问题。美国数学教授哈肯和阿佩尔于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.有向图(Divectedgraph)：连线带箭头的图,用D={V,A}表示,（如图b）a=vx,vy4.起点、终点、弧头、弧尾：弧的端点。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的顶点个数称为它的阶数，与某顶点关联边的数称为该顶点的度(也称为次)(degree）,如图a的阶为5，其中d(v1)=3.d(v4)=4(环包括入次与出次)12.孤立点:度为“0”的点,如图a中v5;13.悬挂点:度为“1”的点,如图a中v3;14.悬挂边:与悬挂点相连的边,如图a中e3.15.奇点:度为奇数的点,如图a中v1和v316.偶点:度为偶数的点;(a)(b)v1v2v3v4e1e2e3e4e5a1a2a3v1v2v3v5e6(a)(b)v1v2v3v4e1e2e3e4e5e1e2e3v1v2v3v5e6定理:图中所有点的次之和是边数的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.完全图：对无向图的任意两点之间都有边相连，对有向图的任意两点之间都有方向相反的弧相连。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.基础图:有向图去掉箭头就变成了无向图,此无向图称为该有向图的基础图.图的存储结构邻接矩阵：简单图),(ENG的邻接矩阵：n阶方阵()ijnnAa其中1,,1,2,,0,ijiaijn当点与点j邻接否则简单有向图),(ANG的邻接矩阵：n阶方阵()ijnnAa，其中1,,1,2,,0,ijiaijn当有弧从点连上点j否则简单图),(ENG的关联矩阵：一个||||EN阶矩阵)(ikbB，其中,0,1否则关联与边当点kibik简单有向图),(ANG的关联矩阵：一个||||AN阶矩阵)(ikbB，其中,0,1,1否则为头以点当弧为尾以点当弧iaiabikikik关联矩阵5.2最短路问题1两点间最短路及Dijkstra标号算法[例]求从点S(发点)到点T(收点)的最短路线.01245213226735441SACEBDFT4Dijkstra标号算法计算步骤:(1)给发点标号Lss=0,记在该点旁边;(2)将标号的点与未标号的点分成两个集合在与V有直接连线的各点中找出min{Lsr+drp},对于p点标号,Lsp=Lsr+drp记在该点旁边;(3),回到第(2)步,重复进行一直到目的地标号为止.,,,VVrVpV,\,VVpVVp[例]单线程最短路问题.求v1到各点的最短路.0236813111415723332285101136474v1v2v3v4v5v6v7v8v9在所有弧的权都非负的情况下，目前公认最好的求最短路的方法是Dijkstra标号法。用实例介绍如下：2.Floyd算法某些问题中，要求网络上任意两点间的最短路。这类问题可以用Dijkstra算法一次改变起点的办法计算，但比较繁琐。这里介绍的Floyd方法（1962）可直接求出网络中任意两点间的最短路。算法基本步骤为：。的所有路中长度最短者到是从顶点而阵算出矩然后用递推公式相连，则弧没有边到如果顶点的边权的邻接矩阵即：是设阶加权简单图已知jia，AAAdAaaaadjiawaDaADnnijnnnkijkkkjkikkijkijijiijiijnnij)()()3()2()()()1()1()1()(,,,,)(},,min{)(,0,)(,求图中任意两点间的最短有向路的长度？2V1V6V2V3V5V4127133316060302107310210AAG为：的边权矩阵解：图06030421063210843210)2(A06030421053210643210)3(A)6()5()4(06030421053210643210AAA没有有向路。到表示从；的最短有向路的长度为到表示从；的最短有向路的长度为到表示从2442533561162266vvavvavva2Floyd算法[例]求各点间最短路线.213226735441SACEBDFT从ij不一定是最短路,可能是ikj,也可能是ikmj.如从S到D先考虑只有一个中间点,有如下方案:02120224203120434340713057506160SABCDEFTSABACDEFT邻接矩阵:SSD;SAD;SBD;SCD;SDD;SED;SFD;STD;(1)02434minmin6017SSSDSAADSBBDSCCDSDSDDDSEEDSFFDSTTDaaaaaaddAdddddddd一般地有:(1)min{,}ijijirrjaaaa(1)02446162022431134204371424043864340774133705116117875063141160SABCDEFTSABACDEFT再构造由两个中间点的矩阵:(2)(1)(1)(1)22min{,},ijijijaaaa(2)0244616520224383420435714240438564340774135370566878750653154660SABCDEFTSABACDEFT所以A(2)即得到了最短路矩阵.计算步骤:(1)构造邻接矩阵A(2)依次求最多k个中间点的可达矩阵A(k),(k=1,2,…,n)(2)(3)AA最短路问题的数学描述给定网络),,(WANG，对G的每一条弧Aai,给定权)(iiaww，设P为G中的一条路,定义P的权（或长）：PaiaWPW)()(问题：寻求有网络中自某一指定点sv到另一指定点tv间的最短有向路。最短路问题的数学模型njixtsiNixxxxxxxdxdijjjiijAtiitniitAjsijnjsjAjiijijnjijij,,2,1,,1,0,,,0)()1(1)1(1.t.s)(min),(1),(1),(n1i1或或或设1,0ijx表示节点iv到节点jv是否走，nnijdd)(的边权的邻接矩阵是G，则出发点出发一次目的地到达一次中间点到达一次离开一次因此，它也可用作为线性规划问题求解，只不过用Excel求解时表格应象运输问题一样作特殊设计。例P167例5.6某人从v1开车到v7上班，开车上班路线如右图所示，求行驶总旅程最短的路线。v1v2v3v4v5v6v7v1029∞∞∞∞v2∞068∞∞∞v3∞∞013∞∞v4∞∞∞043.5∞v5∞∞∞∞0∞2.5v6∞∞∞∞∞05v7∞∞∞∞∞∞0解：由图可得其邻接矩阵表如下用Excel求解得5.3最大流问题例(P155例5.2)：产销地运输线及各段路线最大负载能力如下图,求从v1到v7的最大运输能力.v150v2v3v4v5v6v74070604050308070最大流问题有关概念如下:容量(Capacity):各弧最大负载能力称为该弧的容量,用C(vi,vj)表示.(注意C(vi,vj)与C(vj,vi)不同)8.4.1.基本概念可行流:满足下述条件的流f称为可行流(1)容量限制:0≤fij≤cij;(2)平衡条件:式中:s为发点;t为收点;v(f)为可行流的流量.()()0(,)()()ikjivfisffistvfit发点、收点、中间点.流量(flow):给弧赋予的实际负载量.饱和弧非饱和弧零流弧00ijijijijijfcfcf•最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通讯系统中有信息流，等等。50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。增广链(agumentchan):设f是一个可行流,μ是从vs到vt的一条链,若满足下列条件,则称为一条增广链:（1）所有前向弧都是非饱和弧.（2）所有后向弧都是非零流弧.割:将网络中的发点和收点分割开,使st的流中断的一个弧的集合.最小割定理:网络中st的最大流量等于它的最小割集的容量.前向弧:如果在网络的发点和收点之间能找出一条链,在这条链上所有指向为st的弧,称为前向弧,记为μ+后向弧:所有指向ts的弧(称为后向弧,记作μ-若f＝{f(vi，vj)}是网络G＝（V，A，C）的可行流，v(f)为该可行流的流量，那么从发点vs到收点vt的最大流问题可转化为如下形式的线性规划模型：最大流问题的数学模型与求解(,)(,)(,)(,)(,)(,)max()0(,)()..0,()ijjiijjiijjiijiji