运筹学(七).ppt

第八章 图与网络分析 主要内容： 第一节 图与网络的基本知识 第二节 树 第三节 最短路问题 第四节 最大流问题 第五节 最小费用流问题 第一节 图与网络的基本知识 一、图与网络的基本概念 二、连通图 三、图的矩阵表示 四、欧拉回路与中国邮路问题 第二节 树 一、树的概念和性质 二、图的生成树 三、图的最小生成树 第三节 最 短 路 问 题 一、最短路问题 最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。 最短路径问题的一般提法如下： 设G=（V，E）为连通图，图中各边都有权，vs,vt为图中两个顶点，求一条道路，使它是从vs到vt所有道路中总权最小的道路。 二、Dijkstra算法 步骤： （1）给初始点vs以P标号，P(vs)=0，其余点为T标号，T（vi）=+∞。 （2）若vi为刚得到P标号的点，考虑这样的点vj: (vi,vj)属于E，且vj为T标号。对vj的T标号进行如下修改： T(vj)=min{T(vj)，P(vi)+lij} （3）比较所有具有T标号的点，把最小者该为P标号。返回步骤（2），直到vt为P标号为止。 三、逐次逼近法 求指定点v1到其他任意点vt的最短路（边的权可以为负） 步骤： （1）令 （2） （3）当进行到第t步时，若出现 则停止， 即为v1到各点的最短路长。 四、Floyd算法 五、最短路问题的应用举例 1.设备更新问题 第四节 最 大 流 问 题 一、最大流相关概念 1.容量网络 一、最大流相关概念 2.流 一、最大流相关概念 3. 可行流 4. 最大流 二、最大流-最小割定理 任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。 三、求最大流的标号算法 最短路径问题的求解方法： Dijkstra算法——求解图中指定点vs到其它任意点的最短路，图中所有边的权为非负数。 逐次逼近算法——求解图中指定点vs到其它任意点的最短距离，图中的边可以为负数。 Floyd算法——求解图中任意两点之间的最短距离。 求指定点vs到其他任意点vt的最短路。 V1 V2 V3 V4 V5 V6 V7 6 10 12 3 2 5 5 7 6 9 14 8 11 16 （1）给v1以P标号，P（v1）=0， 给其余点以T标号，T（vi）=+∞ （i=2，…，7） （2）考察点v1，由于（v1，v2），（v1，v3），（v1，v4）属于E，且v2，v3，v4为T标号，因此修改这三个点的标号: （3）比较所有T标号，T（v2）最小，因此令P（v2）=6，并记录路径（v1，v2）。 （4）考察点v2，由于（v2，v3），（v2，v5）属于E，且v3，v5为T标号，因此修改这两个点的标号: （5）比较所有T标号，T（v3）最小，因此令P（v3）=9，并记录路径（v2，v3）。 （6）考察点v3，由于(v3，v4)，(v3，v5)，(v3，v6)属于E，且v4，v5，v6为T标号，因此修改这三个点的标号： （7）比较所有T标号，T（v4）最小，因此令P（v4）=12，且记录路径（v1，v4）。 （9）比较所有T标号，T（v6）最小，因此令P（v6）=16，记录路径（v3，v6）。 （8）考察点v4，由于（v4，v6）属于E，且v6为T标号，因此修改这一个点的标号： （10）考察点v6，由于（v6，v5），（v6，v7）属于E，且v5，v7为T标号，因此修改这两个点的标号： （11）比较所有T标号，T（v5）最小，因此令P（v5）=18，记录路径（v3，v5）。 （12）考察点v5，由于（v5，v7）属于E，且v7为T标号，因此修改这个点的标号： （13）因为只有一个T标号，所以令P（v7）=29，记录路径（v5,v7）。 V1 V2 V3 V4 V5 V6 V7 6 10 12 3 2 5 5 7 6 9 14 8 11 16 （0） （6） （9） （12） （16） （20） （29） 所以，最短路为v1→v2 → v3 → v5 → v7，距离为29。 V1 V2 V3 V4 V5 V6 V7 2 5 -3 -2 7 4 6 4 3 -1 -3 2 4 V8 求下图中v1到其他所有点的最短路： （1）当k=1时， V1 V2 V3 V4 V5 V6 V7 2 5 -3 -2 7 4 6 4 3 -1 -3 2 4 V8 （2）当k=2时，