运筹学教程课件六-图与网路分析.ppt

第六章图与网路分析;;6.1图与网路的根本概念;6.1.2无向图与有向图;6.1.3端点，关联边，相邻，次;6.1.3端点，关联边，相邻，次;6.1.4链，圈，路径，回路，连通图;6.2树图与最小生成树;6.2.1树的定义及其性质;图的生成树;最小生成树;最小生成树;最小生成树;6.3最短路问题;例1狄克斯特拉算法;Dijkstra最短路算法的特点和适应范围;6.3.2Warshall-Floyd算法(1962);例6.3.2求以下图具有负权网络图始点v1到终点v8的最短路径及其长度。;;6.3.4最短路应用举例——市话扩容(实装率=0.8);最短路应用举例—市话扩容;小结;6.4网路的最大流和最小截;6.4.2截集与截集容量;6.4.3确定网路最大流的标号法;6.4.3确定网路最大流的标号法;最大流最小截的标号法步骤;最大流最小截的标号法步骤;最大流最小截集的标号法举例;最大流最小截集的标号法举例;6.4.4多端网路问题;最小费用最大流;6.4.5最小费用最大流

一、根本原理

1、假设f={fi,j}是流量为V(f)的所有可行流中费用最小者，而?是关于f的所有增广链中费用最小的增广链，那么，沿?去调整f得到的可行流f‘就是流量为V(f’)的所有可行流中的最小费用流。这样，当

f‘是最大流时，它就是所求的最小费用最大流。

2、因为dij=0,f={fi,j}=0必是流量为0的最小费用流，因此，可从

f={fi,j}=0开始。

3、给定有向网络G=(V,A)，设f={fi,j}是流量为V(f)的最小费用流，为寻找是关于f的最小费用增广链，构造年一赋权图W(f)，该图的节点与原图G相同，但将网络中的每一弧变成两个相反方向的弧，其权定义如下：;二、根本步骤

1、取初始可行流为f(0)=0；

2、构造W(f(0))并寻找从s到t的最短路，即寻找关于f(0)的最小费用增广链，假设不存在最短路，那么f(0)就是最小费用最大流；假设存在最短路，那么在原网络中得到相应的最小费用增广链?，在?上对f(0)进行调整得f(1)；

3、以f(1)代替f(0)重复2，直到找到最小费用最大流。

三、例6.6求如以下图费用容量网络的最小费用最大流。图中，每一弧的第2个数字表示容量，第1个数字表示单位流量费用。

〔P179-181);以最短路为根底汇总网路上的流;6.5欧拉回路和中国邮递员问题;解中国邮递员问题的步骤;解中国邮递员问题的步骤;6.6哈密尔顿回路及旅行推销员问题;6.6.2旅行推销员问题(TravelingSalesmanProblem);6.7选址问题;1、边上某点到节点的最短距离

dij代表vi与vj间的最短距离，ars代表边(r,s)的边长，令h为边(r,s)上一点的百分位，0?h?1

边上对应h的一点到vj的最短距离为

d[h(r,s),j]=min[h?ars+drj,(1?h)?ars+dsj]

2、节点到某边上最远一点的距离

指定节点j，它到边(r,s)上对应h百分位点有两条路，最远点必使两条路一样长，故有

d[j,(r,s)]=0.5[djr+djs+ars];中心的选择;例