數(shù)學建模案例分析--最優(yōu)化方法建模6動態(tài)規(guī)劃模型舉例

《數(shù)學建模案例分析--最優(yōu)化方法建模6動態(tài)規(guī)劃模型舉例》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、§6動態(tài)規(guī)劃模型舉例　　　　以上討論的優(yōu)化問題屬于靜態(tài)的，即不必考慮時間的變化，建立的模型——線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等，都屬于靜態(tài)規(guī)劃。多階段決策屬于動態(tài)優(yōu)化問題，即在每個階段（通常以時間或空間為標志）根據(jù)過程的演變情況確定一個決策，使全過程的某個指標達到最優(yōu)。例如：（1）化工生產(chǎn)過程中包含一系列的過程設(shè)備，如反應(yīng)器、蒸餾塔、吸收器等，前一設(shè)備的輸出為后一設(shè)備的輸入。因此，應(yīng)該如何控制生產(chǎn)過程中各個設(shè)備的輸入和輸出，使總產(chǎn)量最大。（2）發(fā)射一枚導(dǎo)彈去擊中運動的目標，由于目標的行動是不斷改變的，因此應(yīng)當如何根據(jù)目標運動的情況，不斷地決定導(dǎo)彈飛

2、行的方向和速度，使之最快地命中目標。（3）汽車剛買來時故障少、耗油低，出車時間長，處理價值和經(jīng)濟效益高。隨著使用時間的增加則變得故障多，油耗高，維修費用增加，經(jīng)濟效益差。使用時間俞長，處理價值也俞低。另外，每次更新都要付出更新費用。因此，應(yīng)當如何決定它每年的使用時間，使總的效益最佳。動態(tài)規(guī)劃模型是解決這類問題的有力工具，下面介紹相關(guān)的基本概念及其數(shù)學描述。（1）階段整個問題的解決可分為若干個相互聯(lián)系的階段依次進行。通常按時間或空間劃分階段，描述階段的變量稱為階段變量，記為。（2）狀態(tài)狀態(tài)表示每個階段開始時所處的自然狀況或客觀條件，它描述了研究過程的

3、狀況。各階段的狀態(tài)通常用狀態(tài)變量描述。常用表示第階段的狀態(tài)變量。個階段的決策過程有個狀態(tài)。用動態(tài)規(guī)劃方法解決多階段決策問題時，要求整個過程具有無后效性。即：如果某階段的狀態(tài)給定，則此階段以后過程的發(fā)展不受以前狀態(tài)的影響，未來狀態(tài)只依賴于當前狀態(tài)。（3）決策某一階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段某一狀態(tài)，這種選擇手段稱為決策。描述決策的變量稱為決策變量。決策變量限制的取值范圍稱為允許決策集合。用表示第階段處于狀態(tài)時的決策變量，它是的函數(shù)，用表示的允許決策集合。（4）策略一個由每個階段的決策按順序排列組成的集合稱為策略。由第階段的狀態(tài)

4、開始到終止狀態(tài)的后部子過程的策略記為。在實際問題中，可供選擇的策略有一定范圍，稱為允許策略集合。其中達到最優(yōu)效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程如果第個階段狀態(tài)變量為，作出的決策為，那么第階段的狀態(tài)變量也被完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，寫作，（6）最優(yōu)值函數(shù)指標函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生結(jié)果的數(shù)量表示，是用來衡量策略優(yōu)劣的數(shù)量指標，它定義在全過程和所有后部子過程上。指標函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)。下面的方程在動態(tài)規(guī)劃逆序求解中起著本質(zhì)的作用。稱此為動態(tài)規(guī)劃逆序求解的基本方程（貝爾曼方程）?？梢园呀討B(tài)規(guī)劃模型歸納成以下幾個步驟

5、：（1）將問題恰當?shù)貏澐譃槿舾蓚€階段；（2）正確選擇狀態(tài)變量，使它既能描述過程的演變，又滿足無后效性；（3）規(guī)定決策變量，確定每個階段的允許決策集合；（4）寫出狀態(tài)轉(zhuǎn)移方程；（5）確定各階段各種決策的階段指標，列出計算各階段最優(yōu)后部策略指標的基本方程。下面結(jié)合具體例子闡述建立動態(tài)規(guī)劃模型的思路。例13　生產(chǎn)計劃問題。公司要對某產(chǎn)品制定周的生產(chǎn)計劃，產(chǎn)品每周的需求量、生產(chǎn)和貯存費用、生產(chǎn)能力的限制、初始庫存量等都是已知的，試在滿足需求的條件下，確定每周的生產(chǎn)量，使周的總費用最少。決策變量是第周的生產(chǎn)量，記作。已知下列數(shù)據(jù)及函數(shù)關(guān)系：第周的需求量：第周

6、產(chǎn)量為時的生產(chǎn)費為；第周初貯存量為時這一周的貯存費為；第周的生產(chǎn)能力限制為；初始（）及終結(jié)（）時貯存量均為零。按照最短路問題的思路，設(shè)從第周初貯存量為到（周末）過程結(jié)束的最小費用函數(shù)為，則下列逆向遞推公式成立。(1)而與滿足(2)　　這里貯存量是狀態(tài)變量，（2）式給出了相鄰階段的狀態(tài)在決策變量作用下的轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移規(guī)律。在用（1）式計算時，的取值范圍——允許狀態(tài)集合由（2）式及允許決策集合決定?！　≡趯嶋H問題中，為簡單起見，生產(chǎn)費用常取，；，，其中是單位產(chǎn)品生產(chǎn)費，而是生產(chǎn)準備費。貯存費用常取，是單位產(chǎn)品（一周的）貯存費?！　∽顑?yōu)方程（1）

7、和狀態(tài)轉(zhuǎn)移方程（2）構(gòu)成了這個多階段決策問題的動態(tài)規(guī)劃模型。實際上，多階段決策問題有時也可用靜態(tài)規(guī)劃方法求解，如例2的生產(chǎn)計劃問題。例14資源分配問題?？偭繛榈馁Y源A和總量為的資源B同時分配給個用戶，已知第用戶利用數(shù)量的資源A和數(shù)量的資源B時，產(chǎn)生的效益為，問如何分配現(xiàn)有資源使總效益最大。這本來是個典型的靜態(tài)規(guī)劃問題：(1)（2）（3）但是當比較復(fù)雜及較大時，用非線性規(guī)劃求解是困難的，特別是，若是用表格或圖形給出而無解析表達式時，則難以求解。而這種情況下，將其轉(zhuǎn)化為動態(tài)規(guī)劃，是一種可行的方法。　　資源A，B每分配給一個用戶劃分為一個階段，分配給第用

8、戶的數(shù)量是二維決策變量，而把向第用戶分配之前，分配者手中掌握的資源數(shù)量作為二維狀態(tài)變量，記作，這樣，狀態(tài)轉(zhuǎn)移方程應(yīng)為（4）