【正文】 路 : i1=1, x1(1)=2→ i2=1, x2(1)=0→ i3=0, x3(0)=2→ i4=0 它的子路徑如 i2=1→ i3=0→ i4=0 也是最短路 確定需求下多時(shí)段 (T時(shí)段 )生產(chǎn)計(jì)劃的一般模型 最大生產(chǎn)能力 Xm 最大存貯量 Im 第 1時(shí)段初庫存量 i1 需求量 dt, 產(chǎn)量 xt , 存貯量 it, 生產(chǎn) 費(fèi) c (xt), 存貯費(fèi) h(it) 1. 根據(jù)對時(shí)段 T末存貯量的要求，確定 fT+1(iT+1) 2. 時(shí)段 從后向前 地計(jì)算最小費(fèi)用，遞推公式： 1,1,) } ,()()({m i n)( 111??????????? ???TTtXxIidxiiifihxcifmtmtttttttttxtttf1(i1)為總費(fèi)用最小值 從前向后 地確定最優(yōu)生產(chǎn)計(jì)劃 : 由 i1 , xt(it) 及 it+1= it +xt(it)dt 得到 xt 動(dòng)態(tài)規(guī)劃模型 隨機(jī)需求下的多階段生產(chǎn)計(jì)劃 需求量隨機(jī) 存貯量隨機(jī) 存貯費(fèi)及總費(fèi)用隨機(jī) 優(yōu)化目標(biāo)是總費(fèi)用的期望最小 隨機(jī)動(dòng)態(tài)規(guī)劃模型 隨機(jī)需求 : P(dt=1)=1/3, P(dt=2)=2/3 (t=1,2,3) 存貯費(fèi)的期望值 Eh(it)= h0E (it+ xtdt) =(it+xt1)P(dt=1) +(it+xt2)P(dt=2)=(it+xt1)/3+2(it+xt2)/3=it+xt5/3 對于存貯量 i3, 計(jì)劃結(jié)束時(shí)出售剩余量得到的回報(bào)為 s(i3), 期望值 Es(i3)=[(i3+x31)/3+2(i3+x32)/3]=(i3+x3) 計(jì)劃結(jié)束時(shí)存貯量隨機(jī) , 假定剩余存貯量以 隨機(jī)需求下的多階段生產(chǎn)計(jì)劃 1. 最后時(shí)段 (時(shí)段 3) 時(shí)段 3初的存貯量 i3, 產(chǎn)量 x3(i3), 期望 費(fèi)用最小值 f3(i3) Es(i3)=(i3+x3) P(dt=1)=1/3, P(dt=2)=2/3 f3(0)=c(2)Es(0)=71/2=13/2, x3(0)=2 f3(1)=c(1) Es(1)=51/2=9/2, x3(1)=1 f3(2)=c(0) Es(2)=01/2=1/2, x3(2)=0 f3(3)=c(0) Es(3)=02= 2, x3(3)=0 計(jì)算 2. 時(shí)段 2 時(shí)段 2,3期望 費(fèi)用最小值 }3/)2(23/)1()()({m i n)( 22322322222???????? xifxifiEhxcif x2≤i2+x2≤4, x2≤Xm , i2≤Im i2 x2 c(x2) Eh(i2) f3 (i2+x21)/3 +2 f3 (i2+x22)/3 c+Eh+ f3 f2(i2)， x2(i2) 0 2 7 1/3 35/6 79/6 f2(0)= 37/3 x2(0)=4 0 3 9 4/3 17/6 79/6 0 4 11 7/3 1 37/3* 1 1 5 1/3 35/6 67/6 f2(1)= 31/3 x2(1)=3 1 2 7 4/3 17/6 67/6 1 3 9 7/3 1 31/3* 2 0 0 1/3 35/6 37/6* f2(2)=37/6 x2(2)=0 2 1 5 4/3 17/6 55/6 2 2 7 7/3 1 25/3 3 0 0 4/3 17/6 25/6* f2(3)= 25/6 x2(3)=0 3 1 5 7/3 1 19/3 3. 時(shí)段 1 時(shí)段 1初存貯量 i1=1 }3/)2(23/)1()()({m i n)( 11211211111???????? xifxifiEhxcif x2≤i1+x1≤4 i1 x1 c(x1) Eh(i1) f2 (i1+x11)/3 +2 f2 (i1+x12)/3 c+Eh+ f2 f1(i1)， x1(i1) 1 1 5 1/3 105/9 306/18 f1(1)=303/18 x1(1)=3 1 2 7 4/3 161/18 311/18 1 3 9 7/3 33/6 303/18* 時(shí)段 1~3期望 費(fèi)用最小值 x2(i2)=0 d1=1 i2=1+31=3 d1=2 i2=1+32=2 x2(i2)=0 x3(i3)=0 d2=1 i3=3+01=2 d2=2 i3=3+02=1 x3(i3) =1 x3(i3)=1 d2=1 i3=2+01=1 d2=2 i3=2+02=0 x3(i3) =2 d2=2 d2=2 d2=1 d2=1 d1=2 d1=1 i1=1 x1=3 i2=3 x2=0 i3=2 x3=0 i3=1 x3=1 i3=1 x3=1 i3=0 x3=2 i2=2 x2=0 隨機(jī)需求下多階段生產(chǎn)計(jì)劃 確定性需求下的最優(yōu)生產(chǎn)計(jì)劃在開始時(shí)已完全確定 : x1=2， x2=0， x3=2 隨機(jī)需求下的最優(yōu)生產(chǎn)計(jì)劃只有當(dāng)每個(gè)時(shí)段初的存貯量知道后才能確定 ! 建立動(dòng)態(tài)規(guī)劃模型的主要步驟 (以求解 多階段生產(chǎn)計(jì)劃問題為例 ) 1. 將整個(gè)問題劃分為若干離散階段 . 2. 定義狀態(tài) (如存貯量 )和決策 (如產(chǎn)量 ). 3. 建立狀態(tài)轉(zhuǎn)移律 (如 it+1= it+xtdt). 4. 確定允許狀態(tài)集合和允許決策集合 (如 it≤Im, xt≤Xm). 5. 列出最優(yōu)方程 ( ft(it))并確定終端條件（ fT+1(iT+1)） . 6. 時(shí)段從后向前地求解最優(yōu)方程 . 狀態(tài)應(yīng)描述過程特征 。動(dòng)態(tài)優(yōu)化模型（完整版） ? 連續(xù)動(dòng)態(tài)過程的優(yōu)化歸結(jié)為求泛函的極值 . ? 求泛函極值的常用方法 : 變分法、 最優(yōu)控制論 . ? 離散動(dòng)態(tài)過程的優(yōu)化 ~ 動(dòng)態(tài)規(guī)劃模型 . 靜態(tài)優(yōu)化問題 優(yōu)化目標(biāo)是數(shù)值 最優(yōu)策略是數(shù)值 ? 函數(shù)對應(yīng)的數(shù)值稱為泛函 (函數(shù)的函數(shù) ). 動(dòng)態(tài)優(yōu)化問題 優(yōu)化目標(biāo)是數(shù)值 最優(yōu)策略是 函數(shù) 1 速降線與短程線 通過兩個(gè)古典問題介紹變分法的基本概念 , 給出主要結(jié)果 . 速降線問題 給定豎 直 平面內(nèi)不在一條垂直線上的兩個(gè)點(diǎn) A, B, 求連接 A, B的光滑曲線，使質(zhì)點(diǎn)在重力作用下沿該曲線以 最短時(shí)間 從 A滑到 B (摩擦力不計(jì) ). . A . B 若沿陡峭曲線下滑 , 雖路徑加長，但速度增長很快 . 若沿直線段 AB下滑 , 路徑雖短 , 但速度增長慢 。 速降線問題 . A . B 建立坐標(biāo)系 xOy, x y y=y(x) O 曲線弧長 2d 1 ds y x???能量守恒 21d()2dsm m g yt ?質(zhì)點(diǎn)在曲線 y(x)上的速度 ds/dt 21dd2 ytxgy ???質(zhì)點(diǎn)沿曲線 y(x)從 A到 B的時(shí)間 1 201( ( ) ) d2x yJ y x xgy??? ?11 )(,0)0(yxyy??求 y(x) 使 J(y(x)) 達(dá)到最小 . m~質(zhì)點(diǎn)質(zhì)量，g~重力加速度 A(0,0), B(x1,y1), 曲線 AB ~y=y(x) 滿足條件 短程線問題 . A