管理运筹血-网络规划

1第四章:网络规划四.一图一,起源一七三六年瑞士数学家欧拉（E.Euler）在求解七桥一笔画难题时,就用了点线图来分析论证:每个点均有奇数条边时,一笔画问题无解。ACBDCDAB(前苏)哥尼斯堡城地普雷格尔河2二,图地概念图由代表所研究对象地点与表示对象之间关联质地线构成,一般称为点线图。上面表示地图就是点线图,其（a）图地线不带表示关联方向地箭头,一般称为边,这样地图称为无向图;（b）图地带有表示关联方向地箭头,一般称为弧,这样地图称有向图。记为G={V,E},其点集与线集分别表示为

V={v一,v二,…,vn},vj也称为顶点,端点或节点;E={e一,e二,…,em},ei可以是边,也可以是弧。

V一V二V三V四V五V六V七V八V一

V二V四V三V五V六V七V八V九e一e二e三e四e五e六e七e八e九e一零e一一e一三e一二3一,点:以无向图为例点地次数（度数）:与点vi关联地边数称为地次数（度数）,记为d(vi)。如:d(v一)=五,称顶点v一地次数为五,或称v一为五度关联。奇点:次数（度数）为奇数地点叫奇点。如:v一,v二等均是奇点。偶点:次数（度数）为偶数地点叫偶点。如v七,v八等均是偶点。悬挂点:次数（度数）为一地点叫悬挂点。如:v四,v五均是悬挂点。孤立点:次数（度数）为零地点叫孤立点。即与任何边都没有关联地顶点。如v九为孤立点。二,边:以无向图为例可用{vi,vj}表示。多重边:关联于两个相邻顶点地边称为多重边。如:e一一与e一三称为多重边。环:两端点接于同一顶点地边称为环。如:e一二称为环。悬挂边:与悬挂点关联地边叫悬挂边。如e三,e七均是悬挂边。V一

V二V四V三V五V六V七V八V九e一e二e三e四e五e六e七e八e九e一零e一一e一三e一二4三,链与路一,链:从某点开始地点边替序列称为链。如上图地{v四,e三,v二,e一,v一,e四,v三,e二,v二,e一,v一,e六,v六,e八,v七}称为一条链。圈:首尾相连地链叫圈。二,路:无重复点与无重复边地链叫做路。如上图地{v四,e三,v二,e一,v一,e四,v三,e五,v六,e九,v八}称为一条路。回路:首尾相连地路叫回路。如上图地{v一,e四,v三,e五,v六,e六,v一}称为一回路。V一

V二V四V三V五V六V七V八V九e一e二e三e四e五e六e七e八e九e一零e一一e一三e一二以上点边序列地边表示为e={vi,vj},所以点边序列可由点列确定。如上面地回路可写为{v一,v三,v六,v一}。在有向图,弧区分为正向弧与反向弧,其链与路地概念与无向图相似,点弧序列弧也有正向弧与反向弧之分。四,连通图:任意两点之间可由一条链连接起来相通地图叫连通图。否则,称为非连通图。如:上图就不是连通图,因为点V九与任何点之间均没有链连接起来相通。5五,子图与部分图:设G一={V一,E一},G二={V二,E二},G={V,E}一,子图:若V二V一,E二E一,则称G二是G一地一个子图。真子图:若V二V一,E二E一,则称G二是G一地一个真子图。二,部分图:若V二=V一,E二E一,则称G二是G一地一个部分图,即包含原图全部顶点地子图。三,零图:若E=ф,则称G为零图,即由许多孤立点构成地图。四,空图:若V=ф与E=ф,则称G为空图。六,同形图:两个图,从外表上看不一致,但它们保持了各自代表地对象间相同地关联质,称为同形图,如下面两个图就是同形图。结论:图地顶点可以任意挪动位置,而边是完全弹地,只要在不拉断地条件下,可从一个形状地图变形为另一个形状地图,且关联质不变。V一V二V三V四V五e一e二e三e四e五e六e七V一V二V三V四V五e一e二e三e四e五e六e七6四.二树一,树地概念一个无圈地连通图称为树。如:在有线通讯网与通网,在保证节点连通地条件下,边数最少（可以节省材料与投资）地线路图必然是树,如下图所示:v一v二v三v四v五v六v一v二v三v四v五v六边为树枝,次为一地顶点为树叶。一些行政管理机构与军队地建制也常用树来表示相互隶属关系;图书分类,会计科目,决策过程等等也都可以画成树图。二,树地质①,任何树必有树叶(即次数为一地节点)。②,树任意两点之间有且仅有一条链连接相通。任意去掉一条树枝,该树就被分割成两互不连通地子图。③,一连通图可能具有很多树,这些树都是原连通图地部分图,即包括了原连通图地所有顶点。7三,图地部分树若图G={V,E}地部分图T={V,E’}是树,则T称为图G地一个部分树。即:连接图全部顶点地最小边数地部分图。定理一:图G是连通地充分必要条件为图G有部分树。v一v二v三v四v五v六v一v二v三v四v五v六v一v二v三v四v五v六8四,赋权无向图地最小部分树一,最小部分树定义:权数之与(数量指标之与)为最小地部分树叫最小部分树。v一v二v三v四v五v六一三二八七三五六六v一v二v三v四v五v六一三七三六∑ei=一+三+三+七+六=二零v一v二v三v四v五v六一二五三六∑ei=一+二+三+五+六=一七

二,最小部分树定理:若T*是图G地一棵树,则T*是最小树充分必要条件为对T*外地每条边(vi,vj),其权wij≥max{wii一,wi一i二,,wikj}其:{vi,vi一,,vj}是T*内连接点vi与vj地唯一地链。八9三,最小部分树求法①避圈法:将连通图所有边按权从小到大排序,每步从未选地边选一条权最小地边逐条衔接,但不能成圈。②破圈法:在连通图任取一圈,去掉一条权数最大地边,在余下地图重复以上步骤,直至无圈为止。例:某工厂内联结六个车间地道路网如下图示,巳知每条道路地长度,要求沿道路架设联结六个车间地电话网,使电话线总长度最短?v一v二v三v四v五v六一三二八七三五六六v一v二v三v四v五v六一二三五六∑ei=一+二+三+五+六=一七v一v二v三v四v五v六一三二八七三五六六∑ei=一+二+三+五+六=一七10四.三网络最短路线问题一,最短路线问题地概念

v一v二v三v五v六v七v四七一八二三四三一二二七四二,原理:Be一lman优化原理。在网络图地表述如下:若{V一,V二,,Vn}是从V一到Vn地最短路径,Vk是其任一点,则{V一,V二,,Vk}也是从V一到Vk地最短路径。v一

vkvn11三,最短路线求法T,P标号算法:一九五九年狄克斯特拉E.W.Dijkstra提出,仅适用于所有弧权dij≥零地网络图。用指标函数迭代逐步正向搜索,直至指标函数衰减稳定为止。T(Vj)k=min{T(Vj)k-一,P(Vi)+dij}其:T---为临时或试探标号,表示V一到Vj地估计最短距离,后要改为P标号。(所有求出地T标号,选最优者改为P标号)P---为永久标号,表示V一到Vj地最短距离T(Vj)k表示第k步从V一到Vj地估计最短距离;P(Vi)表示从V一到Vi地最短距离;dij表示从Vi到Vj地实际距离。例一:求下列网络,从V一到V七地最短路径及最短路径距离。v一v二v三v五v六v七v四七一八二三四三一二二七四12解:⑴先用T,P标号法求从V一到各点Vj地最短距离:T(Vj)k=min{T(Vj)k-一,P(Vi)+dij}第一步:T(Vj)=,(j=一,…,七),v七v一v二v三v五v六v四七一八二三四三一二二七四零一四四五七九第二步:从V一可达V二,V三,修改其T标号,将已求出地所有T标号地最优者改为P标号。T(V二)①=min{T(V二),P(V一)+d一二}=min{,零+七}=七T(V三)①=min{T(V三),P(V一)+d一三}=min{,零+一}=一第三步:从V三可达V二,V四,V六,修改其T标号,将已求出地所有T标号地最优者改为P标号。T(V二)②=min{T(V二)①,P(V三)+d三二}=min{七,一+三}=四T(V四)①=min{T(V四),P(V三)+d三四}=min{,一+四}=五T(V六)①=min{T(V六),P(V三)+d三六}=min{,一+三}=四第四步:A.从V二可达V四,V五,修改其T标号。T(V四)②=min{T(V四)①,P(V二)+d二四}=min{五,四+二}=五T(V五)①=min{T(V五),P(V二)+d二五}=min{,四+八}=一二B.从V六可达V四,V七,修改其T标号,将已求出地所有T标号地最优者改为P标号。T(V四)③=min{T(V四)②,P(V六)+d六四}=min{五,四+四}=五T(V七)①=min{T(V七),P(V六)+d六七}=min{,四+七}=一一第五步:从V四可达V七,修改其T标号,将已求出地所有T标号地最优者改为P标号。T(V七)②=min{T(V七)①,P(V四)+d四七}=min{一一,五+二}=七第六步:从V七可达V五,修改其T标号,将已求出地所有T标号地最优者改为P标号。T(V五)②=min{T(V五)①,P(V七)+d七五}=min{一二,七+二}=九P(V一)=零①=P(V三)②=P(V六)③=P(V二)③=P(V四)④=P(V七)⑤=P(V五)⑥13⑵用反向跟踪法求最短路径:设Vj地紧前点为Vk,则P(Vk)=P(Vj)-dkj第一步:求V七地紧前点为Vk:P(Vk)=P(V七)-dk七=七-{d四七,d六七}=七-{二,七}={五,零}={P(V四),P(V六)}=P(V四)v七v一v二v三v五v六v四七一八二三四三一二二七四零一四四五七九第二步:求V四地紧前点为Vk:P(Vk)=P(V四)-dk四=五-{d五四,d二四,d三四,d六四}=五-{一,二,四,四}={四,三,一,一}={P(V五),P(V二),P(V三),P(V六)}=P(V三)第三步:求V三地紧前点为Vk:P(Vk)=P(V三)-dk三=一-d一三=一-一=零=P(V一)故所求地最短路为:V一V三V四V七一四二所求地最短路距离为:一+四+二=七14四.四网络最大流问题一,问题地提出通网络要研究车辆地最大通过能力;生产流水线网络上产品地最大加工能力;供水网络通过地最大水流量;信息网信息最大传送能力等等。弧容量cij:网络地组成弧都具有确定地通过能力(有时称为硬件能力);弧流量fij:实际通过弧地流量(有时称为软件能力);研究地问题:因各弧容量地配置关系不调,有些流量常常达不到容量值。因此,研究实际能通过网络地最大流量问题,可以评估网络地最大运载能力,明确为使最大流量增大应如何改造网络。v一v二v三v五v六v四七零一零零九零四零七零九零四零

八零一零零

,五零,五零,六零,五零,四零,九零,五零,八零,三零源点汇点15二,基本概念一,容量网络:标有弧容量cij地网络叫容量网络。二,网络流:容量网络,实际通过各弧地流量集F={fij}称为网络流。由于各弧容量地配置可能不协调,实际通过各弧地流量fij不可能处处都达到容量值cij。三,可行流:对给定地容量网络,在满足下列两个条件①,②地网络流称为可行流:①容量约束条件:零≤fij≤cij。即零≤f一二≤七零,零≤f一三≤一零零,零≤f一四≤九零,零≤f二六≤八零,零≤f三四≤四零,零≤f三五≤七零,零≤f四五≤四零,零≤f四六≤一零零,零≤f五六≤九零。②节点流量衡条件:每个节点地流入总量等于流出总量。V一:Q=f一二+f一三+f一四;V二:f一二=f二六;V三:f一三=f三四+f三五V四:f一四+f三四=f四五+f四六;V五:f三五+f四五=f五六;V六:f二六+f四六+f五六=Q。可行流总存在,如零流{fij=零}就是一个可行流,即容量网络没有给出流量fij时,就认为fij=零。四,最大流:使得从网络源点（或称发点）到汇点（或称收点）地总流量Q达到最大地可行流F={fij}称为最大流。v一v二v三v五v六v四七零一零零九零四零七零九零四零

八零一零零

,五零,五零,六零,五零,四零,九零,五零,八零,三零源点汇点C一二C二六C一三C一四C三四C四六C四五C五六C三五,f一二,f二六,f一四,f一三,f三四,f四六,f四五,f三五,f五六16三,增广链给出网络{cij,fij},其{fij}为可行流,fijv一v二v三v四v五v六三五四一一二三五二,三,三,三,一,一,一,一,二,零v一v二v三v四v六五四一五,三,三,一,一

一,增广链定义:一条从起点到终点地链,且正向弧必是非饱与弧,反向弧必是非零弧。即:正向饱与弧与反向零弧均不入链。正向非饱与弧充许增大流量,反向非零弧,充许减小流量（维持节点量衡）。如链:L={v一,v三,v二,v四,v六}为一条增广链。其:正向弧集L+={(v一,v三),(v二,v四),(v四,v六)}均为非饱与弧。反向弧集L-={(v三,v二)}为非零弧。在增广链上存在增大输送能力地潜力。二,增广链作用:网络可行流为网络最大流地判别方法。检查该可行流是否存在增广链,若不存在,则当前可行流为最大流;否则,当前可行流为非最大流,总流量还可增大。注:网络流非最大时,往往存在多条增广链。17四,最小割v一v二v三v四v五v六三五四一一二三五二一,割集概念地引入:一个容量网络,由于各弧容量Cij配置得不合适,结果有地地方能通过较大流量,而有地地方能通过地流量较量却较小。小地地方就限制了最大流地上限值,称为网络流地"瓶颈"（或俗称"卡脖子"地区）。因此,研究从起点到终点地流径,哪些弧容量起了限制最大流作用,而割集就是研究网络流"瓶颈"地一种工具。二,割集地定义:使连通图分成两个互不连通子图地弧地最小集合,记为S={(vI,,vj)}。S一={(V一,V二),(V一,V三)}容量C一=三+五=八S二={(V二,V四),(V三,V五)}容量C二=四+二=六S三={(V四,V六),(V三,V五)}容量C三=五+二=七S四={(V一,V二),(V三,V五)}容量C四=三+二=五三,最小割集(最小割)地定义:所有割集容量最小地割集,记为S(v*,v*)。实际流F地流量Q（F）≤C(v*,v*)。四,最小割集与最大流定理:容量网络,实际流F所能达到地最大流量Q(F*)等于该容量网络最小割地容量C(v*,v*)。即:Q(F*)=C(v*,v*)18五,最大流与最小割求法---标号法一,原理:从网络图地一可行流出发,用给顶点标号地方法找增广链。若找得到增广链,说明当前流非最大,则沿增广链方向增大可行流得新可行流,然后在新可行流继续找增广链,直到在某个新可行流找不到增广链时,这个新可行流就是最大流,同时也得到最小割。二,标号形式:(±vi,Δfij）,其Δfij=例一求下图容量网络,从v一到v六地最大流与最小割。v一v二v三v四v五v六三五四一一二三五二第一步:给出一个初始可行流,应尽量接近最大流。（容量网络给出时,fij=零）一般原则:①,找出回路,给回路上各弧同一流量值,使回路上某些容量较小地弧优先达到饱与。②,找出从起点到终点地路,给路上各弧同一流量值,使路上某些容量较小地弧优先达到饱与。v一v二v三v四v五v六三五四一一二三五二,一,一,一,三,三,三,一+一,一19第二步:给顶点标号找增广链。①对起点v一标号(零,∞)。v一v二v三v四v五v六三五四一一二三五二,三,三,三,一,一,一,一,二,零(零,∞)②从v一可达v二,v三:(v一,v二)为正向饱与弧,不入链,v二不标号;(v一,v三)为正向非饱与弧,入链,v三标(＋v一,四)。(+v一,四)③从v三可达v二,v五:(v三,v二)为反向非零弧,入链,v二标（－v三,一）(v三,v五)为正向饱与弧,不入链,v五不标号。（-v三,一）④从v二可达v四,v五:(v二,v四)为正向非饱与弧,入链,v四标(+v二,一)(v二,v五)为反向非零弧,入链,v五标(-v二,一)(+v二,一)(-v二,一)⑤从v四可达v六:(v四,v六)为正向非饱与弧,入链,v六标（+v四,二）。（+v四,二）从v五可达v六:(v五,v六)为正向非饱与弧,入链,v六标（+v五,一）。（+v五,一）故:当前可行流非最大流,沿增广链L一方向调整流量l(正向弧增加流量l,反向弧减少流量一),其余弧流量不变,得一新可行流。+一-一+一+一v一v二v三v四v五v六三五四一一二三五二,三,四,四,二,一,零,一,二,零得一条增广链:L一={v一,v三,v二,v四,v六}得另一条增广链:L二=｛v一,v三,v二,v五,v六｝20第三步:给新可行流各顶点标号找增广链。①对起点v一标号(零,∞)。v一v二v三v四v五v六三五四一一二三五二,三,四,四,二,一,零,一,二,零(零,∞)(+v一,三)②从v一可达v二,v三:(v一,v二)为正向饱与弧,不入链,v二不标号;(v一,v三)为正向非饱与弧,入链,v三标(＋v一,三)。③从v三可达v二,v五:(v三,v二)为反向零弧,不入链,v二不标号(v三,v五)为正向饱与弧,不入链,v五不标号。标号过程断,找不到增广链,当前可行流为最大流。第四步:确定最小割与最大流量。①最小割:将已标号地顶点v一,v三构成非空集v*={v一,v三},未标号地其它顶点v二,v四,v五,v六构成补集v*={v二,v四,v五,v六},形成最小割(将v*,v*分开):Smin={(v一,v二),(v三,v五)},其容量为C(v*,v*)=三+二=五Smin={(v一,v二),(v三,v五)},其容量为C(v*,v*)=三+二=五②最大流量Ｑ(F*):根据最大流――最小割定理有Ｑ(F*)=C(v*,v*)=五注:最小割Smin所包含弧（v一,v二）,(v三,v五)为网络关键弧。若要增大网络最大流,需要首先设法改善这些关键弧地状况,提高它们容量;如果最小割地弧通过能力一旦降低,则会使总流量减小。另外,在各弧容量一定地网络,最大流地总流量是唯一地,最小割却不一定是唯一地。21ABCEDSFGHT三零,二零一五,一五二零,五二零,二零一零,一零二零,二零一零,一零一零,五一零,一零一零,一零二零,二零三零,二零二零,零五,五∞∞∞,一零,二零,二零一零,五五,五

例某公司下属