第八讲网络最优化模型课件.ppt
《第八讲网络最优化模型课件.ppt》由会员分享,可在线阅读,更多相关《第八讲网络最优化模型课件.ppt(62页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第八讲网络最优化模型第1页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型实用管理运筹学实用管理运筹学-基于基于ExcelExcel求解程序和求解模板求解程序和求解模板第2页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型本讲主要讨论的问题本讲主要讨论的问题1 1、网络最优化模型的基本概念、网络最优化模型的基本概念2 2、最小支撑树模型、最小支撑树模型3 3、最大流模型、最大流模型4 4、最小费用流模型、最小费用流模型5 5、最小费用最大流模型、最小费用最大流模型6 6、最小支撑树模型、最小支撑树模型第3页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本
2、概念基本概念图图1 1、点和边、点和边王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)e3e1e2e5e4人群中相互认识关系图人群中相互认识关系图-无向图无向图第4页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图1 1、点和边、点和边人群中相互认识关系图人群中相互认识关系图-无向图(另一种表述形式)无向图(另一种表述形式)王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)e3e1e2e5e4第5页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图2 2、弧、弧人
3、群中相互认识关系图人群中相互认识关系图-有向图有向图钱钱(v2)王王(v7)赵赵(v1)孙孙(v3)李李(v4)周周(v5)吴吴(v6)a1a2a3a4a5a6a13a9a10a11a12a8a7第6页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图人群中相互认识关系图人群中相互认识关系图-无向赋权图无向赋权图王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)w23w12w13w67w343、赋权图、赋权图第7页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图人群中相互认识关系图人群中相互认识关系
4、图-有向赋权图有向赋权图王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)c43c12c21c13c31c23c32c34c56c67c76c47c353、赋权图、赋权图第8页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图4、链、链 在无向图中,点和边的交替序列,其中点和边不在无向图中,点和边的交替序列,其中点和边不能重复。上图中(能重复。上图中(v2,v3,v4)就是一条链。)就是一条链。钱钱(v2)孙孙(v3)李李(v4)e3e4第9页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图5、圈、
5、圈 在无向图中,始点和终点重合的链就是一个圈。上图在无向图中,始点和终点重合的链就是一个圈。上图中(中(v1,v2,v3,v1)就是一条圈。)就是一条圈。赵赵(v1)钱钱(v2)孙孙(v3)e3e1e2第10页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图6、路、路在有向图(或无向图)中,点和弧(或边)的交替序列,在有向图(或无向图)中,点和弧(或边)的交替序列,但点和边均不能重复。上图中(但点和边均不能重复。上图中(v1,v2,v3,v4)就是一条)就是一条路。路。赵赵(v1)钱钱(v2)孙孙(v3)e3e1李李(v4)e4第11页,此课件共62页哦第八讲第
6、八讲 网络最优化模型网络最优化模型基本概念基本概念图图7、回路回路 始点和终点重合的路叫做回路。上图中(始点和终点重合的路叫做回路。上图中(v3,v5,v6,v7,v4,v3)就是一条回路。)就是一条回路。王王(v7)孙孙(v3)李李(v4)周周(v5)吴吴(v6)第12页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图8、连通图、连通图 若一个图中,任意两点之间至少存在一条链,称这若一个图中,任意两点之间至少存在一条链,称这样的图为连通图。下图就是一个非连通图。样的图为连通图。下图就是一个非连通图。王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周
7、周(v5)吴吴(v6)w23w12w13w67w34第13页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念图图9、树、树树就是无圈的连通图树就是无圈的连通图 王王(v7)赵赵(v1)钱钱(v2)孙孙(v3)李李(v4)周周(v5)吴吴(v6)第14页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念网络网络 在在赋权赋权的的有向图有向图中指定了一点,称为发点(或称为源中指定了一点,称为发点(或称为源,记为记为vs),指定另一点为收点(或称为汇),指定另一点为收点(或称为汇,记为记为vt),其余的点称),其余的点称为中间点,并把图中的每一条
8、弧的赋权数为中间点,并把图中的每一条弧的赋权数cij称之为弧(称之为弧(vi,vj)的容量,这样的赋权有向图就称之为网络。)的容量,这样的赋权有向图就称之为网络。网络最优化问题就是基本于这样的网络,建立相应的网网络最优化问题就是基本于这样的网络,建立相应的网络模型,求最大值或最小值。络模型,求最大值或最小值。第15页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型基本概念基本概念网络最优化问题的主要特征网络最优化问题的主要特征1、最短路模型、最短路模型 2、最小费用流模型、最小费用流模型3、最小支撑树模型、最小支撑树模型 4、最大流模型、最大流模型 5、最小费最大流模型、最小费最大
9、流模型 可研究的模型:可研究的模型:第16页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型要解决的问题:最短路模型要解决的问题:对一有向的赋权图中,对一有向的赋权图中,指定一个发点指定一个发点vs和一个收点和一个收点vt。目标是使通过网络找到。目标是使通过网络找到一条路,使两点间的总距离为最短。一条路,使两点间的总距离为最短。第17页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型例例8.1 如下图所示,某人每天从住处如下图所示,某人每天从住处S开车到工作地开车到工作地T上上班,图中各弧旁的数字表示道路的长度(千米),
10、试问班,图中各弧旁的数字表示道路的长度(千米),试问他从家出发到工作地,应选择哪条路线,才能使路上行他从家出发到工作地,应选择哪条路线,才能使路上行驶的总距离最短?驶的总距离最短?第18页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型的基本特征最短路模型的基本特征1、在网络中选择一条路,始于发点(源点)、在网络中选择一条路,始于发点(源点),终于收点(目的终于收点(目的地)地)2、连接两个节点的连线叫做边(允许向任一个方向行进)、连接两个节点的连线叫做边(允许向任一个方向行进)或弧(只允许沿着一个方向行进)或弧(只允许沿着一个方向行进)4、目标是为了
11、寻找从发点到收点的最短路(总长度最、目标是为了寻找从发点到收点的最短路(总长度最小的路)小的路)3、每条边(弧)都有一个相关的非负权数,表示该边、每条边(弧)都有一个相关的非负权数,表示该边(弧)所示的路长(弧)所示的路长第19页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型的求解最短路模型的求解例例8.1中的图中,每两个节点的路线都可以视为有向的,可以中的图中,每两个节点的路线都可以视为有向的,可以将其改画为如下的示意图(将各条边都改为直线段)将其改画为如下的示意图(将各条边都改为直线段)第20页,此课件共62页哦第八讲第八讲 网络最优化模型网络最
12、优化模型最短路模型最短路模型最短路模型的求解最短路模型的求解 求解最短路问题实际上就是找一条总长度最短的路线,求解最短路问题实际上就是找一条总长度最短的路线,对于这样的最短路问题,可以建立对于这样的最短路问题,可以建立0-1整数规划数学模型求整数规划数学模型求解(如下图)。解(如下图)。第21页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型最短路模型的求解最短路模型的求解 为简化求解过程,可以建立专门的最短路求解模型,为简化求解过程,可以建立专门的最短路求解模型,用用计算机求解:可以将图中各条边和每条边是的权数直接录计算机求解:可以将图中各条边和每条边是的权数
13、直接录入到求解模型中,直接得到结果。因此可以称下图就是一个入到求解模型中,直接得到结果。因此可以称下图就是一个最短路问题的数学表述模型最短路问题的数学表述模型。第22页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型建立最短路模型的关键是画出系统的网络图建立最短路模型的关键是画出系统的网络图第23页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型例例8.2 设备更新问题。某工厂的某台机器可连续工作设备更新问题。某工厂的某台机器可连续工作5年,决年,决策者在每年年初都要决定机器是否需要更新。若购置新策者在每年年初都要决定机器是否需要
14、更新。若购置新机器,就要支付购置费用;若继续使用,则需要支付维机器,就要支付购置费用;若继续使用,则需要支付维修与运行费用,而且随着机器使用年限的增加费用会逐修与运行费用,而且随着机器使用年限的增加费用会逐年增多。已知计划期(年增多。已知计划期(5年)中每年的购置价格及维修年)中每年的购置价格及维修与运行费用,如下表所示。试制定今后与运行费用,如下表所示。试制定今后5年的机器更新计年的机器更新计划使总的支付费用最少。划使总的支付费用最少。购置价格及维修与运行费用购置价格及维修与运行费用 年限年限12345购购置置费费(万元)(万元)1111121213维维修与运行修与运行费费(万元)(万元)5
15、681118第24页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型设备使用年限总费用分布情况表设备使用年限总费用分布情况表 单位:万元单位:万元 终终止止 费费 年份年份 用用 起始年份起始年份 1234561-16223041592-162230413-1723314-17235-186-第25页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型可得网络图可得网络图 第26页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最短路模型最短路模型可得最短路结果可得最短路结果 结果为:结果为:,也就是说第一年初购置新机器,
16、使用到第三,也就是说第一年初购置新机器,使用到第三年底(第四年初)报废;第四年初再购置新机器,使用到第五年底年底(第四年初)报废;第四年初再购置新机器,使用到第五年底(第六年初)。支付的费用为最少。(第六年初)。支付的费用为最少。最短路径(需支付的最少费用)为:最短路径(需支付的最少费用)为:53(万元)。(万元)。第27页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型要解决的问题:最小费用流模型要解决的问题:对一有向的赋权图对一有向的赋权图中,指定多个发点和多个收点。目标是使通过网络确中,指定多个发点和多个收点。目标是使通过网络确定各网
17、路上的流量,使所有发点到所有收点间总流量定各网路上的流量,使所有发点到所有收点间总流量所花的费用为最小。所花的费用为最小。第28页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型例例8.3 某公司有两个工厂生产产品,这些产品需要运送到某公司有两个工厂生产产品,这些产品需要运送到两个仓库中,其配送网络如下图所示(产品数量单位:件;两个仓库中,其配送网络如下图所示(产品数量单位:件;费用单位:元)。目标是确定一个运输方案(即每条路线费用单位:元)。目标是确定一个运输方案(即每条路线运送多少件的产品),使通过配送网络的运输成本最小。运送多少件的产品),使通过配
18、送网络的运输成本最小。第29页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型的基本特征最小费用流模型的基本特征最小费用流问题的构成最小费用流问题的构成(网络表示网络表示)节点节点:包括供应点、需求点和转运点:包括供应点、需求点和转运点 最小费用流问题的假设最小费用流问题的假设 至少一个供应点至少一个供应点 至少一个需求点至少一个需求点 剩下都是转运点剩下都是转运点 必须是有向图,各弧容量有限必须是有向图,各弧容量有限 有足够的弧和容量有足够的弧和容量每一条弧的流的成本和流量成正比每一条弧的流的成本和流量成正比 目标是总成本最小(或总利润最
19、大)目标是总成本最小(或总利润最大)最小费用流问题的解的特征最小费用流问题的解的特征 具有可行解的特征具有可行解的特征 具有整数解的特征具有整数解的特征 弧:可行的线路、流量限制、费用。弧:可行的线路、流量限制、费用。第30页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型的求解最小费用流模型的求解 求解最小费用流问题,实际上就是确定网络图中每条求解最小费用流问题,实际上就是确定网络图中每条路线上的流量,使总流量所花的费用为最小。因此可以建路线上的流量,使总流量所花的费用为最小。因此可以建立纯整数规划数学模型求解(如下图)。立纯整数规划数学
20、模型求解(如下图)。305030305040总的费用流:总的费用流:104000(元)(元)第31页,此课件共62页哦第八讲第八讲 网络最优化模型网络最优化模型最小费用流模型最小费用流模型最小费用流模型的求解最小费用流模型的求解 与最短路模型一样,可以建立最小费用流求解模型,将与最短路模型一样,可以建立最小费用流求解模型,将图中各条边和每条边上的权数直接录入到求解模型中,实现图中各条边和每条边上的权数直接录入到求解模型中,实现计算机求解。因此可以称下图就是一个计算机求解。因此可以称下图就是一个最小费用流问题的数最小费用流问题的数学表述模型学表述模型。第32页,此课件共62页哦第八讲第八讲 网络
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 网络 优化 模型 课件
限制150内