動態(tài)規(guī)劃及其在求最短路徑問題中的應(yīng)用(共10頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 計算機算法設(shè)計與分析 論文名：動態(tài)規(guī)劃及其在求最短路徑問題中的應(yīng)用 班級：12醫(yī)軟一班 學(xué)號： 姓名：張健 日期：2015年6月動態(tài)規(guī)劃及其在求最短路徑問題中的應(yīng)用 摘要：在概述動態(tài)規(guī)劃原理的基礎(chǔ)上，提出了動態(tài)規(guī)劃數(shù)學(xué)模型建模主要步驟，并運用動態(tài)規(guī)劃思想對最短路徑進(jìn)行求解，最后總結(jié)出動態(tài)規(guī)劃在此類問題中的優(yōu)越性。 關(guān)鍵字：動態(tài)規(guī)劃；最短路徑；多階段決策。 在實踐中有許多決策問題與時間有關(guān)系，決策過程分成若干階段，各階段的決策相互關(guān)聯(lián)，共同決定最終的目標(biāo)，這樣的問題稱之為多階段決策問題。動態(tài)規(guī)劃方法是解決多階段決策過程最優(yōu)化的一種方法。這一方法最初是由美國數(shù)學(xué)家R.B

2、ellman等人在20世紀(jì)50年代提出的，實踐證明許多問題用動態(tài)規(guī)劃建模求解比用線性規(guī)劃或非線性規(guī)劃更加有效，特別是對離散性問題，運用解析數(shù)學(xué)無法解決，而動態(tài)規(guī)劃就成為得力的工具。動態(tài)規(guī)劃方法把一個比較復(fù)雜的問題分析為一系列同一類型的更容易求解的子問題先按照整體最優(yōu)思想逆序求出各個可能狀態(tài)的最優(yōu)策略，然后順序求出整個問題的最優(yōu)策略和最優(yōu)路徑。由于將動態(tài)規(guī)劃思想應(yīng)用到求解運輸問題的最短路徑中，計算過程單一化便于應(yīng)用于計算機，求解結(jié)果清晰明了，在實踐應(yīng)用中獲得顯著效果。1 動態(tài)規(guī)劃原理概述 動態(tài)規(guī)劃最優(yōu)化原理可以這樣闡述：一個最優(yōu)化策略不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸

3、多策略必須構(gòu)成最優(yōu)策略，即其子策略總是最優(yōu)的。任何思想方法都有一定的局限性，動態(tài)規(guī)劃也有其適應(yīng)的條件。如果某階段的狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，這個性質(zhì)稱為無后效性，適用動態(tài)規(guī)劃的問題必須滿足這個性質(zhì)；其次還須滿足上述最優(yōu)化原理。動態(tài)規(guī)劃基本思想一是正確的寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件；二是在多階段決策過程中，動態(tài)規(guī)劃方法是即把當(dāng)前一段和后來各階段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種多階段決策的最優(yōu)化方法，每階段決策和選取是從全局來考慮，與該段的最優(yōu)選擇的答案一般是不同的；三是在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，兒每階段的決策又都

4、是該階段狀態(tài)的函數(shù)，因而最優(yōu)策略所經(jīng)過的各階段狀態(tài)便可逐次變換得到，從而確定最優(yōu)路線。簡而言之動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。2 動態(tài)規(guī)劃建模主要步驟 用動態(tài)規(guī)劃求解實際問題，首先要建立動態(tài)規(guī)劃模型，需要進(jìn)行以下的基本步驟： 第一步：正確劃分階段，確定階段變量，將多階段決策問題的實際過程，恰當(dāng)?shù)膭澐譃槿舾蓚€相互獨立又相互聯(lián)系的是需要做出一個決策的子問題。階段通常是按決策進(jìn)行的時間或空間上的先后順序劃分的，階段變量用K表示。 第二步：確定狀態(tài)，正確選擇狀態(tài)變量，在多階段決策過程中，狀態(tài)是描述研究問題過程的狀況，表示每個階段開始時所處的自然狀況或客觀條件

5、。一個階段有若干個狀態(tài)，用一個或一組變量來描述，狀態(tài)變量必須滿足兩個條件：一是能描述過程的演變；二是滿足無后效性，用表示第k個階段的狀態(tài)變量。 第三步：正確選擇決策變量及允許的決策集合。決策的實質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)做出的選擇，而在實際問題中，決策變量的取值往往限制在某一范圍內(nèi)，此范圍稱之為允許決策集合。決策變量用表示；允許的決策集合是決策變量的取值范圍用表示。 第四步：寫出狀態(tài)轉(zhuǎn)換方程。狀態(tài)轉(zhuǎn)換方程的一般形式為=，這里的函數(shù)關(guān)系T因問題的不同而不同，如果給定第k個階段的狀態(tài)變量，則該階段的決策變量一經(jīng)確定第k+1階段的狀態(tài)變量的值也就可以確定。 第五步：

6、列出指標(biāo)函數(shù)。根據(jù)題意寫出指標(biāo)函數(shù)，指標(biāo)函數(shù)常用表示。即 =,k=1,2，.，n。 它滿足以下三個性質(zhì)： a.它是定義在全過程及所有后部子過程上的數(shù)量函數(shù)； b.具有可分離性，切滿足遞推關(guān)系，即 =； c.函數(shù)關(guān)于變量要嚴(yán)格單調(diào)。 第六步：寫出動態(tài)規(guī)劃函數(shù)基本方程，用表示k-n階段的最優(yōu)策略函數(shù)： 3 應(yīng)用舉例 最短路徑問題就是從某地出發(fā)，途徑若干中間點最后到達(dá)目的地，要求找出路程或費用最小的路線。這類問題最容易想到的就是窮舉法，即將所有的路線都找出來再作比較，對于中間點較少的最短路徑問題是可行的，但隨著中間點的增加，計算量也大大的增加了。 例1 某工廠需將一筆物資從A地發(fā)送到F地，A地到F地

7、之間的路線可以抽象成如下的線路圖，其中節(jié)點A表示發(fā)貨地，節(jié)點F表示目的地，中間節(jié)點表示中轉(zhuǎn)站，邊線表示可能路徑，邊線上的數(shù)值表示節(jié)點間的距離，問該工廠應(yīng)該如何運送才能使路線最短？ 圖1 A地到F地的網(wǎng)狀路徑圖 分析：首先根據(jù)網(wǎng)絡(luò)圖以及上節(jié)提到的建模方法，我們可以將運輸過程劃分為五個階段，即階段變量k=1,2,3,4,5;設(shè)狀態(tài)變量表示k階段的起點；決策變量表示k階段的終點；狀態(tài)轉(zhuǎn)換方程為；階段指標(biāo)函數(shù)表示k階段與所選擇的路段相應(yīng)的路長；表示第k階段點到終點F的運輸總距離；遞推關(guān)系式為 下面利用表格進(jìn)行計算，從最后一階段開始向前遞推： 表1 k=5時計算過程表K=4時：利用第5階段的數(shù)據(jù)推出本階

8、段（第4階段）的結(jié)果如下表。 表2 k=4時計算過程表K=3時：利用第4階段的數(shù)據(jù)推出本階段（第3階段）的結(jié)果如下表。 表3 k=3時計算過程表K=2時：利用第3階段的數(shù)據(jù)推出本階段（第2階段）的結(jié)果如下表。 表4 k=2時計算過程表K=1時：利用第2階段的數(shù)據(jù)推出本階段（第1階段）的結(jié)果如下表。 表5 k=1時計算過程表 按計算表格的順序反推算，可得如下結(jié)果： A到F的最短路線為：； A到F的最短距離為：。 通過對上述實例運用動態(tài)規(guī)劃的思想進(jìn)行計算，我們發(fā)現(xiàn)得到的不僅僅是由A點到F點的最短路線，而且還得到了從所有各中間點出發(fā)到F點的最短路線，這就是說求出的不僅是一個最優(yōu)策略，而且是一族的最優(yōu)

9、策略，這對于許多實際問題來講是很有用的。 在上述實例中只考慮了一個發(fā)貨中心的應(yīng)用實例，在實際中有可能存在多個發(fā)貨中心的情況，因此我們可以考慮假設(shè)發(fā)貨中心不是A點，而是，分別到F三條最短路線，這樣圖1中的A點就是一個虛構(gòu)點。對于這樣的問題我們可以這樣考慮，我們將A點看成一個假想的“發(fā)貨中心”，如下圖所示 圖2虛構(gòu)A點后的網(wǎng)狀路徑圖 那么從到，到，到的距離就都是0，這樣我們?nèi)匀豢梢园凑丈侠挠嬎氵^程進(jìn)行計算，但只需計算到k=2時就可以了，同樣我們可以得到問題的結(jié)論： 從到的最短路線為：，最短距離為：14； 從到的最短路線為：，最短距離為：9； 從到的最短路線為：，最短距離為：12。 由本實例我們可以總結(jié)出動態(tài)優(yōu)化思想的幾點優(yōu)越性： （1)計算過程單一化便于應(yīng)用于計算機，求解結(jié)果清晰明了； （2）能得到一族解，有利于分析結(jié)果，進(jìn)行推廣應(yīng)用； （3）易于確定全局最優(yōu)解，并能利用經(jīng)驗提高求解效率。參考