第八讲 网络最优化模型.ppt

1、第八届网络优化模型，实用管理运营学-基于excel求解器和求解模板，第八届网络优化模型，本文主要讨论的问题，1，网络优化模型的基本概念，2，最小支撑树模型，3，最大流模型，4，最小1 赵(v1)、金(v2)、孙(v3)、李(v4)、王(v7)、赵(v1)、金(v2)、孙(v3)、李(v4)、周(v5)、吴(v5)在人群中互相认识的关系图-无向权利图、王(v7)、王(v7)。 在第八届网络优化模型、基本概念、图、图、5、循环、无向图中，起点和终点重叠的链是一个循环。 上图中(v1、v2、v3、v1)为一圈。在第八届网络优化模型、基本概念、图、6、道路、有向图(或无向图)中，点和弧(或边)的交替排

2、列，但点和边不能重叠。 在上图中，(v1、v2、v3、v4)是道路。第八届网络优化模型、基本概念、图、图、7、电路、起点和终点重叠的道路称为电路。 上图中的(v3、v5、v6、v7、v4、v3)是电路。 另外，对于第八网络优化模型、基本概念、图、8、连通图，只要是一个图，在任意2点之间存在至少一条链，并且将这种图称为连通图。 下图为非连通图。 第八次网络优化模型，基本概念，图，9，树，树是无旋转的连通图，、王(v7)、赵(v1)、金钱。 另一点称为收集点(或宿，记为vt )，其馀的点称为中间点，图中各弧的加权数cij称为弧(vi，vj )的容量，这样的加权有向图称为网络。 网络优化问题基本上是

3、基于这种网络构建对应的网络模型，并且获得最大值或最小值。 第八届网络优化模型、基本概念、网络优化问题的主要特征、1、最短模型、2、最小费用流模型、3、最小支撑树模型、4、最大流模型、5、最小费用最大流模型、可研究模型： 目标是通过网络找到一条路，使两点之间的总距离最短。第八届网络优化模型，最短路模型，例8.1如下图所示，有的人每天从家s开车上班到工作单位t，图中各弧旁的数字表示道路的长度(公里)，询问从家到工作单位应该选择哪条路线。第八届网络优化模型、最短路模型、最短路模型的基本特征、1、从网络中选择一条路，将起点(源点)、终点(目的地)、2、连接两个节点的链路称为边(允许向任一方向行进)或3

4、 .边(允许向任一方向行进) 所表示的路径长度，第八次网络优化模型、最短路径模型、最短路径模型的求解，在例8.1的图中，两个节点的路径可以被认为是有向的，可以变更为如下模式图的第八次网络优化模型、最短路径模型、最短路径模型的求解建立了专业的最短求解模型，可以用修正机求解：将图中各边和各边的权重直接输入求解模型，可以得到直接结果。 因此，下图可以说是最短路问题的数学表现模型。 创建第八网络优化模型、最短路模型、最短路模型的关键是创建系统的网络图、第八网络优化模型、最短路模型、例8.2设备更新问题。 有一家工厂的机器可以连续工作五年，决策者必须决定每年年初是否需要更新机器。 如果购买新机器，必须支

5、付购买费用；如果继续使用，必须支付维护和运行成本，并且随着机器使用年限的增加，费用逐年增加。 修订期(5年)的年购买价格、修理和运行成本如下表所示。 制定今后5年的机器更新修订计划，试着使总支付费用达到最小。 购买价格和维修和运行成本，第八次网络优化模型，最短路模型，设备使用年限总费用分布情况表单位：万元，第八次网络优化模型，最短路模型，网络图，第八次网络优化模型，最短路模型第四年初购买新机器支付的费用是最低的。 最短路线(支付的最低费用)为53 (万元)。第八次网络优化模型、最小费用流模型、最小费用流模型需要解决的问题：对有向授权图指定多个发行点和多个接收点。 我们的目标是通过网络确定每个网

6、络上的通信量，并最大限度地减少从所有出发点到所有接收点的总通信量费用。第八届网络优化模型，最小费用流模型，例8.3某公司有两个工厂生产产品，这些产品需要运输到两个仓库，其配送网络如下图所示(产品数量单位：件； 费用单位：元)。 目标是确定一个运输方案(即通过每条路线运输多少个产品)，以最大限度地减少通过运输网络的运输成本。第八次网络优化模型、最小费用流模型、最小费用流模型的基本特征、最小费用流问题的配置(网络表示)、节点：供应点、需求点和运输点、最小费用流问题的假设、至少一个供应点、至少一个需求点目标包括总成本最小(或总利润最大)、最小费用流问题解的特征、可行解的特征、整数解的特征、弧：可行线

7、路、流量限制、费用。、第八次网络优化模型、最小费用流模型、最小费用流模型的求解、解决最小费用流问题，实际确定网络图的各路径上的通信量，使总通信量花费最小。 因此，可以创建纯整数修正图数学模型的解，如下图所示。 总费用流： 104000 (元)、第八次网络优化模型、最小费用流模型、最小费用流模型的求解与最短路模型一样，建立最小费用流求解模型，将图中各边和各边的权重直接输入到求解模型中，实现修正计算机求解。 因此，下图可以说是最小费用流问题的数学表示模型。第八届网络优化模型、最大流模型、最大流模型需要解决的问题：在有向授权地图中指定发起点和接收点。 我们的目标是通过网络确定每个网络上的通信量，使从

8、出发点到接收点的总通信量最大化。第八届网络优化模型、最大流量模型，例8.4某石油公司拥有管线网络，可以使用该管线网络将石油从采油厂运到几个销售点，该网络的一部分如下图所示。 根据配管的直径，各段配管的流量也不同。 图中各圆弧(各段配管)显示的数字是该段配管的最大流量(吨/小时)。 使用该网络系统从采油厂VS向销售地VT输送石油，每小时最多可以输送多少吨石油，第八次网络优化模型，最大流量模型，最大流量模型的基本特征是，1，网络中的所有流量都是起点(来源2、其馀的节点称为运输点，3、通过各弧的流仅沿弧的箭头方向流动，因此，如下图所示，也可建立纯整数修正图数学模型进行解决。 最佳值maxz=150，

9、30，20，20，30，10，30，0，30，50，40，30，30，40，第八次网络优化模型，最大流，因此下面的视图可以说是最大流问题的数学表示模型。 求解最大流模型，第八次网络优化模型，最小费用流模型，例8.5修订编制问题。 一家市政工程公司需要在5月8日完成4项工程：地下通道建设、人行横道建设、道路和道路建设。 工期和所需劳动力如下表所示。 该公司劳动力120人，任何工程一个月内的劳动力投入不得超过80人。 公司如何分配劳动力完成所有工程，能否按时完成？ 工期和必要劳动力、第八次网络优化模型、最小费用流模型、可按需绘制的网络图如下： 图中33:s表示工程结束5、月6、月7、月8、月a、工

10、程b、工程d、工程d，求出第八次网络优化模型、最小费用流模型，结果如下表3360每月的劳动力分配结果、最佳值3360 最小费用最大流模型、最小费用最大流模型需要解决的问题：在有向权限图中指定发行点和接收点。 目标是在网络内的系统中不仅运输量最大，而且总费用最小。 第八届网络优化模型、最小费用最大流模型，例8.6某石油公司拥有管线网络，可以使用该管线网络将石油从采油厂Vs输送到几个销售点Vt，该网络的一部分如下图所示。 由于管径不同，管线的长度也不同，所以各段的管线除了流量不同外，每单位流量的费用也不同。在图中各圆弧(各管)旁边的括弧中，前面的数字是该段管的最大流量(吨/小时)，下面的数字是该段

11、管的单位流量的费用(meta /吨)。 网络系统中运输石油最多，总运输费用最低，如何安排网络各段的通信量第八次网络优化模型，最低费用最大流模型，最低费用最大流模型的基本特征是1，1个接收点2、给一个弧施加容量，3、给一个弧同时施加单位流量的费用，4、在确定网络最大流量的同时，使总费用最小化的第二步：在最大流量f的所有方案中，选择最小费用的方案，第八次网络优化模型，最小费用最大流模型，最小费用最大流模型解决最小费用最大流问题，其实是多目标修订画问题，各级目标建立各自的网图形式的数学表现模型，用修正计算机解决。 以与目标修正像素的求解方法类似的方式，Excel求解器模块也可以一次求解两个目标模型(

12、如下图)。 系统最大流程： 10、第一级(最大流程)、第二级(最小费用流程)、系统最小费用流程： 145、第八次网络优化模型、最小费用最大流程模型以表格形式表示，第八次网络优化模型、最小支撑树模型、第八次网络最大公司管理层已经决定建设最先进的光纤网络，在公司主要部门之间提供高速通信(数据、语音、图像)。 下图中的节点显示了该公司主要部门(包括总部、巨型计算机、科研区、生产和配送中心等)的分布图。 虚线是可能铺设纤维光缆的位置。 每条虚线旁边的数字表示选择在此位置敷设光缆所需的成本(单位：万美元)。 第八届网络优化模型、最小支撑树模型、应确定的公司光纤最小支撑树如下图所示。 树中各边的权重之和(该光纤网络所需的成本):112222=11 (万元)，第八次网络优化模型，最小支撑树模型，最小支撑树模型的基本特征2 .构成连通图的边都加权相应的权重，而且边的数量是总节点的数量除去任何一条边必定是不连通的，4、邻接顶点如果不连接一条边，正好回路(环)，5、在满足上述四个要求的所有构成方案中，构成树的破圈法求解(手动)、修正机程序模块求解(基于贪婪法)、第八回网最小支撑树模型的求解-贪婪法，选择1，第一条边：选择成本最低的候补边，选择2，不构成下一个(b )轮