運(yùn)籌學(xué)第9章2講

k階段與k+1階段之間的遞推關(guān)系：一般情況，k階段與k+1階段的遞推關(guān)系式可寫成邊界條件為

遞推關(guān)系式(8-1)稱為動(dòng)態(tài)規(guī)劃的基本方程。

如例1最短路線問題，初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有從而可得最優(yōu)策略為｛u1(A),u2(B1),…,u0’(F2)｝，相應(yīng)的最短路線為2、在多階段決策過程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)各段分開，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的。動(dòng)態(tài)規(guī)劃方法基本思想歸納： 1、動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件(簡(jiǎn)言之為基本方程)。 3、在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。二、如何建立DP模型將原問題轉(zhuǎn)化成多階段決策問題；正確寫出狀態(tài)變量，使它既能描述過程演變，又滿足無(wú)后效性；確定決策變量和每階段的允許決策集合；正確寫出狀態(tài)轉(zhuǎn)移方程；正確寫出指標(biāo)函數(shù)（分離性、遞推性、單調(diào)性）。三、標(biāo)號(hào)法1、算法引入逆行方向[4][3][7][5][9][7][6][8][13][10][9][12][13][16][18]規(guī)定：從A到G點(diǎn)為順行；從G到A是逆行。[0]順行方向[0][5][3][6][8][10][9][11][13][13][13][13][15][16][15][18]設(shè)指標(biāo)函數(shù)是取各階段指標(biāo)的和的形式，即所以上式可寫成

當(dāng)初始狀態(tài)給定時(shí)，過程的策略就被確定，則指標(biāo)函數(shù)也就確定了。因此，指標(biāo)函數(shù)是初始狀態(tài)和策略的函數(shù)?？捎洖橄旅婵紤]動(dòng)態(tài)規(guī)劃基本方程。其中表示第

j

段的指標(biāo)。上面遞推關(guān)系又可寫成其中

如果用p*k,n(sk)表示初始狀態(tài)為sk的后部子過程所有子策略中的最優(yōu)子策略，則最優(yōu)值函數(shù)為而

動(dòng)態(tài)規(guī)劃逆序解法的基本方程：邊界條件為式中

求解過程，根據(jù)邊界條件，從k=n開始，由后向前逆推，從而逐步可求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出時(shí)，就得到整個(gè)問題的最優(yōu)解。動(dòng)態(tài)規(guī)劃順序解法的基本方程

邊界條件為式中求解過程：根據(jù)邊界條件，從k=1開始，由前向后順推，逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出時(shí)，就得到整個(gè)問題的最優(yōu)解。第三節(jié)：動(dòng)態(tài)