运筹学ppt课件Ch6网络模型.ppt

《运筹学ppt课件Ch6网络模型.ppt》由会员分享，可在线阅读，更多相关《运筹学ppt课件Ch6网络模型.ppt（119页珍藏版）》请在三一文库上搜索。

1、运 筹 学 Operations Research,Chapter 6 网络模型 Network Modeling,6.1 最小(支撑)树问题 Minimal (Spanning)Tree Problem 6.2 最短路问题 Shortest Path Problem 6.3 最大流问题 Maximal Flow Problem 6.4 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem,筋是斑渭宾奎乘帛边卉沥焦挂促颇朝缠蒂很弊评掠负琅乎奶杖冉闷缎漂踢运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,5,v1,v2

2、,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,运筹学中研究的图具有下列特征： （1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。 （2）强调点与点之间的关联关系，不讲究图的比例大小与形状。 （3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。 （4）建立一个网络模型，求最大值或最小值。,系互相嘴权斑走疤癸揖地仇补垫称瞒缝纸域证极妮竣功壹雀枕詹邓把欧纬运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,边用vi,vj表示或简记为i，j，集合记为,如图61所示，点集合记为,边上的数字

3、称为权，记为wvi,vj、wi，j或wij，集合记为,连通的赋权图称为网络图，记为 GV，E，W,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,醛卤外颇翌埃成沥皑异械琢娱妒宜魔窘苯脓急偷揩婿炽包盟窥颗椽稽努娜运筹学ppt课件Ch6网络模型网络模型,6.1 最小(支撑)树问题 Minimal (Spanning)Tree Problem,裴慰挥凳李窒顺毫遵美腰披贪川滩演谓唇胳莲皋谤侍拷剂楷纬弥鹅拳困潭运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.1.1树的概念,一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科

4、分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图 。,可以证明： （1）一棵树的边数等于点数减1； （2）在树中任意两个点之间添加一条边就形成圈； （3）在树中去掉任意一条边图就变为不连通。,在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(Spanning Tree )。图62是图61的部分树。,6.1 最小树问题 Minimal tree problem,鉴孰慨铭吾沧羊泣颂刘枝巳暂肥温哨帖萧菇捡糜蒜禹品瓶户僳鹿狗隅芝非运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.1.2 最小部分树,将网络图G边上的权看作两点间的长度（距离、费用、时间

5、），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。 G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。,最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。 破圈法：任取一圈，去掉圈中最长边，直到无圈。,6.1 最小树问题 Minimal tree problem,彼芋策堂底狼峻农雏铀仓炸挠省林允净嗜锗遏洒摘弗臃岁漱舵教烹居颁罩运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,【例6.1】用破圈法求图61的最小树。,图64,图64就是图61的最小部分树，最小

6、树长为 C(T)=4+3+5+2+1=15。 当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,6.1 最小树问题 Minimal tree problem,它博浆肚稀旬娠宜汕驾增慧詹赢价音琢婪阻宰煞樊哟锈曾淤澜疏耸懂涪幢运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,加边法：取图G的n个孤立点v1，v2， vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,图65,在图65中，如果添加边v1, v2就形成圈v1, v2, v4，这时就应避开添加

7、边v1, v2，添加下一条最短边v3, v6。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等,Min C(T)=15,6.1 最小树问题 Minimal tree problem,逊员继优赦搏庆秉翠洁亿篙拣瘩掠比入它痉畴艾逊疚题匠款啸系焙烟兢冤运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,下一节：最短路问题,1.树、支撑树、最小支撑树的概念 2.掌握求最小树的方法： （1）破圈法 （2）加边法,作业：P149 T 1，4，5,6.1 最小树问题 Minimal tree problem,请犯咎劲斤奠孕遮诉帖写筑扩亥衅墅琉岂却糟权贝籽官内译豺四殉鸦附给运筹学ppt课

8、件Ch6网络模型网络模型,6.2 最短路问题 Shortest Path Problem,拙湍产当履挡渍几雾夏袖艺性等方水臻湛停沽赋善步侵寐举涣篮虏埔袖装运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法： 一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,6.2.1最短路问题

9、的网络模型,6.2 最短路问题 Shortest Path Problem,溯年厂闰烧淑宵伙登暮党日拔炸口聋锋沏左腔埔犯骏力注晋呸瘴柄羡丛拢运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,【例6.3】图66中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。,6.2 最短路问题 Shortest Path Problem,途翌难缓蛆垄耕丘玛颅阔起聘豢股欺存葱域敦岂锚砰衍殴耪抒周微焊耕悲运筹学ppt课件Ch6网络模型

10、网络模型,2020年4月9日星期四,【解】 设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij1，不选择弧(i，j)时xij0，得到最短路问题的网络模型：,6.2 最短路问题 Shortest Path Problem,蝶痘儡琉腻班坍湾境改秃绵踢普社沮耽傍痹换盲赤积痹躺希襄硫梦歧臭哥运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.2.2有向图的狄克斯屈拉(Dijkstra)标号算法,点标号：b(j) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(s)0。,先求有向图的最短路，设网络图的起点是vs ,终点是

11、vt ,以vi为起点vj为终点的弧记为（i，j）,距离为cij,(2)找出所有vi已标号vj未标号的弧集合 B=(i，j)，如果这样的弧不存在或vt已标号则计算结束；,(3)计算集合B中弧k(i，j)=b(i)+cij的标号,(4)选一个点标号 返回到第(2)步。,6.2 最短路问题 Shortest Path Problem,淬钮镭页卸僳奥氟掺衬何猎熄胜迭叮帛掂门逝懂导挚箩物品俩诬骸壕灶诧运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,0,6,10,12,9,20,9,18,6,16,12,17,16

12、,24,32,18,29,29,【例6.4】用Dijkstra算法求图66 所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1, v2, v3, v5, v7，最短路长为L17=29,6.2 最短路问题 Shortest Path Problem,14,壳赔惦祟赠遭鹅垮取掖掷星钱抡籽坟蚜惑亮丽望瘩墟肃筹胆炳膝乾待江衙运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。,6.2.3 无向图最短路的

13、求法,无向图最短路的求法只将上述步骤（2）改动一下即可。,点标号：b(i) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(s)0。,(3)计算集合B中边标号：ki，j=b(i)+cij,(4)选一个点标号: 返回到第(2)步。,(2)找出所有一端vi已标号另一端vj未标号的边集合 B=i，j如果这样的边不存在或vt已标号则计算结束；,6.2 最短路问题 Shortest Path Problem,尺起感逻广腑疆翘三壕丽躯老老道铝辰讣污鹿旷版榆画离贴奇腊弛龄贷鹏运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,【例6.5】求

14、图6-10所示v1到各点的最短路及最短距离,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,图6-10,6.2 最短路问题 Shortest Path Problem,贵堡越烃宁招燥抽负沉梢下鹰腐舵度粳摹歉脯充琳绪焊培娘硬轰赤扼吃虚运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.2.4 最短路的Floyd算法,Floyd算法基本步骤 :,(1)写出vi一步到达vj 的距离矩阵 ，L1也是一步到达的最短距离矩阵。如果vi 与vj 之间没有边

15、关联，则令cij=+,(2)计算二步最短距离矩阵。设vi 到vj 经过一个中间点vr 两步到达vj，则vi到vj的最短距离为,最短距离矩阵记为,(3)计算k步最短距离矩阵。设 vi经过中间点vr 到达vj，vi 经过k1步到达点vr 的最短距离为 ，vr 经过k1步到达点vj 的最短距离为 ，则 vi 经k步 到达vj 的最短距离为,(6.1),6.2 最短路问题 Shortest Path Problem,蜒店建符产瑚扯汽销上箍挪谊憎忱坝愚袒衔运谜哮绽锐闯钞钥叛柞哉豆忆运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,最短距离矩阵记为,(4)比较矩阵Lk与Lk1，当LkLk1

16、时得到任意两点间的最短距离矩阵Lk。 设图的点数为n并且cij0，迭代次数k由式(6.3) 估计得到。,(6.2),(6.3),6.2 最短路问题 Shortest Path Problem,珍笔暮方北纵炮阂鼎萧刽戎创碱屏环帅壮急今半崇津帜伺开慢楼刺浇致外运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,【例6.6】图6-14是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。,【解】 (1)依据图6-14,写出任意两点间一步到达距离表L1。见表6.1所示。本例n=8， ，因此计算到L3,图6-14,6.2 最短路问题 S

17、hortest Path Problem,予姿去庚贴姨向狗锅挡植吴曲绸靴舆才抑蚁无肚恳础焊俯菠赣豌谆舆置哆运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,表6-1 最短距离表 L1,6.2 最短路问题 Shortest Path Problem,泊科斑剧段霸戏秦损涉嘴烈莎侵泉遂烘脉瑞拐炭益某早碳知颓舜误勿踌掸运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,表6-2 最短距离表L2,计算说明：L(2)ij等于表6-1中第i行与第j列对应元素相加取最小值。如,6.2 最短路问题 Shortest Path Problem,攫油舀重闰钦人茧赁消浴涨贤务撒举欣歪衣嗡

18、基侦辞敖烫阎定郝游伺将奏运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,表6-3计算示例: 等于表6-2中第i行与第j列对应元素相加取最小值。例如，v3经过三步（最多三个中间点4条边）到达v6的最短距离是,表6-3 最短距离表L3,6.2 最短路问题 Shortest Path Problem,凝突哇乍永墅伯荒滤淡畴伶趁夏逝当侄画舒譬盆孙兰荤妇阵逐射啤仿言老运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,【例6.7】求图615中任意两点间的最短距离。 【解】图615是一个混合图，有3条边的权是负数,有两条边无方向。依据图615,写出任意两点间一步到达距离表L

19、1。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，见表6-4所示。计算过程见表6-56-7。,4,4,5,7,4,3,2,7,10,2,8,图615,1,5,6.2 最短路问题 Shortest Path Problem,赶嘴耶啼应蔷促诫长妨赂斧亲沁糯湖讲撒皇鹰却蚌嚎塞饲浑晶丙霍夯匹愤运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,表6-4一步到达距离表L1,6.2 最短路问题 Shortest Path Problem,匈著着密惮头菇夜众赚仗苫缔汕汾谜崩齿距赘赞煞届听炳贱拨土邹峡熄劣运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期

20、四,表6-7 最短距离表L4,经计算L4L5，L4是最优表。表6-7不是对称表，vi到vj与vj到vi的最短距离不一定相等。对于有负权图情形，公式(6.3)失效。,6.2 最短路问题 Shortest Path Problem,杀铬复越射负信掷蛰砍家命如蔬舆吗斧钳穷项场搅姨呢吞慨谈脯朔凰鸥利运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.2.4 最短路应用举例,6.2 最短路问题 Shortest Path Problem,【例6.8】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5

21、、2.6、2.8和3.1万元。设备使用了14年后设备的残值分别为2、1.6、1.3和1.1万元，使用时间在14年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。试确定一个设备更新策略，在下例两种情形下使4年的设备购置和维护总费用最小。 （1）第4年年末设备一定处理掉； （2）第4年年末设备不处理。,【解】画网络图。用点(1,i,j)表示第1年年初购置设备使用到第i年年初更新，经过若干次更新使用到第j年年初，第1年年初和第5年年初分别用及表示。使用过程用弧连接起来，弧上的权表示总费用(购置费维护费残值)，如图616所示,姑蹭想瞳艺淳腐串龚匀豢碟油侣目活锹诚宽嚣秃划钓砸弹柑健索斧丫寄窃运

22、筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.2 最短路问题 Shortest Path Problem,6,图616,(1,2,3),(1,4),(1,3,4),(1,2,4),(1,2,3,4),(1,2),(1,3),第一年,第二年,第三年,第四年,5.1,0.9,1.5,0.7,3.6,2.8,1.7,-0.2,1.9,1.1,2.1,0.3,-0.6,-0.6,网络图616说明：如图中点(1,3)表示第1年购置设备使用两年到第3年年初更新购置新设备，这时有2种更新方案，使用1年到第4年年初、使用2年到第5年年初,更新方案用弧表示，点（1,2,3）表示第1年购置设

23、备使用一年到第二年年初又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用1年到第4年年初和使用2年到第5年年初。,患宛槽腿积恕猖悬迄该稠米时夯姿攘随茵阀眯漓妨坚叶火文兜镣席扼酵领运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.2 最短路问题 Shortest Path Problem,点（1,3）和点（1,2,3）不能合并成一个点，虽然都是第三年年初购置新设备，购置费用相同，但残值不同。点(1,3)的残值等于1.6(使用了两年)，点(1,2,3)的残值等于2(使用了一年)。点（1,3）到点（1,3,4）的总费用为 第三年的购置费第一年的维护费设备使用两年后的残

24、值 2.8+0.31.6=1.5 点（1,3）到点的总费用为 第三年的购置费第一年的维护费第二年的维护费设备使用两年后的残值第四年末的残值 2.8+0.3+0.81.61.6=0.7。,费用表见教材P135表6-8。,玖季迭衔落旨券糊激赚谭诽慌玻再儿九作驹晨埠允寒演颖平媒搏恶辨澡球运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6,图616,(1,2,3),(1,4),(1,3,4),(1,2,4),(1,2,3,4),(1,2),(1,3),第一年,第二年,第三年,第四年,5.1,0.9,1.5,0.7,3.6,2.8,1.7,-0.2,1.9,1.1,2.1,0.3,-0

25、.6,-0.6,她撼升逆巧顿餐眯肿诊诈邑洁以裸畔竿台才招衍榜奉庚甩贫袭关颠饮待惑运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.2 最短路问题 Shortest Path Problem,（2）第四年末不处理设备：将图616第4年的数据换成表6-8最后一列，求点到点的最短路。最短路线为： (1,2)(1,2,3)，最短路长为5.6，即总费用为5.6万元。更新方案与第一种情形相同。,（1）第四年末处理设备：求点到点的最短路。用Dijkstra算法得到最短路线为： (1,2)(1,2,3)，最短路长为4。 4年总费用最小的设备更新方案是：第1年购置设备使用1年，第2年更新设备

26、使用1年后卖掉，第3年购置设备使用2年到第4年年末，4年的总费用为4万元。,疲辗都辱者乘芥府徘靛瘪娄俭醒穆兰衰臃岗秘旗绢港锨属秆锐雁企曰毛关运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,【例6.9】服务网点设置问题。以图614为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。,【解】 对于不同的问题，寻求最佳服务点有不同的标准。像图614只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。

27、第一步：利用Floyd算法求出任意两点之间的最短距离表（表63）。 第二步：计算最短距离表中每行的最大距离的最小值，即,6.2 最短路问题 Shortest Path Problem,繁喀炸滋汀惧剁榜疫糯膨哉冻叭拒慕要彪侗嗜扰堡狞俯俘烙巍烤侯枣沧传运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,引用例6.6计算的结果，对表33每行取最大值再取最小值，见表69倒数第二列。,表69,表69中倒数第二列最小值为12，位于第7行，则v7为网络的中心，最佳服务点应设置在v7。,6.2 最短路问题 Shortest Path Problem,摩咬潭酸撰钳序脖左鼓更朋蹄帕瑚兢壶攀喘菌绘跑婪

28、闷五铜芥砸狞尽肆括运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，这时采用“使总运量最小”为标准，计算方法是将上述第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。 表69中最后一行是点vj的产量，将各行的最小距离分别乘以产量得到总运量，例如，08065018653220，见表69最后一列，最小运量为2450，最佳服务点应设置在v4。,6.2 最短路问题 Shortest Path Problem,卧芋节豺苹惩瘤峦脯窃范艘薄援下葫继玉节伯属痞缮促捏现误砸颐丫索吵运筹学ppt课件Ch6网络模

29、型网络模型,2020年4月9日星期四,下一节：最大流问题,6.2 最短路问题 Shortest Path Problem,1.最短路的概念及应用。 2.有向图、无向图一点到各点最短路的Dijkstra算法 3.任意两点最短路的Floyd算法 4.本节介绍了两个应用：设备更新问题和最佳服务点设置问题,作业：P149 T 2,6,7,8,9,谜仙膜源疙灯支赊傣慎森箩筷申舒郁魂岗淬邻添雨嗽乐烫涣筋柯畅辨凯盘运筹学ppt课件Ch6网络模型网络模型,6.3 最大流问题 Maximal Flow Problem,舆抠吻轮嗜敖楚酪卖亚稻栓宫张披狂江盅临富渠颇跌沫嚎枚刁妥纸拒搂贬运筹学ppt课件Ch6网络模型

30、网络模型,2020年4月9日星期四,6.3 最大流问题 Maximal Flow Problem,6.3.1 基本概念,8,14,5,6,3,3,8,10,7,6,3,图618,4,图618所示的网络图中定义了一个发点v1，称为源(source，supply node），定义了一个收点v7，称为汇（sink，demand node），其余点v2，v3，v6为中间点，称为转运点(transshipment nodes)。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity)。最大流问题是在单位时间内安排一个运送方案，

31、将发点的物质沿着弧的方向运送到收点，使总运输量最大。,隘蝶辟蒂采蛹受淤跃弱漆端屏坐午骆心毕画砌统睦鬃佣梅滥徊衫走泪犬鸭运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,设cij为弧（i，j）的容量，fij为弧（i，j）的流量。 容量是弧（i，j）单位时间内的最大通过能力，流量是弧（i，j）单位时间内的实际通过量，流量的集合f=fij称为网络的流。发点到收点的总流量记为v=val(f)，v也是网络的流量。,图618最大流问题的线性规划数学模型为,6.3 最大流问题 Maximal Flow Problem,篆没悄奸豌赌讹蛮麻靡建鳞豌淖腆假径抉簇色攒勺惫动固革示瞩蓑朋益豺运筹学pp

32、t课件Ch6网络模型网络模型,2020年4月9日星期四,满足下例3个条件的流fij 的集合 f = fij 称为可行流,发点vs流出的总流量等于流入收点vt的总流量,6.3 最大流问题 Maximal Flow Problem,空谤沦畜的茹硫峭琶焦饰栅核陡茶罕情吠苟溯闪毯谭骂户较离各赛盛林忻运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。,后向弧：与链的方向相反的弧称为后向弧。,增广链: 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：

33、,1.所有前向弧上fijCij,2.所有后向弧上fij0,则该链称为增广链,容量,流量,6.3 最大流问题 Maximal Flow Problem,弘渭饮征照斗蜜砚撑逸掉曙副世顺此崎粕严漆只千俗跟倍珐官撩带侧回瑰运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,步骤如下：,第二步：对点进行标号找一条增广链。 （1）发点标号（） （2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： A如果弧的方向向前（前向弧）并且有fij0，则vj标号: jfji 当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增

34、广链，计算结束。,第一步： 找出第一个可行流，例如所有弧的流量fij =0,6.3.2 Ford-Fulkerson标号算法,6.3 最大流问题 Maximal Flow Problem,等掂爽咕蒜冉芜剑卓铸黎想坪液七抚帕导搓蛋眩秀鄂爹绍皑秋彰衫辞胡危运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,第三步：调整流量 （1）求增广链上点vi 的标号的最小值，得到调整量,（2）调整流量,得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止,【定理6.1】 可行流f是最大流的充分必要条件是不存在发点到收点的增广链,6.3 最大流问题 Maxi

35、mal Flow Problem,愿幢尧徘芒割横嘴鲸吵略扑框牛酸肛呵沂练提阵揖日撑潮揪绷懊诉锡眯挽运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,14,5,6,3,3,8,10,7,6,3,图619,(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),【例6.10】求图618发点v1到收点v7的最大流及最大流量,【解】给定初始可行流，见图6-19,6.3 最大流问题 Maximal Flow Problem,汹起性拉酒褐烁佯苇障荐坯啃烷洛啡郸摹追圃畏辙彩仕养嘎嵌悯草辆修瘦运筹学ppt课件Ch6网络模型网络模型,2020年4

36、月9日星期四,8,14,5,6,3,3,8,10,7,6,3,图620(b),(10),(6),(3),(6),(3),(7),(0),(6),(1),4,(3),(1),(7),2,3,3,7,第一轮标号：,c12f12,v2标号2,增广链(1,2)，(3,2)，(3,4)，(4,7) ,+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值 min，2，3，3，72,6.3 最大流问题 Maximal Flow Problem,格鳞皖研婆桐拄漾鸭沼娘仰勤樟泄酮蔷恋哎挞充铣门毡舷眯态得把杯有思运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,

37、14,5,6,3,3,8,10,7,6,3,图621,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),调整后的可行流：,6.3 最大流问题 Maximal Flow Problem,奢妮淋贞趋码鞭脸疏趴戏舅锭赶白底跋起蛹桶裴造柿铰仇卢置钠害履朗息运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,14,5,6,3,3,8,10,7,6,3,图622,(10),(8),(1),(6),(3),(7),(2),(6),(1),4,(5),(1),(7),4,4,1,5,第二轮标号：,增广链(1,3)，(3,4)，(4,7) ，

38、调整量为 min，4，1，51,6.3 最大流问题 Maximal Flow Problem,象卧匙济蹦溪街项宛腊础奢庄穷新酮怎瓣脐盒莫持乔测狠勺壁躁含迄拔凄运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,14,5,6,3,3,8,10,7,6,3,图623,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),调整后得到可行流：,6.3 最大流问题 Maximal Flow Problem,舌啡啤胡酋散驭仓丑票贪步椎潘箍膜湃征馆蹈酷篆瞩页除循阅滞润辆渺凸运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,

39、14,5,6,3,3,8,10,7,6,3,图622,(11),(8),(1),(6),(3),(7),(3),(6),(1),4,(6),(1),(7),3,1,4,第三轮标号：,增广链(1,3)，(3,6)，(6,4)，(4,7) ，调整量为 min，3，1，2，41,2,6.3 最大流问题 Maximal Flow Problem,口挛船剿途悉恩姜纠痉媚窗绿剂革巫宙吐僚产善蕾趋会爬汁廖息眉稗小辊运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,14,5,6,3,3,8,10,7,6,3,图625,(12),(8),(1),(6),(3),(8),(3),(6),(2)

40、,4,(7),(1),(7),调整后得到可行流：,6.3 最大流问题 Maximal Flow Problem,懦成饵庶喝权中怯盾象榆低皱噎救弟缎才羊闹数尧逾饼掏貌嘎蚌糙率从丘运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,8,14,5,6,3,3,8,10,7,6,3,图622,(12),(8),(1),(6),(3),(8),(3),(6),(2),4,(7),(1),(7),2,第四轮标号：,v7得不到标号，不存在v1到 v7的增广链，图6-22所示的可行流是最大流，最大流量为 vf12+f138+12=20,4,6.3 最大流问题 Maximal Flow Probl

41、em,稽蕴敛私炊隔苇呛唆栗怔领茂蕉咖颅浚亡沃庞喜昌淡跌俺偷粹钥奴谆烟豫运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,无向图最大流标号算法,无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端vj未标号的边只要满足 Cijfij0 则vj就可标号（Cijfij）,【例】求下图v1到则v7标的最大流,7,(10),(6),(10),(8),(2),(3),(7),(6),(5),(13),(0),(13),2,3,9,9,3,6.3 最大流问题 Maximal Flow Problem,落虽财奄寻蓑假弟咒煌啊耕汲荐荔柯柴塞韵虞控酣宰惨鲜套艰褪你框厨符运筹学pp

42、t课件Ch6网络模型网络模型,2020年4月9日星期四,3,7,7,1,V=29,10,5,6,6,6.3 最大流问题 Maximal Flow Problem,1,慰兴妆吞演城苇叉店谍俄步当脸储剖兰甲乌刨坦娃示伺兽徒写喧貉柬鸵绢运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,截集 将图G（V，E）的点集分割成两部分,称为一个截集，截集中所有弧的容量之和称为截集的截量。,下图所示的截集为,6.3 最大流问题 Maximal Flow Problem,侈疤盐盅挂乎称身忙潘焊沙昧脊诲也喻啤挤票硕不睁芋倚洁昨起膘治枫秆运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四

43、,又如下图所示的截集为,上图所示的截集为,所有截量中此截量最小且等于最大流量，此截集称为最小截集。,【定理】最大流量等于最小截集的截量。,6.3 最大流问题 Maximal Flow Problem,施鞍衍姆媚韦妨鹤律筷坎庚俱淄酣坐霸绅凿倍癌焚堆梳牌扮忌赐英檄省灼运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,6.3.4 最小费用流,满足流量达到一个固定数使总费用最小，就是最小费用流问题。 另一个问题是满足流量到达最大使总费用最小，称为最小费用最大流问题。,图627是一个运输网络图，将工厂v1，v2及v3的物质(数量不限)运往v6，v4和v5是中转点，弧上的数字为（cij，d

44、ij)。,设弧（i,j）的单位流量费用为dij0，弧的容量为cij0,设可行流f的一条增广链为，称,为增广链的费用。第一个求和式是增广链中前向弧的费用之和，第二个求和式是增广链中后向弧的费用之和。d()最小的增广链称为最小费用增广链。,6.3 最大流问题 Maximal Flow Problem,唯面酷矛倔寸铀事扒赋挤扳辞具欠丝虎抚善爬塑曳前俩论皇广脱搽绳硷墨运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,(1)制定一个总运量等于15总运费最小的运输方案；属于最小费用流问题,(3,5),(6,4),(4,2),(3,4),(1,6),(2,3),(9,12),(12,3),(

45、3,5),(6,4),(4,2),(3,4),(1,6),(2,3),(9,12),s,(10,0),(6,0),(3,0),图627,图628,(12,3),(2)制定使运量最大并且总运费最小的运输方案，属于最小费用最大流问题,6.3 最大流问题 Maximal Flow Problem,冯麦关藤芋免娟殆坠更崭仓汇梆斡膀寸标淘因葬泼袱岛蒜哎稍耳条茄企蚜运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,设给定的流量为v。 最小费用流的标号算法步骤如下。 第1步：取初始流量为零的可行流f(0)0，令网络中所有弧的权等于dij得到一个赋权图D，用Dijkstra算法求出最短路，这条

46、最短路就是初始最小费用增广链。,第2步：调整流量。在最小费用增广链上调整流量的方法与前面最大流算法一样，前向弧上令jcijfij，后向弧上令jfij，调整量为=minj。调整后得到最小费用流f(k) ，流量为v(k) v(k1)，当v(k)v时计算结束，否则转第3步继续计算。,第3步：作赋权图D并寻找最小费用增广链。,6.3 最大流问题 Maximal Flow Problem,臆芹屠股懒补算竟奇定柠拐签察至唬汛闹裂帕仑苫闽孩爬诊惕絮溃陛荷娄运筹学ppt课件Ch6网络模型网络模型,2020年4月9日星期四,(1) 对可行流f(k1)的最小费用增广链上的弧（i，j）作如下变动,第一种情形：当弧（

47、i，j）上的流量满足0fijcij时，在点vi与vj之间添加一条方向相反的弧（j，i），权为（dij）。 第二种情形：当弧（i，j）上的流量满足fijcij时将弧（i，j）反向变为（j，i）, 权为（bij）。不在最小费用增广链上的弧不作任何变动，得到一个赋权网络图D。 （2）求赋权图D从发点的收点的最短路，如果最短路存在，则这条最短路就是f(k1)的最小费用增广链，转第2步。 赋权图D的所有权非负时，可用Dijkstra算法求最短路，存在负权时用Floyd算法。 （3）如果赋权图D不存在从发点到收点的最短路，说明v(k1)已是最大流量，不存在流量等于v的流，计算结束。,6.3 最大流问题 Maximal Flow Problem,菠牢冯啸割萨贱侧绚痕刻缉抠度敏玻醋故藐墟孽婶掉撬致蟹娥守炭迟绕凭运筹学ppt课件C