資源描述：
《數(shù)學(xué)建模案例分析--最優(yōu)化方法建模6動(dòng)態(tài)規(guī)劃模型舉例》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、§6動(dòng)態(tài)規(guī)劃模型舉例 以上討論的優(yōu)化問題屬于靜態(tài)的，即不必考慮時(shí)間的變化，建立的模型——線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等，都屬于靜態(tài)規(guī)劃。多階段決策屬于動(dòng)態(tài)優(yōu)化問題，即在每個(gè)階段（通常以時(shí)間或空間為標(biāo)志）根據(jù)過程的演變情況確定一個(gè)決策，使全過程的某個(gè)指標(biāo)達(dá)到最優(yōu)。例如：（1）化工生產(chǎn)過程中包含一系列的過程設(shè)備，如反應(yīng)器、蒸餾塔、吸收器等，前一設(shè)備的輸出為后一設(shè)備的輸入。因此，應(yīng)該如何控制生產(chǎn)過程中各個(gè)設(shè)備的輸入和輸出，使總產(chǎn)量最大。（2）發(fā)射一枚導(dǎo)彈去擊中運(yùn)動(dòng)的目標(biāo)，由于目標(biāo)的行動(dòng)是不斷改變的，因此應(yīng)當(dāng)如何根據(jù)目標(biāo)運(yùn)動(dòng)的情況，不斷地決定導(dǎo)彈飛行的方向和速度，使之最快地命中目標(biāo)。（3
2、）汽車剛買來時(shí)故障少、耗油低，出車時(shí)間長，處理價(jià)值和經(jīng)濟(jì)效益高。隨著使用時(shí)間的增加則變得故障多，油耗高，維修費(fèi)用增加，經(jīng)濟(jì)效益差。使用時(shí)間俞長，處理價(jià)值也俞低。另外，每次更新都要付出更新費(fèi)用。因此，應(yīng)當(dāng)如何決定它每年的使用時(shí)間，使總的效益最佳。動(dòng)態(tài)規(guī)劃模型是解決這類問題的有力工具，下面介紹相關(guān)的基本概念及其數(shù)學(xué)描述。（1）階段整個(gè)問題的解決可分為若干個(gè)相互聯(lián)系的階段依次進(jìn)行。通常按時(shí)間或空間劃分階段，描述階段的變量稱為階段變量，記為。（2）狀態(tài)狀態(tài)表示每個(gè)階段開始時(shí)所處的自然狀況或客觀條件，它描述了研究過程的狀況。各階段的狀態(tài)通常用狀態(tài)變量描述。常用表示第階段的狀態(tài)變量。個(gè)階段的決策過程
3、有個(gè)狀態(tài)。用動(dòng)態(tài)規(guī)劃方法解決多階段決策問題時(shí)，要求整個(gè)過程具有無后效性。即：如果某階段的狀態(tài)給定，則此階段以后過程的發(fā)展不受以前狀態(tài)的影響，未來狀態(tài)只依賴于當(dāng)前狀態(tài)。（3）決策某一階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段某一狀態(tài)，這種選擇手段稱為決策。描述決策的變量稱為決策變量。決策變量限制的取值范圍稱為允許決策集合。用表示第階段處于狀態(tài)時(shí)的決策變量，它是的函數(shù)，用表示的允許決策集合。（4）策略一個(gè)由每個(gè)階段的決策按順序排列組成的集合稱為策略。由第階段的狀態(tài)開始到終止?fàn)顟B(tài)的后部子過程的策略記為。在實(shí)際問題中，可供選擇的策略有一定范圍，稱為允許策略集合。其中達(dá)到最優(yōu)效果的策略稱
4、為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程如果第個(gè)階段狀態(tài)變量為，作出的決策為，那么第階段的狀態(tài)變量也被完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，寫作，（6）最優(yōu)值函數(shù)指標(biāo)函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生結(jié)果的數(shù)量表示，是用來衡量策略優(yōu)劣的數(shù)量指標(biāo)，它定義在全過程和所有后部子過程上。指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)。下面的方程在動(dòng)態(tài)規(guī)劃逆序求解中起著本質(zhì)的作用。稱此為動(dòng)態(tài)規(guī)劃逆序求解的基本方程（貝爾曼方程）。可以把建立動(dòng)態(tài)規(guī)劃模型歸納成以下幾個(gè)步驟：（1）將問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)階段；（2）正確選擇狀態(tài)變量，使它既能描述過程的演變，又滿足無后效性；（3）規(guī)定決策變量，確定每個(gè)階段的允許決策集合；（4）寫出
5、狀態(tài)轉(zhuǎn)移方程；（5）確定各階段各種決策的階段指標(biāo)，列出計(jì)算各階段最優(yōu)后部策略指標(biāo)的基本方程。下面結(jié)合具體例子闡述建立動(dòng)態(tài)規(guī)劃模型的思路。例13 生產(chǎn)計(jì)劃問題。公司要對某產(chǎn)品制定周的生產(chǎn)計(jì)劃，產(chǎn)品每周的需求量、生產(chǎn)和貯存費(fèi)用、生產(chǎn)能力的限制、初始庫存量等都是已知的，試在滿足需求的條件下，確定每周的生產(chǎn)量，使周的總費(fèi)用最少。決策變量是第周的生產(chǎn)量，記作。已知下列數(shù)據(jù)及函數(shù)關(guān)系：第周的需求量：第周產(chǎn)量為時(shí)的生產(chǎn)費(fèi)為；第周初貯存量為時(shí)這一周的貯存費(fèi)為；第周的生產(chǎn)能力限制為；初始（）及終結(jié)（）時(shí)貯存量均為零。按照最短路問題的思路，設(shè)從第周初貯存量為到（周末）過程結(jié)束的最小費(fèi)用函數(shù)為，則下列逆向遞推
6、公式成立。(1)而與滿足(2) 這里貯存量是狀態(tài)變量，（2）式給出了相鄰階段的狀態(tài)在決策變量作用下的轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移規(guī)律。在用（1）式計(jì)算時(shí)，的取值范圍——允許狀態(tài)集合由（2）式及允許決策集合決定。 在實(shí)際問題中，為簡單起見，生產(chǎn)費(fèi)用常取，；，，其中是單位產(chǎn)品生產(chǎn)費(fèi)，而是生產(chǎn)準(zhǔn)備費(fèi)。貯存費(fèi)用常取，是單位產(chǎn)品（一周的）貯存費(fèi)。 最優(yōu)方程（1）和狀態(tài)轉(zhuǎn)移方程（2）構(gòu)成了這個(gè)多階段決策問題的動(dòng)態(tài)規(guī)劃模型。實(shí)際上，多階段決策問題有時(shí)也可用靜態(tài)規(guī)劃方法求解，如例2的生產(chǎn)計(jì)劃問題。例14資源分配問題?？偭繛榈馁Y源A和總量為的資源B同時(shí)分配給個(gè)用戶，已知第用戶利用數(shù)量的資源A和數(shù)量的資源B
7、時(shí)，產(chǎn)生的效益為，問如何分配現(xiàn)有資源使總效益最大。這本來是個(gè)典型的靜態(tài)規(guī)劃問題：(1)（2）（3）但是當(dāng)比較復(fù)雜及較大時(shí)，用非線性規(guī)劃求解是困難的，特別是，若是用表格或圖形給出而無解析表達(dá)式時(shí)，則難以求解。而這種情況下，將其轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃，是一種可行的方法?！ ≠Y源A，B每分配給一個(gè)用戶劃分為一個(gè)階段，分配給第用戶的數(shù)量是二維決策變量，而把向第用戶分配之前，分配者手中掌握的資源數(shù)量作為二維狀態(tài)變量，記作，這樣，狀態(tài)轉(zhuǎn)移方程應(yīng)為（4）
