系統(tǒng)工程---第六章動態(tài)規(guī)劃(已修改)
2025-10-25 18:55 本頁面
【正文】 山東理工大學管理學院 第六章 動態(tài)規(guī)劃 ? 動態(tài)規(guī)劃的基本原理和基本方程 ? 機器負荷分配問題 ? 資源分配問題 ? 背包問題 ? 連續(xù)型動態(tài)規(guī)劃問題 山東理工大學管理學院 動態(tài)規(guī)劃的基本原理和基本方程 ? 動態(tài)規(guī)劃的最優(yōu)性原理 ? 動態(tài)規(guī)劃的基本概念 ? 動態(tài)規(guī)劃的基本方程 ? 建立動態(tài)規(guī)劃的數(shù)學模型 ? 動態(tài)規(guī)劃的求解 山東理工大學管理學院 動態(tài)規(guī)劃的最優(yōu)性原理 動態(tài)規(guī)劃的基本原理和基本方程 ◆ 動態(tài)規(guī)劃是解決多階段決策問題的一種數(shù)學方法。 ◆ 所謂多階段決策問題 ， 是指對系統(tǒng)運行過程中若干相繼階段的每一段都要作出決策，并使整個過程達到最優(yōu)的一類問題 。 50年代，美國數(shù)學家貝爾曼 (Richard Bellman)等人，根據(jù)多階段決策問題的性質(zhì)，提出了解決這類問題的 “ 最優(yōu)性原理 ” ，并研究了許多實際問題，從而建立了一種新的最優(yōu)化方法 —— 動態(tài)規(guī)劃 （ Dynamic Programming)。 山東理工大學管理學院 表述一 ：一個最優(yōu)策略具有這樣的性質(zhì)，不論初始狀態(tài)及初始決策如何，對于該決策所造成的某一狀態(tài)而言，下余的所有決策必構(gòu)成一個最優(yōu)策略。 表述二 ： 假設(shè)對任意的時刻 t，不論過程在時刻 t以前的歷史狀態(tài)如何，若按時刻 t的狀態(tài)而言，過程今后的行為是最優(yōu)的。則整個過程的行為亦必是最優(yōu)的。 (無后效性 ) 表述三： 如圖，假設(shè)采取了最優(yōu)策略，得到了某個系統(tǒng)運動的最優(yōu)軌線，該最優(yōu)軌線將狀態(tài)空間中的點（起點）與點（終點）連接起來，現(xiàn)在最優(yōu)軌線上取某個中間點，從而將最優(yōu)線分為 Ⅰ 、 Ⅱ 兩段，則子軌線 Ⅱ 也是最優(yōu)的。 Ⅱ′ Ⅰ Ⅱ 系統(tǒng)運動最優(yōu)軌線圖 0x 1x vx 2x Tx 動態(tài)規(guī)劃的基本原理和基本方程 動態(tài)規(guī)劃的最優(yōu)性原理 山東理工大學管理學院 表示每個階段開始所處的自然狀況或客觀條件。又稱不可控因素。描述過程狀態(tài)的變量稱為 狀態(tài)變量 ，用 si 表示。 顯然， si 既是階段（ i1）的結(jié)束狀態(tài)，又是階段 i 的起始狀態(tài)。 將整個系統(tǒng)過程恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段 ， 以便能按一定的次序求解 。 描述階段的變量稱為階段變量 ， 常用 i 表示 。 階段數(shù)用 n表示 。 (2)狀態(tài)（ State） (1)階段（ Stage） 動態(tài)規(guī)劃的基本原理和基本方程 動態(tài)規(guī)劃的基本概念 山東理工大學管理學院 (3)決策（ Decision） (4)策略 （ Policy） 各階段的決策組成的一個決策序列稱為一個策略 ， 記為： ? ?nxxxp , 21 ?? 從階段 i開始的過程 ， 稱為 i子過程 ， 它包含階段 i， 階段 i+1， … ， 階段 n。 i子過程的決策序列稱為 i子策略 ， 記為 ? ?1,2,1, 1 ??? ? nixxxp niii ?? 動態(tài)規(guī)劃的基本原理和基本方程 山東理工大學管理學院 階段指標 (或階段收益 )， 是衡量每一階段決策優(yōu)劣的數(shù)量指標。 指標函數(shù) 是衡量全過程策略或 i子過程策略優(yōu)劣的數(shù)量指標 ,指標函數(shù)的最優(yōu)值稱為 最優(yōu)指標函數(shù) ，記為 f1(s1) 或 fi (si)。 （ 5）狀態(tài)轉(zhuǎn)移方程 由某一階段的一個狀態(tài)到下一階段的另一狀態(tài)的演變稱為狀態(tài)轉(zhuǎn)移。描述狀態(tài)轉(zhuǎn)移規(guī)律的方程稱為 狀態(tài)轉(zhuǎn)移方程 。記為 si+1 = gi (si , xi) gi稱為狀態(tài)轉(zhuǎn)移函數(shù)。 （ 6）階段指標、指標函數(shù)、最優(yōu)指標函數(shù) 動態(tài)規(guī)劃的基本原理和基本方程 山東理工大學管理學院 動態(tài)規(guī)劃的基本原理和基本方程 動態(tài)規(guī)劃的基本方程 (1) 動態(tài)規(guī)劃的基本方程 (逆序遞推公式 ) ? ? 1,1,)(),()( 1* 1* ????? ?? nnisfxsvoptsf iiiixii i),(1 iii xsgs ?? ， 0)( 1* 1 ??? nn xf(2) 動態(tài)規(guī)劃的基本方程 (正序遞推公式 ) ? ? nisfxsvo p tsf iiiixii i,2,1)()
教學課件相關(guān)推薦
鄂ICP備17016276號-1