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

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

2、量最大。（2）發(fā)射一枚導(dǎo)彈去擊中運(yùn)動的目標(biāo)，由于目標(biāo)的行動是不斷改變的，因此應(yīng)當(dāng)如何根據(jù)目標(biāo)運(yùn)動的情況，不斷地決定導(dǎo)彈飛行的方向和速度，使之最快地命中目標(biāo)。（3）汽車剛買來時故障少、耗油低，出車時間長，處理價值和經(jīng)濟(jì)效益高。隨著使用時間的增加則變得故障多，油耗高，維修費(fèi)用增加，經(jīng)濟(jì)效益差。使用時間俞長，處理價值也俞低。另外，每次更新都要付出更新費(fèi)用。因此，應(yīng)當(dāng)如何決定它每年的使用時間，使總的效益最佳。動態(tài)規(guī)劃模型是解決這類問題的有力工具

3、，下面介紹相關(guān)的基本概念及其數(shù)學(xué)描述。（1）階段整個問題的解決可分為若干個相互聯(lián)系的階段依次進(jìn)行。通常按時間或空間劃分階段，描述階段的變量稱為階段變量階段變量，記為。k（2）狀態(tài)狀態(tài)表示每個階段開始時所處的自然狀況或客觀條件，它描述了研究過程的狀況。各階段的狀態(tài)通常用狀態(tài)變量狀態(tài)變量描述。常用表示第階段的狀態(tài)變量。個階段的決策過程有kxkn個狀態(tài)。用動態(tài)規(guī)劃方法解決多階段決策問題時，要求整個過程具有無后效性無后效性。即：如果1?n某階段

4、的狀態(tài)給定，則此階段以后過程的發(fā)展不受以前狀態(tài)的影響，未來狀態(tài)只依賴于當(dāng)前狀態(tài)。（3）決策某一階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段某一狀態(tài)，這種選擇手段稱為決策決策。描述決策的變量稱為決策變量決策變量。決策變量限制的取值范圍稱為允許決策集合允許決策集合。用表示第階段處于狀態(tài)時的決策變量，它是的函數(shù)，用表示的允許)(kkxukkxkx)(kkxDkx決策集合。（4）策略一個由每個階段的決策按順序排列組成的集合稱為策略策略。

5、由第階段的狀態(tài)開始kkx到終止?fàn)顟B(tài)的后部子過程的策略記為。在實(shí)際問題中，)()()()(11nnkkkkkkxuxuxuxp????可供選擇的策略有一定范圍，稱為允許策略集合允許策略集合。其中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程如果第個階段狀態(tài)變量為，作出的決策為，那么第階段的狀kkxku1?k態(tài)變量也被完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，寫作，1?kx(1kkTx??kx)ku（6）最優(yōu)值函數(shù)指標(biāo)函數(shù)是系統(tǒng)

6、執(zhí)行某一策略所產(chǎn)生結(jié)果的數(shù)量表示，是用來衡量策略優(yōu)劣的數(shù)量指標(biāo)，它定義在全過程和所有后部子過程上。指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)最優(yōu)值函數(shù)。數(shù)學(xué)建模數(shù)學(xué)建模，其中是單位產(chǎn)品生產(chǎn)費(fèi)，而是生產(chǎn)準(zhǔn)備費(fèi)。貯存費(fèi)用常取，是單0?kucakkkhxxh?)(h位產(chǎn)品（一周的）貯存費(fèi)。最優(yōu)方程（1）和狀態(tài)轉(zhuǎn)移方程（2）構(gòu)成了這個多階段決策問題的動態(tài)規(guī)劃模型。實(shí)際上，多階段決策問題有時也可用靜態(tài)規(guī)劃方法求解，如例2的生產(chǎn)計劃問題。例14資源分配問題?？?/p>

7、量為的資源A和總量為的資源B同時分配給n個用戶，已知第1m2m用戶利用數(shù)量的資源A和數(shù)量的資源B時，產(chǎn)生的效益為，問如何分配現(xiàn)有資kkukv)(kkkvug源使總效益最大。這本來是個典型的靜態(tài)規(guī)劃問題：(1)???nkkkkvugZMax1)(????nkkkumuts110..（2）????nkkkvmv120（3）但是當(dāng)比較復(fù)雜及n較大時，用非線性規(guī)劃求解是困難的，特別是，若是用表格或圖形給kgkg出而無解析表達(dá)式時，則難以求解。而

8、這種情況下，將其轉(zhuǎn)化為動態(tài)規(guī)劃，是一種可行的方法。資源A，B每分配給一個用戶劃分為一個階段，分配給第用戶的數(shù)量是二維決策變量k，而把向第用戶分配之前，分配者手中掌握的資源數(shù)量作為二維狀態(tài)變量，記作)(kkvuk，這樣，狀態(tài)轉(zhuǎn)移方程應(yīng)為)(kkyx?????????kkkkkkvyyuxx11（4）最優(yōu)值函數(shù)定義為將數(shù)量的資源分配給第至第n用戶時能獲得的最大效益，)(kkkyxf)(kkyxk它滿足最優(yōu)方程????????????????