圖論網絡規(guī)劃

1、圖論網絡規(guī)劃 圖論練習 汪帆 2021306202113 土規(guī) 1202 1 1 某城市要建立一個消防站，為該市所屬的七個區(qū)服務，如圖所示，問應設在那個區(qū)，才能使它至最遠區(qū)的路徑最短。 圖 圖 5.1.1 城市點線模型圖 解：分析：要求建立的消防站離最遠區(qū)的路徑最短，即要求出任意兩點間最優(yōu)路徑，而后從最優(yōu)路徑中選取最大值中的最小值。具體方法則要運用warshall-foryd 算法求出該圖的路由表，從而根據路由表中的最優(yōu)路線，尋求v1-v7 到每一點的最優(yōu)路徑，并比較各路徑中最長路徑的大小，擇取最小值即為題中之所問。 （1），建立權矩陣： a=0 3 inf inf inf inf inf ;

2、 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 任意兩點間最優(yōu)路徑表（路由表） 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

3、 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

4、8.5 v5 v7 5.5 v6 v5 7 v7 v4 8.5 從表 5.12 可以看出，比較最遠距離，不難看出，當消防站點選在 v2 城市時，其離最遠城市的最優(yōu)距離為最優(yōu)：4.8。故而，應將消防站建立在 v2 城市。 2 2 某礦區(qū)有七個礦點，如圖所示，已知各礦點每天的產礦量, , 現(xiàn)要從這七個礦點選一個來建造礦廠，問應選在哪個礦點，才能使各礦點所產的礦運到選礦廠所在地的總運力（千噸公里）最小。 圖 圖 5.2.1 礦區(qū)點線模型圖 解：分析：總運力與兩個因素有關：礦點與礦廠的距離、礦點產礦量，且都是正比的關系，故而應當把礦點與礦廠的距離l和礦點產礦量x的成績當做運力，進而將運力當做權矩陣的元

5、，運用 warshall-foryd 算法求出該圖的路由表，從而根據路由表中的最優(yōu)路線，尋求 v1-v7 到每一點的最優(yōu)路徑，再將最優(yōu)路徑加總，進而尋求 7 個預設廠址中的最優(yōu)路徑總值的最小值的點即為所求礦廠點。 （1），距離矩陣： 精選文庫 3 l l= =úúúúúúúúúûùêêêêêêêêêëé0 , 5 . 1 inf, inf, inf, inf, inf,5 .

6、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 úúúúúú&#

7、250;úúûùêêêêêêêêêëé=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)函數，求出該圖的路由表（程序

8、詳見附錄 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 可知，廠址預設與該址到各個礦區(qū)的最優(yōu)路徑表清晰而明朗，并在表中最后一欄中的總運力可以觀察出：當把 v3 設為礦廠時，其總運力最小，為 57。故而應當選取 v3 礦區(qū)建立礦廠。 精選文庫 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