文档介绍：第5章网络最优化问题第5章网络最优化问题第5章网络最优化问题本章内容要点网络最优化问题的基本概念网络最优化问题的四种主要类型: 最小费用流、最大流、最短路、最小支撑树各种网络最优化问题的建模与应用第5章网络最优化问题本章节内容网络最优化问题基本概念最小费用流问题最大流问题最短路问题最小支撑树问题货郎担问题和中国邮路问题第5章网络最优化问题本章主要内容框架图???????????????????? ?? ?? ?? ??????????????????点连线(边或弧) 基本概念权(赋权图) 网络图最小费用流问题最大流问题网络最优化问题主要类型最短路问题最小支撑树问题货郎担问题和中国邮路问题节点(供应点、转运点、需求点) 净流量建模和求解数学模型电子表格模型第5章网络最优化问题网络最优化问题基本概念?网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面,网络规划也广泛用于解决不同领域中的各种问题,如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。?网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助,广泛应用于科学、社会和经济活动的各个领域中。?近些年来,运筹学(管理科学)中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。第5章网络最优化问题网络最优化问题基本概念?许多研究的对象往往可以用一个图表示,研究的目的归结为图的极值问题。?运筹学中研究的图具有下列特征: ?(1) 用点表示研究对象,用连线(不带箭头的边或带箭头的弧)表示对象之间某种关系; ?(2) 强调点与点之间的关联关系,不讲究图的比例大小与形状; ?(3) 每条边上都赋有一个权,其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义; ?(4) 建立一个网络模型,求最大值或最小值。第5章网络最优化问题网络最优化问题基本概念 v1 v3v5 v2v4v6 8736 5 48 52 1对于该网络图,可以提出许多极值问题第5章网络最优化问题网络最优化问题基本概念?(1 )将某个点 v i 的物资或信息送到另一个点 v j ,使得运送成本最小。这属于最小费用流问题。?(2 )将某个点 v i 的物资或信息送到另一个点 v j ,使得流量最大。这属于最大流问题。?(3 )从某个点 v i 出发到达另一个点 v j ,怎样安排路线使得总距离最短或总费用最小。这属于最短路问题。第5章网络最优化问题网络最优化问题基本概念?(4 )点 v i 表示自来水厂及用户, v i与v j 之间的边表示两点间可以铺设管道,权为 v i与v j 间铺设管道的距离或费用,极值问题是如何铺设管道,将自来水送到其他 5 个用户并且使总的费用最小。这属于最小支撑树问题。?(5) 售货员从某个点 v i 出发走过其他所有点后回到原点 v i ,如何安排路线使总路程最短。这属于货郎担问题或旅行售货员问题。?(6 )邮递员从邮局 v i 出发要经过每一条边将邮件送到用户手中,最后回到邮局 v i ,如何安排路线使总路程最短。这属于中国邮递员问题。第5章网络最优化问题网络最优化问题基本概念?网络最优化问题类型主要包括: ?(1)最小费用流问题; ?(2)最大流问题; ?(3)最短路问题; ?(4)最小支撑树问题; ?(5 )货郎担问题和中国邮路问题,等等