《运筹学》课程教学课件（PPT电子教案）第八章 网络模型

凌晨: 第八章网络模型 网络模型的讨论,本质上属于图论范畴 用途极其广泛(如:运输系统设计、信息系统 设计、项目计划管理等)、实用性强,是网络 模型的特征之一,其解法的特殊,也是值得关 注的地方 需要重点掌握:各种网络模型的算法

Ling Xueling 网络模型的讨论，本质上属于图论范畴 用途极其广泛（如：运输系统设计、信息系统 设计、项目计划管理等）、实用性强，是网络 模型的特征之一，其解法的特殊，也是值得关 注的地方 需要重点掌握：各种网络模型的算法。 第八章 网络模型 凌晨: 凌晨:

凌晨: 第一节最短路问题 问题及网络图表示 1、什么是最短路问题 在网络中任意选择某点为起点,求出从此起点到网络中其余 各点的最短路径。如:Taxi的调度问题 2、例子 Gorman建筑公司承担了散布在邻近三个区域内的一些建筑 项目,公司总部与这些工地之间经常有人员、设备、材料等 的运输往来。与运输成本相关的最短路问题,就是很值得考 虑的重要问题 设公司总部与六个工地间的公路网络如下页所示: (单位:km)

Ling Xueling 一、问题及网络图表示 1、什么是最短路问题 在网络中任意选择某点为起点，求出从此起点到网络中其余 各点的最短路径。如：Taxi 的调度问题 2、例子 Gorman 建筑公司承担了散布在邻近三个区域内的一些建筑 项目，公司总部与这些工地之间经常有人员、设备、材料等 的运输往来。与运输成本相关的最短路问题，就是很值得考 虑的重要问题 设公司总部与六个工地间的公路网络如下页所示： ( 单位：km )。 第一节 最短路问题 凌晨: 凌晨:

凌晨: 第一节最短路问题 问题及网络图表示 17 2 15 1 4 6 10 总部 3 4 5 NODE ARC

Ling Xueling 一、问题及网络图表示 第一节 最短路问题 凌晨: 凌晨: 1 2 3 4 5 6 7 总部 1 5 3 1 0 1 7 6 2 4 6 5 4 node arc

凌晨: 第一节最短路问题 最短路算法 介绍 Dijkstra算法 ( Dijkstra于1959年提出,又称加标号法 labeling procedure 1、结点之标号(给出:累计路程、路径两个指标) 20.4 表示从起始结点 表示从起始结点至 到本结点的距离 是20 结点 本结点的最短路仨 上前一个结点是4

Ling Xueling 二 、 最 短 路 算 法 － － 介 绍 Dijkstra 算 法 (Dijkstra 于 1959 年提 出，又称 加标号 法 labeling procedure ) 1、结点之标号(给出：累计路程、路径两个指标) 第一节 最短路问题 凌晨: 凌晨: 20, 4 结点 表示从起始结点 到本结点的距离 是 20 表示从起始结点到 本结点的最短路径 上前一个结点是 4

凌晨: 第一节最短路问题 最短路算法( Dijkstra算法) 、结点标号的分类 1)有/无标号结点 有标号结点一一已指定从起始结点到此结点的一条路径 无标号结点一一未指定从起始结点到此结点的路径 2)永久/临时标号 有永久标号结点一一已求出从起始点到此结点的最短路径 有临时标号结点—一未求出从起始点到此结点的最短路径

Ling Xueling 二、最短路算法（Dijkstra算法） 2、结点标号的分类 1）有/无标号结点 有标号结点－－已指定从起始结点到此结点的一条路径 无标号结点－－未指定从起始结点到此结点的路径 2）永久/临时标号 有永久标号结点－－已求出从起始点到此结点的最短路径 有临时标号结点－－未求出从起始点到此结点的最短路径。 第一节 最短路问题 凌晨: 凌晨:

凌晨: 第一节最短路问题 二、最短路算法( Dijkstra算法) 3、例子的解 1)定起始点,写上永久标号[0,S]-一如:结点内涂黑表 示已有永久标号 2)(迭代)反复以下步骤: (1)为起始点能直达的结点写上临时标号 2)比较临时标号内第一个数,选择小的一个 (3)小者写成永久标号(圈内涂黑) (4)有最新永久标号的结点视为新的起始点

Ling Xueling 二、最短路算法（Dijkstra算法） 3、例子的解 1 ) 定起始点，写上永久标号 [0 ，S]－－如：结点内涂黑表 示已有永久标号 2 ) ( 迭代 ) 反复以下步骤： (1) 为起始点能直达的结点写上临时标号 (2) 比较临时标号内第一个数，选择小的一个 (3) 小者写成永久标号 ( 圈内涂黑 ) (4) 有最新永久标号的结点视为新的起始点。 第一节 最短路问题 凌晨: 凌晨:

凌晨: 第一节最短路问题 最短路算法( Dijkstra算法) 4、求出最短路 41-3 1-3-5-61-3-5-6-7 5、第二个例子 在如下页的网络中,求结点1和结点10之间的最短路径 解 3--5--8--10 total=19

Ling Xueling 二、最短路算法（Dijkstra算法） 4、求出最短路 1－3－2 1－3 1－3－5－4 1－3－5 1－3－5－6 1－3－5－6－7 5、第二个例子 在如下页的网络中，求结点 1 和结点 10 之间的最短路径 解答： 1－－3－－5－－8－－10 total = 19。 第一节 最短路问题 凌晨: 凌晨:

凌晨: 第一节最短路问题 最短路算法( Dijkstra算法) 12 4 5 14 8 5 5 10 6)5 10 12 13 9 10

Ling Xueling 二、最短路算法（Dijkstra算法） 第一节 最短路问题 凌晨: 凌晨: 1 2 3 4 5 6 7 8 9 1 0 2 5 1 1 2 1 4 6 1 0 4 1 3 1 2 1 1 3 9 6 5 8 1 0 5 2

凌晨: 第一节最短路问题 说明 1、算法中,起始结点可以任意选定,N个结点问题, 般需要有N-1次迭代 2、“MS软件包只要先输入网络,可以解决此类问题 3、其它用处:最小旅行时间问题、旅行成本问题、管 道铺设问题、线路安排问题、厂区布局问题、设备更 新问题等等 4、练习的第四题一一设备维护问题说明 5、标号法已发展到可以解决:(时间所限不展开讨论) (1)弧值为负数; )有向网络(如:单行道运输问题)

Ling Xueling 三、说明 1、算法中，起始结点可以任意选定, N 个结点问题， 一般需要有 N－1 次迭代 2、 “MS”软件包只要先输入网络，可以解决此类问题 3、其它用处：最小旅行时间问题、旅行成本问题、管 道铺设问题、线路安排问题、厂区布局问题、设备更 新问题等等 4、练习的第四题――设备维护问题说明 5、标号法已发展到可以解决：(时间所限不展开讨论) (1) 弧值为负数； (2) 有向网络 ( 如：单行道运输问题 )。 第一节 最短路问题 凌晨: 凌晨:

凌晨: 筒二节最小支撑树问题 概念 1、树一一不含圈的联通图 2、什么是(网络)最小支撑树 1)贯通网络所有结点一一支撑 2)分枝(弧)总长度最小一一最小 3、用处:分子结构问题、电网络分析问题、计算机 网络设立问题、管道铺设问题等等的解决

Ling Xueling 一、概念 1、树－－不含圈的联通图 2、什么是（网络）最小支撑树 1) 贯通网络所有结点――支撑 2) 分枝 (弧) 总长度最小――最小 3、用处：分子结构问题、电网络分析问题、计算机 网络设立问题、管道铺设问题等等的解决。 第二节 最小支撑树问题 凌晨: 凌晨: