動態(tài)規(guī)劃的基本概念-展示頁
2024-08-20 03:53本頁面
【正文】 按時間（或空間）分成若干個階段，每個階段都需要作出決策，以便得到過程的最優(yōu)結(jié)局。然而，動態(tài)規(guī)劃也可以處理一些本來與時間沒有關(guān)系的靜態(tài)模型，這只要在靜態(tài)模型中人為地引入 “ 時間 ” 因素，分成時段，就可以把它看作是多階段的動態(tài)模型，用動態(tài)規(guī)劃方法去處理。首先，它沒有統(tǒng)一的處理方法，必須根據(jù)問題的各種性質(zhì)并結(jié)合一定的技巧來處理；另外當(dāng)變量的維數(shù)增大時，總的計算量及存貯量急劇增大。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。 167。在多階段決策過程中，系統(tǒng)的動態(tài)過程可以按照時間進程分為相互聯(lián)系而又相互區(qū)別的各個階段，在每個階段都要進行決策。因而在尋求多階段決策問題的最優(yōu)解時，重要的是不能僅僅從眼前的局部利益出發(fā)進行決策，而需要從系統(tǒng)所經(jīng)過的整個期間的總效應(yīng)出發(fā)，有預(yù)見性地進行動態(tài)決策，找到不同時點的最優(yōu)決策及整個過程的最優(yōu)策略。 例 1（最短路線問題）在線路網(wǎng)絡(luò)圖 1中，從 A至 E有一批貨物需要調(diào)運。 A B1 B2 E B3 C2 C3 C1 D2 D3 D1 4 5 3 4 4 4 3 1 6 5 8 8 7 7 10 2 9 6 為了找到由 A至 E的最短線路，可以將該問題分成 A— B— C— D—E 4個階段，在每個階段都需要作出決策，即在 A點需決策下一步到 B1還是到 B2或 B3；同樣，若到達第二階段某個狀態(tài)，比如 B1 ，需決定走向 C1還是 C2 ；依次類推，可以看出：各個階段的決策不同，由 A至 E的路線就不同，當(dāng)從某個階段的某個狀態(tài)出發(fā)作出一個決策，則這個決策不僅影響到下一個階段的距離，而且直接影響后面各階段的行進線路。 圖 1 例 2（帶回收的資源分配問題）某廠新購某種機床 125臺。此機車如在高負荷狀態(tài)下工作，年損壞率為 1/2，年利潤為 10萬元；如在低負荷狀態(tài)下工作，年損壞率為 1/5，年利潤為 6萬元。所以在每年初作決策時，必須將當(dāng)年的利潤和以后各年利潤結(jié)合起來，統(tǒng)籌考慮。 動態(tài)規(guī)劃的基本概念 動態(tài)規(guī)劃問題通常都具有時間或空間上的次序性，因此求解這類問題時，首先要將問題按一定的次序劃分成若干相互聯(lián)系的階段，以便能按一定次序去求解。 在多階段決策過程中，每階段都需要作出決策，而決策是根據(jù)系統(tǒng)所處情況決定的。如例 1中每階段的出發(fā)點位置就是狀態(tài)，例 2中每年初擁有的完好機床數(shù)是作出機床負荷安排的根據(jù)，所以年初完好機床數(shù)是狀態(tài)。記第 k 階段的狀態(tài)變量為 xk， k=1,2, …,n. :多階段決策過程的發(fā)展是用各階段的狀態(tài)演變來描述的，階段決策就是決策者從本階段某狀態(tài)出發(fā)對下一階段狀態(tài)所作出的選擇。這就是說決策變量 uk還是狀態(tài)變量 xk 的函數(shù)，因此，又可將第 k階段 xk狀態(tài)下的決策變量記為 uk(xk)。如例 2中取高負荷運行的機床數(shù) uk為決策變量，則 0≤uk≤xk（ xk是 k階段初完好機床數(shù)）為允許決策變量集合。也就是說 xk+1是 xk和 uk函數(shù)，這種關(guān)系可記為 xk+1=T(xk, uk) 稱之為 狀態(tài)轉(zhuǎn)移方程 。稱決策序列 {u1(x1), u2(x2), …, un(xn)}為該過程的一個 策略 ，從階段 k到階段 n的決策序列稱為 子策略 ，表示成 {uk(xk), uk+1(xk+1), …, un(xn) }。例 1中存在 12條不同路線，其中A— B2— C1— D2— E是最短線路。在階段 k的 xk狀態(tài)下執(zhí)行決策 uk，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也必然對目標函數(shù)給予影響，階段效應(yīng)就是執(zhí)行階段決策時給目標函數(shù)的影響。常見的全過程目標函數(shù)有以下兩種形式： ? （ 1）全過程的目標函數(shù)等于各階段目標函數(shù)的和，即： R=r1 (x1, u1) +r2 (x2, u2) +… +rn(xn, un) ? （ 2）全過程的目標函數(shù)等于各階段目標函數(shù)的積，即： R=r1 (x1, u1) r2 (x2, u
物理相關(guān)推薦
鄂ICP備17016276號-1