《第八讲 网络最优化模型.ppt》由会员分享,可在线阅读,更多相关《第八讲 网络最优化模型.ppt(62页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、陈士成 主讲Email: TEL:13909315693 实用管理运筹学 基于Excel求解程序和求解模板 第八讲第八讲 网络最优化模型网络最优化模型实用管理运筹学实用管理运筹学-基于基于ExcelExcel求解程序和求解模板求解程序和求解模板第八讲第八讲 网络最优化模型网络最优化模型本讲主要讨论的问题本讲主要讨论的问题1 1、网络最优化模型的基本概念、网络最优化模型的基本概念2 2、最小支撑树模型、最小支撑树模型3 3、最大流模型、最大流模型4 4、最小费用流模型、最小费用流模型5 5、最小费用最大流模型、最小费用最大流模型6 6、最小支撑树模型、最小支撑树模型第八讲第八讲 网络最优化模型网
2、络最优化模型基本概念基本概念图图1 1、点和边、点和边王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)e3e1e2e5e4人群中相互认识关系图人群中相互认识关系图-无向图无向图第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图1 1、点和边、点和边人群中相互认识关系图人群中相互认识关系图-无向图(另一种表述形式)无向图(另一种表述形式)王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)e3e1e2e5e4第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图2 2、弧、弧人群中相互认识关系图人群中相互认识
3、关系图-有向图有向图钱钱(v2)王王(v7)赵赵(v1)孙孙(v3)李李(v4)周周(v5)吴吴(v6)a1a2a3a4a5a6a13a9a10a11a12a8a7第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图人群中相互认识关系图人群中相互认识关系图-无向赋权图无向赋权图王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)w23w12w13w67w343、赋权图、赋权图第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图人群中相互认识关系图人群中相互认识关系图-有向赋权图有向赋权图王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v
4、4)周周(v5)吴吴(v6)c43c12c21c13c31c23c32c34c56c67c76c47c353、赋权图、赋权图第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图4、链、链 在无向图中,点和边的交替序列,其中点和边在无向图中,点和边的交替序列,其中点和边不能重复。上图中(不能重复。上图中(v2,v3,v4)就是一条链。)就是一条链。钱钱(v2)孙孙(v3)李李(v4)e3e4第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图5、圈、圈 在无向图中,始点和终点重合的链就是一个圈。在无向图中,始点和终点重合的链就是一个圈。上图中(上图中(v1,v2,v3,v1)
5、就是一条圈。)就是一条圈。赵赵(v1)钱钱(v2)孙孙(v3)e3e1e2第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图6、路、路在有向图(或无向图)中,点和弧(或边)的交替序在有向图(或无向图)中,点和弧(或边)的交替序列,但点和边均不能重复。上图中(列,但点和边均不能重复。上图中(v1,v2,v3,v4)就是一条路。)就是一条路。赵赵(v1)钱钱(v2)孙孙(v3)e3e1李李(v4)e4第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图7、回路回路 始点和终点重合的路叫做回路。上图中(始点和终点重合的路叫做回路。上图中(v3,v5,v6,v7,v4,v3)就是
6、一条回路。)就是一条回路。王王(v7)孙孙(v3)李李(v4)周周(v5)吴吴(v6)第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图8、连通图、连通图 若一个图中,任意两点之间至少存在一条链,称若一个图中,任意两点之间至少存在一条链,称这样的图为连通图。下图就是一个非连通图。这样的图为连通图。下图就是一个非连通图。王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)w23w12w13w67w34第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图9、树、树树就是无圈的连通图树就是无圈的连通图 王王(v7)赵赵(v1)钱钱(v2)孙孙(v
7、3)李李(v4)周周(v5)吴吴(v6)第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念网络网络 在在赋权赋权的的有向图有向图中指定了一点,称为发点(或称为源中指定了一点,称为发点(或称为源,记为记为vs),指定另一点为收点(或称为汇),指定另一点为收点(或称为汇,记为记为vt),其),其余的点称为中间点,并把图中的每一条弧的赋权数余的点称为中间点,并把图中的每一条弧的赋权数cij称称之为弧(之为弧(vi,vj)的容量,这样的赋权有向图就称之为网)的容量,这样的赋权有向图就称之为网络。络。网络最优化问题就是基本于这样的网络,建立相应网络最优化问题就是基本于这样的网络,建立相应的网络模
8、型,求最大值或最小值。的网络模型,求最大值或最小值。第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念网络最优化问题的主要特征网络最优化问题的主要特征1、最短路模型、最短路模型 2、最小费用流模型、最小费用流模型3、最小支撑树模型、最小支撑树模型 4、最大流模型、最大流模型 5、最小费最大流模型、最小费最大流模型 可研究的模型:可研究的模型:第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型要解决的问题:最短路模型要解决的问题:对一有向的赋权图对一有向的赋权图中,指定一个发点中,指定一个发点vs和一个收点和一个收点vt。目标是使通过。目标是使通过网络找到一条路,使
9、两点间的总距离为最短。网络找到一条路,使两点间的总距离为最短。第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型例例8.1 如下图所示,某人每天从住处如下图所示,某人每天从住处S开车到工作地开车到工作地T上班,图中各弧旁的数字表示道路的长度(千米),上班,图中各弧旁的数字表示道路的长度(千米),试问他从家出发到工作地,应选择哪条路线,才能使试问他从家出发到工作地,应选择哪条路线,才能使路上行驶的总距离最短?路上行驶的总距离最短?第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路最短路模型模型的基本特征的基本特征1、在网络中选择一条路,始于发点(源点)、在网络中选择
10、一条路,始于发点(源点),终于收终于收点(目的地)点(目的地)2、连接两个节点的连线叫做边(允许向任一个方向、连接两个节点的连线叫做边(允许向任一个方向行进)或弧(只允许沿着一个方向行进)行进)或弧(只允许沿着一个方向行进)4、目标是为了寻找从发点到收点的最短路(总长度、目标是为了寻找从发点到收点的最短路(总长度最小的路)最小的路)3、每条边(弧)都有一个相关的非负权数,表示该、每条边(弧)都有一个相关的非负权数,表示该边(弧)所示的路长边(弧)所示的路长第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型的求解最短路模型的求解例例8.1中的图中,每两个节点的路线都可以视为
11、有向的,中的图中,每两个节点的路线都可以视为有向的,可以将其改画为如下的示意图(将各条边都改为直线可以将其改画为如下的示意图(将各条边都改为直线段)段)第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型的求解最短路模型的求解 求解最短路问题实际上就是找一条总长度最短的求解最短路问题实际上就是找一条总长度最短的路线,对于这样的最短路问题,可以建立路线,对于这样的最短路问题,可以建立0-1整数规划整数规划数学模型求解(如下图)。数学模型求解(如下图)。第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型的求解最短路模型的求解 为简化求解过程,可以建立专门的
12、最短路求解模为简化求解过程,可以建立专门的最短路求解模型,用型,用计算机求解:可以将图中各条边和每条边是的计算机求解:可以将图中各条边和每条边是的权数直接录入到求解模型中,直接得到结果。因此可权数直接录入到求解模型中,直接得到结果。因此可以称下图就是一个以称下图就是一个最短路问题的数学表述模型最短路问题的数学表述模型。第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型建立最短路模型的关键是画出系统的网络图建立最短路模型的关键是画出系统的网络图第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型例例8.2 设备更新问题。某工厂的某台机器可连续工作设备更新问题。某工厂的某台机
13、器可连续工作5年,决策者在每年年初都要决定机器是否需要更新。年,决策者在每年年初都要决定机器是否需要更新。若购置新机器,就要支付购置费用;若继续使用,则若购置新机器,就要支付购置费用;若继续使用,则需要支付维修与运行费用,而且随着机器使用年限的需要支付维修与运行费用,而且随着机器使用年限的增加费用会逐年增多。已知计划期(增加费用会逐年增多。已知计划期(5年)中每年的购年)中每年的购置价格及维修与运行费用,如下表所示。试制定今后置价格及维修与运行费用,如下表所示。试制定今后5年的机器更新计划使总的支付费用最少。年的机器更新计划使总的支付费用最少。购置价格及维修与运行费用购置价格及维修与运行费用
14、年限年限12345购购置置费费(万元)(万元)1111121213维维修与运行修与运行费费(万元)(万元)5681118第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型设备使用年限总费用分布情况表设备使用年限总费用分布情况表 单位:万元单位:万元 终终止止 费费 年份年份 用用 起始年份起始年份 1234561-16223041592-162230413-1723314-17235-186-第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型可得网络图可得网络图 第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型可得最短路结果可得最短路结果 结果为:结果为:
15、,也就是说第一年初购置新机器,使用到,也就是说第一年初购置新机器,使用到第三年底(第四年初)报废;第四年初再购置新机器,使用到第三年底(第四年初)报废;第四年初再购置新机器,使用到第五年底(第六年初)。支付的费用为最少。第五年底(第六年初)。支付的费用为最少。最短路径(需支付的最少费用)为:最短路径(需支付的最少费用)为:53(万元)。(万元)。第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型要解决的问题:最小费用流模型要解决的问题:对一有向的对一有向的赋权图中,指定多个发点和多个收点。目标是使赋权图中,指定多个发点和多个收点。目标是使通过网络确定各网路上的
16、流量,使所有发点到所通过网络确定各网路上的流量,使所有发点到所有收点间总流量所花的费用为最小。有收点间总流量所花的费用为最小。第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型例例8.3 某公司有两个工厂生产产品,这些产品需要某公司有两个工厂生产产品,这些产品需要运送到两个仓库中,其配送网络如下图所示(产品运送到两个仓库中,其配送网络如下图所示(产品数量单位:件;费用单位:元)。目标是确定一个数量单位:件;费用单位:元)。目标是确定一个运输方案(即每条路线运送多少件的产品),使通运输方案(即每条路线运送多少件的产品),使通过配送网络的运输成本最小。过配送网络的运输成本最小。
17、第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最最小费用流模型小费用流模型的基本特征的基本特征最小费用流问题的构成最小费用流问题的构成(网络表示网络表示)节点节点:包括供应点、需求点和转运点:包括供应点、需求点和转运点 最小费用流问题的假设最小费用流问题的假设 至少一个供应点至少一个供应点 至少一个需求点至少一个需求点 剩下都是转运点剩下都是转运点 必须是有向图,各弧容量有限必须是有向图,各弧容量有限 有足够的弧和容量有足够的弧和容量每一条弧的流的成本和流量成正比每一条弧的流的成本和流量成正比 目标是总成本最小(或总利润最大)目标是总成本最小(或总利润最大)最小费用流问
18、题的解的特征最小费用流问题的解的特征 具有可行解的特征具有可行解的特征 具有整数解的特征具有整数解的特征 弧:可行的线路、流量限制、费用。弧:可行的线路、流量限制、费用。第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型的求解最小费用流模型的求解 求解最小费用流问题,实际上就是确定网络图中求解最小费用流问题,实际上就是确定网络图中每条路线上的流量,使总流量所花的费用为最小。因每条路线上的流量,使总流量所花的费用为最小。因此可以建立纯整数规划数学模型求解(如下图)。此可以建立纯整数规划数学模型求解(如下图)。305030305040总的费用流:总的费用流:104
19、000(元)(元)第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型的求解最小费用流模型的求解 与最短路模型一样,可以建立最小费用流求解模型,与最短路模型一样,可以建立最小费用流求解模型,将图中各条边和每条边上的权数直接录入到求解模型中,将图中各条边和每条边上的权数直接录入到求解模型中,实现计算机求解。因此可以称下图就是一个实现计算机求解。因此可以称下图就是一个最小费用流最小费用流问题的数学表述模型问题的数学表述模型。第八讲第八讲 网络最优化模型网络最优化模型最大流模型最大流模型最大流模型要解决的问题:最大流模型要解决的问题:对一有向的赋权图对一有向的赋权图中
20、,指定一个发点和一个收点。目标是使通过网中,指定一个发点和一个收点。目标是使通过网络确定各网路上的流量,使发点到收点间总流量络确定各网路上的流量,使发点到收点间总流量为最大。为最大。第八讲第八讲 网络最优化模型网络最优化模型最大流模型最大流模型例例8.4 某石油公司有一个管道网络,使用这个管道网络可某石油公司有一个管道网络,使用这个管道网络可以将石油从采油场运送到一些销售点,这个网络的一部分以将石油从采油场运送到一些销售点,这个网络的一部分如下图所示。由于管道直径不同,各段管道的流量也不一如下图所示。由于管道直径不同,各段管道的流量也不一样,在图中每个弧(每段管道)上标的数字是该段管道的样,在
21、图中每个弧(每段管道)上标的数字是该段管道的最大流量(吨最大流量(吨/小时)。如果使用这个网络系统从采油场小时)。如果使用这个网络系统从采油场VS向销地向销地VT运送石油,每小时最多能运送多少吨石油?运送石油,每小时最多能运送多少吨石油?第八讲第八讲 网络最优化模型网络最优化模型最大流模型最大流模型最最大流模型大流模型的基本特征的基本特征1、网络中所有流起源于发点(源),所有的流终止、网络中所有流起源于发点(源),所有的流终止于收点(汇)于收点(汇)2、其余的节点叫做转运点、其余的节点叫做转运点 3、通过每一条弧的流只允许沿着弧的箭头方向流动、通过每一条弧的流只允许沿着弧的箭头方向流动 4、目
22、标是使得从发点(源)到收点(汇)的总流量最大、目标是使得从发点(源)到收点(汇)的总流量最大 第八讲第八讲 网络最优化模型网络最优化模型最大流模型最大流模型最大流模型的求解最大流模型的求解 求解最大流问题,实际上就是确定网络图中每条求解最大流问题,实际上就是确定网络图中每条路线上的流量,使整个网络中的总流量为最大。因此路线上的流量,使整个网络中的总流量为最大。因此也可以建立纯整数规划数学模型求解(如下图)。也可以建立纯整数规划数学模型求解(如下图)。最优值最优值 max Z=150 3030202020203030101030300 0303050504040303030304040第八讲第八
23、讲 网络最优化模型网络最优化模型最大流模型最大流模型 与最短路模型一样,可以将图中各条边和每条边是与最短路模型一样,可以将图中各条边和每条边是的权数直接录入到求解模型中,实现计算机求解。因此的权数直接录入到求解模型中,实现计算机求解。因此可以称下图就是一个可以称下图就是一个最大流问题的数学表述模型最大流问题的数学表述模型。最大流模型的求解最大流模型的求解第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型例例8.5 计划编制问题。某市政工程公司在计划编制问题。某市政工程公司在58月份内需月份内需完成完成4项工程:修建一条地下通道、修建一座人行天桥、项工程:修建一条地下通道、修
24、建一座人行天桥、新建一条道路及道路维修。工期和所需劳动力见下表。新建一条道路及道路维修。工期和所需劳动力见下表。该公司共有劳动力该公司共有劳动力120人,任一工程在一个月内的劳动力人,任一工程在一个月内的劳动力投入不能超过投入不能超过80人,问公司应如何分配劳动力以完成所人,问公司应如何分配劳动力以完成所有工程,是否能按期完成?有工程,是否能按期完成?工期和所需劳动力工期和所需劳动力工程工程工期工期需要需要劳动劳动力(人)力(人)A地下通道地下通道57月月100B人行天人行天桥桥67月月80C新建道路新建道路58月月200D道路道路维维修修8月月80第八讲第八讲 网络最优化模型网络最优化模型最
25、小费用流模型最小费用流模型根据要求可画网络图如下根据要求可画网络图如下:图中图中:s 表示开工表示开工 t表示工程结束表示工程结束 5表示月份表示月份 6表示月份表示月份 7表示月份表示月份 8表示月份表示月份 A表示工程表示工程 B表示工程表示工程 C表示工程表示工程 D表示工程表示工程第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型求得结果如下表求得结果如下表:每个月的劳动力分配结果每个月的劳动力分配结果月份月份投入投入劳动劳动力力项项目目A项项目目B项项目目C项项目目D512040806100 4080712020 8081204080合合计计46010080200
26、80最优值最优值:460第八讲第八讲 网络最优化模型网络最优化模型最小费用最大流模型最小费用最大流模型最小费用最大流模型要解决的问题:最小费用最大流模型要解决的问题:对一有向对一有向的赋权图中,指定一个发点和一个收点。目标是在的赋权图中,指定一个发点和一个收点。目标是在网络中系统中不但要追求运量最大,还要考虑总费网络中系统中不但要追求运量最大,还要考虑总费用最小用最小。第八讲第八讲 网络最优化模型网络最优化模型最小费用最大流模型最小费用最大流模型例例8.6 某石油公司有一个管道网络,使用这个管道网络可以将石某石油公司有一个管道网络,使用这个管道网络可以将石油从采油场油从采油场Vs运送到一些销售
27、点运送到一些销售点Vt,这个网络的一部分如下图所,这个网络的一部分如下图所示。由于管道直径不同,输油管道长短也不一样,使得各段管道示。由于管道直径不同,输油管道长短也不一样,使得各段管道除了流量不一样外,还有不同的单位流量的费用。图中每条弧除了流量不一样外,还有不同的单位流量的费用。图中每条弧(每段管道)旁的括号中,前一个数字是该段管道的最大流量(每段管道)旁的括号中,前一个数字是该段管道的最大流量(吨(吨/小时),后一个数字是该段管道的单位流量的费用(元小时),后一个数字是该段管道的单位流量的费用(元/吨)吨)。如何安排网络各段的流量,使整个网络系统能运送最多的石油。如何安排网络各段的流量,
28、使整个网络系统能运送最多的石油并使得总的运送费用最小?并使得总的运送费用最小?(1,3)(6,6)(2,3)(6,3)(3,2)(2,5)(2,4)(3,4)(2,8)(4,4)(5,7)V4VTV1V2V3V5VS第八讲第八讲 网络最优化模型网络最优化模型最小费用最大流模型最小费用最大流模型最最小费用最大流模型小费用最大流模型的基本特征的基本特征1、给定一个带收点和发点的网络、给定一个带收点和发点的网络 2、每条弧上给出容量、每条弧上给出容量3、每条弧上同时还给出单位流量的费用、每条弧上同时还给出单位流量的费用 4、要求确定网络的最大流量,同时还要使总的费用最小、要求确定网络的最大流量,同时
29、还要使总的费用最小 解决方法解决方法:第一步:先求出此网络系统的最大流量第一步:先求出此网络系统的最大流量F。第二步:在最大流量第二步:在最大流量F的所有方案中,选出一个最小费的所有方案中,选出一个最小费用的方案用的方案 第八讲第八讲 网络最优化模型网络最优化模型最小费用最大流模型最小费用最大流模型最小费用最大流模型的求解最小费用最大流模型的求解 求解最小费用最大流问题,实际上就是一个多目求解最小费用最大流问题,实际上就是一个多目标规划问题,而每级目标都建立各自的网络图形式的标规划问题,而每级目标都建立各自的网络图形式的数学表述模型,用计算机求解。而数学表述模型,用计算机求解。而Excel求解
30、程序模块求解程序模块也与目标规划的求解方法一样,可以将两个目标的模也与目标规划的求解方法一样,可以将两个目标的模型一次求解(如下图)。型一次求解(如下图)。(1,3)(6,6)(2,3)(6,3)(3,2)(2,5)(2,4)(3,4)(2,8)(4,4)(5,7)V4VTV1V2V3V5VS55322321253 系统最大流:系统最大流:10(1,3)(6,6)(2,3)(6,3)(3,2)(2,5)(2,4)(3,4)(2,8)(4,4)(5,7)V4VTV1V2V3V5VS5531232125364312312253 第一级(最大流)第一级(最大流)第二级(最小费用流)第二级(最小费用流
31、)系统最小费用流:系统最小费用流:145第八讲第八讲 网络最优化模型网络最优化模型最小费用最大流模型最小费用最大流模型用表格形式表述该结果用表格形式表述该结果发点发点收点收点容量容量单位费用单位费用最优流量最优流量实际费用实际费用净流量净流量v1v2664244v1v4636186v2v534312v2v32515v3v52428v3v62326v4v33236v4v61313v4v728216-2v5v757535-5v6v744312-3合计合计14510第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最小支撑树模型要解决的问题:最小支撑树模型要解决的问题:对给定的无
32、向对给定的无向的赋权图中,确定一个树,目标是该树的各边权数的赋权图中,确定一个树,目标是该树的各边权数之和为最小之和为最小。第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型例例8.7 某公司铺设光导纤维网络问题。公司的管理层已经某公司铺设光导纤维网络问题。公司的管理层已经决定铺设最先进的光导纤维网络,为公司的主要部门之间决定铺设最先进的光导纤维网络,为公司的主要部门之间提供高速通信(数据、声音和图像)。下图中的节点显示提供高速通信(数据、声音和图像)。下图中的节点显示了该公司主要部门(包括公司的总部、巨型计算机、科研了该公司主要部门(包括公司的总部、巨型计算机、科研区、生
33、产和配送中心等)的分布图。虚线是铺设纤维光缆区、生产和配送中心等)的分布图。虚线是铺设纤维光缆的可能位置。每条虚线旁边的数字表示了如果选择在这个的可能位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本(单位:万元)。位置铺设光缆需要花费的成本(单位:万元)。第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型需要确定的公司光纤的最小支撑树如下图需要确定的公司光纤的最小支撑树如下图 树中各边权数之和(该光纤网络所需的成本为):树中各边权数之和(该光纤网络所需的成本为):112222=11(万元)(万元)第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型
34、最小支撑树模型最最小支撑树模型小支撑树模型的基本特征的基本特征1、在网络图中,所有节点构成连通图,但没有回路(圈)、在网络图中,所有节点构成连通图,但没有回路(圈)2、构成联通图的边都赋有相应的权数,且边数总比节、构成联通图的边都赋有相应的权数,且边数总比节点数少一个点数少一个3、若去掉任意一条边,必变为不连通、若去掉任意一条边,必变为不连通 4、若不相邻顶点连一条边,恰得一回路(圈)、若不相邻顶点连一条边,恰得一回路(圈)5、在所有满足上述四条要求的组成方案中,构成树的、在所有满足上述四条要求的组成方案中,构成树的各边权数之和为最小各边权数之和为最小第八讲第八讲 网络最优化模型网络最优化模型
35、最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解贪婪法求解(手工)贪婪法求解(手工)破圈法求解(手工)破圈法求解(手工)计算机程序模块求解(基于贪婪法)计算机程序模块求解(基于贪婪法)第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-贪婪法贪婪法1、选择第一条边:选择成本最低的备选边、选择第一条边:选择成本最低的备选边 2、选择下一条边:从剩下的边中取一条边满足:、选择下一条边:从剩下的边中取一条边满足:(a)最小边;()最小边;(b)不构成圈。)不构成圈。3、重复步骤、重复步骤2,直到选取的边数为节点数,直到选
36、取的边数为节点数1。此时就得。此时就得到了最优解(最小支撑树)到了最优解(最小支撑树)第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-贪婪法贪婪法该光纤网络所需的成本为:该光纤网络所需的成本为:112222=11(万元)(万元)第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小
37、支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法第八讲第八讲 网络最优化模型网络最优化模型最小支撑树模型最小支撑树模型最最小支撑树模型小支撑树模型的的求解求解-破圈法破圈法该光纤网络所需的成本为:该光纤网络所需的成本为:112222=11(万元)(万元)第八讲第八讲 网络最优化模型网络最优化模型