图论网络规划

　图论练习 汪帆 2011306200513 土规 1202

　1 1 某城市要建立一个消防站，为该市所属的七个区服务，如图所示，问应设在那个区，才能使它至最远区的路径最短。

　图 图 5.1.1

　城市点线模型图

　解：分析：要求建立的消防站离最远区的路径最短，即要求出任意两点间最优路径，而后从最优路径中选取最大值中的最小值。具体方法则要运用Warshall-Foryd 算法求出该图的路由表，从而根据路由表中的最优路线，寻求V1-V7 到每一点的最优路径，并比较各路径中最长路径的大小，择取最小值即为题中之所问。

　（1），建立权矩阵：

　A=[0 3 inf inf inf inf inf ; 3 0 2 inf 1.8 2.5 inf; Inf 2 0 6 2 inf inf ; Inf inf 6 0 3 inf inf ; Inf 1.8 2 3 0 4 inf;

　Inf 2.5 inf inf 4 0 1.5;

　Inf inf inf inf inf 1.5 0]

　（2），运用 Warshall-Foryd 算法，调用 floyd(A)函数，求出该图的路由表（程序详见附录 5.1）：

　表 表 5.1.1

　任意两点间最优路径表（路由表）

　V1 V2 V3 V4 V5 V6 V7 V1 0 3 5 7.8 4.8 5.5 7 V2 3 0 2 4.8 1.8 2.5 4 V3 5 2 0 5 2 4.5 6 V4 7.8 4.8 5 0 3 7 8.5 V5 4.8 1.8 2 3 0 4 5.5 V6 5.5 2.5 4.5 7 4 0 1.5 V7 7 4 6 8.5 5.5 1.5 0

　精选文库 — 2 （3），结果分析：上述n n ij )V ( V 矩阵为对称阵，主对角线为 0，即消防站所建立的位置。其具体涵义为：消防站建立在 V i 处时对应各个城市的最短路径，如此可以建立表 5.1.2:

　表 表 5.1.2

　各点建立消防站的最远城市及其两者距离表

　消防站点 最远城市 两者距离 V1 V4 7.8 V2 V2 4.8 V3 V7 6 V4 V7 8.5 V5 V7 5.5 V6 V5 7 V7 V4 8.5

　从表 5.12 可以看出，比较最远距离，不难看出，当消防站点选在 V2 城市时，其离最远城市的最优距离为最优：4.8。故而，应将消防站建立在 V2 城市。

　 2 2 某矿区有七个矿点，如图所示，已知各矿点每天的产矿量, , 现要从这七个矿点选一个来建造矿厂，问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小。

　图 图 5.2.1

　矿区点线模型图

　解：分析：总运力与两个因素有关：矿点与矿厂的距离、矿点产矿量，且都是正比的关系，故而应当把矿点与矿厂的距离L和矿点产矿量X的成绩当做运力，进而将运力当做权矩阵的元，运用 Warshall-Foryd 算法求出该图的路由表，从而根据路由表中的最优路线，寻求 V1-V7 到每一点的最优路径，再将最优路径加总，进而寻求 7 个预设厂址中的最优路径总值的最小值的点即为所求矿厂点。

　（1），距离矩阵：

　精选文库 — 3 L L= =0 , 5 . 1 inf, inf, inf, inf, inf,5 . 1 , 0 , 4 inf, inf, , 4 inf,inf , 4 , 0 , 1 , 2 inf, inf,inf inf, , 1 , 0 , 6 inf, inf,inf inf, , 2 , 6 , 0 , 2 inf,inf , 4 inf, inf, , 2 , 0 , 3inf inf, inf, inf, , inf , 3 , 0

　产量矩阵：

　  4 , 1 , 6 , 1 , 7 , 2 , 3  X

　（2），权矩阵（运算程序见附录 5.1）：

　X i L * :). , ( A 

　i=1:7 0

　 1.5000

　 Inf

　 Inf

　Inf

　Inf

　Inf6

　0

　24

　 Inf

　Inf

　8

　InfInf

　4

　0

　1

　14

　 Inf

　InfInf

　Inf

　6

　0

　42

　 Inf

　InfInf

　Inf

　12

　 6

　0

　4

　InfInf

　4

　Inf

　Inf

　14

　 0

　9Inf

　Inf

　Inf

　Inf

　Inf

　6

　0A

　（3），运用 Warshall-Foryd 算法，调用 floyd(A)函数，求出该图的路由表（程序详见附录 5.2.2）：

　表 表 5.2.1

　厂址 预设及总运力

　V1 V2 V3 V4 V5 V6 V7 总运力 V1 0 6 20 26 32 10 16 110 V2 9 0 14 20 26 4 10 83 V3 13 4 0 6 12 8 14 57 V4 27 18 20 0 6 10 16 97 V5 21 12 14 1 0 4 10 62 V6 17 8 22 25 24 0 6 102 V7 18.5 9.5 23.5 26.5 25.5 1.5 0 105

　（4），结果分析 由表 5.2.1 可知，厂址预设与该址到各个矿区的最优路径表清晰而明朗，并在表中最后一栏中的总运力可以观察出：当把 V3 设为矿厂时，其总运力最小，为 57。故而应当选取 V3 矿区建立矿厂。

　精选文库 — 4 附录 5.1 function [D,R]=floyd(A) D=A;n=length(D); for i=1:n

　 for j=1:n

　 R(i,j)=i;

　 end end for k=1:n

　for i=1:n

　 for j=1:n

　if D(i,k)+D(k,j)<D(i,j)

　 D(i,j)=D(i,k)+D(k,j);

　 R(i,j)=R(k,j);

　 end

　 end

　 end

　 hl=0;

　 for i=1:n

　 if D(i,i)<0

　hl=1;

　break;

　 end

　 end

　 if(hl==1)

　 fprintf("有负回路")

　 break;

　 end end

　 5.2.1 %求权矩阵。

　n=7; for i=n A=[L(i,:).*X] end