网络优化模型专题培训课件.ppt

网络优化模型第七章网络优化模型哥尼斯堡七桥问題(BridgesofKoenigsberg)解决七桥问题的欧拉解决七桥问题的方法欧拉路径解決哥尼斯堡七桥问題一笔画定理哈密頓（Hamilton）周遊世界问題实际生活中的图论GraphModel电路模拟交通网络有向道路图某学校网络架构图走迷宫与深度优先搜索(Depth-FirstSearch)第1节图论的基本概念和术语什么是图？图论的术语图的表示法图的表示再來一些术语树Trees树─实例：行政组织图生成树(SpanningTree)有向图(Digraph)加权图(WeightedGraph)一些特殊的图完全图Completegraphs二分图（偶图）Bipartitegraphs平面图Planargraphs更多平面图实例第2节最短路径问題(ShortestPathProblem)最短路问题算法—标号法最短路问题最短路问题最短路问题的一个应用模型最短路问题最短路问题第3节最小生成树问题最小生成树问题最小生成树问题最小生成树问题最小生成树问题第4节最大流问题4最大流问题4最大流问题4最大流问题4最大流问题4最大流问题第四次迭代：选择路为v1v4v3v6v7。弧（v3,v6）的顺流容
量为2，决定了pf=2，改进的网络流量图如下图：

第五次迭代：选择路为v1v2v3v5v7。弧（v2,v3）的顺流容
量为2，决定了pf=2，改进的网络流量图如下图：经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。
最大流量图如下图：

第5节最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题5最小费用最大流问题第6节网络计划技术（关键路径法）关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法关键路径法THEEND