運(yùn)用動(dòng)態(tài)規(guī)劃模型解決最短路徑問題3

《運(yùn)用動(dòng)態(tài)規(guī)劃模型解決最短路徑問題3》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、運(yùn)用動(dòng)態(tài)規(guī)劃模型解決物流配送中的最短路徑問題摘要：隨著現(xiàn)代社會(huì)的高速發(fā)展，物流配送成為了連接各個(gè)生產(chǎn)棊地的樞紐，運(yùn)輸?shù)某杀締栴}也成為了企業(yè)發(fā)展的關(guān)鍵。運(yùn)費(fèi)不但與運(yùn)量有關(guān)，而且與運(yùn)輸行定的線路相關(guān)。傳統(tǒng)的運(yùn)輸問題沒有考慮交通網(wǎng)絡(luò)，在已知運(yùn)價(jià)的條件下僅求出最優(yōu)調(diào)運(yùn)方案，沒冇求出最優(yōu)行走路徑。文中提出“網(wǎng)絡(luò)上的物流配送問題“，在未知運(yùn)價(jià)，運(yùn)量確定的情況下，將運(yùn)輸過程在每階段屮選取最優(yōu)策略，燄后找到整個(gè)過程的總體最優(yōu)目標(biāo)，節(jié)省企業(yè)開支。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃，數(shù)學(xué)模型，物流配送，最優(yōu)路徑1引言物流配送是現(xiàn)代化物

2、流系統(tǒng)的一個(gè)重要環(huán)節(jié)。它是指按用戶的訂貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送交收貨人的活動(dòng)。在物流配送業(yè)務(wù)中，合理選擇配送徑路，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本及增加經(jīng)濟(jì)效益都有較大影響。物流配送最短徑路是指物品由供給地向需求地的移動(dòng)過程中，所經(jīng)過的距離最短（或運(yùn)輸?shù)臅r(shí)間最少，或運(yùn)輸費(fèi)用最低），因此，選定最短徑路是提高物品時(shí)空價(jià)值的重要環(huán)節(jié)經(jīng)典的Dijkstra算法和Floyd算法思路清楚，方法簡(jiǎn)便，但隨著配送點(diǎn)數(shù)的增加，計(jì)算的復(fù)雜性以配送點(diǎn)數(shù)的平方增加，并具有一定的主觀

3、性。我國(guó)學(xué)者用模糊偏好解試圖改善經(jīng)典方法叫取得了較好的效果。遺憾的是，模糊偏好解本身就不完全是客觀的。文獻(xiàn)同詳細(xì)分析了經(jīng)典方法的利弊Z后，提出將鄰接矩陣上三角和下三角復(fù)制從而使每條邊成為雙通路徑，既適用于有向圖也適用于無向圖，但復(fù)雜性增加了。為了避免上述方法存在的不足，木文以動(dòng)態(tài)規(guī)劃為理論,選擇合理的最優(yōu)值函數(shù),用于解決物流配送最短路徑問題。動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種數(shù)學(xué)方法。1951年美國(guó)數(shù)學(xué)家Bellman（貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)

4、性原理”，并研究了許多實(shí)際問題，從而創(chuàng)建了最優(yōu)化問題的一種新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃在工程技術(shù)、管理、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事及現(xiàn)代控制工程等方面都有廣泛的應(yīng)用，而且曲于動(dòng)態(tài)規(guī)劃方法有其獨(dú)特之處，在解決某些實(shí)際問題時(shí)，顯得更加方便有效。由于決策過程的時(shí)間參數(shù)有離散的和連續(xù)的情況，故決策過程分為離散決策過程和連續(xù)決策過程。⑵這種技術(shù)采用自底向上的方式遞推求值，將待求解的問題分解成若干個(gè)子問題，先求解子問題，并把子問題的解存儲(chǔ)起來以便以后用來計(jì)算所需要求的解。簡(jiǎn)言之，動(dòng)態(tài)規(guī)劃的基本思想就是把全局的問題化

5、為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。多階段決策問題是根據(jù)問題本身的特點(diǎn)，將英求解的過程劃分為若干個(gè)和互獨(dú)立又相互聯(lián)系的階段，在每個(gè)階段都需要做出決策，并且在每個(gè)階段的確定后再轉(zhuǎn)移到下一個(gè)階段，在每一個(gè)階段選取具最有決策，從而實(shí)現(xiàn)整個(gè)過程總體決策最優(yōu)的目的。24】適合用動(dòng)態(tài)規(guī)劃方法求解的問題是一類特殊的多階段決策問題，具有“無后效性”的多階段決策問題，一般具有以下特點(diǎn)：(1)可以劃分為若干個(gè)階段，問題的求解過程就是對(duì)若干個(gè)階段的一系列決策過程。(2)每個(gè)階段有若干個(gè)可能狀態(tài)。(3)一個(gè)決策將你從

6、一個(gè)階段的一種狀態(tài)帶到下一個(gè)階段的某種狀態(tài)。(4)在任一個(gè)階段，最佳的決策序列和該階段以前的決策無關(guān)。(5)各階段狀態(tài)Z間的轉(zhuǎn)換有明確定義的費(fèi)用，而且在選擇最佳決策時(shí)有遞推關(guān)系(即動(dòng)態(tài)轉(zhuǎn)移方程)。⑶2動(dòng)態(tài)規(guī)劃模型在現(xiàn)實(shí)生活的生產(chǎn)運(yùn)輸中，往往出發(fā)地與目的地之間有多種路線可供選擇，不同的路線所花費(fèi)的時(shí)間與費(fèi)用也不同，時(shí)間與費(fèi)用決定著企業(yè)的發(fā)展，這就需要選擇最短的路徑來提高效率。為了解決這個(gè)問題，將動(dòng)態(tài)規(guī)劃的理論與方法運(yùn)用于生產(chǎn)運(yùn)輸屮，節(jié)約了時(shí)間，為：企業(yè)的發(fā)展提供了契機(jī)。建立這個(gè)規(guī)劃模型的具體步驟如下

7、：①劃分階段:把所給問題的過程，恰當(dāng)?shù)膭澐譃槿舾蓚€(gè)相互聯(lián)系的部分，以便于求解，其屮每個(gè)部分叫階段。通常用k表示階段變量②確定狀態(tài)變量及其取值范圍：狀態(tài)表示在任一階段所處的，它既是該階段的起點(diǎn)，又是前一階段的終點(diǎn)。通常一個(gè)階段有若干個(gè)階段。描述狀態(tài)的變量稱為狀態(tài)變量。參數(shù)*表示第k階段的狀態(tài)變量。該階段所有可能狀態(tài)的全體稱為狀態(tài)集合，記為耳。狀態(tài)變量要能描述決策過程演變的狀態(tài)，又要滿足無后效性的要求，而且維數(shù)要盡可能地少。①確定決策變量及其収值范圍：在某一階段，當(dāng)狀態(tài)給定后，往往可以作出不同的決定，

8、從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱為決策變量，用/（&）表示第k階段當(dāng)狀態(tài)為幾時(shí)的決策變量，它是狀態(tài)變量耳的函數(shù)。決策變量的取值范圍稱為決策集合，通常用表示第k階段狀態(tài)為*時(shí)的允許決策集合。顯然有Uk（Sk）eD,（Sk）o②建立狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程描述由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程。因?yàn)槟骋浑A段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨Z而定。用幾嚴(yán)T伍“）表示k階段與k+1階段狀態(tài)的變換規(guī)律◎指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)值：階段指標(biāo)（乂稱階段效益）