動態(tài)規(guī)劃模型舉例ppt課件-展示頁
2025-05-15 12:08本頁面
【正文】 限制、初始庫存量等都是已知的，試在滿足需求的條件下，確定每周的生產(chǎn)量，使 n周的總費用最少。 可以把建立動態(tài)規(guī)劃模型歸納成以下幾個步驟： （ 1）將問題恰當?shù)貏澐譃槿舾蓚€階段； （ 2）正確選擇狀態(tài)變量，使它既能描述過程的演變，又滿足無后效性； （ 3）規(guī)定決策變量，確定每個階段的允許決策集合； （ 4）寫出狀態(tài)轉(zhuǎn)移方程； （ 5）確定各階段各種決策的階段指標，列出計算各階段最優(yōu)后部策略指標的基本方程。 kkx ku 1?k1?kx(1 kk Tx ?? kx )ku6/3/2022 14 下面方程在動態(tài)規(guī)劃逆序求解中起著本質(zhì)的作用。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，寫作 , （ 6）最優(yōu)值函數(shù) 指標函數(shù)是系統(tǒng)執(zhí)行某一策略所產(chǎn)生結(jié)果的數(shù)量表示，是用來衡量策略優(yōu)劣的數(shù)量指標，它定義在全過程和所有后部子過程上。其中達到最優(yōu)效果的策略稱為 最優(yōu)策略 。 （ 4）策略 一個由每個階段的決策按順序排列組成的集合稱為 策略 。決策變量限制的取值范圍稱為 允許決策集合 。 kkx kn 1?n6/3/2022 12 （ 3）決策 某一階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段某一狀態(tài)，這種選擇手段稱為 決策 。用動態(tài)規(guī)劃方法解決多階段決策問題時，要求整個過程具有 無后效性 。常用 表示第 階段的狀態(tài)變量。 （ 2）狀態(tài) 狀態(tài)表示每個階段開始時所處的自然狀況或客觀條件，它描述了研究過程的狀況。 E D A B C V4 V5 V6 V3 V1 V2 2 5 3 5 2 6 7 5 1 2 8 7 2 3 1 1 6 3 10 圖３ 圖４ 6/3/2022 11 下面介紹動態(tài)規(guī)劃相關的基本概念及其數(shù)學描述 （ 1）階段 整個問題的解決可分為若干個相互聯(lián)系的階段依次進行。在動態(tài)規(guī)劃中 f（ x）稱最優(yōu)值函數(shù)，（ 1）式稱最優(yōu)方程。 ,)(,12)(,)(,9)(,)(,10)(,)(,13)(34343233331232311313DCuCfDCuCfDCuCfDCuCf????????6/3/2022 9 不難看出，上述計算過程可以表示為如下的一般形式： (1) 其中 D（ x）表示在 x的允許決策集合，如 D2（ B1） =（ C1， C2， C3)， X表示第 k段的允許狀態(tài)集合，如 X2=(B1，B2）。 ????????)(),()(),(2621516115FfFEdFfFEd????????35431F56 66 66/3/2022 7 表明 E2到 G的最短路是 E2－ F2－ G，即 E2的最優(yōu)決策為 u5（ E2） = F2。用 dk（ xk， xk+1）表示第 k段的點 xk與第 k+1段的點 xk+1之間的（已知）距離（視 k的不同， x分別代表 A， B， … ， F），用 uk（ xk）表示在 xk的決策，即從 xk向哪一點走，則 xk+1可以記作xk+1=uk（ xk）。根據(jù)最短路的這一特性，我們可以從最后一段開始，用逐步向前遞推的方法，依次求出路段上各點到 G的最短路，最后得到 A到 G的最短路。 A B1 B2 C1 C2 C3 C4 D3 D2 D1 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 8 4 3 3 5 3 8 6 2 2 1 2 3 3 6 6 2 5 5 3 4 3 圖２ 6/3/2022 5 用動態(tài)規(guī)劃解決問題的思路，來源于生活中這樣一個基本常識：如果已經(jīng)找到由 A到 G的最短路線是 A— B1—C2— D1 — E2— F2— G（圖中粗線，記作 L），那么當尋求L中的任何一點（如 D1）到 G的最短路時，它必然是 L中的子路 D1 — E2— F2— G（記作 L1）。不難算出，一共有 48條從 A到 G的路線，用加法得到每條路線的長度后，再作比較即可找出最短路線。圖 2是一個線路網(wǎng)，連線上的數(shù)字表示兩點之間的距離（或費用），尋找一條由 A到G的路線，使距離最短（或費用最省）。下面結(jié)合具體例子闡述建立動態(tài)規(guī)劃模型的思路。因此，應當如何決定它的使用年限，使總的效益最佳。使用時間俞長，處理價值也俞低。 6/3/2022 3 （ 3）汽車剛買來時故障少、耗油低，出車時間長，處理價值和經(jīng)濟效益高。因此，應該如何控制生產(chǎn)過程中各個設備的輸入和輸出，使總產(chǎn)量最大。多階段決策屬于動態(tài)優(yōu)化問題，即在每個階段（通常以時間或空間為標志）要根據(jù)過程的演變情況確定一個決策，使全過程的某個指標達到最優(yōu)。6/3/2022 1 167。 6 動態(tài)規(guī)劃模型舉例 6/3/2022 2 以上討論的優(yōu)化問題大多數(shù)屬于靜態(tài)的，即不必考慮時間的變化，建立的模型 —— 線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃等，都屬于靜態(tài)規(guī)劃。 例如： （ 1）化工生產(chǎn)過程中包含一系列的過程設備
教學課件相關推薦
鄂ICP備17016276號-1