鋼管訂購(gòu)和運(yùn)輸計(jì)劃的最小費(fèi)用問題(崔王李)

《鋼管訂購(gòu)和運(yùn)輸計(jì)劃的最小費(fèi)用問題(崔王李)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、鋼管訂購(gòu)和運(yùn)輸計(jì)劃的最小費(fèi)用問題崔亞奇，王瑩桂，李潤(rùn)澤指導(dǎo)教員：數(shù)模組（海軍航空工程學(xué)院，煙臺(tái)，264001）摘要：這是一個(gè)求最少費(fèi)用以及如何取得最少費(fèi)用的問題。針對(duì)鐵路運(yùn)費(fèi)因里程不同而不等，首先，將鐵路轉(zhuǎn)化為等價(jià)公路，構(gòu)造無向圖并求其最短路徑；進(jìn)一步將問題轉(zhuǎn)化一個(gè)非線性規(guī)劃問題，建模并用Lingo求解即得。在研究銷價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響時(shí)，采用了分別波動(dòng)銷價(jià)，觀察對(duì)最小費(fèi)用的影響的方法；而在研究上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響時(shí)，則采用了放松各廠鋼管生產(chǎn)上限約束條件均到所需鋼管的總量以上，通過分析對(duì)其購(gòu)買量的影響程度來確定。關(guān)鍵字：等價(jià)公路，圖的最短路徑，

2、Floyd算法，非線性規(guī)劃。141.問題的提出現(xiàn)要鋪設(shè)一條的輸送天然氣的主管道。所給條件如下：一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè)單位（1km主管道鋼管稱為1單位鋼管）。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個(gè)單位，鋼管出廠銷價(jià)1單位鋼管為萬元，經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。在運(yùn)輸過程中所要經(jīng)過的鐵路、公路的運(yùn)費(fèi)為已知，其中鐵路運(yùn)費(fèi)隨著距離的增加而改變，公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）。沿鋪設(shè)的管道或者原來有公路，或者建有施工公路。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)，而是管道全線）。（1）制定一

3、個(gè)主管道鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用)。（2）就（1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響最大，哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出一種解決辦法，并對(duì)圖二按（1）的要求給出模型和結(jié)果。2.問題的分析對(duì)于問題一，我們分以下兩步進(jìn)行。首先，解決如何用最少運(yùn)費(fèi)把鋼管從鋼廠運(yùn)到各管道節(jié)點(diǎn)，這是一個(gè)圖的最小路徑問題，由于鐵路運(yùn)費(fèi)和里程有關(guān)，所以我們要對(duì)其進(jìn)行等價(jià)轉(zhuǎn)換，即把鐵路等價(jià)為同等運(yùn)費(fèi)的公路

4、，再和原有公路一起建構(gòu)一個(gè)具有權(quán)值（權(quán)值為一單位鋼的運(yùn)費(fèi)）的完全圖，對(duì)其利用Floyd算法求出最短路經(jīng)，我們就得到了從鋼管廠到所要鋪設(shè)的管道節(jié)點(diǎn)之間的最少運(yùn)費(fèi)路徑。然后，解決從各個(gè)鋼廠運(yùn)到管道節(jié)點(diǎn)的鋼管如何鋪設(shè)問題。如果我們從節(jié)點(diǎn)往一個(gè)方向或者跨節(jié)點(diǎn)鋪設(shè)，勢(shì)必會(huì)增加我們的總費(fèi)用，所以我們從節(jié)點(diǎn)分別向兩邊鋪設(shè)，很好的解決了運(yùn)費(fèi)問題。建立以鋼管的價(jià)格費(fèi)用和運(yùn)輸費(fèi)用（包括鋪設(shè)過程中的運(yùn)費(fèi)）之和為最小的目標(biāo)函數(shù)，用非線性規(guī)劃求解，最終得到問題的答案。問題二對(duì)于鋼廠鋼管的銷價(jià)的變化對(duì)總費(fèi)用影響，我們可以采用分別讓鋼廠的銷價(jià)在一定范圍內(nèi)改變，做出銷價(jià)和總費(fèi)用的敏感程度曲線，對(duì)其分

5、析即可得出影響的大??；鋼廠鋼管產(chǎn)量上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響，可以通過放開生產(chǎn)上限這個(gè)約束條件，從各鋼廠供貨數(shù)量的變化中得出。問題三是問題一的一個(gè)推廣，可以在模型一的基礎(chǔ)上修改得到。3.問題的假設(shè)141.假設(shè)沿管道的公路（施工公路）運(yùn)輸費(fèi)用也為每公里0.1萬元（不足整公里部分按整公里計(jì)算）。2.假設(shè)公路運(yùn)輸費(fèi)用不是整公里的按整公里計(jì)算是合理的。3.假設(shè)不考慮鐵路、公路及施工公路的運(yùn)輸能力限制，并且運(yùn)輸單位可提供足夠的火車與汽車。4.只考慮訂購(gòu)費(fèi)用和運(yùn)輸費(fèi)用，不考慮裝卸等其它費(fèi)用。5.假設(shè)在鋪設(shè)過程中，每公里卸下一單位鋼管是合理的。4.符號(hào)的說明：鋼廠；：火車站

6、；：管道節(jié)點(diǎn)；:鋼廠在指定期限內(nèi)生產(chǎn)鋼管的最大數(shù)量（單位：?jiǎn)挝讳摴埽?鋼廠單位鋼管的出廠價(jià)格（單位：萬元）；：從鋼廠運(yùn)到的鋼管數(shù)量（單位：?jiǎn)挝讳摴埽?；：與之間所需要的鋼管數(shù)量（單位：?jiǎn)挝讳摴埽?；：表?單位鋼管從鋼廠到的最少運(yùn)費(fèi)（單位：萬元）；：表示1單位鋼管從鋼廠到的最小費(fèi)用（單位：萬元）；：運(yùn)到的鋼管總數(shù)（單位：?jiǎn)挝讳摴埽?；：從向方向鋪設(shè)的鋼管的數(shù)量（單位：?jiǎn)挝讳摴埽?；其中：，，?.模型的建立與求解5.1問題一的求解5.1.1最短路徑的求解首先，將鐵路運(yùn)輸轉(zhuǎn)化為公路運(yùn)輸，具體步驟如下：僅考慮鐵路運(yùn)輸，以火車站及鋼廠為節(jié)點(diǎn)，并以鐵路里程為權(quán)值，構(gòu)造一個(gè)帶有權(quán)值的

7、無向圖。用Floyd算法求出到最短路經(jīng)，14進(jìn)一步根據(jù)鐵路里程和運(yùn)費(fèi)之間的關(guān)系，計(jì)算出到所需要的費(fèi)用，現(xiàn)在假設(shè)到之間有一條所需運(yùn)費(fèi)為的公路，并用這些公路代替原來鐵路。至此，我們已經(jīng)把鐵路運(yùn)輸轉(zhuǎn)化為公路運(yùn)輸?shù)膯栴}。進(jìn)一步分析，假設(shè)公路與原公路可以組成一個(gè)新的無向圖。對(duì)其邊進(jìn)行賦權(quán)值，其中假設(shè)公路的權(quán)值為，原公路的權(quán)值為其運(yùn)費(fèi)（可由已知條件求得），如果到之間的公路與原公路發(fā)生沖突（即任意兩節(jié)點(diǎn)之間出現(xiàn)兩條邊），我們就取權(quán)值較小的邊構(gòu)成無向圖。用Floyd算法求出到管道節(jié)點(diǎn)之間的最短路經(jīng)，即從運(yùn)輸一單位鋼管到管道節(jié)點(diǎn)的最少運(yùn)費(fèi)。由所給條件知的鋼管價(jià)格為，最