广工管理运筹学第7章 最短路实例.ppt

§2　最短路问题 例 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 已知：设备每年年初的价格表 设备维修费如下表 §2　最短路问题 解： 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的 设备一直使用到第j年年初。 把所有弧的权数计算如下表： §2　最短路问题 (继上页) 把权数赋到图中，再用Dijkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6 §3　最小生成树问题 树是图论中的重要概念，所谓树就是一个无圈的连通图。 §3　最小生成树问题 §3　最小生成树问题 一、求解最小生成树的破圈算法 算法的步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。 §3　最小生成树问题 例4 用破圈算法求图（a）中的一个最小生成树 §3　最小生成树问题 例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。 §4　最大流问题 最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。 一、最大流的数学模型 例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运送多少加仑石油？ §4　最大流问题 §4　最大流问题 §4　最大流问题 二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和 (b)、(c)和(d)的意义相同。 用以上方法对例6的图的容量标号作改进，得下图 §4　最大流问题 求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 （2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 （3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 用此方法对例6求解： 第一次迭代：选择路为v1 v4 v7 。弧（ v4 , v7 ）的顺流容量为2， 决定了pf=2，改进的网络流量图如下图： §4　最大流问题 第二次迭代：选择路为v1 v2 v5 v7 。弧（ v2 , v5 ）的顺流容量为 3，决定了pf=3，改进的网络流量图如下图： 第三次迭代：选择路为v1 v4 v6 v7 。弧（ v4 , v6 ）的顺流容量为 1，决定了pf=1，改进的网络流量图如下图： §4　最大流问题 第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（ v3 , v6 ）的顺流容 量为2，决定了pf=2，改进的网络流量图如下图： 第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（ v2 , v3 ）的顺流容 量为2，决定了pf=2，改进的网络流量图如下图： §4　最大流问题 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图： §5　最小费用最大流问题 最小费用最大流问题：给了一个带收发点的网络，对每一条