數學建模數學建模§6動態規劃模型舉例以上討論的優化問題屬于靜態的，即不必考慮時間的變化，建立的模型——線性規劃、非線性規劃、整數規劃等，都屬于靜態規劃。多階段決策屬于動態優化問題，即在每個階段（通常以時間或空間為標志）根據過程的演變情況確定一個決策，使全過程的某個指標達到最優。例如：（1）化工生產過程中包含一系列的過程設備，如反應器、蒸餾塔、吸收器等，前一設備的輸出為后一設備的輸入。因此，應該如何控制生產過程中各個設備的輸入和輸出，使總產量最大。（2）發射一枚導彈去擊中運動的目標，由于目標的行動是不斷改變的，因此應當如何根據目標運動的情況，不斷地決定導彈飛行的方向和速度，使之最快地命中目標。（3）汽車剛買來時故障少、耗油低，出車時間長，處理價值和經濟效益高。隨著使用時間的增加則變得故障多，油耗高，維修費用增加，經濟效益差。使用時間俞長，處理價值也俞低。另外，每次更新都要付出更新費用。因此，應當如何決定它每年的使用時間，使總的效益最佳。動態規劃模型是解決這類問題的有力工具，下面介紹相關的基本概念及其數學描述。（1）階段整個問題的解決可分為若干個相互聯系的階段依次進行。通常按時間或空間劃分階段，描述階段的變量稱為階段變量，記為。（2）狀態狀態表示每個階段開始時所處的自然狀況或客觀條件，它描述了研究過程的狀況。各階段的狀態通常用狀態變量描述。常用表示第階段的狀態變量。個階段的決策過程有個狀態。用動態規劃方法解決多階段決策問題時，要求整個過程具有無后效性。即：如果某階段的狀態給定，則此階段以后過程的發展不受以前狀態的影響，未來狀態只依賴于當前狀態。（3）決策某一階段的狀態確定后，可以作出各種選擇從而演變到下一階段某一狀態，這種選擇手段稱為決策。描述決策的變量稱為決策變量。決策變量限制的取值范圍稱為允許決策集合。用表示第階段處于狀態時的決策變量，它是的函數，用表示的允許決策集合。（4）策略一個由每個階段的決策按順序排列組成的集合稱為策略。由第階段的狀態開始到終止狀態的后部子過程的策略記為。在實際問題中，可供選擇的策略有一定范圍，稱為允許策略集合。其中達到最優效果的策略稱為最優策略。（5）狀態轉移方程如果第個階段狀態變量為，作出的決策為，那么第階段的狀態變量也被完全確定。用狀態轉移方程表示這種演變規律，寫作，（6）最優值函數指標函數是系統執行某一策略所產生結果的數量表示，是用來衡量策略優劣的數量指標，它定義在全過程和所有后部子過程上。指標函數的最優值稱為最優值函數。下面的方程在動態規劃逆序求解中起著本質的作用。稱此為動態規劃逆序求解的基本方程（貝爾曼方程）。可以把建立動態規劃模型歸納成以下幾個步驟：（1）將問題恰當地劃分為若干個階段；（2）正確選擇狀態變量，使它既能描述過程的演變，又滿足無后效性；（3）規定決策變量，確定每個階段的允許決策集合；（4）寫出狀態轉移方程；（5）確定各階段各種決策的階段指標，列出計算各階段最優后部策略指標的基本方程。下面結合具體例子闡述建立動態規劃模型的思路。例13生產計劃問題。公司要對某產品制定周的生產計劃，產品每周的需求量、生產和貯存費用、生產能力的限制、初始庫存量等都是已知的，試在滿足需求的條件下，確定每周的生產量，使周的總費用最少。決策變量是第周的生產量，記作。已知下列數據及函數關系：第周的需求量：第周產量為時的生產費為；第周初貯存量為時這一周的貯存費為；第周的生產能力限制為；初始（）及終結（）時貯存量均為零。按照最短路問題的思路，設從第周初貯存量為到（周末）過程結束的最小費用函數為，則下列逆向遞推公式成立。(1)而與滿足(2)這里貯存量是狀態變量，（2）式給出了相鄰階段的狀態在決策變量作用下的轉移規律，稱為狀態轉移規律。在用（1）式計算時，的取值范圍——允許狀態集合由（2）式及允許決策集合決定。在實際問題中，為簡單起見，生產費用常取，；，，其中是單位產品生產費，而是生產準備費。貯存費用常取，是單位產品（一梯服務的層段，使送完全部乘客的時間最短。按照由下而上安排電梯服務層次的序號劃分階段。第部電梯（即第階段）開始服務的層次為狀態，它服務的層數為決策，滿足（1）當，時，已知第部電梯服務的時間為。因為對于第兩部電梯而言，總的服務時間為，所以最優值函數（即從第部到第部電梯總的最短服務時間）滿足（2）（3）這里我們假定每部電梯至少服務1層，且從第2層起開始服務。應用動態規劃方法求解多階段決策問題分為兩個步驟。第一是應用動態規劃基本方程，逆序地求出條件最優目標函數值集合和條件最優決策集合。第二是順序地求出最優決策序列。下面以一個例子加以說明。例17機器負荷分配問題。某種機器可以在高低兩種不同的負荷下進行生產。在高負荷下生產時，每臺機器生產產品的年產量為7噸，年折損率（即若年初完好的機器有臺，則年終完好的機器數為臺），在低負荷下生產時，每臺機器生產產品的年產量為5噸，年折損率。若開始時完好的機器數有臺，要求制定一個三年計劃，在每年開始時，決定如何重新分配在兩種不同的負荷下生產的完好機器數，使在三年內產品的總產量達到最大。設第年初完好的機器數為，分配給高負荷下生產的機器數為，即在低負荷下生產的機器數為-。這里、可取非負實數，如表示第年度一臺機器正常工作時間只占。于是第年初完好的機器數第年度的產量設三年總產量為，則問題即求解下面的線性規劃問題：現用動態規劃來解。本題要求的是已知第一年度初擁有的完好機器數臺，用最優方案到第三年度末這段期間的產品產量，將它記為。為此先求：已知第年度初擁有的完好機器數，用最優方案到第三年末這段期間的產品產量，將它記為，列出動態規劃的基本方程求解過程如下：（1）即，得最優解，從而。（2）即，得最優解，從而。