§2最短路问题 6.2.4最短路应用举例 【例】设备更新问题。企业在使用某设备时,每年年初可购置 新设备,也可以使用一年或几年后卖掉重新购置新设备。已知4 年年初购置新设备的价格分别为25、26、28和3.1万元。设备 使用了1~4年后设备的残值分别为2、1.6、1.3和11万元,使用 时间在1~4年内的维修保养费用分别为0.3、0.8、1.5和20万元。 试确定一个设备更新策略,在下例两种情形下使4年的设备购置 和维护总费用最小。 (1)第4年年末设备一定处理掉 (2)第4年年末设备不处理。 【解】画网络图。用点(1,表示第1年年初购置设备使用到第 汽年初更新,经过若干次更新使用到第卢年年初,第1年年初和 第5年年初分别用①及⑤表示。使用过程用弧连接起来,弧上的 权表示总费用(购置费+维护费一残值),如图6-16所示 运筹
管 理 运 筹 学 16 §2 最短路问题 6.2.4 最短路应用举例 【例】设备更新问题。企业在使用某设备时，每年年初可购置 新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4 年年初购置新设备的价格分别为2.5、2.6、2.8和3.1万元。设备 使用了1～4年后设备的残值分别为2、1.6、1.3和1.1万元，使用 时间在1～4年内的维修保养费用分别为0.3、0.8、1.5和2.0万元。 试确定一个设备更新策略，在下例两种情形下使4年的设备购置 和维护总费用最小。 （1）第4年年末设备一定处理掉； （2）第4年年末设备不处理。 【解】画网络图。用点(1,i,…,j)表示第1年年初购置设备使用到第 i年年初更新，经过若干次更新使用到第j年年初，第1年年初和 第5年年初分别用①及⑤表示。使用过程用弧连接起来，弧上的 权表示总费用(购置费＋维护费－残值)，如图6－16所示
§2最短路问题 (1,4) 5.1 0.7 1.5 3.6-(1,3) +(1,3,4) -0.6 0.9(1,2,3) →(1,2,3,4) 2.8 0.3 (1,2 (1,2,4) -0.2 L第一年」第二年第三年 第四年 图 6-16 网络图6-16说明:如图中点(1,3表示第1年购置设备使用两年到第3年年初更新 购置新设备,这时有2种更新方案,使用1年到第4年年初、使用2年到第5年年 初,更新方案用弧表示,点(1,2,3)表示第1年购置设备使用一年到第二年年初 又更新,使用一年到第三年初再更新,这时仍然有2种更新方案,使用1年到第 4年年初和使用2年到第5年年初。 运筹
管 理 运 筹 学 17 §2 最短路问题 ① 6 ⑤ 图6－16 (1,2,3) (1,4) (1,3,4) (1,2,4) (1,2,3,4) (1,2) (1,3) 第一年 第二年 第三年 第四年 5.1 0.9 1.5 0.7 3.6 2.8 1.7 -0.2 1.9 1.1 2.1 0.3 -0.6 -0.6 网络图6－16说明：如图中点(1,3)表示第1年购置设备使用两年到第3年年初更新 购置新设备，这时有2种更新方案，使用1年到第4年年初、使用2年到第5年年 初,更新方案用弧表示，点（1,2,3）表示第1年购置设备使用一年到第二年年初 又更新，使用一年到第三年初再更新，这时仍然有2种更新方案，使用1年到第 4年年初和使用2年到第5年年初
§2最短路问题 点(1,3)和点(1,2,3)不能合并成一个点,虽然都是第三年 年初购置新设备,购置费用相同,但残值不同。点(1,3)的残值 等于16(使用了两年),点(1,2,3)的残值等于2(使用了一年)。点 (1,3)到点(1,3,4)的总费用为 第三年的购置费+第一年的维护费一设备使用两年后的残值 =28+0.3-1.6=1.5 点(13)到点⑤的总费用为 第三年的购置费+第一年的维护费+第二年的维护费一设备使 用两年后的残值一第四年末的残值 =28+0.3+08-1.6-1.6=0.7。 管理蓦
管 理 运 筹 学 18 §2 最短路问题 点（1,3）和点（1,2,3）不能合并成一个点，虽然都是第三年 年初购置新设备，购置费用相同，但残值不同。点(1,3)的残值 等于1.6(使用了两年)，点(1,2,3)的残值等于2(使用了一年)。点 （1,3）到点（1,3,4）的总费用为 第三年的购置费＋第一年的维护费－设备使用两年后的残值 ＝2.8+0.3－1.6=1.5 点（1,3）到点⑤的总费用为 第三年的购置费＋第一年的维护费＋第二年的维护费－设备使 用两年后的残值－第四年末的残值 ＝2.8+0.3+0.8－1.6－1.6=0.7
§2最短路问题 (1,4) 5.1 0.7 1.5 3.6-(1,3) +(1,3,4) -0.6 1,2)(,2,3) →(1,2,3,4) 2.8 0.3 (1,2,4) -0.2 L第一年」第二年第三年 第四年 图6-16 (1)第四年末处理设备:求点①到点⑤的最短路。用 Dijkstra 算法得到最短路线为: ①→(1,2)→(1,2,3)⑥,最短路长为4。 4年总费用最小的设备更新方案是:第1年购置设备使用1年, 第2年更新设备使用1年后卖掉,第3年购置设备使用2年到第4年 年末,4年的总费用为4万元9学
管 理 运 筹 学 19 §2 最短路问题 ① 6 ⑤ 图6－16 (1,2,3) (1,4) (1,3,4) (1,2,4) (1,2,3,4) (1,2) (1,3) 第一年 第二年 第三年 第四年 5.1 0.9 1.5 0.7 3.6 2.8 1.7 -0.2 1.9 1.1 2.1 0.3 -0.6 -0.6 （1）第四年末处理设备：求点①到点⑤的最短路。用Dijkstra 算法得到最短路线为： ①→(1,2)→(1,2,3)→⑤，最短路长为4。 4年总费用最小的设备更新方案是：第1年购置设备使用1年， 第2年更新设备使用1年后卖掉，第3年购置设备使用2年到第4年 年末，4年的总费用为4万元
§3最小生成树问题 树是图论中的重要概念,所谓树就是一个无圈的连通图。 (b) a 图11-11 图11,(a)就是一个树,而(b因为图中有圈所以就不 是树,(c)因为不连通所以也不是树。 理蓦总
管 理 运 筹 学 20 §3 最小生成树问题 • 树是图论中的重要概念，所谓树就是一个无圈的连通图。 图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不 是树， (c)因为不连通所以也不是树。 图11-11 v1 v2 v3 v5 v4 v6 v7 v8 v9 v1 v2 v3 v5 v8 v7 v6 v4 v1 v2 v3 v4 v5 v7 v6 v8 v9 (a) (b) (c)