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

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

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

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

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

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

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

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

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

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