运筹学11-图与网络-1.ppt

* * v2 v3 v4 v5 v6 S1 2 6 ∞ ∞ ∞ v2 3 8 9 ∞ S2 3 8 9 ∞ v3 5 3 ∞ S3 5 3 ∞ v5 ∞ 1 S4 5 1 v6 3 S5 3 * * v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * 11.3 最短路问题 最短路问题的一般提法是：欲寻找网络中从起点υ1到终点υn的最短路线，即寻求连接这两点的边的总长度为最小的通路，最短路线中的网络大都是有向网络，也可以是无向网络。 9 7 5 7 8 4 5 6 4 6 5 4 7 s a b c d e f t * * 最短路问题的狄克斯拉算法 把V分成两个集合 令 计算 求 若vk=vn则已经求得vn到v1的最短路线，否则继续计算 使用条件 lij≥0 * * 算法解释 若以P(vi)记v1到vi的最短距离，则根据动态规划原理应有 第一步 取P(v1)＝0，而T(vj)则是对P(vj)所取的初值； v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * 第二步 利用P(vi)已知，据上式对T(vj)进行修正； v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * 第三步 对T(vj)求 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * k=2, 不是最优，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * 在所有的T(vj)中确定最小的 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * k=3, 不是最优，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * k=5, 不是最优，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * k=6=n, 已经是最优。如果希望计算v1到v4的最短距离，继续 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * 表格实现 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * vj v1 v2 v3 v4 v5 v6 初始值 T( vj ) 0 ∞ ∞ ∞ ∞ ∞ 第一次 P( )+lij 0+2 0+6 0+∞ 0+∞ 0+∞ T( ) 2 6 ∞ ∞ ∞ 第二次 P( )+lij 2+3 2+8 2+9 2+∞ T( ) 5 10 11 ∞ 第三次 P( )+lij 5+5 5+3 5+∞ T( ) 10 8 ∞ 第四次 P( )+lij 8+ ∞ 8+1 T( ) 10 9 * * 福德算法 适用于有负权，但无负回路的有向或无向网络，设dj(k)为从υ1到υj的边数不超过k的路线中距离最短的。 算法依据的思想是动态规划最优性原理，在此处形成递推公式： 其算法步骤如下： 令 计算 若对所有j 则最优，否则把k的值加1，继续计算。 若k=n-1，则说明存在负回路，最短路线不存在。 * * 福德算法示例 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 * * v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 0 2 6 ∞ ∞ ∞ * * v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 0 2 6 ∞ ∞ ∞ 0 2 5(2) 10(2) 9(3) ∞ * * v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ∞ ∞ ∞ 6 2 0 0 2 5(2) 10(2) 9(3) ∞ 10(5) 8(3) 10 5 2 0 0 2 5 10 8 9(5) 0 2 5 10 8 9 * * 例 求：5年内，哪些年初购置新设备，使5年内的总费用最小。 解：（1）分析：可行的购置方案（更新计划）是很多的， 如： 1） 每年购置一台新的，则对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的，一直用到第五年年底，则总费用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的