【正文】 建立與求解 問(wèn)題一：討論如何調(diào)整主管道鋼管的訂購(gòu)和運(yùn)輸方案使總費(fèi)用最小 iSiS 運(yùn)到運(yùn)輸點(diǎn) 的最小費(fèi)用 1）將圖 1轉(zhuǎn)換為一系列以單位鋼管的運(yùn)輸費(fèi)用為權(quán)的賦權(quán)圖 . iSjb所以可先求出鋼廠 到鐵路與公路相交點(diǎn) 的最短路徑 .如圖 3 由題意可知：將鋼管從鋼廠 運(yùn)到運(yùn)輸點(diǎn) 的費(fèi)用 包括鋼管的銷售價(jià)格、 鋼管的鐵路運(yùn)輸費(fèi)用和鋼管的公路運(yùn)輸費(fèi)用 .在費(fèi)用 最小時(shí)，對(duì)鋼管的訂購(gòu)和運(yùn)輸 進(jìn)行分配，可得出本問(wèn)題的最佳方案 . 總費(fèi)用 =鋼廠到各節(jié)點(diǎn)的費(fèi)用 +主管道的運(yùn)輸（鋪設(shè)費(fèi)用） 450 80 1150 1100 306 195 20 202 1200 720 690 520 170 690 160 88 462 70 320 160 70 290 30 圖 4 1SjA2） 計(jì)算單位鋼管從 到 的最少運(yùn)輸費(fèi)用 1S jA根據(jù)圖 4，借助圖論軟件包中求最短路的方法求出單位鋼管從 到 的最短路，從而得出將單位鋼管從 1S 運(yùn)輸?shù)礁鬟\(yùn)輸點(diǎn) jA 最小費(fèi)用 。由于在途中可能 發(fā)生火車 — 汽車 — 火車的轉(zhuǎn)運(yùn)方案，而這種情況發(fā)生的前提條件是公路 （或管道）的兩端必須都是火車站點(diǎn)，由于鐵路運(yùn)輸?shù)馁M(fèi)用是分段函數(shù)，故 求各鋼廠到各管道結(jié)點(diǎn)的最小費(fèi)用步驟如下： 1）首先找出公路的兩個(gè)端點(diǎn)都是火車站站點(diǎn)的結(jié)點(diǎn) V1,V2,… Vs 2) 把公路網(wǎng)和鐵路網(wǎng)分開(kāi)，分別組成網(wǎng)絡(luò)； 3）在鐵路網(wǎng)中求出各鋼廠 Si及各點(diǎn) Vi到各火車站點(diǎn)的最短路，并把它轉(zhuǎn)化 為最小費(fèi)用路 4)在公路網(wǎng)中求出各管道結(jié)點(diǎn)到各火車站點(diǎn)的最短路，并把它轉(zhuǎn)化為最小 費(fèi)用路 5）把前面的結(jié)點(diǎn)合并成一個(gè)網(wǎng)絡(luò)，分別求出各鋼廠 Si 到各管道結(jié)點(diǎn)的最小 運(yùn)輸費(fèi)用路 。即：每次只讓一個(gè)鋼廠鋼管的銷售價(jià)格發(fā)生相同的變化，其余鋼廠鋼管的銷售價(jià)格不發(fā)生變化；當(dāng)每個(gè)鋼廠的銷售價(jià)個(gè)發(fā)生同樣的變化 C 時(shí)，求出相應(yīng)的總費(fèi)用，然后比較。 2) 討論鋼廠產(chǎn)量的上限變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響 本問(wèn)題同樣采用比較法。 問(wèn)題三、討論鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形 本問(wèn)題是討論鋪設(shè)的管道是樹形圖，鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形，對(duì)于這種 問(wèn)題的求解過(guò)程，以圖 2進(jìn)行說(shuō)明。 運(yùn)輸費(fèi)用依次為： ， ， ， ， 38， ， ， ， ， 92， 96， 106， ， 128， 142（單位：萬(wàn)元） 加上單位鋼管的銷售 價(jià)