第6篇_网络模型.ppt

第6章 网络模型 6.1 图论导引 6.1.1 图论的基本概念 我们今后只讨论有限简单图： 图的矩阵表示 6.1.2 最短路与最小生成树 求赋权图中任意两点的最短路的Floyd算法： 求赋权图中任意两点的最短路Floyd算法的MATLAB程序： 最小生成树 选址问题 6.2 网络流问题 寻求最大流的方法 6.3最小费用流问题 Ford算法的迭代步骤： 6.4 关键路径问题 PT(Potentialtask graph)图 关键路径(最长路径)算法 PERT图 (4,10,0) (1,8,5) (2,5,5) (6,2,0) (1,7,5) (3,10,0) (2,4,0) v2 v1 v3 vs vt 弧上的数字为 (bij , wij , fij ) 继续构造有向赋权图Df = (V, Af , F) 如下： 4 ?1 ?2 6 1 3 2 v2 v1 v3 vs vt 1 ?1 弧上的数字为 bij 或?bij 4 ?1 ?2 6 1 3 2 v2 v1 v3 vs vt 1 ?1 弧上的数字为 bij 或?bij 用Ford算法求出有向赋权图Df =(V, Af ,F)中发点vs到其它各点的最短路.计算结果如下： ? (v1)=4, ? (v2)=1, ? (v3)=4, ? (vt)=5, ? (v1)=vs, ? (v2)=vs, ? (v3)=v2, ? (vt)=v1. 由? (vt)=v1, ? (v1)=vs, 得vs到vt的最短路 ? = vsv1vt . (10,0) (8,5) (5, 5) (2,0) (7,5) (10,0) (4,0) v2 v1 v3 vs vt 弧上的数字为 (wij , fij ) 增流.上图中? = vsv1vt为前图中vs到vt的最小费用链,调整量? = min{wij ? fij | vivj∈? } =min{10,7?5}=2.增流后的结果如下图： (10,2) (8,5) (5, 5) (2,0) (7,7) (10,0) (4,0) v2 v1 v3 vs vt 弧上的数字为 (wij , fij ) (4,10,2) (1,8,5) (2,5,5) (6,2,0) (1,7,7) (3,10,0) (2,4,0) v2 v1 v3 vs vt 弧上的数字为 (bij , wij , fij ) 继续构造有向赋权图Df = (V, Af , F) 如下： 4 ?1 ?2 6 ?1 3 2 v2 v1 v3 vs vt 1 ?4 弧上的数字为 bij 或?bij 4 ?1 ?2 6 ?1 3 2 v2 v1 v3 vs vt 1 ?4 弧上的数字为 bij 或?bij 用Ford算法求出有向赋权图Df =(V, Af ,F)中发点vs到其它各点的最短路.计算结果如下： ? (v1)=4, ? (v2)=1, ? (v3)=4, ? (vt)=6, ? (v1)=vs, ? (v2)=vs, ? (v3)=v2, ? (vt)=v3. 由? (vt)=v3, ? (v3)=v2, ? (v2)=vs, 得vs到vt的最短路 ? = vsv2v3vt . (10,2) (8,5) (5, 5) (2,0) (7,7) (10,0) (4,0) v2 v1 v3 vs vt 弧上的数字为 (wij , fij ) 增流.上图中? = vsv2v3vt为前图中vs到vt的最小费用链,调整量? = min{wij ? fij | vivj∈? } =min{8?5,10,4}=3.增流后的结果如下图： (10,2) (8,8) (5, 5) (2,0) (7,7) (10,3) (4,3) v2 v1 v3 vs vt 弧上的数字为 (wij , fij ) 在增流前,Wf = 2 + 5 = 7,如果预定的流量值为9,则令? = 2,使增流后Wf 等于预定的流量值9,那么 f 是所求的最小费用流,终止算法.此时总费用b( f )=2×4+7×1+5×2+7×1+2×3+2×2=42. (4,10,2) (1,8,8) (2,5,5) (6,2,0) (1,7,7) (3,10,3) (2,4,3) v2 v1 v3 vs vt 弧上的数字为 (bij , wij , fij ) 继续构造有向赋权图Df = (V, Af , F) 如下： 4 ?1 ?2 6 ?1 3 2 v2 v1 v3