利用動(dòng)態(tài)規(guī)劃法求解運(yùn)輸問題的最短路徑

1、=J最利用動(dòng)態(tài)規(guī)劃法求解運(yùn)輸問題的最短路徑分析：針對(duì)最短路徑問題，最容易想到的方法是窮舉法，即列出所有 可能發(fā)生的方案和結(jié)果，針對(duì)要求進(jìn)行比較求出最優(yōu)方案，對(duì)于簡(jiǎn)單 變量少的問題還是可行的，但是對(duì)于復(fù)雜變量多的問題計(jì)算工作量就 比較大。最短路徑的最優(yōu)性原理啟發(fā)我們從最后一步逐步向前推的方 法來求解，也就引入了動(dòng)態(tài)規(guī)劃方法，實(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ù)雜的問題分解為一系列同一類型的更容易求解的子問 題，計(jì)算過程單一化便于應(yīng)用于計(jì)算機(jī)。先按照整體最優(yōu)思想逆序求 出

2、各個(gè)可能狀態(tài)的最優(yōu)策略，然后順序求出整個(gè)問題的最優(yōu)策略和最 優(yōu)路徑。由于把最優(yōu)化應(yīng)用到每個(gè)子問題上，就系統(tǒng)的刪減去了所有 中間非最優(yōu)方案使得計(jì)算量比窮舉法大大減少。將動(dòng)態(tài)規(guī)劃思想應(yīng)用 到求解運(yùn)輸問題的最短路徑中，方法簡(jiǎn)便，理論可靠，求解結(jié)果清晰 明了，在實(shí)際運(yùn)用中取得了良好的效果。建模（1）將實(shí)際問題的過程劃分成恰當(dāng)階段，確定階段變量。根據(jù)多階段決策問題的實(shí)際過程，將其劃分為若干個(gè)相互獨(dú)立又 相互聯(lián)系的部分每一個(gè)部分為一個(gè)階段，劃分出的每一個(gè)階段通常就 是需要做出一個(gè)決策的子問題。階段通常是按決策進(jìn)行的時(shí)間或空間 上的先后順序劃分的，階段變量用表示。（2）確定狀態(tài)，正確選擇狀態(tài)變量。在多階段決

3、策過程中，狀態(tài)是描述每個(gè)階段所必須的信息，表示 每個(gè)階段開始時(shí)所處的自然狀況或客觀條件。一個(gè)階段有若干個(gè)狀態(tài)， 用一個(gè)或一組變量來描述，狀態(tài)變量必須既能描述過程的演變，又要 滿足無后效性。用n表示第n個(gè)階段的狀態(tài)變量。（3）確定決策變量及允許的決策集合。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì) 下一階段狀態(tài)做出的選擇。決策變量用xk表示；允許的決策集合是決 策變量的取值范圍用Dk （sk）表示。（4）寫出狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程sk+1 =Tk（sk，xk），這里的函數(shù)關(guān)系Tk因問題 的不同而不同，如果給定第k個(gè)階段的狀態(tài)變量sk，則該階段的決策 變量xk 一經(jīng)確定，第k+1

4、階段的狀態(tài)變量的值也就可以確定。（5）列出指標(biāo)函數(shù)。指標(biāo)函數(shù)vkn的關(guān)系，并要求具有可分離性及遞推性；（6）寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程，用fk（sn+1）表示k-n階段的最優(yōu) 策略函數(shù)：fn+1 （xn+1）=0 （邊界條件）fk （sk ）=opt vk+fk+1 ，k=n， n-1， 1。解：如圖1所示，節(jié)點(diǎn)A表示發(fā)送點(diǎn)，節(jié)點(diǎn)E表示終到點(diǎn)，其余節(jié)點(diǎn)為運(yùn)輸過程中可經(jīng)由點(diǎn)，邊線表示可能路徑，邊線上數(shù)值表示 其間運(yùn)輸成本。利用動(dòng)態(tài)規(guī)劃模型并求解運(yùn)輸過程中的最短路徑。n4首先根據(jù)網(wǎng)絡(luò)圖以及上節(jié)提到的建模方法我們可以將運(yùn)輸過程劃分成四個(gè)階段，階段變 量用k表示；狀態(tài)變量林表示k階段初可能的位置；決策匕

5、表示k階段初可能選擇的路線；狀 態(tài)轉(zhuǎn)移方程sk+1=sk-xk；階段指標(biāo)vk表示k階段與所選擇的路段相應(yīng)的路長(zhǎng)；指標(biāo)函數(shù) vkn=富表示k至4階段的總路長(zhǎng)；fk表示第k階段點(diǎn)sk到終點(diǎn)E的運(yùn)輸成本；遞推公式 fk=minvk+fk+1，k=4, 3, 2, 1； xk*表示最優(yōu)決策；邊界條件k=5時(shí)，f5=0。將動(dòng)態(tài)規(guī) 劃的計(jì)算結(jié)果列表表示，如表1所示。計(jì)算結(jié)果列表KS(k)X(k)V(k)V=V0+F(_K+1)F(k)X(k)4D1D2E33+04+03E3C1C2C3D1D2D1D2D1D241+34+46+33+43+33+44D1D2D12B1B2B3C1C2C3C1C2C3C1C2C374+7 7+4 6+63+42+74+64+4 1+7 5+611C1,C2C1C1,C21AB1B222+1