圖論網絡規(guī)劃

1、圖論練習汪帆土規(guī)1202 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 ;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），運用Warshall-Foryd算法，調用floyd(A)函數，求出該圖的路由表（程序詳見附錄5.1）：表5.1.1 任意兩點間最優(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、，結果分析：上述矩陣為對稱陣，主對角線為0，即消防站所建立的位置。其具體涵義為：消防站建立在Vi處時對應各個城市的最短路徑，如此可以建立表5.1.2:表5.1.2 各點建立消防站的最遠城市及其兩者距離表消防站點最遠城市兩者距離V1V47.8V2V24.8V3V76V4V78.5V5V75.5V6V57V7V48.5從表5.12可以看出，比較最遠距離，不難看出，當消防站點選在V2城市時，其離最遠城市的最優(yōu)距離為最優(yōu)：4.8。故而，應將消防站建立在V2城市。2某礦區(qū)有七個礦點，如圖所示，已知各礦點每天的產礦量,現(xiàn)要從這七個礦點選一個來建造礦廠，問應選在哪個礦點，才能使各礦點所產的礦運到選礦廠所在地

4、的總運力（千噸公里）最小。圖5.2.1 礦區(qū)點線模型圖解：分析：總運力與兩個因素有關：礦點與礦廠的距離、礦點產礦量，且都是正比的關系，故而應當把礦點與礦廠的距離L和礦點產礦量X的成績當做運力，進而將運力當做權矩陣的元，運用Warshall-Foryd算法求出該圖的路由表，從而根據路由表中的最優(yōu)路線，尋求V1-V7到每一點的最優(yōu)路徑，再將最優(yōu)路徑加總，進而尋求7個預設廠址中的最優(yōu)路徑總值的最小值的點即為所求礦廠點。（1），距離矩陣：L=產量矩陣：（2），權矩陣（運算程序見附錄5.1）： i=1:7（3），運用Warshall-Foryd算法，調用floyd(A)函數，求出該圖的路由表（程序詳見附

5、錄）：表5.2.1 廠址預設及總運力V1V2V3V4V5V6V7總運力V1062026321016110V29014202641083V3134061281457V427182006101697V52112141041062V617822252406102V718.59.523.526.525.51.50105（4），結果分析由表5.2.1可知，廠址預設與該址到各個礦區(qū)的最優(yōu)路徑表清晰而明朗，并在表中最后一欄中的總運力可以觀察出：當把V3設為礦廠時，其總運力最小，為57。故而應當選取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