图与网络分析

第八章 图与网络分析

也叫网络规划。我们讲三个问题:最短路问题,最大流问题,最小费用最大流问题。

第一讲: 最短路问题(与上章设备更新凑成一讲)

最短路问题是网络理论中应用最广泛的问题之一。许多优化问题都可以使用这个模型,如设备更新、管道的铺设、线路的安排、厂区的布局等。

最短路问题的一般提法是:设G?(V,E)为连通图,图中各边(vi,vj)有权lij(lij=∞表示vi,vj之间没有边),vs,vt为图中任意两点,求一条道路?,使它是从vs到vt的所有路中总权最小的路。即:L(?)=

(vi,vj)??l?。

ij最短路算法中1959年由Dijkstra(狄克斯特洛)提出的算法被公认为是目前最好的方法,我们称之为Dijkstra算法。下面通过例子来说明此法的基本思想。

条件:所有的权数lij≥0。 思路:逐步探寻。

v2(4) 5 4 4 v1(0) 4 6 v3(6) 7 下求v1到v8的最短路:

1) 从v1出发,向v8走。首先,v1到v1的距离为0,给v1标号(0)。画第一个圈。(表

明已标号,或已走出v1)

2) 从v1出发,只有两条路可走,(v1,v2),(v1,v3),其距离记为k11,k12。当然

想选一条长度短的路,即 Min{(k12),k13}={4,6}=4

给v2标号(4):表明走出v1后走向v8的最短路目前看是v2,最优距离是4。

1给(v,v)划成粗线。 ○12v4(9) 9 7 5 v6(13) 4 v8(15)

1 6 v5(8) v7(14) 1

2划第二个圈。 ○

现已完成第二个圈内的路已考察完毕,或者说,已走出包含v1,v2的第二个圈。 3)出了第二个圈,接着往下走,有三条路可走:(v1,v3),(v2,v4),(v2,v5)。那条路最近?记三条路长度为k13,k24,k25,即求:

Min{(k13),k24,k25}=min{6,9,8}=6

给v3标号(6):表明从第二个圈出来最近的一站是v3,总长度是6。

○1给(v1,v3)划成粗线。 ○

2划第三个圈。 表明:圈内的点已完成考察。

4)现已走出第三个圈,向v8奔。有四条路可走,最优路线在何方?即: Min{k24,(k25),k34,k35}=min{9,8,10,13}=8

给v5标号(8):表明从第三个圈出来后最近的一站是v5,总长度是8。

○1给(v2,v5)划成粗线。 ○

2划第四个圈。 表明:圈内的点已完成考察。

5)现已走出第四个圈,向v8奔。有四条路可走,最优路线在何方?即: Min{k56,k57,(k24),k34}=min{13,14,9,10}=9

给v4标号(9):表明从第四个圈出来后最近的一站是v4,总长度是9。

○1给(v2,v4)划成粗线。 ○

2划第五个圈。 表明:圈内的点已完成考察。

6)现已走出第五个圈,向v8奔。有四条路可走,最优路线在何方?即: Min{k46,k47,(k56),k57}=min{18,16,13,14}=13

给v6标号(13):表明从第五个圈出来后最近的一站是v6,总长度是13。

○1给(v5,v6)划成粗线。 ○

2划第六个圈。 2

表明:圈内的点已完成考察。

7)现已走出第六个圈,向v8奔。有三条路可走,最优路线在何方?即: Min{k68,k47,(k57)}=min{17,16,14}=14

给v7标号(14):表明从第六个圈出来后最近的一站是v7,总长度是14。

1给(v,v)划成粗线。 ○572划第七个圈。 ○

表明:圈内的点已完成考察。

8)最后,奔v8,有两条路,考察最短路: Min{k68,(k78)}=min{17,15}=15 给v8标号(15),同时给(v7,v8)划粗线。 最后,从v8逆寻粗线到v1,得最短路:

v1—v2—v5—v7—v8 长度为15。

第二讲:最短路问题的两个应用

最短路问题在图论应用中处于很重要的地位,下面举两个实际应用的例子。 例12/P-164 设备更新问题

某工厂使用一台设备,每年年初工厂要作出决定:继续使用,购买新的?如果继续使用旧的,要负维修费;若要购买一套新的,要负购买费。试确定一个5年计划,使总支出最小。

若已知设备在各年的购买费,及不同机器役龄时的残值与维修费,如表8-2所示 表8-2 项目 购买费 维修费 残值 第1年 第2年 第3年 第4年 第5年 11 5 4 12 1-2 6 3 13 2-3 8 2 14 3-4 11 1 14 4-5 18 0 机器役龄 0-1 解:把这个问题化为最短路问题。

用点vi表示第i年初购进一台新设备,虚设一个点v6,表示第5年底。 边(vi,vj)表示第i年购进的设备一直使用到第j年初(即第j-1年底)。

边(vi,vj)上的数字表示第i年初购进设备,一直使用到第j年初所需支付的购买费、维修的全部费用(可由表8-2计算得到)。例如:(v1,v4)边上的28是第一年初的购买费

3

11加上三年的维修费5,6,8,减去3年役龄机器的残值2;(v2,v4)边上的20是第二年初购买费12减去机器残值3与使用二年维修费5,6之和,见下图:

59 40 28 30 19 21 13 14 v 15 15 1(0) 12 v2(12) v3(1920 ) v4(28) v5(40) v6(49) 29 22 41 这样设备更新问题就变为:求从v1到v6的最短路问题, 1)v1(0)。

2)min{(k12),k13,k14,k15,k16}=12, 给v2标号(12),(v1,v2)加粗线。 3)min{(k13),k14,k15,k16, k23,k24, k25,k26}

={19, ? 13+12, ? }=19,

给v3标号(19),(v1,v3)加粗线。

4) min{(k14),k15,k16,k24,k25,k26,k34,k35,k36}

={59,? 19+30,? 12+20,?}=28, 给v4标号(28),(v1,v4)加粗线。 5) min{(k15),k16,k25,k26,(k35),k36,k45,k46}

={40,? 41, 40,? 43, ?}=40, 对应两个边: 给v5标号(40),(v1,v5)加粗线,(v3,v5)加粗线。 6)min{k16,k26,(k36),k46,k56}= min{59,53,49,50,55}=49 给v6标号(49),(v3,v6)加粗线。

计算结果:v1—v3—v6为最短路,路长为49。

即:在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。

4

联系客服:779662525#qq.com(#替换为@)