运筹学：第6章 网络规划

1、第六章 网络规划6.1 图的基本概念6.2 最短路径问题6.3 最长路径问题6.4 最小生成树6.5 运输网络6.6 最大流6.7 最小代价流问题6.1图的基本概念车站之间的连通关系没有改变车站之间的连通关系没有改变, 顶点和边构成的无向图顶点和边构成的无向图地图问题地图问题欧拉环游问题欧拉环游问题18世纪东欧哥尼斯堡城原问题：从岸上任一地方开始，能否通过每座桥一次且仅一次就能回到原地？欧拉证明了该问题没有解，并发表了图论的第一篇数学论文。欧拉证明了该问题没有解，并发表了图论的第一篇数学论文。图论问题：是否可能从某一点出发经过各条边一次且仅一次又回到出发点？一笔画问题。保留了陆地之间的关联关系

2、煤炭调运问题 发点和收点 物资运送方向 结论 一个图可以由一个表示具体事物的点的集合和表示事物之间联系的边的集合组成。 根据边带方向与否，图可分为无向图和有向图。无向图有向图子图与生成子图平行边简单图完备图子图生成子图导出子图1EE1VV11,VV EE网 络 （图）给有向图D=（V，E）， V=v1，v2，vn各边e=（vi，vj）赋予一定的物理量所赋予的物理量叫做权W(e)=W(vi,vj)=wij； 边的权可以是：距离、时间、成本、容量等赋权图D 俗称网络（图）网络规划中涉及的图都是网络图最短路径问题路与路径路与路径最短路径问题问题：如何寻找非负赋权图问题：如何寻找非负赋权图D中，顶点中

3、，顶点v1至各顶点至各顶点vj的的最短路径及其长度？最短路径及其长度？狄克斯特拉算法狄克斯特拉算法看书217页倒数4段。狄克斯特拉算法狄克斯特拉算法 算法特点 非负赋权图 将V1至其他各点最短路全部计算出来。最短路径的子路一定是最短路径最短路径的子路一定是最短路径例题一求出v1到v6最短路网络图里不能有平行边，是简单图。任意两个顶点之间都有两条有向边相连接。是完备图。(v1,v4)的权应当是？计算机中存储。例题一没有回路的连通图-树例题二如求如求v1-v7最短路径，从表中可直接求出。最短路径，从表中可直接求出。建 模每年年初购买一台新设备替换旧的，总费用？第1，3，5年初购买一台新设备替换旧的

4、，总费用？每年可买新设备、可维修，共有25个组合，可以穷举。但如果有60个时段，则260 ，计算机无法穷举。 作业：285页1，2 网络图，表格计算必须完整 图要工整，用尺画285页1第二节第二节 运输网络运输网络一、基本概念二、割、最小割、最大流三、最大流算法第二节第二节 运输网络运输网络一、 基本概念同构图同构图12242016源源汇汇中间顶点中间顶点容量容量C（e） ， f（e）标准化运输网络模型标准化运输网络模型单源单源单汇单汇下一步：如何分配流量，实现下一步：如何分配流量，实现Valf最大？最大？二、割、最小割、最大流1、割、割割为边的集合割为边的集合容量图N的任一流值的任一流值Va

5、lf不能超过任一割的容量不能超过任一割的容量流量最小的割成为网络流的瓶颈，决定着流量最小的割成为网络流的瓶颈，决定着N的最大流值！的最大流值！那么如何才能找到最小割？那么如何才能找到最小割？三 最大流算法方向边不同向，称作链；同向为路；路的顶点只出现一次，成为路径方向边不同向，称作链；同向为路；路的顶点只出现一次，成为路径增流链15-10=56-0=613-7=63=33=313-7=6增流链找到最大流的判定方法既然寻找增流链是关键，既然寻找增流链是关键，那么如何通过计算机寻找增流链？那么如何通过计算机寻找增流链？查视uxxv1v2v5v4v3标记vxv1v2-v5v4v3y标号l(v)+ 5

6、 + 2+2-2-2+2查视uxv1v2v5v4v3标记vxv1v2v5v4v3y标号l(v)+ 5 +5+4-1-1+1查视uxv1v2v5标记vxv1v2v5-标号l(v)+4+4+3书258页12543,Sx v v vSv vy 作业：1、自学例6-282、阅读6.8.1和6.8.2结合C语言思考计算机编程实现的步骤。例6-31 求运输网络图的最大流和最小割查视u标记v标号l(v)例6-31 求运输网络图的最大流和最小割查视u标记v标号l(v)例6-31 求运输网络图的最大流和最小割查视u标记v标号l(v)运输网络建模11223344max,5tttt于是，进一步寻找加工时间小于5小时

7、的加工方案。用最大流算法求得最大流流值为3，不能实现4个机床分别加工4个零件的要求。故（2）步为最优方案。容量图流量图 作业287页15运输网络回顾 增流链运输网络回顾 增流链例6-31 求运输网络图的最大流和最小割查视u标记vx标号l(v)+（1）从）从x开始查视开始查视（2）先标记先查视）先标记先查视（3）调整量比较不加符号）调整量比较不加符号（4）标记行点不可重复）标记行点不可重复例6-31 求运输网络图的最大流和最小割查视u标记vx标号l(v)+（1）从）从x开始查视开始查视（2）先标记先查视）先标记先查视（3）调整量比较不加符号）调整量比较不加符号（4）标记行点不可重复）标记行点不可

8、重复例6-31 求运输网络图的最大流和最小割查视u标记vx标号l(v)+（1）从）从x开始查视开始查视（2）先标记先查视）先标记先查视（3）调整量比较不加符号）调整量比较不加符号（4）标记行点不可重复）标记行点不可重复P258页 最小代价流一、引例则流的代价是？图图 1图图 2图图 3图1的代价?图2的代价?图3的代价?3个图的流值都是个图的流值都是4，但代价却不同，但代价却不同，我们关心流值是我们关心流值是4的最小代价流。的最小代价流。图图 1图图 2图图 3图1的代价为28，不是最小代价流（1）不是最小代价流，图中有何特征？）不是最小代价流，图中有何特征？（2）不是最小代价流，如何改进？）

9、不是最小代价流，如何改进？（3）如何判别是最小代价流？）如何判别是最小代价流？最小代价流二、增流网络存在负回路可调整min 4,4,22算法一NNf 伴随f的增流网络C(e)，w(e)C(e)，f(e)，w(e)111113,2,14,2,23,2,65,0,24,2,2222223,2,14,2,23,0,65,2,24,4,2333333,3,14,1,23,0,65,1,24,4,2此时，图中无负回路，已求出流值为此时，图中无负回路，已求出流值为4的最小代价流。的最小代价流。第一个算法的基本思想：第一个算法的基本思想：（1）任意给出流值为）任意给出流值为 的网络流的网络流（2）作增流网络

10、，通过枚举法找出负回路）作增流网络，通过枚举法找出负回路（3）如有负回路，进行调整；如没有负回路，就找到最小代）如有负回路，进行调整；如没有负回路，就找到最小代价流。价流。 4,-23,0,44,4,23,2,45,2,24,2,2那么，如果在已知流值为流值为4的最小代价流基础上，的最小代价流基础上，希望将流值提高到6，并找出最小代价流，应如何处理？算法二无负回路，已为最小代价流用枚举法，找最短路径3,0,44,4,23,2,45,2,24,2,2边的容量分别为：3, 2, 1取调整量为：14 15 111113,1,44,4,23,3,45,1,24,2,222222此时，已求出流值为此时，

11、已求出流值为6的最小代价流。的最小代价流。边的容量分别为：2, 2可用调整量为：2按本题要求，需要调整量为：15 16 3,1,44,4,23,3,45,1,24,2,23,2,44,4,23,3,45,1,24,3,2第二个算法的算法思想：（1）要求初始流为最小代价流（2）作增流网络（3）找最短路径，取最短路径容量作为调整量进行调整（结合实际要求）3,3,44,4,23,3,45,1,24,4,2527求出流值为求出流值为7的最小代价流。的最小代价流。此时，伴随网络中没有（最短）路径存在了，此时，伴随网络中没有（最短）路径存在了，这时得到了这时得到了最小代价最小代价-最大流最大流。例题 最优

12、分配问题板书作业 ： 作业：15题例题 作业：288页21，22，23，24回顾 最短路径算法 狄克斯特拉算法狄克斯特拉算法有适用的局限性！有适用的局限性！3,0,44,4,23,2,45,2,24,2,2如果在已知流值为流值为4的最小代价流基础上，的最小代价流基础上，希望将流值提高到6，并找出最小代价流，应如何处理？最小代价流最小代价流 算法二算法二无负回路，已为最小代价流用枚举法，找最短路径3,0,44,4,23,2,45,2,24,2,2边的容量分别为：3, 2, 1取调整量为：14 15 11111如果不用枚举法，如何在计算机如果不用枚举法，如何在计算机中寻找带有负权的最短路径呢？中寻

13、找带有负权的最短路径呢？最长路径算法 可以解决找最长路径问题解决许多建模问题 同时可以解决带有负权网络（实数负权图）的最短路径问题最长路径算法VnV1Vi否则算法无意义最长路的性质最长路的性质最长路径算法迭代终止判定方法迭代终止判定方法具体算法例1hkijv1v2v3v4v50011 1011 31241320117132413813412135301171324139132415134545v1至至v4没有边没有边直接相连，我们直接相连，我们给其边权为？给其边权为？算法改进具体算法例1hkijv1v2v3v4v50011-12345v1至至v4没有边没有边直接相连，我们直接相连，我们给其边权为？给其边权为？具体算法例1hkijv1v2v3v4v50011-1011 312413813415134520117132413813415134530117132413913241613245401171324139132416132455v1至至v4没有边没有边直接相连，我们直接相连，我们给其边权为？给其边权为？例2hkijv1v2v3v4v5v6v7v80011-1234例2hkijv1v2v3v4v5v6v7v80011