第6章 图与网络分析-终端部分ppt课件.ppt

《第6章 图与网络分析-终端部分ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章图与网络分析终端1：城规问题—迪克斯矩阵应用终端2：网络最小费用流方法的应用期末复习部分终端1：城规问题—迪克斯矩阵应用P178[例5]已知有七个村子和村间距离如图所示。已知七个村子的小学生人数分别为：30，40，25，20，50，60，60。目前需要在七个村子中选择一个村子建小学。请你规划小学应建在哪个村子使得小学生上学走的总路程为最短。v1v4v6v3v7v5v252277624136终端2：最小费用流问题预备知识：（1）求最短路问题。（2）网络最大流问题。最小费用流问题（1）问题的提出最大流问题，只考虑了两点之间弧上的负载量（可行流fij）的容量限制（fi

2、j≤cij）。但是未考虑流量通过各条弧时发生的费用。实际上既要考虑弧的容量限制，又要考虑流量通过时的费用最小。这就是最小费用流要研究的问题。类似于前边讲过的运输问题，按照产销量最大满足，还要考虑总费用最低。如果将单位流量通过弧的费用当成是距离，就等价于求最短距离问题。最小费用流问题（2）模型描述设网络有n个点，fij为（i，j）弧上的流量，cij为该弧的容量，bij为在弧上通过单位流量时的费用。sv3tv2v1最小费用流问题（2）模型描述设网络有n个点，fij为（i，j）弧上的流量，cij为该弧的容量，bij为在弧上通过单位流量时的费用。在图中表示成（cij，bij）

3、sv3tv2v1（5，8）（4，9）（2，5）（8，7）（10，9）（3，2）（8，4）最小费用流问题（3）模型求解给定一个容量—费用网络，即：cij为该弧的容量，bij为在弧上通过单位流量时的费用。在图中表示成（cij，bij），求出最小费用的最大流量sv3tv2v1（5，8）（4，9）（2，5）（8，7）（10，9）（3，2）（8，4）最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第一步：从零流开始，fij=0构造费用bij加权网络。sv3tv2v18957924最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第一步：从零流开始，fij=0构造费

4、用bij加权网络。sv3tv2v18957924求出最小费用路径。以便根据容量cij赋予流量fij最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第一步：从零流开始，fij=0构造费用bij加权网络。sv3tv2v18957924求出最小费用路径。以便根据容量cij赋予流量fij最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第一步：从零流开始，fij=0构造费用bij加权网络。此时fij可调整到3则：流量图sv3tv2v13000033Fij=min{5,3,8}=3最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第二步：从f（s，v1，v3

5、，t）=3开始，构造费用bij加权网络。sv3tv2v18957924最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第二步：从f（s，v1，v3，t）=3开始，构造费用bij加权网络。求出费用的最短路径，再根据容量调整流量。sv3tv2v18957924流量小于容量出现后向弧流量小于容量出现后向弧-8-4最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第二步：从f（s，v1，v3，t）=3开始，构造费用bij加权网络。sv3tv2v189579-24流量小于容量出现后向弧流量小于容量出现后向弧-8-4流量=容量只出现后向弧最小费用流问题—求出最小费用

6、的最大流量（4）模型求解步骤第二步：从f（s，v1，v3，t）=3开始，构造费用bij加权网络。求出费用的最短路径，再根据容量调整流量。sv3tv2v130000-23增加Fij=min{5-3,4}=2最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第二步：从f（s，v1，v3，t）=3开始，构造费用bij加权网络。求出费用的最短路径，再根据容量调整流量。sv3tv2v15200033增加Fij=min{5-3,4}=2最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第三步：从f（s，v1，v3，t）=3开始，加上f（s，v1，t）=2重新开始，构造

7、费用bij加权网络。sv3tv2v1-89579-24-9-4最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第三步：从f（s，v1，v3，t）=3开始，加上f（s，v1，t）=2重新开始，构造费用bij加权网络。求出费用的最短路径，再根据容量调整流量。sv3tv2v15205538最小费用流问题—求出最小费用的最大流量（4）模型求解步骤第三步：从f（s，v1，v3，t）=3开始，加上f（s，v1，t）=2重新开始，构造费用bij加权网络。sv3tv2v1-89579-2-9-4-7-9最小费用流问题—求出最小费用的最大流量（4）模型求解步骤