運(yùn)籌學(xué)第八章動(dòng)態(tài)規(guī)劃的基本方法山東大學(xué)期末考試知識(shí)點(diǎn)復(fù)習(xí)

第八章動(dòng)態(tài)規(guī)劃的基本方法1．動(dòng)態(tài)規(guī)劃的概念動(dòng)態(tài)規(guī)劃是解決多階段決策問(wèn)題最優(yōu)化的一種數(shù)學(xué)方法，是一種解決問(wèn)題的思路，而不是一種算法。這一點(diǎn)與線性規(guī)劃不同。因此，在應(yīng)用動(dòng)態(tài)規(guī)劃方法求解多階段決策問(wèn)題時(shí)，要對(duì)具體問(wèn)題進(jìn)行具體分析。2．動(dòng)態(tài)規(guī)劃的基本思想(1)動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件(簡(jiǎn)言之為基本方程)，要做到這一點(diǎn)，必須先將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題化成一組同類型的子問(wèn)題，然后逐個(gè)求解，最后一個(gè)子問(wèn)題所得的最優(yōu)解就是整個(gè)問(wèn)題的最優(yōu)解。(2)在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的。(3)在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。如初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有從而可得最優(yōu)策略為{u1(A)，u2(B1)，…，u'0(F2)}，相應(yīng)的最短路線為A→B1→C2→…→F2→G。3．動(dòng)態(tài)規(guī)劃的基本方程動(dòng)態(tài)規(guī)劃的基本方程：k階段與k+1階段之間的遞推關(guān)系邊界條件為fn+1(sn+1)=04．狀態(tài)轉(zhuǎn)移方程(1)逆序遞推的基本方程其求解過(guò)程：根據(jù)邊界條件從k=n開(kāi)始，由后向前逆推，可逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，當(dāng)最后求出f1(s1)時(shí)，便得到整個(gè)問(wèn)題的最優(yōu)解。其各階段和各變量之間的關(guān)系如圖8—1所示。(2)順序遞推的基本方程其求解過(guò)程：根據(jù)邊界條件從k=1開(kāi)始，由前向后順推，可逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，當(dāng)最后求得fn(sn+1)時(shí)，便得到整個(gè)問(wèn)題的最優(yōu)解。其各階段和各變量之間的關(guān)系如圖8—2所示。一般來(lái)說(shuō)，當(dāng)過(guò)程的始點(diǎn)給定時(shí)，用逆序遞推比較方便；而當(dāng)過(guò)程的終點(diǎn)給定時(shí)，用順序遞推比較方便。5．指標(biāo)函數(shù)指標(biāo)函數(shù)是用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)。它是定義在全過(guò)程和所有后部子過(guò)程上的確定的數(shù)量函數(shù)，常用Vk，n表示。作為動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性。6．最優(yōu)值函數(shù)指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)，記為fk(sk)，它表示從第志階段的狀態(tài)sk開(kāi)始一直到第n階段的終止?fàn)顟B(tài)的過(guò)程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即其中“opt”是最優(yōu)化的意思，根據(jù)題意可取min或max。7．動(dòng)態(tài)規(guī)劃的最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去的狀態(tài)和