运筹学-图论

《运筹学》任课教师：饶卫振邮箱：[e-mail]手机：[phone]QQ：8316203011图与网络优化引言--图论的起源哥尼斯堡七桥问题11图与网络优化引言--图论的起源莱昂哈德·欧拉（LeonhardEuler，1707年4月15日～1783年9月18日），瑞士数学家、自然科学家。1707年4月15日出生于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡去世。欧拉出生于牧师家庭，自幼受父亲的影响。13岁时入读巴塞尔大学，15岁大学毕业，16岁获得硕士学位。欧拉是18世纪数学界最杰出的人物之一，他不但为数学界作出贡献，更把整个数学推至物理的领域11图与网络优化引言--图论的起源欧拉的解决思路ABCDACBD11图与网络优化引言--图论的起源一笔画问题：任意1个能够1笔画出的点线图，所具有的特征：如果单线图，每个点连接的边数为偶数（欧拉圈），或者仅有两个点连接的边为奇数（欧拉链），那么这个图可以1笔画出。11图与网络优化引言--图论的起源欧拉解决哥尼斯堡七桥问题结论由于该图既不是欧拉圈，也不是欧拉链，因此不能1笔画出。即哥尼斯堡7桥问题无解。ACBD11图与网络优化11.1图的基本概念在实际生活中，点线图可以表示非常多的对象，如实际的交通网络、电力光缆网络、管道网络等，虚拟网络如人际关系网络、信息传播网络等。概念（1）有向图、无向图；（2）点、弧、边；（3）关联边、次；（4）端点、相邻点、环、多重边、简单图、多重图；（5）奇点、偶点、悬挂点、孤立点。定理：任何1个图中奇点的个数必定为偶数个。初等链（圈）、简单链（圈）的概念，例P297图11-9.连通图和不连通图，支撑子图11图与网络优化11.2树的基本概念一个没有圈的连通图为树；包含n个节点的树，一定包括n-1条边11图与网络优化11.3最小支撑树及求解方法任何1个连通加权图，均可能有1个或多个支撑子图为树，其中权重和最小的为最小支撑数，如下图去掉任何1条边，均为该图支撑数，其最小支撑数权重和为9.532432411图与网络优化11.3最小支撑树及求解方法破圈法步骤概述：找到加权连通图中任何1个圈，去掉权重最大的边，不断找到当前图中的圈，重复该步骤，直到图中没有圈为止。53243212最小支撑树的总权重为：3+2+2+2+1=10练习题：P326-图11-3911图与网络优化11.3最小支撑树及求解方法避圈法以P325-11.5为例城市PeTPaMNLPe×T13×Pa5160×M777057×N68673620×L505925534×PaTPeMNL213203450最小支撑树的总权重为：2+13+20+34+50=11911图与网络优化11.4最短路问题Dijkstra算法求解最短路问题的Dijkstra算法ppt求解最短路问题的Dijkstra算法视频L11图与网络优化11.4最短路问题Bellman算法638-2-1-3-5-121-37-5112-1v1v2v5v8v7v4v3v6v1v2v3v4v5v6v7v8v10-1-23v2602v3-30-5v4802v5-10v61017v7-10v8-3-5011图与网络优化11.4最短路问题Bellman算法v1v2v3v4v5v6v7v8t=1t=2v10-1-23v2602v3-30-5v4802v5-10v61017v7-10v8-3-500-1-230-5-2-71-15t=3t=400-5-5-2-2-7-7-3-3-1-1-5-56611图与网络优化11.4最短路问题Bellman算法v1v2v3v4v5v6v7v8t=1t=2v10-1-23v2602v3-30-51v4802v5-10v61017v7-10v8-3-500-1-230-5-2-71-15t=3t=400-5-5-2-2-7-7-3-3-1-1-5-56611图与网络优化11.4最短路问题Bellman算法负回路：如果D为有向图，C是D中的一个回路，且W(C)小于零，那么C是D中的一个负回路。如果D中不含负回路，那么图中任意两点间的最短中间点数量至多为n-2个，即至多迭代n-1次就能求解到某点至其他所有节点的最短路。如果一个有向图D，采用Bellman算法，迭代次数超过t=n-1，仍然不收敛，那么D中存在负回路，不一致的数据没有下界，会无限制减少。11图与网络优化11.4最短路问题最短路练习题P311-例题13P326-11.7和P327-11.8Excel实现11图与网络优化11.5最大流问题应用：交通系统、信息传输系统、管道系统、金融系统。相关概念：发点vs，收点vt，弧的容量，弧的流量（流量小于等于容量）；可行流，最大流，增广链，饱和弧，非饱和弧，零流弧，非零流弧，前向弧，后向弧，截集，截量。概念内容见P313-314定理：任何一个网络中的最大流量等于最小截量。(3,1)vsv1v4vtv6v3v2v5(3,2)(4,2)(6,5)(1,1)(7,6)(1,1)(5,5)(1,0)(3,2)(2,2)(3,3)11图与网络优化11.5最大流问题寻求最大流的标号法P316。vs标号为(0,+∞),v1(vs,1),v4(-v1,1),vt(v4,1),因为vt获得标号，找到一条增广链。调整量为vt标号数字信息，前向弧增加后向弧减少调整量。(3,1)vsv1v4vtv6v3v2v5(3,2)(4,2)(6,5)(1,1)(7,6)(1,1)(5,5)(1,0)(3,2)(2,2)(3,3)(6,6)(1,0)(3,3)(3,2)(3,3)(4,3)当标号法进行不下去时，表示当前网络已经为最大流。11图与网络优化11.6中国邮递员问题由中国学者管梅谷在1962年提出管梅谷教授（1934-），1957年毕业于华东师范大学自1957年至1990年在山东师范大学工作1984年至1990年担任山东师范大学校长1990年至1995年任复旦大学运筹学系主任1995年至今任澳大利亚皇家墨尔本理工大学交通研究中心高级研究员，国际项目办公室高级顾问及复旦大学管理学院兼职教授。11图与网络优化11.6中国邮递员问题问题的提出：邮递员要遍历自己负责的街道，收集邮件，如何在负责的道路上至少行走一遍的前提下，使邮递员从邮局出发，最终回到邮局的总路程最短？如果负责的街道恰好是一个欧拉圈，那么将负责的街道走一遍，刚好是里程最短的。如果存在奇点，通过匹配奇点，将每对奇点之间的路重复一遍，可以得到一个可行解。11图与网络优化11.6中国邮递员问题中国邮递员问题最优解的特征：（1）图的每一边上最多有一条重复边；（2）图中每个圈上的重复边的总权重，不大于该圈总权重的一半。满足以上两特点的可行解，也必定为最优解。中国邮递员问题的求解难点，在于检查特征（2），一个图中的圈数量可能是个天文数字，如“田”字中就有13个圈。10个点的全图，圈的个数1000个，20个100万，30个点10个亿，40个点1万亿个。练习题P328-11.16