資源描述:
《數(shù)學(xué)建模案例分析--最優(yōu)化方法建模6動態(tài)規(guī)劃模型舉例》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、word資料下載可編輯§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)發(fā)射一枚導(dǎo)彈去擊中運(yùn)動的目標(biāo),由于目標(biāo)的行動是不斷改變的,因此應(yīng)當(dāng)如何
2、根據(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ī)劃模型是解決這類問題的有力工具,下面介紹相關(guān)的基本概念及其數(shù)學(xué)描述。(1)階段整個問題的解決可分為若干個相互聯(lián)系的階段依次進(jì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)只依賴于當(dāng)前狀態(tài)。(3)決策某一階段的狀態(tài)確定后,可以作出各種選擇從而演變到下一階段某一狀態(tài),這種選擇手段稱為決策。描述決策的變量稱為決策變量。決策變量限制的取值范圍稱為允許決策集合。用表示第階段處于狀態(tài)時的決策變量,它是的函數(shù),用表示的允許決策
4、集合。(4)策略一個由每個階段的決策按順序排列組成的集合稱為策略。由第階段的狀態(tài)開始到終止?fàn)顟B(tài)的后部子過程的策略記為。在實(shí)際問題中,可供選擇的策略有一定范圍,稱為允許策略集合。其中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。(5)狀態(tài)轉(zhuǎn)移方程如果第個階段狀態(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ù)。下面的方程在動態(tài)規(guī)劃逆序求解中起
5、著本質(zhì)的作用。專業(yè)技術(shù)資料word資料下載可編輯稱此為動態(tài)規(guī)劃逆序求解的基本方程(貝爾曼方程)??梢园呀討B(tài)規(guī)劃模型歸納成以下幾個步驟:(1)將問題恰當(dāng)?shù)貏澐譃槿舾蓚€階段;(2)正確選擇狀態(tài)變量,使它既能描述過程的演變,又滿足無后效性;(3)規(guī)定決策變量,確定每個階段的允許決策集合;(4)寫出狀態(tài)轉(zhuǎn)移方程;(5)確定各階段各種決策的階段指標(biāo),列出計算各階段最優(yōu)后部策略指標(biāo)的基本方程。下面結(jié)合具體例子闡述建立動態(tài)規(guī)劃模型的思路。例13生產(chǎn)計劃問題。公司要對某產(chǎn)品制定周的生產(chǎn)計劃,產(chǎn)品每周的需求量、生產(chǎn)和貯存費(fèi)用、生產(chǎn)能力的限制
6、、初始庫存量等都是已知的,試在滿足需求的條件下,確定每周的生產(chǎn)量,使周的總費(fèi)用最少。決策變量是第周的生產(chǎn)量,記作。已知下列數(shù)據(jù)及函數(shù)關(guān)系:第周的需求量:第周產(chǎn)量為時的生產(chǎn)費(fèi)為;第周初貯存量為時這一周的貯存費(fèi)為;第周的生產(chǎn)能力限制為;初始()及終結(jié)()時貯存量均為零。按照最短路問題的思路,設(shè)從第周初貯存量為到(周末)過程結(jié)束的最小費(fèi)用函數(shù)為,則下列逆向遞推公式成立。(1)而與滿足(2)這里貯存量是狀態(tài)變量,(2)式給出了相鄰階段的狀態(tài)在決策變量作用下的轉(zhuǎn)移規(guī)律,稱為狀態(tài)轉(zhuǎn)移規(guī)律。在用(1)式計算時,的取值范圍——允許狀態(tài)集合由(
7、2)式及允許決策集合決定。在實(shí)際問題中,為簡單起見,生產(chǎn)費(fèi)用常取,;,專業(yè)技術(shù)資料word資料下載可編輯,其中是單位產(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)成了這個多階段決策問題的動態(tài)規(guī)劃模型。實(shí)際上,多階段決策問題有時也可用靜態(tài)規(guī)劃方法求解,如例2的生產(chǎn)計劃問題。例14資源分配問題??偭繛榈馁Y源A和總量為的資源B同時分配給個用戶,已知第用戶利用數(shù)量的資源A和數(shù)量的資源B時,產(chǎn)生的效益為,問如何分配現(xiàn)有資源使總效益最大。這本來是個典型的靜態(tài)規(guī)劃問題:(1)(2)
8、(3)但是當(dāng)比較復(fù)雜及較大時,用非線性規(guī)劃求解是困難的,特別是,若是用表格或圖形給出而無解析表達(dá)式時,則難以求解。而這種情況下,將其轉(zhuǎn)化為動態(tài)規(guī)劃,是一種可行的方法。資源A,B每分配給一個用戶劃分為一個階段,分配給第用戶的數(shù)量是二維決策變量,而把向第用戶分配之前,分配者手中掌