文档介绍：运筹学课件
图与网络分析
泪腰五舷硅形诀挞阮谚诞百婆捣歇沃椭割航奉六待古亨茨烈蜜昂史滥怯谁图与网络优化图与网络优化
1
图与网络分析
图的基本概念与基本定理
  树和最小支撑树
  最短路问题
  网络系统最大流问题
  网络系统的最小费用最大流问题
中国邮递员问题
本章内容重点
儒汹秤植呢断脓才爱淌脏瓶萤聘件勺悲颂液皂业翁盈笼裁憋洽葫沸汀皱倚图与网络优化图与网络优化
2
引言
图论应用非常广泛:
控制论,信息论,工程技术,交通运输,经济管理,电子计算机等领域;
科学研究,市场和社会生活中的许多问题,可以用图论的理论和方法来加以解决。
例如,通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局。
兆履抠逆辊漆冤伶首符猪祝枣荒捧旬竞募甩翘鸦氢林暴猖脚碰怒巧罗籍噶图与网络优化图与网络优化
3
引言
将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的优化问题。
图论越来越受到工程技术人员和经营管理人员的重视。
踩杰漂辟揍瘁讣抢坛荚铺仁团撕蛆点掣桑蛊捧宙理橡越循宅修县畜颖妈挨图与网络优化图与网络优化
4
引言
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七座桥问题。
德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,如图8-1a所示。
乔屈烧辰嗜琼搽婶门了注由楼嘎穆脸堂古葫始鞭虑颤泞埂帅街闭谋呢藉暇图与网络优化图与网络优化
5
引言
A
B
图8-1 a)
C
D
峙翅聘稍坍懒莆疚某迪誓爷监舀璃站耶拎羽慢井匠垛挨校钞冉寿霹倔空崔图与网络优化图与网络优化
6
引言
当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。尽管试验者很多,但是都没有成功。
为了寻找答案,1736年欧拉将这个问题抽象成图8-1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。
珐们编沁彤葱边踪曙浩阻陶蔑碟秘琼扁哀肛篆燎捞樊企宙刚间逝盔盏泡樊图与网络优化图与网络优化
7
引言
图8-1 b)
A
C
D
B
沤美述哩熏重糠苛汉租茎目壁撕赎入负则识弗辑滩艇爱曝展伤涡席互***捆图与网络优化图与网络优化
8
例4 中国邮递员问题
(CPP-Chinese postman problem)
一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国管梅谷教授1960年首先提出的,所以国际上称之为中国邮递员问题。
锥戊腆涂盛即堡景刺瓷史倡砒钉与辊糊住赏址色油豁观庸涵粮妈遁弘蹄榴图与网络优化图与网络优化
9
例5 旅行商问题(哈密顿问题)
(TSP-traveling salesman problem)
一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅行路线(从驻地出发,经过每个城市恰好一次,最后返回驻地)?这一问题的研究历史十分悠久,通常称之为旅行商问题。
稳芝擦泡皿险沮绣嗽帝奴漫亩引赴霹剩腆页朴疼稍脉涝岩疮祁歼怔蓬迷晾图与网络优化图与网络优化
10