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

1、圖論練習(xí)汪帆土規(guī)1202 1某城市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示，問應(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)路徑，并比較各路徑中最長路徑的大小，擇取最小值即為題中之所問。（1），建立權(quán)矩陣：A=0 3 inf inf inf inf inf ;3 0 2 inf 1.8 2.5 inf;Inf 2 0 6 2 i

2、nf 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ù)，求出該圖的路由表（程序詳見附錄5.1）：表5.1.1 任意兩點(diǎn)間最優(yōu)路徑表（路由表）V1V2V3V4V5V6V7V10357.84.85.57V23024.81.82.54V3520524.56V47.84.850378.5V54.81.823045.5V65.52.54.57401.5V77468.55.51.50（3）

3、，結(jié)果分析：上述矩陣為對稱陣，主對角線為0，即消防站所建立的位置。其具體涵義為：消防站建立在Vi處時(shí)對應(yīng)各個(gè)城市的最短路徑，如此可以建立表5.1.2:表5.1.2 各點(diǎn)建立消防站的最遠(yuǎn)城市及其兩者距離表消防站點(diǎn)最遠(yuǎn)城市兩者距離V1V47.8V2V24.8V3V76V4V78.5V5V75.5V6V57V7V48.5從表5.12可以看出，比較最遠(yuǎn)距離，不難看出，當(dāng)消防站點(diǎn)選在V2城市時(shí)，其離最遠(yuǎn)城市的最優(yōu)距離為最優(yōu)：4.8。故而，應(yīng)將消防站建立在V2城市。2某礦區(qū)有七個(gè)礦點(diǎn)，如圖所示，已知各礦點(diǎn)每天的產(chǎn)礦量,現(xiàn)要從這七個(gè)礦點(diǎn)選一個(gè)來建造礦廠，問應(yīng)選在哪個(gè)礦點(diǎn)，才能使各礦點(diǎn)所產(chǎn)的礦運(yùn)到選礦廠所在地

4、的總運(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的成績當(dāng)做運(yùn)力，進(jìn)而將運(yùn)力當(dāng)做權(quán)矩陣的元，運(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），距離矩陣：L=產(chǎn)量矩陣：（2），權(quán)矩陣（運(yùn)算程序見附錄5.1）： i=1:7（3），運(yùn)用Warshall-Foryd算法，調(diào)用floyd(A)函數(shù)，求出該圖的路由表（程序詳見附

5、錄）：表5.2.1 廠址預(yù)設(shè)及總運(yùn)力V1V2V3V4V5V6V7總運(yùn)力V1062026321016110V29014202641083V3134061281457V427182006101697V52112141041062V617822252406102V718.59.523.526.525.51.50105（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ū)建立礦廠。附錄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; brea