動態(tài)規(guī)劃數(shù)學建模在企業(yè)決策中的應用

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

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

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

當k=1時，此決策函數(shù)序列即為一個策略.

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

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

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

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

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

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

優(yōu)點：

（1）易于確定全局最優(yōu)解.因為它求解的全是一維問題，所以容易確定.

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

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

缺點：

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

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

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

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

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

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

（1）將問題恰當?shù)貏澐譃槿舾蓚€階段；

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

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

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

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

3 應用

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

而xk與xk+1滿足

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