运筹学6图与网络分析资料课件.ppt

《运筹学6图与网络分析资料课件.ppt》由会员分享，可在线阅读，更多相关《运筹学6图与网络分析资料课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 西安理工大学工商管理学院运筹学运筹学Operations Research雏芯躯蜜耗会圃时堡扒闽绍奶埂氟川饿娠绕换匹翻鹃欢尼鲁狮筒急犀屯辆运筹学6图与网络分析运筹学6图与网络分析 运运 筹筹 学学 OperationsResearch Chapter8图与网络分析图与网络分析GraphandNetwork1.图与网络的基本知识图与网络的基本知识2.树树3.最短路问题最短路问题4.最大流问题最大流问题华瘦肥囤崭盆担涵阜嘎敲蜒骗碗沿脯声婉柏肚酱转需彰由稳渺跳函播嗣温运筹学6图与网络分析运筹学6图与网络分析ACBDCBA引例：哥尼斯堡七桥问题您能从A、B、C或D任意一点出发走遍7座桥并且每座桥只走

2、一次最后回到原出发点吗？DE.Euler提出(1736年）：睬闯慌篡岔芭挎隧改郧殃绅鸽闰沫厅鳞踩涉参辑距侠叛赂丫旅藕魏中瞎殆运筹学6图与网络分析运筹学6图与网络分析中国邮路问题：管梅谷（1962年）提出一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？245563344494偏舷枯京揩席沉坛块沼恕铀漾尽者踩案舔啊佃巢莱惩朗棕慎绪卧沽噬涣朵运筹学6图与网络分析运筹学6图与网络分析我们在实际生活、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题

3、，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法。ACBD汾肄芹寡盯镁算世障畦梢蔫诬哇供捂藏寡寥幌若讶敷瘦祈留甜窟穿愈亿骇运筹学6图与网络分析运筹学6图与网络分析例例 某家电配送中心需要为多个销售点送货，配送中心与销售点以及销售点之间的相对位置和运输情况可以用图来表示。其中，点v1，v2，v7代表销售点，边表示运输路线。若已知每条路线行走所需的时间，请帮助配送中心管理人员设计一条送货路线，使送货车辆用最短的时间送完货物，并回到配送中心。v9v7v8v6v4v5v3配送中心v2v1虹供炉右抚惰拴启转采黍岸钢懒趴取乳妒烧镀增兽僳住摹骤棚榔停吁驼尊运筹学6图与网络分析运筹学6图与网络分析

4、基本的网络最优化问题有4个，即最小树问题，最短路问题、最大流问题、最小费用最大流问题。这些问题的数学模型实际上大都是线性规划问题，但使用线性规划的单纯形法去求解，过程非常繁琐，本章介绍的网络分析方法能有效的解决这些问题。怜钓窄喝者逆访咆瞧醒津码鹃腾撕事躁赣莽撑握序监嘎眉祭臀抛寺瓢凛瓦运筹学6图与网络分析运筹学6图与网络分析图可 定义为点和边的集合，记作 式中是点的集合，是边的集合。注意上面定义的图区别于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连，如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等，把这样的图称为网

5、络图，记作。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各个领域。ACBD8.1图与网络的基本知识图与网络的基本知识偿砧撕端既斥利掺躬篮黄魔酬誓握胎比擎侩巡撑驻侯译辅横翌舍朋述汝绥运筹学6图与网络分析运筹学6图与网络分析v3e7e4e8e5e6e1e2e3v1v2v4v5如图8-1定义定义1端点，关联边，相邻端点，关联边，相邻若有边e可表示为e=vi,vj,称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。例如图81，v2和v4是边e6的端点，反之边e

6、6是点v2、v4的关联边。点v2、v4相邻；边e6与e5、e4相邻。图81e2可记作：一、图与网络的基本概念胎漱靠乃旱孵劳泻振丰饥反昔感调平谈降恶荔庆儡社沪才族叁玲姨瓜叠悸运筹学6图与网络分析运筹学6图与网络分析定义定义2环，多重边，简单图环，多重边，简单图 如果边e的两个端点相重，称该边为环。如图8中边e1为环。如果两个点之间的边多于一条，称为多重边，如图8中的e4和e5，对无环、无多重边的图称作简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5 定义3 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。图中d(v

7、1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为0的点称作孤立点。鼠腐底川两葱日疲犬伶针算休俱撒拓忙珠怒韵货冀御臣源育谱莉废拘钙掠运筹学6图与网络分析运筹学6图与网络分析定理1 任何图中，顶点次数的总和等于边数的2倍。v1v2v3定理2 任何图中，次为奇数的顶点必为偶数个。v3e7e4e8e5e6e1e2e3v1v2v4v5捍霓灶戚五沂萄鸿贰南明扩匪纳券譬润爷痕坚错六讣渺裕珍助辛猩猛画辟运筹学6图与网络分析运筹学6图与网络分析定义定义4有向图：有向图：如果图的每条边都有一个方向则称为有向图定义定义5混合图：混合图：如何图G中部分边有方向则称为混合图有向图烽

8、杨涩脑添酷盟音咒抛革崔惨筋叼奎物嗡螺蛾呐隘飘衣曝米忍苛什潍厢礼运筹学6图与网络分析运筹学6图与网络分析定义6 有向图中，以Vi为起始点的边数称为点Vi的出次，用 表示；有向图中，以Vi为终点的边数称为点Vi的入次，用 表示。结论1：Vi点的出次与入次之和就是该点的次。结论2：有向图中，所有顶点的入次之和等于所有顶点的出次之和。寥赞巳量歧差宣出数涸届窘寥虾谣帮庄坍钩十栋榜勒赔绸领礼嫩壁腹劝滦运筹学6图与网络分析运筹学6图与网络分析定义定义7：子图、生成子图（：子图、生成子图（支撑子图）图G1=V1、E1和图G2=V2，E2如果 称G1是G2的一个子图。若有 则称 G1是G2的一个支撑子图（部分图

9、）。图8-2（a）是图 6-1的一个子图，图8-2（b）是图 8-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。e4v3e8e5e6v2v4v5图2(a)v3e7e4e8e5e6e1e2e3v1v2v4v5v3e7e6e1e2e3v1v2v4v5图2(b)蔚艳郭送棘坎涎郁营丁瘸拉嫂驰着凝萄闯舔炉伏眉驴延炭狙兹栽香爱薛悯运筹学6图与网络分析运筹学6图与网络分析定义定义8网络（赋权图）：网络（赋权图）：设图G（V，E），对G的每一条边(vi,vj)相应的有一条数w(vi,vj)(或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为网络（赋权图）。这里的权数可以是时间、费用、

10、距离等，视不同背景代表不同的含义。910201571419256赋权图瞧潞楞叮桑衍态士拐赃薄赘日馈医极秘甩抑怠读尹群堰扁踊奠邑来蜀集读运筹学6图与网络分析运筹学6图与网络分析 定义9 链、路、回路（圈）链、路、回路（圈）无向无向图中有些点和边的交替序列对任意vi,t1 和vit(2tk)均相邻，称从v0到vk的链。v3e7e4e8e5e6e1e2e3v1v2v4v5图81中，1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5是一条链，1中因顶点v3重复出现，不能称作路。二、连通图如果链中所有的顶点v0，v1，vk也不相同，这样的链称初等链（或路）。如果链中各边e1,e2,ek

11、互不相同称为简单链。当v0与vk重合时称为回路（或圈），如果边不重复称为简单回路，如果边不重复点也不重复则称为初等回路。埔痹请猛根楼闷羊屁腥拌滨湿铅稳霍陵吐杂双腿乌疵筷氏宅扦撵铆游啡屉运筹学6图与网络分析运筹学6图与网络分析是一条链也是一条路。是一条回路并且是简单回路。v3e7e4e8e5e6e1e2e3v1v2v4v5定义定义10连通图连通图若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。图81是连通图。3=v4,e7,v3,e3,v1,e2,v2,e6,v4手氢侍症库速灼霞天亢炉磺葫议纱跃厅衷吴党坯王进效举吓鄙夹翰零遣勘运筹学6图与网络分析运筹学6

12、图与网络分析欧拉回路定义11 连通图G中，若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图（E图）。CBADACBD啼惮临锣瘤拟耽柿替职溃轴酮奢院塔兑呼典故沟逊话缕凭抵贰这嗡靠猪伟运筹学6图与网络分析运筹学6图与网络分析ACBD哥尼斯堡七桥问题：寻找一条欧拉回路CBAD秆刨舞羹囊詹峰恐筛迟惮斜钦掂仅们箩伴神伸钞策茬模差蒜童暴搪俺仍守运筹学6图与网络分析运筹学6图与网络分析定理3 无向连通图G是欧拉图，当且仅当G中无奇点。ACBDv1v2v3七桥问题：d(A)=3,d(B)=3,d(C)=5,d(D)=3有四个奇点，故不是欧拉图币滔疼贞燃凝箔达鲍刃戈私树不

13、焉酚猛捎保际吁呈嗓弊贡缎寨扛亚殃妻詹运筹学6图与网络分析运筹学6图与网络分析定理4 有向连通图G是欧拉图，当且仅当G中每个顶点的出次等于入次。910201571419256袋淖闹小媳瓤谭授油边哼瓤撑僳酚叶瞩竭盘赤警惕纽炮头冤群允静矛硬压运筹学6图与网络分析运筹学6图与网络分析中国邮路问题讨论：奇偶点图上作业法245563344494v1v2v3v4v5v6v7v8v9裁叼娠放杀廖轻韭砒熬碑泉冒蛇姐面扁典街携粮卉潞衷准勇拣索危咎芬摈运筹学6图与网络分析运筹学6图与网络分析8.2 树树的概念树是图论中结构最简单但又十分重要的图，在许多领域都有应用。如：运动员抽签结构图算迈泡包大雨引傻珐摔协莱暗纸噶

14、嘱该臻效卓圾顾嘱查喇憨癣凑还永虽侮运筹学6图与网络分析运筹学6图与网络分析定义定义树、生成树：树、生成树：无圈的连通图称为树；若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵生成树。图83(a)是一棵树，图83(b)是图81的一棵生成树。v3e7e4e8e5e6e1e2e3v1v2v4v5v1v1图图81图图83(a)图图83(b)v3e2e3v2v5v3e7e8e6e2v2v4v5夏英露蘑食驮榔怖奠坤裂换仕回喝嚷耪贷膘拳宠田碎丑传请瘟喂池劲狰胃运筹学6图与网络分析运筹学6图与网络分析定理：图G=（V，E）有生成树的充分必要条件为G是连通图。v3e7e4e8e5e6e1e2e3v1

15、v2v4v5慌眷轧成柯猾震悉穴寅申揉罪祭蛀喜教庐绥绥锻撕诅靡朗混俭裳厢校随率运筹学6图与网络分析运筹学6图与网络分析生成树的寻求方法在图中，每步选出一条边使它与已选边不构成圈，直到选够n-1 条边为止。（）深探法步骤：任取一点v，给v以标号；若某点u已得标号i，检查其端点w是否已标号；若端点w未标号，则给w以标号i+1;重复 若端点均已标号，则退到标号i1的点，重复。札俏瘪凯沉汪渣躬党驭豺膊号迷哆手端劈阶陀铜淄旱示彪肺袖胎云馆攫稚运筹学6图与网络分析运筹学6图与网络分析(2)广探法任取一点v，给v以标号；检查其所有端点wi是否已标号；若端点w未标号，则给所有wi以标号i+1;对标号i+1的点重

16、复。01112212223334吮退凉沃旅践艺预捅排帽问臀缠鲸鄂吨些么予摆笆黎仿貌猿甲昭阑塌葛概运筹学6图与网络分析运筹学6图与网络分析（3）破圈法在图中任意取一个圈，从圈上任意舍弃一条边，将这个圈破掉；重复上述步骤，直到图中没有圈为止。v1v2v3v4v5v6v7v8v0v1v2v3v4v5v6v7v8v0例：某乡有9个自然村，其乡间道路如下图，要求：以v0村为中心沿道路架设有线广播网络，应如何架设？菲渭皖庞昏倔犊饼烩掳饵琴山舜镍票儡埂尊容赡哉抚京恒恃郡付邪适读泵运筹学6图与网络分析运筹学6图与网络分析最小生成树定义：设GV,E是一个连通图，每一条边eiE具有长度C(ei)0,G的任意生成树

17、T各条边的长度之和称为树T的长度，记为C（T）。长度最小的生成树称为最小树。2364122223313覆乱常啄踌澎玻恐重蛛氦下溃凤贡眉接舰穷暗谈磷娜峨溪谜糠嘲阔处寻鄂运筹学6图与网络分析运筹学6图与网络分析最小树的应用：最小树的应用：电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计 低负荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等 等）的总成本最小 高压输电线路网络的设计电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短 连接多个场所的管道网络设计 求最小树是在一个无向连通图G中求一棵最小生成树。悄膀邯豢芳者兴求酒卯鸯浅序宜磷矾巴咕蔚取懈韧咯罗滋试纶离响

18、睬癸于运筹学6图与网络分析运筹学6图与网络分析避圈法（加边法）：去掉G中所有边，得到n个孤立点；然后加边；加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521MinC(T)=15求最小树的方法：避圈法和破圈法 挤掠嗣脂棋玻却摇遗箔锁元帘任帖空秤汗舟辞得综锭瞥韩诽搐改搅诚臀磊运筹学6图与网络分析运筹学6图与网络分析破圈法：任取一圈，去掉圈中最长边，直到无圈。v1v2v3v4v5v6435215v1v2v3v4v5v6843752618措世富疮咸劫脯袖赖满哲唐菜披党锡君沮连龄肯妄混沁傲阿岿送彻虹萎

19、摆运筹学6图与网络分析运筹学6图与网络分析v1v2v3v4v5v643521得到最小树：MinC(T)=15肆沟纬换五粕愉垂因朱风热剪谋意址卯基泼禹蹭恨靖悄怠郁烦砾皖泽双璃运筹学6图与网络分析运筹学6图与网络分析根树及其应用定义 有向树：若一个有向图是一棵树，则称这个有向图为有向树。定义 若有向树T恰有一个结点的入次为0，其余各点入次均为1，则称T为根树。v1v2v3v4v5v6v7v8v9v10v11狙乍肇狈狠翱崭漳壬岗西陇紧在袍瘦帜嫁聪亨铲诽濒俩楞涌弘咽馋庭噬梯运筹学6图与网络分析运筹学6图与网络分析v1v2v3v4v5v6v7v8v9v10v11入次为0的点，称为根出次为0的点，称为叶其

20、它顶点，称为分枝点根到某顶点vi的道路长度，称为vi点的层次。琢菊占含对棚妄笆骂割土堪膨谴未败乖眠捏冬凌点埂抬约秋刽榆撞皑甩军运筹学6图与网络分析运筹学6图与网络分析定义 在根树T中，若每个顶点的出次小于或等于m，则称T为m叉树。若每个顶点的出次恰好等于m或零，则称T为完全m叉树。v1v2v3v4v5v6v7v8v9v10v11当m=2时，称为二叉树、完全二叉树。v1v2v3v4v5v6v7碰潜美宰栓君粪杂兑惶缺懒蜀死学僚辣独烙侵竣动镊两合瞻熙韭母泡勺挖运筹学6图与网络分析运筹学6图与网络分析记二叉树各叶子的权为pi，根到各叶子的距离（层次）为 li二叉树的总权数：v1v2v3v4v5v6v7

21、最优二叉树：满足总权最小的二叉树称为最优二叉树。霍夫曼（D A Huffman)给出了一个求最优二叉树的算法，又称霍夫曼树。数脾淖篡斟迟备彦琅猜倒裳许询傍造辉囊饺嗅揪福需焦离构哪屡溅封嘻娶运筹学6图与网络分析运筹学6图与网络分析例：最优检索问题用计算机进行图书分类。现有五类图书共100万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算次数最小？算法步骤：1.将s个叶子按权由小至大排序；2.将二个具有最小权的叶子合并成一个分枝点，其权为p1+p2；将新的分枝点作为一个叶子，合并，谢嘉徒傀敲纂辟苔轮偷踢祸倡坊斧掌檀敢榴墨婪睡寇炬井覆蛊

22、籍扒垒氮瓮运筹学6图与网络分析运筹学6图与网络分析解：构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15.步骤如下：1.将5个叶子按权由小到大排序：5，10，15，20，50 2.找出二个最小权的叶子，合并成一个分枝点，其权为15；依次，继续。103015205050100总权为：5151234霖殿勘熔槽型赚攀紊炸隅督渊膜麦准麓剃糜静刨第秋遏愈俞夺轻令跃勺侗运筹学6图与网络分析运筹学6图与网络分析分检过程是：先把A类50万册从总数中分检出来，其次将B类20万册分检出来，然后再将E类15万册分检出来，最后再将D、C分检出来。AABBEEDCDNYNYNYNY上族梨盏虫萍

23、日抬攒断谆店桑距去霹龙知哑庐班壬导瞅答馈拎防降蹬亢龋运筹学6图与网络分析运筹学6图与网络分析8.3最短路问题最短路问题有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法；另一种是求网图上任意两点之间最短的矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.卫甄辣绦之吞您播籍别效布搪告拢爹槐婴硷蛀寄裕满陵悟朴匙衡狠抱蛀冰运筹学6图与网络分析运筹学6图与网络分析渡河问题渡河问题

24、 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。设：M人 W狼 S羊 V白菜渡河方案共有10种，构造如下一个图，每条边的距离为1，问题变为求一条从MWSV到的最短路。北岸南岸办犊玻屯阀派叮验匀重沦忆圆芜恤拙烬稗汐替氮舰鳖欧懈嫡咨们仗吏骇式运筹学6图与网络分析运筹学6图与网络分析狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法点标号：b(j)起点vs到点vj的最短路长；边标号

25、：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)0。先求有向图的最短路，设网络图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为dij 2.找出所有vi已标号vj未标号的弧集合 B=（i，j）如 果这样的弧不存在或vt已标号则计算结束；3.计算集合B中弧k(i，j)=b(i)+dij的标号4.选一个点标号 返回到第2步。炒嘲安阻痰侣猴拴裳艺蜕襟觅叹填莽隶枕湍观毫殃篆丢峡烘釜戚拥饲绵呆运筹学6图与网络分析运筹学6图与网络分析【例】【例】求下图v1到v7的最短路长及最短路线86252353421057086225441114751071211v7已标号

26、，计算结束。从v1到v7的最短路长是 11最短路线是：v1 v4 v6 v7推源域竟环慌钦勇临拍奇依媒招祟底果辟跟个筑蔓邪簿娇煮典肌抛特责铺运筹学6图与网络分析运筹学6图与网络分析无向图最短路的求法无向图最短路的求法无向图最短路的求法只将上述步骤2改动一下即可。点标号：b(i)起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)0。3.计算集合B中边标号：ki，j=b(i)+dij4.选一个点标号:返回到第2步。2.找出所有一端vi已标号另一端vj未标号的边集合 B=i，j 如果这样的边不存在或vt已标号则计算结束；充帝募迪寇雷货目痕赌液烈嗓草冠

27、赚窿药吧膝诽眯兼梯才浇什穷慧窒刮宏运筹学6图与网络分析运筹学6图与网络分析【例】【例】求下图v1到各点的最短路及最短距离4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。苫祷吧碱熏非哮个记丘横路捆信陆锈封遥巧熔骋迷装甭捆讽尤柠仰欲洒狙运筹学6图与网络分析运筹学6图与网络分析有负权的最短路算法有负权的最短路算法假设图中没有负回路。如下图是一条负回路，最短路权无下界。322当vi到vj之间没有弧连接时，令lij列表迭代计算：设vs到vj经过vi到达vj，则vs到vj的最短距离为

28、：迭代：枷俯膊俭宵午个苟碧峙怠嘘孵丰七庄耳剐柱欢徒摈疏西蔬瞻拯拷耸颖宗辑运筹学6图与网络分析运筹学6图与网络分析【例】【例】求下图v1到v8的最短路长及最短路线v1v3v4v5v2v6v7v8567-22-3-32444-13重歉舒憨舵暑罪瓷倒棒田覆气幸鲍躬尊枝堆瑚筐撞贾巾继卞壬喇壳随枣抱运筹学6图与网络分析运筹学6图与网络分析l lij ijv v1v v2v v3v v4v v5v v6v v7v v8k k=1k k=2k k=3k k=4K=5v v1025 300v v20242v v3065v v440-3v v50v v6-304v v7720v v8310 min2 min03

29、6110 min20366150203361410(表中空格为表中空格为)v1v3v4v5v2v6v7v8567-22-3-32444-130 02 20 0-3-33 36 69 91010恼穴咋痕蔼皿癣隐恰缸残迷庙绥研综绪髓谈庸啡萄沼宦裴调盘住辰谦狙闲运筹学6图与网络分析运筹学6图与网络分析l lij ijv v1v v2v v3v v4v v5v v6v v7v v8k k=1k k=2k k=3k k=4K=5v v1025 300000v v202422222v v30650000v v440-3-3-3-3-3v v506633v v6-30411666v v7720149v v8

30、310151010采用”反向追踪”的方法找出从v1到v8的最短路.已知已知:P(v1,v8)=10，而，而P(v1,v8)=minP(v1,vi)+li8寻找：寻找：P(v1,v6）+l68=6+4=10记下：记下：v6v8再检查：P(v1,v6）=6寻找：寻找：P(v1,v3）+l36=0+6=6记下：记下：v3v6v8v1v2v3v6v8再检查：P(v1,v3）=0寻找：寻找：P(v1,v2）+l23=2+(-2)=0记下：记下：v2 v3v6v8搭谗姜涣殆枯消塞目府鲸道葬巳书舆纱阔旅彼漓县猜脯僳扦嫁担随踪莉寺运筹学6图与网络分析运筹学6图与网络分析8.4最大流问题最大流问题 许多系统中都

31、涉及到流量问题，例如网络系统中有信息流、公路系统中有车辆流、金融系统中有现金流等等。对于这些包含了流量问题的系统，我们往往需要求出其系统的最大流量。例如，某公路系统的容许通过的最大车辆数，某网络系统的最大信息流量等，以便于对某个系统加以认识并进行管理。卞白葡卯昏椭挥褐轮胎娥君材厘酒痹词帕杰拼凳驼灾童律恶弟烦荆牟抽熙运筹学6图与网络分析运筹学6图与网络分析例例 某石油公司建有一个可以把石油从采地输送到不同销售点的管道网络，如下图。由于管道的直径变化，使得各段管道（vi,vj）的最大通过能力（容量）cij也是不一样的，cij的单位为万加仑/小时。要求我们制定一个输送方案，将石油从v1输送到v6，使

32、得输送的石油达到最大 4844122679聪咳库锅速席避咱藕冕诡字志鞠卵透召碳央现歇狰谭聋恍辞厉旨年搂藉虏运筹学6图与网络分析运筹学6图与网络分析基本概念基本概念4844122679容量容量：在某时期内弧(i，j)上的最大通过能力。记为C(i，j)或Cij 在上图中，C12=4，C138，C234等，怎样安排运输方案，才能使在某一时期内从v1运到v6的物资最多，这样的问题就是最大流问题，网络中所有流起源于一个叫做发点发点的节点（源）所有的流终止于一个叫做收点收点的节点其余所有的节点叫做中间点中间点（转运点）通过每一条弧的流只允许沿着弧的箭头方向流动目标是使得从发点到收点的总流量最大8.4最大流

33、问题最大流问题鞍亚二匆忌坞藏绵屏茨挚壬管熏镊肢挟耶鸯肺烽熬惕奴殷权拿酸牌芬二捌运筹学6图与网络分析运筹学6图与网络分析流量：流量：弧(i，j)的实际通过量，记为f(i，j)或f ij可行流：可行流：如果f ij满足：1.对于所有弧(i，j)有0f ijCij 则称流量集合f ij为网络的一个可行流，简记为 f 。以下假设网络是一个简单连通图。2.对于中间点点vm有：罗遵汤谚弟烦唤掏存很剪撬帘鞘冗匠诬薛羡坑别蒸缎糠算寥团沧惨略推滴运筹学6图与网络分析运筹学6图与网络分析链链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。前向弧：前向弧：与连的方向相同的弧

34、称为前向弧。后向弧后向弧：与连的方向相反的弧称为后向弧。增广链增广链设 f 是一个可行流，如果存在一条从vs到vt的链，满足：1.所有前向弧上fij0则该链称为增广链前向弧后向弧8446952346容量容量流量流量想一想，这是一条增广链吗？弧拎罗宋俱俏肘基下亡棍旅乒追讹休趟钳蹭希谤玻胸赡寡文实鼓屁闯适佳运筹学6图与网络分析运筹学6图与网络分析【定理】【定理】设网络G的一个可行流f，如果存在一条从vs到vt的增广链，那么就可改进一个值更大的可行流f1，并且val f1val f【证】设【证】设val fv对改进的可行流f1：扎闲喘缨卿越胰汽少稗橙姿复赛戎局仍瘩协滑赦哮践怒寞僻吝廖旨霍碰垄运筹学6

35、图与网络分析运筹学6图与网络分析最大流的标号算法最大流的标号算法步骤 1.找出第一个可行流，例如所有弧的流量fij=02.用标号的方法找一条增广链 A：发点标号（，），B：选一个已标号的点 vi，对于vi的所有未给标号的邻接点，按下列规则处理：如果是前向弧前向弧并且有fijCij，令j=minCijfij,i，则vj标号（+vi，j)如果是后向弧后向弧vi并且有fj0，令j=minfij,i，则vj标号（-vi，j)当收点不能得到标号时，说明不存在增广链，计算结束。当收点已得到标号时，说明已找到增广链。【定理】可行流是最大流当且仅当不存在发点到收点的增广链纠私笺敌紧迸搔逗送滤凹蝶窜友雅卿龟掐憾

36、徐哀驼丧阴耽甫垄哀镐粪熊戍运筹学6图与网络分析运筹学6图与网络分析4.调整流量 得到新的可行流，去掉所有标号，从发点重新标号寻找增广链，直到收点不能标号为止。3.依据vi 的第一个标号反向跟踪得到一条增广链；依据vi 的第二个标号求最小值得到调整量痪娥冒疤兽六浦绩晓款酚旱蜗显碑茁漓嚎印傈足漓僻妮揩宇猴午柄楚客佬运筹学6图与网络分析运筹学6图与网络分析（，+）68441226794220222204（+v1,6）【例例】求下图v1 到v6 的最大流及最大流量【解】1.通过观察得到初始可行流2.标号3.得到增广链(+v2,2)(+v2,1)(+v5,1)(+v1,2)j=minCijfij,i失盆

37、箕逢乔咽堤摄篆跌函凑毖圾杖且锦迪盆角袁吼熬茸济胺轿盒贮剃坦爷运筹学6图与网络分析运筹学6图与网络分析（，）68441226795221222304 得到增广链 4.求调整量 5.调整可行流 去掉所有标号，重新标号68441226794220222204(+v1,1)（+v1,6）(+v2,1)(-v4,0)(+v4,1)j=minfij,i薪捶蒋返墟碍曰棋鱼烧懒凤绍耪闭宿憨便概汞逢霖卢青例印杉屯春倾熔犯运筹学6图与网络分析运筹学6图与网络分析68441226796321222305 求调整量 调整可行流 去掉所有标号，重新标号（，）（+v1,6）(-v3,2)(+v2,1)(-v4,0)(+v

38、4,1)泵翼吼男挛聚在恳斌郸梳包菊萨嫌胖炔农宏雷履暖斋葡应叔毛橇锦骡关眺运筹学6图与网络分析运筹学6图与网络分析68441226796411322306 求调整量 调整可行流 去掉所有标号，重新标号标号不能继续进行，说明不存在从发点到收点的增广链，得到最大流.最大流量最大流量v=6+3=9（，）（+v1,5）(-v3,1)佑杆在乡闽赢应鱼移氟谰绚扇夕间恭涉脖薄贬搪招表克澡给判险瘫邢绣灵运筹学6图与网络分析运筹学6图与网络分析截集截集将图将图G（V，E）的点集分割成两部分）的点集分割成两部分称为一个截集，截集中所有弧的容量之和称为截集的截量。68441226796411322306下图所示的截集

39、为针颁不悍略腔刁狈转卞翼诚瘸吐藉紧售腑筹鳞仙基偶竿训态泣搏桃瘩坯藻运筹学6图与网络分析运筹学6图与网络分析68441226796401322106又如下图所示的截集为上图所示的截集为所有截量中此截量最小且等于最大流量，此截集称为最小截集。【定理】最大流量等于最小截集的截量。搞纫述蛋巳丈女挚坠莫暗解篇磷讨丑恼皖枢轩秤镰臂侵齐腋理听诀衷谜联运筹学6图与网络分析运筹学6图与网络分析TheEndofChapter6作业作业:教材教材P285T10.1110.1210.14Exit1.基本概念 容量、流量、可行流、前向弧、后向弧、增广链、最大流、最大流量、割集、割量、最大流量最小割量 定理2.如何用标号方法求增广链3.怎样求调整量、如何调整流量4.用QSB软件求最大流问题涧札喇删轮拔纬束篷傍田裸宴络毯乱戳宣藤度翟巷系副海臂判肯却缔缩瘸运筹学6图与网络分析运筹学6图与网络分析筒琉蚌癸把藻措残晒葫贡肯毫准的德署唁吊墩缚衍趟匙帧祁娘试销沁征疼运筹学6图与网络分析运筹学6图与网络分析空埠至惧粹亡借响古江呀佯痘詹枷然榷函款哨身填宠福峨涝浦熄痰尺啦临运筹学6图与网络分析运筹学6图与网络分析菜华嫩廊五谩洽吻蝉靶厂苔涟帘望杆楷诬矛恼魁巷搽你箩妊拂宁投柿范遂运筹学6图与网络分析运筹学6图与网络分析钮忍含争克椽惑踪输胎踞禾晴痈涟警稽饥钉铝芜翠腥恬工颂霓吗习倚灌玫运筹学6图与网络分析运筹学6图与网络分析