第5章 网络最优化问题ppt课件.ppt

《第5章 网络最优化问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实用运筹学－运用Excel建模和求解第5章网络最优化问题本章内容要点网络最优化问题的基本概念网络最优化问题的四种主要类型：最小费用流、最大流、最短路、最小支撑树各种网络最优化问题的建模与应用本章节内容5.1网络最优化问题基本概念5.2最小费用流问题5.3最大流问题5.4最短路问题5.5最小支撑树问题5.6货郎担问题和中国邮路问题本章主要内容框架图图论的起源和发展1736年，欧拉的哥尼斯堡七桥问题BACD图论的起源和发展1847年，基尔霍夫，电网络，树”；1852年，《四色猜想》；1964年，华罗庚，《统筹方法平话》。1857年，凯莱，同分异构，“

2、树”；1956年，杜邦公司，CPM，关键路线法；1958年，美国海军部，PERT，计划评审技术；1962年，管梅谷，《中国邮路问题》；1859年，哈密顿，哈密顿回路；几个例子例1是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。北京天津济南青岛武汉南京上海郑州连云港徐州例2旅行商问题/货郎（担）问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久

3、，通常称之为旅行商问题.例3稳定婚配假设有n个男人和n个女人,每人都希望从n个异性中选择一位自己的配偶.假设每人都对n个异性根据自己的偏好进行了排序,以此作为选择配偶的基础.当给定一种婚配方案(即给每人指定一个配偶)后,如果存在一个男人和一个女人不是互为配偶,但该男人喜欢该女人胜过其配偶,且该女人喜欢该男人也胜过其配偶,则该婚配方案称为不稳定的.安排稳定的婚配方案的问题称为稳定婚配问题。5.1网络最优化问题基本概念网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面，网络规划也广泛用于解决不同领域中的各种问题

4、，如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助，广泛应用于科学、社会和经济活动的各个领域中。近些年来，运筹学（管理科学）中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。5.1网络最优化问题基本概念许多研究的对象往往可以用一个图表示，研究的目的归结为图的极值问题。运筹学中研究的图具有下列特征：(1)用点表示研究对象，用连线（不带箭头的边或带箭头的弧）表示对象之间某种关系；(2)强调点与点之间的关联关系，不讲究图的比例大小与形状；

5、(3)每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义；(4)建立一个网络模型，求最大值或最小值。5.1网络最优化问题基本概念v1v3v5v2v4v68736548521对于该网络图，可以提出许多极值问题5.1网络最优化问题基本概念（1）将某个点vi的物资或信息送到另一个点vj，使得运送总成本最小。这属于最小费用流问题。（2）将某个点vi的物资或信息送到另一个点vj，使得总流量最大。这属于最大流问题。（3）从某个点vi出发到达另一个点vj，怎样安排路线使得总距离最短或总费用最小。这属于最短路问

6、题。5.1网络最优化问题基本概念（4）点vi表示自来水厂及用户，vi与vj之间的边表示两点间可以铺设管道，权为vi与vj间铺设管道的距离或费用，极值问题是如何铺设管道，将自来水送到其他5个用户并且使总的费用最小。这属于最小支撑树问题。(5)售货员从某个点vi出发走过其他所有点后回到原点vi，如何安排路线使总路程最短。这属于货郎担问题或旅行售货员问题。（6）邮递员从邮局vi出发要经过每一条边将邮件送到用户手中，最后回到邮局vi，如何安排路线使总路程最短。这属于中国邮递员问题。5.1网络最优化问题基本概念网络最优化问题类型主要包括：（1）最小费用流问题

7、；（2）最大流问题；（3）最短路问题；（4）最小支撑树问题；（5）货郎担问题和中国邮路问题，等等5.2最小费用流问题最小费用流问题的模型在网络最优化中扮演着重要的角色，因为它的适用性很广，并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时，以最小的成本满足需求，一种典型的应用就是使得配送网络的运营最优。最小费用流问题的特殊类型包括运输问题和指派问题，以及在下面将要提到的两种重要类型：最大流问题和最短路问题。5.2最小费用流问题例5.1某公司有两个工厂生产产品，这些产品需要运送到两个仓库中。其配送网络

8、图如图5-2所示。目标是确定一个运输方案（即每条路线运送多少单位的产品），使通过配送网络的总运输成本最小。（50，400）