文/趙曉艷，河南質(zhì)量工程職業(yè)學(xué)院基礎(chǔ)教學(xué)部

1 動態(tài)規(guī)劃的定義

決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義.因此，把處理它的方法稱為動態(tài)規(guī)劃方法.但是，一些與時(shí)間沒有關(guān)系的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃等）問題，只要人為地引進(jìn)“時(shí)間”因素，也可把它視為多階段決策問題，用動態(tài)規(guī)劃方法來處理[1].涉及到動態(tài)規(guī)劃，總會有下面幾個(gè)概念：下面介紹動態(tài)規(guī)劃的基本概念。階段：把所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序求解.描述階段的變量稱為階段變量，常用k表示.階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來劃分，但要便于把問題的過程能轉(zhuǎn)化成為多階段決策的過程.狀態(tài)：狀態(tài)表示每個(gè)階段開始所處的自然狀況或客觀條件，它描述了研究問題的狀況，又稱不可控因素.在最短路問題中，狀態(tài)就是某階段的出發(fā)位置.它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn).通常一個(gè)階段有若干個(gè)狀態(tài)（一般第一個(gè)階段只有一個(gè)狀態(tài)，它構(gòu)成動態(tài)規(guī)劃的遞推方程的出口），每一個(gè)階段的所有狀態(tài)構(gòu)成一個(gè)集合，叫做狀態(tài)集合.用一個(gè)變量Si來描述在第i個(gè)階段的狀態(tài)集合上的取值，此變量Si稱為狀態(tài)變量（如7.2節(jié)中最短路問題中的Si，以及后面要介紹的背包問題、分割問題及設(shè)備更新問題中的參數(shù)λ）.這里所說的狀態(tài)是具體的屬于某階段的[2]，它應(yīng)具備下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各階段狀態(tài)的影響.換句話說，過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的總結(jié).這個(gè)性質(zhì)稱為無后效性，也稱馬爾可夫（Markov）性.如果狀態(tài)僅僅描述過程的具體特征，則并不是任何實(shí)際過程都能滿足無后效性的要求.所以，在構(gòu)造決策過程的動態(tài)規(guī)劃模型時(shí)，不能僅由描述過程的具體特征這點(diǎn)著眼去規(guī)定狀態(tài)變量，而要充分注意到是否滿足無后效性的要求.如果狀態(tài)的某種規(guī)定方式可能導(dǎo)致不滿足無后效性，則應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的規(guī)定方法，達(dá)到能使它滿足無后效性的要求.決策：決策表示當(dāng)過程處于某一階段的某一狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策.在最優(yōu)控制中也稱為控制（只有它才是我們能夠控制的）.描述決策的變量稱為決策變量.它可以用一個(gè)數(shù)、一組數(shù)或一個(gè)向量來描述.常用 uk(sk)表示第k階段當(dāng)狀態(tài)處于sk時(shí)的決策變量，它是狀態(tài)或狀態(tài)變量的函數(shù)（可能是向量值函數(shù)或多值函數(shù)）.在實(shí)際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合.常用Dk(sk)表示第k階段當(dāng)狀態(tài)處于sk出發(fā)的允許決策集合，顯然有uk(sk)∈ Dk(sk).例如，在最短路問題中，策略：策略是一個(gè)按順序排列的決策組成的集合.由過程的第k階段開始到終止?fàn)顟B(tài)為止的過程，稱為問題的后部子過程.由每段的決策按順序排列組成的決策函數(shù)序列稱為子策略，記為

當(dāng)k=1時(shí)，此決策函數(shù)序列即為一個(gè)策略.

在實(shí)際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合.從允許策略集合中找到達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略.狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程式確定過程有一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程.若給定第k階段狀態(tài)sk和該階段的決策變量uk(sk)，則第k+1階段的狀態(tài)sk+1也就完全確定.即sk+1的值隨sk和 uk( sk)的值變化而變化.這種確定的對應(yīng)關(guān)系，記為sk+1=Tk(sk,uk(sk))，它描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程.Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)[3].例如，在最短路問題中，狀態(tài)轉(zhuǎn)移方程為 sk+1=uk( sk).指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來衡量所實(shí)現(xiàn)過程優(yōu)劣的數(shù)量指標(biāo)，稱為指標(biāo)函數(shù).它是定義在全過程和所有后部子過程上確定的函數(shù).對于要構(gòu)成動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分性，并滿足遞推關(guān)系。在實(shí)際問題中，很多指標(biāo)函數(shù)都滿足此性質(zhì).指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù).根據(jù)問題，取min或max之一.在動態(tài)規(guī)劃模型中，總會出現(xiàn)一個(gè)或一組遞推關(guān)系，我們把它稱為動態(tài)規(guī)劃的基本方程動態(tài)規(guī)劃方法的基本思想

2 現(xiàn)將動態(tài)規(guī)劃方法的基本思想

2.1 動態(tài)規(guī)劃方法的關(guān)鍵在于正確寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（基本方程）.要做到這一點(diǎn)，必須先將問題的整個(gè)過程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問題化成一族同類型的子問題，然后逐個(gè)求解.即從邊界條件開始[4]，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解.

2.2 在多階段決策過程中，動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法.因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.

2.3 在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)策略.

動態(tài)規(guī)劃的理論基礎(chǔ)叫做動態(tài)規(guī)劃的最優(yōu)化原理，它是這樣描述的：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的狀態(tài)和決策如何，對前面決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略.簡言之，一個(gè)最優(yōu)策略的子策略總是最優(yōu)的.動態(tài)規(guī)劃的優(yōu)劣：

優(yōu)點(diǎn)：

（1）易于確定全局最優(yōu)解.因?yàn)樗蠼獾娜且痪S問題，所以容易確定.

（2）能得到一族（全部的）最優(yōu)解，有利于分析結(jié)果.

（3）能利用經(jīng)驗(yàn)，提高求解效率.

缺點(diǎn)：

（1）到目前為止，沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型可供應(yīng)用.由于問題的不同，有時(shí)要將問題轉(zhuǎn)化成滿足條件（無后效性、目標(biāo)函數(shù)的可分性）的多階段決策過程是非常困難的，需要豐富的想象力和靈活的技巧.

（2）應(yīng)用的局限性.“無后效性”條件的限制，降低了動態(tài)規(guī)劃的通用性.

（3）在數(shù)值計(jì)算時(shí)，存在所謂的“維數(shù)災(zāi)難”.當(dāng)階段數(shù)目較多且每一階段的允許狀態(tài)也較多時(shí)，計(jì)算成本變得非常昂貴，有時(shí)使得計(jì)算不可能進(jìn)行下去.在二維或三維動態(tài)規(guī)劃中，問題顯得更加突出.

下面的方程在動態(tài)規(guī)劃逆序求解中起著本質(zhì)的作用。

稱此為動態(tài)規(guī)劃逆序求解的基本方程（貝爾曼方程）。

可以把建立動態(tài)規(guī)劃模型歸納成以下幾個(gè)步驟：

（1）將問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)階段；

（2）正確選擇狀態(tài)變量，使它既能描述過程的演變，又滿足無后效性；

（3）規(guī)定決策變量，確定每個(gè)階段的允許決策集合；

（4）寫出狀態(tài)轉(zhuǎn)移方程；

（5）確定各階段各種決策的階段指標(biāo)，列出計(jì)算各階段最優(yōu)后部策略指標(biāo)的基本方程。

3 應(yīng)用

下面結(jié)合具體例子闡述建立動態(tài)規(guī)劃模型的思路。例如生產(chǎn)計(jì)劃問題。公司要對某產(chǎn)品制定n周的生產(chǎn)計(jì)劃，產(chǎn)品每周的需求量、生產(chǎn)和貯存費(fèi)用、生產(chǎn)能力的限制、初始庫存量n等都是已知的，試在滿足需求的條件下，確定每周的生產(chǎn)量，使 周的總費(fèi)用最少。決策變量是第k周的生產(chǎn)量，記作 uk(k = 1,2, … ,n)。已知下列數(shù)據(jù)及函數(shù)關(guān)系：第k周的需求量dk：第k周產(chǎn)量為uk時(shí)的生產(chǎn)費(fèi)為 ck( uk)；第k周初貯存量為xk時(shí)這一周的貯存費(fèi)為 hk( xk)；第k周的生產(chǎn)能力限制為Uk；初始（k=0）及終結(jié)（k=n）時(shí)貯存量均為零。按照最短路問題的思路，設(shè)從第k周初貯存量為xk到（n周末）過程結(jié)束的最小費(fèi)用函數(shù)為 fk( xk)，則下列逆向遞推公式成立。

而xk與xk+1滿足

這里貯存量xk是狀態(tài)變量，（2）式給出了相鄰階段的狀態(tài)在決策變量作用下的轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移規(guī)律。在用（1）式計(jì)算時(shí)，xk的取值范圍——允許狀態(tài)集合Xk由（2）式及允許決策集合(0≤ uk≤Uk)決定。在實(shí)際問題中，為簡單起見，生產(chǎn)費(fèi)用常取ck(uk)， uk=0； ck(uk)= a +cuk， uk＞0，其中c是單位產(chǎn)品生產(chǎn)費(fèi)，而a是生產(chǎn)準(zhǔn)備費(fèi)。貯存費(fèi)用常取 hk(xk)= hxk，h是單位產(chǎn)品（一周的）貯存費(fèi)。最優(yōu)方程（1）和狀態(tài)轉(zhuǎn)移方程（2）構(gòu)成了這個(gè)多階段決策問題的動態(tài)規(guī)劃模型。實(shí)際上，多階段決策問題有時(shí)也可用靜態(tài)規(guī)劃方法求解，如例2的生產(chǎn)計(jì)劃問題。