管道訂購(gòu)與運(yùn)輸問題-2000年全國(guó)數(shù)學(xué)建模競(jìng)賽b題優(yōu)秀論文

1、管道訂購(gòu)與運(yùn)輸問題1問題重述4問題的簡(jiǎn)化求SAP矩陣的基本思路是圖的最短路算法.由于鐵路的運(yùn)輸費(fèi)用與線路的長(zhǎng)度不是線性關(guān)系必須對(duì)鐵路網(wǎng)做一些預(yù)處理才能套用圖的標(biāo)準(zhǔn)最短路算法.下面敘述求SAP矩陣的過程:1.利用圖的標(biāo)準(zhǔn)最短路算法從鐵路網(wǎng)絡(luò)得出圖中任兩個(gè)點(diǎn)之間的最短路徑表T(如果兩個(gè)點(diǎn)之間不連通認(rèn)為它們之間的最短路長(zhǎng)度為∞).2.利用題中的鐵路運(yùn)價(jià)表將T中的每個(gè)元素(即最短距離)轉(zhuǎn)化為運(yùn)輸費(fèi)用將運(yùn)輸費(fèi)用表記為C.3.將公路的長(zhǎng)度換算為運(yùn)輸

2、費(fèi)用由公路路程圖(包括要沿線鋪設(shè)管道的公路)得出公路費(fèi)用圖G若ij不連通則令Gij=∞.4.對(duì)于任一組(ij)∈1…n1…m如果Cij∞且小于Gij那么就在公路費(fèi)用圖中加一條邊.即令Gij=minCijGij.5.利用圖的標(biāo)準(zhǔn)最短路算法求公路費(fèi)用圖中任一個(gè)S點(diǎn)到任一個(gè)A點(diǎn)的最小費(fèi)用路徑得出SAP矩陣.如表1所示:SAP矩陣A123456789101112131415S11707160314029863802053121264292096

3、0106012121280142022157205319021716111095586071211421420146015601712178019203230722032002181612101055960862482820860960111211801320426072503235221661560140513101162842620510610762830970525572453225220661460130512101112792