圖論網(wǎng)絡(luò)規(guī)劃

1、圖論網(wǎng)絡(luò)規(guī)劃 圖論練習(xí) 汪帆 2021306202113 土規(guī) 1202 1 1 某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示，問(wèn)應(yīng)設(shè)在那個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短。 圖 圖 5.1.1 城市點(diǎn)線模型圖 解：分析：要求建立的消防站離最遠(yuǎn)區(qū)的路徑最短，即要求出任意兩點(diǎn)間最優(yōu)路徑，而后從最優(yōu)路徑中選取最大值中的最小值。具體方法則要運(yùn)用warshall-foryd 算法求出該圖的路由表，從而根據(jù)路由表中的最優(yōu)路線，尋求v1-v7 到每一點(diǎn)的最優(yōu)路徑，并比較各路徑中最長(zhǎng)路徑的大小，擇取最小值即為題中之所問(wèn)。 （1），建立權(quán)矩陣： 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），運(yùn)用 warshall-foryd 算法，調(diào)用 floyd(a)函數(shù)，求出該圖的路由表（程序詳見(jiàn)附錄 5.1）： 表 表 5.1.1 任意兩點(diǎn)間最優(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 精選文庫(kù) 2 （3），結(jié)果分析：上述n n ij )v ( v´= 矩陣為對(duì)稱(chēng)陣，主對(duì)角線為 0，即消防站所建立的位置。其具體涵義為：消防站建立在 v i 處時(shí)對(duì)應(yīng)各個(gè)城市的最短路徑，如此可以建立表 5.1.2: 表 表 5.1.2 各點(diǎn)建立消防站的最遠(yuǎn)城市及其兩者距離表 消防站點(diǎn) 最遠(yuǎn)城市 兩者距離 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 可以看出，比較最遠(yuǎn)距離，不難看出，當(dāng)消防站點(diǎn)選在 v2 城市時(shí)，其離最遠(yuǎn)城市的最優(yōu)距離為最優(yōu)：4.8。故而，應(yīng)將消防站建立在 v2 城市。 2 2 某礦區(qū)有七個(gè)礦點(diǎn)，如圖所示，已知各礦點(diǎn)每天的產(chǎn)礦量, , 現(xiàn)要從這七個(gè)礦點(diǎn)選一個(gè)來(lái)建造礦廠，問(wèn)應(yīng)選在哪個(gè)礦點(diǎn)，才能使各礦點(diǎn)所產(chǎn)的礦運(yùn)到選礦廠所在地的總運(yùn)力（千噸公里）最小。 圖 圖 5.2.1 礦區(qū)點(diǎn)線模型圖 解：分析：總運(yùn)力與兩個(gè)因素有關(guān)：礦點(diǎn)與礦廠的距離、礦點(diǎn)產(chǎn)礦量，且都是正比的關(guān)系，故而應(yīng)當(dāng)把礦點(diǎn)與礦廠的距離l和礦點(diǎn)產(chǎn)礦量x的成績(jī)當(dāng)做運(yùn)力，進(jìn)而將運(yùn)力當(dāng)做權(quán)矩陣的元

5、，運(yùn)用 warshall-foryd 算法求出該圖的路由表，從而根據(jù)路由表中的最優(yōu)路線，尋求 v1-v7 到每一點(diǎn)的最優(yōu)路徑，再將最優(yōu)路徑加總，進(jìn)而尋求 7 個(gè)預(yù)設(shè)廠址中的最優(yōu)路徑總值的最小值的點(diǎn)即為所求礦廠點(diǎn)。 （1），距離矩陣： 精選文庫(kù) 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 產(chǎn)量矩陣： 4 , 1 , 6 , 1 , 7 , 2 , 3 = x （2），權(quán)矩陣（運(yùn)算程序見(jiàn)附錄 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），運(yùn)用 warshall-foryd 算法，調(diào)用 floyd(a)函數(shù)，求出該圖的路由表（程序

8、詳見(jiàn)附錄 5.2.2）： 表 表 5.2.1 廠址 預(yù)設(shè)及總運(yùn)力 v1 v2 v3 v4 v5 v6 v7 總運(yùn)力 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），結(jié)果分析 由表 5.2.1 可知，廠址預(yù)設(shè)與該址到各個(gè)礦區(qū)的最優(yōu)路徑表清晰而明朗，并在表中最后一欄中的總運(yùn)力可以觀察出：當(dāng)把 v3 設(shè)為礦廠時(shí)，其總運(yùn)力最小，為 57。故而應(yīng)當(dāng)選取 v3 礦區(qū)建立礦廠。 精選文庫(kù) 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