图论网络规划

图论练习汪帆 13 土规1202 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 任意两点间最优路径表（路由表）V1V2V3V4V5V6V7V10357.84.85.57V23024.81.82.54V3520524.56V47.84.850378.5V54.81.823045.5V65.52.54.57401.5V77468.55.51.50（3），结果分析：上述矩阵为对称阵，主对角线为0，即消防站所建立的位置。其具体涵义为：消防站建立在Vi处时对应各个城市的最短路径，如此可以建立表5.1.2:表5.1.2 各点建立消防站的最远城市及其两者距离表消防站点最远城市两者距离V1V47.8V2V24.8V3V76V4V78.5V5V75.5V6V57V7V48.5从表5.12可以看出，比较最远距离，不难看出，当消防站点选在V2城市时，其离最远城市的最优距离为最优：4.8。故而，应将消防站建立在V2城市。2某矿区有七个矿点，如图所示，已知各矿点每天的产矿量,现要从这七个矿点选一个来建造矿厂，问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小。图5.2.1 矿区点线模型图解：分析：总运力与两个因素有关：矿点与矿厂的距离、矿点产矿量，且都是正比的关系，故而应当把矿点与矿厂的距离L和矿点产矿量X的成绩当做运力，进而将运力当做权矩阵的元，运用Warshall-Foryd算法求出该图的路由表，从而根据路由表中的最优路线，寻求V1-V7到每一点的最优路径，再将最优路径加总，进而寻求7个预设厂址中的最优路径总值的最小值的点即为所求矿厂点。（1），距离矩阵：L=产量矩阵：（2），权矩阵（运算程序见附录5.1）： i=1:7（3），运用Warshall-Foryd算法，调用floyd(A)函数，求出该图的路由表（程序详见附录5.2.2）：表5.2.1 厂址预设及总运力V1V2V3V4V5V6V7总运力V1062026321016110V29014202641083V3134061281457V427182006101697V52112141041062V617822252406102V718.59.523.526.525.51.50105（4），结果分析由表5.2.1可知，厂址预设与该址到各个矿区的最优路径表清晰而明朗，并在表中最后一栏中的总运力可以观察出：当把V3设为矿厂时，其总运力最小，为57。故而应当选取V3矿区建立矿厂。附录5.1function D,R=floyd(A)D=A;n=length(D);for i=1:n for j=1:n R(i,j)=i; endendfor 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;