動(dòng)態(tài)規(guī)劃簡(jiǎn)介

1、動(dòng)態(tài)規(guī)劃法簡(jiǎn)介多階段決策過程最短路問題特點(diǎn)：若O-H-P-D是最短路，則H-P-D是從H到D的最短路。最短路求解過程動(dòng)態(tài)規(guī)劃法減少了計(jì)算量,豐富了計(jì)算結(jié)果動(dòng)態(tài)規(guī)劃的基本概念1.階段:反映問題時(shí)間或空間的自然特性k;2.狀態(tài):表示在某階段開始所處的自然狀態(tài)或客觀條件sk;3.決策:可作出的選擇dk,允許決策集合;4.策略:決策序列(子策略);過程:狀態(tài)序列(子過程);對(duì)狀態(tài)要求具有無后效性,允許決策集合只與當(dāng)時(shí)的狀態(tài)有關(guān);5.狀態(tài)轉(zhuǎn)移方程:決策對(duì)下一階段狀態(tài)的影響sk+1 =Tk(sk ,dk);收益或支出函數(shù)r=rk(sk ,dk);6.最優(yōu)值函數(shù) fk(sk );遞推方程 fk(sk )=o

2、ptrk(sk ,dk)+fk+1(sk+1);kskdksk+1rk動(dòng)態(tài)規(guī)劃最優(yōu)性原理Bellman最優(yōu)性原理：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì):無論過去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的決策必定構(gòu)成一個(gè)最優(yōu)策略。換言之，最優(yōu)策略的子策略總是最優(yōu)的。同樣，最優(yōu)軌線的子軌線也是最優(yōu)的。用動(dòng)態(tài)規(guī)劃方法解優(yōu)化問題1)將問題恰當(dāng)?shù)膭澐蛛A段；2)狀態(tài)變量的選擇:能描述過程的演變，滿足無后效性；3)確定決策變量及允許決策集合；4)寫出狀態(tài)轉(zhuǎn)移方程和階段效益式；5)最優(yōu)值函數(shù):是定義在全過程和所有后部子過程的函數(shù)，具有可分離性，與原問題目標(biāo)相關(guān),寫出遞推方程及初始條件。例 用動(dòng)態(tài)規(guī)

3、劃方法求如下優(yōu)化問題的最優(yōu)解：. 0,5s.t.3min321321232221xxxxxxxxxz例 用動(dòng)態(tài)規(guī)劃方法求如下優(yōu)化問題的最優(yōu)解：分兩步：逆推確定各狀態(tài)的最優(yōu)值函數(shù)及最優(yōu)決策規(guī)則，順推確定最優(yōu)過程及最優(yōu)策略。動(dòng)態(tài)規(guī)劃的主要缺點(diǎn)是所謂的“維數(shù)災(zāi)”。且為整數(shù)。, 0,5s.t.3min321321232221xxxxxxxxxz資源分配問題例例: 某公司擬將某公司擬將50萬元資金投放下屬萬元資金投放下屬A、B、C三個(gè)部門，各三個(gè)部門，各部門在獲得資金后的收益如表所示，用動(dòng)態(tài)規(guī)劃方法求總部門在獲得資金后的收益如表所示，用動(dòng)態(tài)規(guī)劃方法求總收益最大的投資分配方案（投資數(shù)以收益最大的投資分配方案（投資數(shù)以10萬元為單位）。萬元為單位）。 投放資金（萬投放資金（萬元）元） 0102030405