开云网址·(中国)官方网站

　　开云网址第八讲 网络优化模型ppt第八讲 网络最优化模型 最小费用流模型 最小费用流模型的求解 求解最小费用流问题，实际上就是确定网络图中每条路线上的流量，使总流量所花的费用为最小。因此可以建立纯整数规划数学模型求解（如下图）。 30 50 30 30 50 40 总的费用流：104000（元） 第八讲 网络最优化模型 最小费用流模型 最小费用流模型的求解 与最短路模型一样，可以建立最小费用流求解模型，将图中各条边和每条边上的权数直接录入到求解模型中，实现计算机求解。因此可以称下图就是一个最小费用流问题的数学表述模型。 第八讲 网络最优化模型 最大流模型 最大流模型要解决的问题：对一有向的赋权图中，指定一个发点和一个收点。目标是使通过网络确定各网路上的流量，使发点到收点间总流量为最大。 第八讲 网络最优化模型 最大流模型 例8.4 某石油公司有一个管道网络，使用这个管道网络可以将石油从采油场运送到一些销售点，这个网络的一部分如下图所示。由于管道直径不同，各段管道的流量也不一样，在图中每个弧（每段管道）上标的数字是该段管道的最大流量（吨/小时）。如果使用这个网络系统从采油场VS向销地VT运送石油，每小时最多能运送多少吨石油？ 第八讲 网络最优化模型 最大流模型 最大流模型的基本特征 1、网络中所有流起源于发点（源），所有的流终止于收点（汇） 2、其余的节点叫做转运点 3、通过每一条弧的流只允许沿着弧的箭头方向流动 4、目标是使得从发点（源）到收点（汇）的总流量最大 第八讲 网络最优化模型 最大流模型 最大流模型的求解 求解最大流问题，实际上就是确定网络图中每条路线上的流量，使整个网络中的总流量为最大。因此也可以建立纯整数规划数学模型求解（如下图）。 最优值 max Z=150 30 20 20 30 10 30 0 30 50 40 30 30 40 第八讲 网络最优化模型 最大流模型 与最短路模型一样，可以将图中各条边和每条边是的权数直接录入到求解模型中，实现计算机求解。因此可以称下图就是一个最大流问题的数学表述模型。 最大流模型的求解 第八讲 网络最优化模型 最小费用流模型 例8.5 计划编制问题。某市政工程公司在5～8月份内需完成4项工程：修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳动力见下表。该公司共有劳动力120人，任一工程在一个月内的劳动力投入不能超过80人，问公司应如何分配劳动力以完成所有工程，是否能按期完成？ 工期和所需劳动力 工程 工期 需要劳动力（人） A．地下通道 5～7月 100 B．人行天桥 6～7月 80 C．新建道路 5～8月 200 D．道路维修 8月 80 第八讲 网络最优化模型 最小费用流模型 根据要求可画网络图如下: 图中:s 表示开工 t表示工程结束 5表示月份 6表示月份 7表示月份 8表示月份 A表示工程 B表示工程 C表示工程 D表示工程 第八讲 网络最优化模型 最小费用流模型 求得结果如下表: 每个月的劳动力分配结果 月份 投入劳动力 项目A 项目B 项目C 项目D 5 120 40 80 6 100 40 80 7 120 20 80 8 120 40 80 合计 460 100 80 200 80 最优值: 460 第八讲 网络最优化模型 最小费用最大流模型 最小费用最大流模型要解决的问题：对一有向的赋权图中，指定一个发点和一个收点。目标是在网络中系统中不但要追求运量最大，还要考虑总费用最小 。 第八讲 网络最优化模型 最小费用最大流模型 例8.6 某石油公司有一个管道网络，使用这个管道网络可以将石油从采油场Vs运送到一些销售点Vt，这个网络的一部分如下图所示。由于管道直径不同，输油管道长短也不一样，使得各段管道除了流量不一样外，还有不同的单位流量的费用。图中每条弧（每段管道）旁的括号中，前一个数字是该段管道的最大流量（吨/小时），后一个数字是该段管道的单位流量的费用（元/吨）。如何安排网络各段的流量，使整个网络系统能运送最多的石油并使得总的运送费用最小？ (1,3) (6,6) (2,3) (6,3) (3,2) (2,5) (2,4) (3,4) (2,8) (4,4) (5,7) V4 VT V1 V2 V3 V5 VS 第八讲 网络最优化模型 最小费用最大流模型 最小费用最大流模型的基本特征 1、给定一个带收点和发点的网络 2、每条弧上给出容量 3、每条弧上同时还给出单位流量的费用 4、要求确定网络的最大流量，同时还要使总的费用最小 解决方法: 第一步：先求出此网络系统的最大流量F。 第二步：在最大流量F的所有方案中，选出一个最小费用的方案 第八讲 网络最优化模型 最小费用最大流模型 最小费用最大流模型的求解 求解最小费用最大流问题，实际上就是一个多目标规划问题，而每级目标都建立各自的网络图形式的数学表述模型，用计算机求解。而Excel求解程序模块也与目标规划的求解方法一样，可以将两个目标的模型一次求解（如下图）。 (1,3) (6,6) (2,3) (6,3) (3,2) (2,5) (2,4) (3,4) (2,8) (4,4) (5,7) V4 VT V1 V2 V3 V5 VS 5 5 3 2 2 3 2 1 2 5 3 系统最大流：10 (1,3) (6,6) (2,3) (6,3) (3,2) (2,5) (2,4) (3,4) (2,8) (4,4) (5,7) V4 VT V1 V2 V3 V5 VS 5 5 3 1 2 3 2 1 2 5 3 6 4 3 1 2 3 1 2 2 5 3 第一级（最大流） 第二级（最小费用流） 系统最小费用流：145 第八讲 网络最优化模型 最小费用最大流模型 用表格形式表述该结果 发点 收点 容量 单位费用 最优流量 实际费用 净流量 v1 v2 6 6 4 24 4 v1 v4 6 3 6 18 6 v2 v5 3 4 3 12 v2 v3 2 5 1 5 v3 v5 2 4 2 8 v3 v6 2 3 2 6 v4 v3 3 2 3 6 v4 v6 1 3 1 3 v4 v7 2 8 2 16 -2 v5 v7 5 7 5 35 -5 v6 v7 4 4 3 12 -3 合计 145 10 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型要解决的问题：对给定的无向的赋权图中，确定一个树，目标是该树的各边权数之和为最小 。 第八讲 网络最优化模型 最小支撑树模型 例8.7 某公司铺设光导纤维网络问题。公司的管理层已经决定铺设最先进的光导纤维网络，为公司的主要部门之间提供高速通信（数据、声音和图像）。下图中的节点显示了该公司主要部门（包括公司的总部、巨型计算机、科研区、生产和配送中心等）的分布图。虚线是铺设纤维光缆的可能位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本（单位：万元）。 第八讲 网络最优化模型 最小支撑树模型 需要确定的公司光纤的最小支撑树如下图 树中各边权数之和（该光纤网络所需的成本为）： 1＋1＋2＋2＋2＋2=11（万元） 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的基本特征 1、在网络图中，所有节点构成连通图，但没有回路（圈） 2、构成联通图的边都赋有相应的权数，且边数总比节点数少一个 3、若去掉任意一条边，必变为不连通 4、若不相邻顶点连一条边，恰得一回路（圈） 5、在所有满足上述四条要求的组成方案中，构成树的各边权数之和为最小 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解 贪婪法求解（手工） 破圈法求解（手工） 计算机程序模块求解（基于贪婪法） 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----贪婪法 1、选择第一条边：选择成本最低的备选边 2、选择下一条边：从剩下的边中取一条边满足： （a）最小边；（b）不构成圈。 3、重复步骤2，直到选取的边数为节点数－1。此时就得到了最优解（最小支撑树） 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----贪婪法 该光纤网络所需的成本为：1＋1＋2＋2＋2＋2=11（万元） 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 第八讲 网络最优化模型 最小支撑树模型 最小支撑树模型的求解-----破圈法 该光纤网络所需的成本为：1＋1＋2＋2＋2＋2=11（万元） 第八讲 网络最优化模型 陈士成 主讲TEL 实用管理运筹学 ——基于Excel求解程序和求解模板 第八讲 网络最优化模型 实用管理运筹学------基于Excel求解程序和求解模板 第八讲 网络最优化模型 本讲主要讨论的问题 1、网络最优化模型的基本概念 2、最小支撑树模型 3、最大流模型 4、最小费用流模型 5、最小费用最大流模型 6、最小支撑树模型 第八讲 网络最优化模型 基本概念 图 1、点和边 ● ● ● ● ● ● ● 王(v7) 赵(v1) 钱(v2) 孙(v3) 李(v4) 周(v5) 吴(v6) e3 e1 e2 e5 e4 人群中相互认识关系图------无向图 第八讲 网络最优化模型 基本概念 图 1、点和边 人群中相互认识关系图------无向图（另一种表述形式） ● ● ● ● ● ● ● 王(v7) 赵(v1) 钱(v2) 孙(v3) 李(v4) 周(v5) 吴(v6) e3 e1 e2 e5 e4 第八讲 网络最优化模型 基本概念 图 2、弧 人群中相互认识关系图------有向图 钱(v2) ● ● ● ● ● ● 王(v7) ● 赵(v1) 孙(v3) 李(v4) 周(v5) 吴(v6) a1 a2 a3 a4 a5 a6 a13 a9 a10 a11 a12 a8 a7 第八讲 网络最优化模型 基本概念 图 人群中相互认识关系图------无向赋权图 ● ● ● ● ● ● ● 王(v7) 赵(v1) 钱(v2) 孙(v3) 李(v4) 周(v5) 吴(v6) w23 w12 w13 w67 w34 3、赋权图 第八讲 网络最优化模型 基本概念 图 人群中相互认识关系图------有向赋权图 ● ● ● ● ● ● ● 王(v7) 赵(v1) 钱(v2) 孙(v3) 李(v4) 周(v5) 吴(v6) c43 c12 c21 c13 c31 c23 c32 c34 c56 c67 c76 c47 c35 ● ● ● 3、赋权图 第八讲 网络最优化模型 基本概念 图 4、链 在无向图中，点和边的交替序列，其中点和边不能重复。上图中（v2，v3，v4）就是一条链。 ● ● ● 钱(v2) 孙(v3) 李(v4) e3 e4 第八讲 网络最优化模型 基本概念 图 5、圈 在无向图中，始点和终点重合的链就是一个圈。上图中（v1，v2，v3开云网址·(中国)官方网站，v1）就是一条圈。 ● ● ● 赵(v1) 钱(v2) 孙(v3) e3 e1 e2 第八讲 网络最优化模型 基本概念 图 6、路 在有向图（或无向图）中，点和弧（或边）的交替序列，但点和边均不能重复。上图中（v1，v2，v3，v4）就是一条路。 ● ● ● 赵(v1) 钱(v2) 孙(v3) e3 e1 ● 李(v4) e4 第八讲 网络最优化模型 基本概念 图 7开云网址·(中国)官方网站、 回路 始点和终点重合的路叫做回路。上图中（v3，v5，v6，v7，v4 ，v3）就是一条回路。 王(v7) 孙(v3) 李(v4) 周(v5) 吴(v6) ● ● ● ● ● 第八讲 网络最优化模型 基本概念 图 8、连通图 若一个图中，任意两点之间至少存在一条链，称这样的图为连通图。下图就是一个非连通图。 ● ● ● ● ● ● ● 王(v7) 赵(v1) 钱(v2) 孙(v3) 李(v4) 周(v5) 吴(v6) w23 w12 w13 w67 w34 第八讲 网络最优化模型 基本概念 图 9、树 树就是无圈的连通图 ● ● ● ● ● ● ● 王(v7) 赵(v1) 钱(v2) 孙(v3) 李(v4) 周(v5) 吴(v6) 第八讲 网络最优化模型 基本概念 网络 在赋权的有向图中指定了一点，称为发点（或称为源,记为vs），指定另一点为收点（或称为汇,记为vt），其余的点称为中间点，并把图中的每一条弧的赋权数cij称之为弧（vi，vj）的容量，这样的赋权有向图就称之为网络。 网络最优化问题就是基本于这样的网络，建立相应的网络模型，求最大值或最小值。 第八讲 网络最优化模型 基本概念 网络最优化问题的主要特征 1、最短路模型 2、最小费用流模型 3、最小支撑树模型 4、最大流模型 5、最小费最大流模型 可研究的模型： 第八讲 网络最优化模型 最短路模型 最短路模型要解决的问题：对一有向的赋权图中，指定一个发点vs和一个收点vt 。目标是使通过网络找到一条路，使两点间的总距离为最短。 第八讲 网络最优化模型 最短路模型 例8.1 如下图所示，某人每天从住处S开车到工作地T上班，图中各弧旁的数字表示道路的长度（千米），试问他从家出发到工作地，应选择哪条路线，才能使路上行驶的总距离最短？ 第八讲 网络最优化模型 最短路模型 最短路模型的基本特征 1、在网络中选择一条路，始于发点（源点）,终于收点（目的地） 2、连接两个节点的连线叫做边（允许向任一个方向行进）或弧（只允许沿着一个方向行进） 4、目标是为了寻找从发点到收点的最短路（总长度最小的路） 3、每条边（弧）都有一个相关的非负权数，表示该边（弧）所示的路长 第八讲 网络最优化模型 最短路模型 最短路模型的求解 例8.1中的图中，每两个节点的路线都可以视为有向的，可以将其改画为如下的示意图（将各条边都改为直线段） 第八讲 网络最优化模型 最短路模型 最短路模型的求解 求解最短路问题实际上就是找一条总长度最短的路线，对于这样的最短路问题，可以建立0-1整数规划数学模型求解（如下图）。 第八讲 网络最优化模型 最短路模型 最短路模型的求解 为简化求解过程，可以建立专门的最短路求解模型，用计算机求解：可以将图中各条边和每条边是的权数直接录入到求解模型中，直接得到结果。因此可以称下图就是一个最短路问题的数学表述模型。 第八讲 网络最优化模型 最短路模型 建立最短路模型的关键是画出系统的网络图 第八讲 网络最优化模型 最短路模型 例8.2 设备更新问题。某工厂的某台机器可连续工作5年，决策者在每年年初都要决定机器是否需要更新。若购置新机器，就要支付购置费用；若继续使用，则需要支付维修与运行费用，而且随着机器使用年限的增加费用会逐年增多。已知计划期（5年）中每年的购置价格及维修与运行费用，如下表所示。试制定今后5年的机器更新计划使总的支付费用最少。 购置价格及维修与运行费用 年限 1 2 3 4 5 购置费（万元） 11 11 12 12 13 维修与运行费（万元） 5 6 8 11 18 第八讲 网络最优化模型 最短路模型 设备使用年限总费用分布情况表 单位：万元 终止 费 年份 用 起始年份 1 2 3 4 5 6 1 - 16 22 30 41 59 2 - - 16 22 30 41 3 - - - 17 23 31 4 - - - - 17 23 5 - - - - - 18 6 - - - - - - 第八讲 网络最优化模型 最短路模型 可得网络图 第八讲 网络最优化模型 最短路模型 可得最短路结果 结果为：①→③→⑥，也就是说第一年初购置新机器，使用到第三年底（第四年初）报废；第四年初再购置新机器，使用到第五年底（第六年初）。支付的费用为最少。 最短路径（需支付的最少费用）为：53（万元）。 第八讲 网络最优化模型 最小费用流模型 最小费用流模型要解决的问题：对一有向的赋权图中，指定多个发点和多个收点。目标是使通过网络确定各网路上的流量，使所有发点到所有收点间总流量所花的费用为最小。 第八讲 网络最优化模型 最小费用流模型 例8.3 某公司有两个工厂生产产品开云网址·(中国)官方网站，这些产品需要运送到两个仓库中，其配送网络如下图所示（产品数量单位：件；费用单位：元）。目标是确定一个运输方案（即每条路线运送多少件的产品），使通过配送网络的运输成本最小。 第八讲 网络最优化模型 最小费用流模型 最小费用流模型的基本特征 最小费用流问题的构成(网络表示) 节点 ：包括供应点、需求点和转运点 最小费用流问题的假设 至少一个供应点 至少一个需求点 剩下都是转运点 必须是有向图，各弧容量有限 有足够的弧和容量 每一条弧的流的成本和流量成正比 目标是总成本最小（或总利润最大） 最小费用流问题的解的特征 具有可行解的特征 具有整数解的特征 弧：可行的线路、流量限制、费用。 陈士成 主讲 Email:.cn TEL 实用管理运筹学 ——基于Excel求解程序和求解模板

　　原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者