運用動態(tài)規(guī)劃模型解決最短路徑問題

《運用動態(tài)規(guī)劃模型解決最短路徑問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

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

2、訂貨要求,在配送中心進行分貨、配貨,并將配好的貨物及時送交收貨人的活動。在物流配送業(yè)務中,合理選擇配送徑路,對加快配送速度、提高服務質(zhì)量、降低配送成本及增加經(jīng)濟效益都有較大影響。物流配送最短徑路是指物品由供給地向需求地的移動過程中,所經(jīng)過的距離最短(或運輸?shù)臅r間最少,或運輸費用最低),因此,選定最短徑路是提高物品時空價值的重要環(huán)節(jié)。經(jīng)典的Dijkstra算法和Floyd算法思路清楚,方法簡便,但隨著配送點數(shù)的增加,計算的復雜性以配送點數(shù)的平方增加,并具有一定的主觀性。我國學者用模糊偏好解試圖改善經(jīng)典方法,取得了較好的效果。遺憾的是,模糊偏好解本身就不完全是客觀的。文獻詳細分析了

3、經(jīng)典方法的利弊之后,提出將鄰接矩陣上三角和下三角復制從而使每條邊成為雙通路徑,既適用于有向圖也適用于無向圖,但復雜性增加了。為了避免上述方法存在的不足,本文以動態(tài)規(guī)劃為理論,選擇合理的最優(yōu)值函數(shù),用于解決物流配送最短路徑問題。動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化問題的一種數(shù)學方法。1951年美國數(shù)學家Bellman（貝爾曼）等人根據(jù)一類多階段決策問題的特性，提出了解決這類問題的“最優(yōu)性原理”，并研究了許多實際問題，從而創(chuàng)建了最優(yōu)化問題的一種新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃在工程技術、管理、經(jīng)濟、工業(yè)生產(chǎn)、軍事及現(xiàn)代控制工程等方面都有廣泛的應用，而且由于動態(tài)規(guī)劃方法有其獨特之處，在解決

4、某些實際問題時，顯得更加方便有效。由于決策過程的時間參數(shù)有離散的和連續(xù)的情況，故決策過程分為離散決策過程和連續(xù)決策過程。這種技術采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。多階段決策問題是根據(jù)問題本身的特點，將其求解的過程劃分為若干個相互獨立又相互聯(lián)系的階段，在每個階段都需要做出決策，并且在每個階段的確定后再轉(zhuǎn)移到下一個階段，在每一個階段選取其最有決策，從而實現(xiàn)整個過程總體決策最優(yōu)的目的。適合用動態(tài)規(guī)劃方法求解的

5、問題是一類特殊的多階段決策問題，具有“無后效性”的多階段決策問題，一般具有以下特點：(1)可以劃分為若干個階段，問題的求解過程就是對若干個階段的一系列決策過程。(2)每個階段有若干個可能狀態(tài)。(3)一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài)。(4)在任一個階段，最佳的決策序列和該階段以前的決策無關。(5)各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費用，而且在選擇最佳決策時有遞推關系（即動態(tài)轉(zhuǎn)移方程）。2動態(tài)規(guī)劃模型在現(xiàn)實生活的生產(chǎn)運輸中，往往出發(fā)地與目的地之間有多種路線可供選擇，不同的路線所花費的時間與費用也不同，時間與費用決定著企業(yè)的發(fā)展，這就需要選擇最短的路徑來提高效率

6、。為了解決這個問題，將動態(tài)規(guī)劃的理論與方法運用于生產(chǎn)運輸中，節(jié)約了時間，為：企業(yè)的發(fā)展提供了契機。建立這個規(guī)劃模型的具體步驟如下：劃分階段:把所給問題的過程，恰當?shù)膭澐譃槿舾蓚€相互聯(lián)系的部分，以便于求解，其中每個部分叫階段。通常用k表示階段變量確定狀態(tài)變量及其取值范圍：狀態(tài)表示在任一階段所處的，它既是該階段的起點，又是前一階段的終點。通常一個階段有若干個階段。描述狀態(tài)的變量稱為狀態(tài)變量。參數(shù)表示第k階段的狀態(tài)變量。該階段所有可能狀態(tài)的全體稱為狀態(tài)集合，記為。狀態(tài)變量要能描述決策過程演變的狀態(tài)，又要滿足無后效性的要求，而且維數(shù)要盡可能地少。確定決策變量及其取值范圍：在某一階段，當

7、狀態(tài)給定后，往往可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。描述決策的變量稱為決策變量，用表示第k階段當狀態(tài)為時的決策變量，它是狀態(tài)變量的函數(shù)。決策變量的取值范圍稱為決策集合，通常用表示第k階段狀態(tài)為時的允許決策集合。顯然有。建立狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程描述由一個狀態(tài)到另一個狀態(tài)的演變過程。因為某一階段的狀態(tài)變量及決策變量取定后，下一階段的狀態(tài)就隨之而定。用表示k階段與k+1階段狀態(tài)的變換規(guī)律指標函數(shù)和最優(yōu)指標函數(shù)值：階段指標（又稱階段效益）是衡量該階段決策效果的數(shù)量指標