動(dòng)態(tài)規(guī)劃DynamicProgramming第八章動(dòng)態(tài)規(guī)劃的基本方法§1多階段決策問題與動(dòng)態(tài)規(guī)劃§2動(dòng)態(tài)規(guī)劃的基本概念和基本方程§3動(dòng)態(tài)規(guī)劃的最優(yōu)性原理§4動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系及動(dòng)態(tài)規(guī)劃的解法第九章動(dòng)態(tài)規(guī)劃的應(yīng)用

重點(diǎn)和難點(diǎn)§1多階段決策問題與動(dòng)態(tài)規(guī)劃

要求從A點(diǎn)到G點(diǎn)的最短路，弧旁的數(shù)字表示距離例2機(jī)器負(fù)荷分配問題某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)．在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u的關(guān)系為g＝g(u),這時(shí)機(jī)器的年完好率為a（0<a<1)．在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量v的關(guān)系為h＝h(v),這時(shí)機(jī)器的年完好率為b（a<b<1）．假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1，要求制定一個(gè)五年計(jì)劃,在每年開始時(shí)決定機(jī)器在兩種不同負(fù)荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。圖8-1

多階段決策問題和我們一般的決策問題不同，它是和時(shí)間有關(guān)的。與時(shí)間有關(guān)的活動(dòng)過程稱為動(dòng)態(tài)過程，其優(yōu)化方法稱為動(dòng)態(tài)規(guī)劃。而與時(shí)間無關(guān)的活動(dòng)過程稱為靜態(tài)過程，相應(yīng)的的優(yōu)化方法稱為靜態(tài)規(guī)劃。多階段決策多階段決策（Multi-StageDecisionMaking），是將決策問題的全過程恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系的子過程（每個(gè)子過程為一個(gè)決策階段），以便按照一定的次序去求解。階段一般是根據(jù)時(shí)間和空間的自然特征來劃分，以便于問題的求解為目的.

描述階段的變量稱為階段變量，一般用k表示.從第k個(gè)階段開始點(diǎn)到全過程終點(diǎn)的過程稱為后部子過程，或k子過程。§2

動(dòng)態(tài)規(guī)劃的基本概念

和基本方程2.1

動(dòng)態(tài)規(guī)劃的基本概念階段（stage）把所研究的決策問題，按先后順序劃分為若干相互聯(lián)系的決策步驟，以便按一定的次序進(jìn)行求解。描述階段的變量稱階段變量，常用k表示。狀態(tài)（state）狀態(tài)表示每個(gè)階段開始時(shí)所處的自然狀況或客觀條件，它描述了影響決策的因素隨決策進(jìn)程的變化情況，它既是前面階段所作決策的結(jié)果，又是本階段作出決策的出發(fā)點(diǎn)和依據(jù)。描述狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示。通常，在第一階段狀態(tài)變量s1是確定的，稱初始狀態(tài)。(3)決策（decisionmaking）：決策表示在某一階段處于某種狀態(tài)時(shí)，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk(sk)表示。決策變量的取值會(huì)受到狀態(tài)變量的制約，被限制在某一范圍D(sk)——允許決策集合之內(nèi)。(4)策略（strategy）：把從第一階段開始到最后階段終止的整個(gè)決策過程，稱為問題的全過程；而把從第k階段開始到最后階段終止的決策過程，或稱為k子過程。在全過程上，各階段的決策按順序排列組成的決策序列p1,n＝{u1,u2,……,un}稱為全過程策略，簡稱策略；而在k子過程上的決策序列pk,n＝{uk,uk+1,……,un}稱為k子過程策略，也簡稱子策略。(5)狀態(tài)轉(zhuǎn)移方程若第k階段的狀態(tài)變量值為sk，當(dāng)決策變量uk的取值決定后，下一階段狀態(tài)變量sk+1的值也就完全確定。即sk+1的值對(duì)應(yīng)于sk和uk的值。這種對(duì)應(yīng)關(guān)系記為sk+1＝Tk(sk,uk)或sk+1＝uk(sk)，稱為狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程描述了由一個(gè)階段的狀態(tài)到下一階段的狀態(tài)的演變規(guī)律。(6)指標(biāo)函數(shù)（準(zhǔn)則函數(shù)）

（CriterionFunction）

、目標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來衡量所實(shí)現(xiàn)過程或決策優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)。指標(biāo)函數(shù)分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。階段指標(biāo)函數(shù)是對(duì)某一階段的狀態(tài)和決策產(chǎn)生的效益值的度量，用vk(sk,uk)表示。過程指標(biāo)函數(shù)是指過程所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值，記為

Vk,n＝Vk,n(sk,uk,sk+1,uk+1,……,sn,un)定義在全過程上的準(zhǔn)則函數(shù)相當(dāng)于目標(biāo)函數(shù)，一般記為V1,n＝V1,n(s1,u1,s2,u2,……,sn,un)，或簡記為V1,n動(dòng)態(tài)規(guī)劃所要求的過程指標(biāo)函數(shù)應(yīng)具有可分離性，即可表達(dá)為它所包含的各階段指標(biāo)函數(shù)的函數(shù)形式。常見的兩種過程指標(biāo)函數(shù)形式是：①各階段指標(biāo)函數(shù)的和Vk,n＝∑vj(sj,uj)；②各階段指標(biāo)函數(shù)的積Vk,n＝∏vj(sj,uj)。把過程指標(biāo)函數(shù)Vk,n對(duì)k子過程策略pk,n求最優(yōu)，得到一個(gè)關(guān)于狀態(tài)sk的函數(shù)，稱為最優(yōu)值函數(shù)，記為fk(sk)。即

fk(sk)＝optVk,n(sk,uk,……,sn,un)uk,…,un式中的“opt”（optimization）可根據(jù)具體問題的題意

而取min或max。動(dòng)態(tài)規(guī)劃中，多階段決策問題具有無后效性（馬爾可夫性質(zhì)），即當(dāng)某階段的狀態(tài)一旦確定,則此后過程的演變不再受此前各狀態(tài)和決策的影響,或者說“未來與過去無關(guān)，只與現(xiàn)在有關(guān)”.即由狀態(tài)xk出發(fā)的后部子過程可以看成一個(gè)以xk為初始狀態(tài)的獨(dú)立過程.2.2動(dòng)態(tài)規(guī)劃的基本思想2511214106104131112396581052C1C3D1AB1B3B2D2EC2求從A到E的最短路徑最短路問題最短路的性質(zhì)定理：

如果A到F的最短路程是ABCDEF，那么C到F的最短路程一定是CDEF

(Bellman最優(yōu)化原理）交通大學(xué)南坪解放碑北橋頭最短路的性質(zhì)：若交通學(xué)院到解放碑的最短路要經(jīng)過南坪和北橋頭則南坪到解放碑的最短路要經(jīng)過北橋頭。最短路的性質(zhì)定理：

如果A到F的最短路程是ABCDEF，那么C到F的最短路程一定是CDEF

(Bellman最優(yōu)化原理）階段n+1=4+1=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0階段42511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0階段42511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5階段32511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8階段32511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7階段3階段22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21階段22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14階段22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21階段1最短路2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1最短路2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1

（C1，D1）D1最短路2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1

（C1，D1）D1

（D1，E）E從A到E的最短路徑為19，路線為A→B2→C1→D1→E最短路多階段決策過程k=1k=n

kk=2fk(xk)表示第k階段初始狀態(tài)為xk時(shí)，k后部子過程的最優(yōu)準(zhǔn)則函數(shù)

§3動(dòng)態(tài)規(guī)劃的最優(yōu)性原理一、最優(yōu)性原理

“全過程的最優(yōu)策略具有這樣的性質(zhì)：不管該最優(yōu)策略上某狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)而言，余下的諸決策必定構(gòu)成最優(yōu)子策略.”即：最優(yōu)策略的子策略都是最優(yōu)的.二、最優(yōu)性定理定理1：設(shè)有一個(gè)準(zhǔn)則函數(shù)可分的無后效性的多階段決策過程,階段變量k=1,2,…,n,允許策略是最優(yōu)策略的充要條件是:對(duì)任意1<k<n,當(dāng)初始狀態(tài)為x1時(shí),有

式中,,即是由給定的初始狀態(tài)x1和子策略p1，k-1所確定的第k階段的狀態(tài).最優(yōu)性原理只是最優(yōu)性定理的一個(gè)推論，即最優(yōu)策略的必要條件。最優(yōu)性定理是動(dòng)態(tài)規(guī)劃問題的理論基礎(chǔ)！最優(yōu)性定理的推論若允許策略是最優(yōu)策略，則對(duì)任意的１＜ｋ＜ｎ，它的子策略對(duì)于以為起點(diǎn)的k到n子過程來說，必是最優(yōu)的策略。§4動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系線性規(guī)劃和非線性規(guī)劃一般是靜態(tài)規(guī)劃，與時(shí)間無關(guān)；動(dòng)態(tài)規(guī)劃時(shí)多階段的決策，一般與時(shí)間有關(guān)。但是，動(dòng)態(tài)規(guī)劃問題和動(dòng)態(tài)規(guī)劃問題在求解時(shí)可以相互轉(zhuǎn)化動(dòng)態(tài)規(guī)劃的解法有逆推解法和順推解法動(dòng)態(tài)規(guī)劃的關(guān)鍵：1、將問題恰當(dāng)?shù)貏澐譃槿舾呻A段；2、明確狀態(tài)變量和決策變量；3、正確地寫出狀態(tài)轉(zhuǎn)移方程和指標(biāo)函數(shù)的遞推關(guān)系。4、選擇逆推解法或順推解法。4.1逆推解法k=1k=n

kk=2fk(xk+1)表示第k階段（結(jié)束）狀態(tài)為xk+1時(shí)，起始階段到k階段（可以稱為k前部子過程）的最優(yōu)準(zhǔn)則函數(shù)。

逆推解法4.2、順序遞推k=1k=n

kk=2fk(xk)表示第k階段初始狀態(tài)為xk時(shí)，k后部子過程的最優(yōu)準(zhǔn)則函數(shù)

順序遞推優(yōu)點(diǎn)：1、動(dòng)態(tài)規(guī)劃方法可以處理廣泛的實(shí)際優(yōu)化問題；2、可以得到各階段的一系列最優(yōu)解.【例3】用動(dòng)態(tài)規(guī)劃法求解例1的最短路問題

AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643逆推解法此問題的基本方程為fk(sk)＝Min{dk(uk)+fk+1(sk+1)}

uk∈Dk(sk)

k＝6,5,4,3,2,1f7(s7)＝0按基本方程由后向前遞推有:當(dāng)k=6時(shí)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643當(dāng)k=6時(shí)當(dāng)k=5時(shí)當(dāng)k=5時(shí)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643當(dāng)k=4時(shí)當(dāng)k=4時(shí)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=3當(dāng)k=3時(shí)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=2當(dāng)k=2時(shí)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=1當(dāng)k=1時(shí)AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643

由此可以看出，A到G的最短路長為18，路徑為：A→B1→C2→D1→E2→F2→G順序解法AB1m=5,AB2m=3,AC1m=6AC2m=min{AB1m+3,AB2m+8}=min{5+3,3+8}=8AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643AC3m=min{AB1m+6,AB2m+7}=min{5+6,3+7}=10AC4m=9AD1m=min{AC1m+6,AC2m+3}=min{6+6,8+3}=11AD2m=min{AC1m+8,AC2m+5,AC3m+3,AC4m+8}=min{6+8,8+5,10+3,9+8}=13AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643AD3m=min{AC3m+3,AC4m+4}=min{10+3,9+4}=13AE1m=min{AD1m+2}=min{11+2}=13AE2m=min{AD1m+2,AD2m+1,AD3+3}=min{11+2,13+1,13+3}=13AE3m=min{AD2m+2,AD3m+3}=min{13+2,13+3}=15AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643AF1m=min{AE1m+3,AE2m+5,AE3+6}=min{13+3,13+5,15+6}=16AF2m=min{AE1m+5,AE2m+2,AE3+6}=min{13+5,13+2,15+6}=15AGm=min{AF1m+4,AF2m+3}=min{16+4,15+3}=18AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643動(dòng)態(tài)規(guī)劃的步驟用動(dòng)態(tài)規(guī)劃解決實(shí)際問題的基本過程是：（1）正確劃分階段，選擇階段變量k.（2）對(duì)每個(gè)階段，正確選擇狀態(tài)變量xk.選擇狀態(tài)變量時(shí)應(yīng)當(dāng)注意兩點(diǎn)：一是要能夠正確描述受控過程的演變特性，二是要滿足無后效性.（3）

對(duì)每個(gè)階段，正確選擇決策變量uk.（4）

列出相鄰階段的狀態(tài)轉(zhuǎn)移方程：xk+1=Tk(xk,uk).（5）列出按階段可分的準(zhǔn)則函數(shù)V1,n.（6）寫出遞推方程和邊界條件，建立基本方程；（7）

按照基本方程遞推求解。以上步驟是動(dòng)態(tài)規(guī)劃法處理問題的基本步驟，其中的前六步是建立動(dòng)態(tài)規(guī)劃模型的步驟。第九章動(dòng)態(tài)規(guī)劃的應(yīng)用一、資源分配問題【例4】（資源分配問題）某公司現(xiàn)有M臺(tái)設(shè)備準(zhǔn)備分配給該公司所屬的N家工廠.當(dāng)分配uk臺(tái)設(shè)備給工廠k時(shí)，工廠k利用這些設(shè)備為公司創(chuàng)造的利潤（假設(shè)非負(fù)）為gk(uk).應(yīng)當(dāng)如何分配設(shè)備資源，使得公司總利潤最大？資源分配問題數(shù)學(xué)模型

工廠k設(shè)備數(shù)

1

2

301234046770256803578共有N個(gè)工廠，可以把問題分解為N個(gè)階段： 當(dāng)階段k=N時(shí)，把手中設(shè)備分配給工廠N； 當(dāng)階段k=N-1時(shí)，把手中設(shè)備分配給工廠N-1； 依次類推； 在任意階段k時(shí)，把手中設(shè)備分配給工廠k； 當(dāng)階段k=1時(shí)，把手中設(shè)備分配給工廠1.

狀態(tài)變量xk-第k階段初分配者手中擁有的設(shè)備臺(tái)數(shù).

由題意可知

x0=M，xN+1=0解決策變量uk-第k階段分配給工廠k的設(shè)備臺(tái)數(shù)（），狀態(tài)轉(zhuǎn)移方程階段k的準(zhǔn)則函數(shù)為用fk(xk)

表示將手中資源xk分配給工廠k,k+1,…,N時(shí)的最大利潤，原問題即為計(jì)算f1(M)

具體計(jì)算（例）M=4，N=3，邊界條件f4(x4)=f4(0)=0

工廠k設(shè)備數(shù)

1

2

301234046770256803578k=3時(shí)：（增函數(shù)）

K=2時(shí)：

工廠k設(shè)備數(shù)

1

2

301234046770256803578K=2時(shí)

工廠k設(shè)備數(shù)

1

2

301234046770256803578

工廠k設(shè)備數(shù)

1

2

301234046770256803578K=2時(shí)最優(yōu)解

,最大利潤為

.

工廠k設(shè)備數(shù)

1

2

301234046770256803578K=1時(shí)推廣：非線性整數(shù)規(guī)劃問題M=4,N=3二、幾何規(guī)劃例5用動(dòng)態(tài)規(guī)劃法求解如下幾何規(guī)劃（一種特殊的非線性規(guī)劃）問題。令，，，則目標(biāo)函數(shù)為對(duì)非負(fù)實(shí)數(shù)u，令則原問題等價(jià)于求解

f3(6)

遞推方程邊界條件為

狀態(tài)轉(zhuǎn)移方程

類似P208例4順推法求解非線性規(guī)劃：

maxZ=4x1+9x2+2x32x1+x2+x3=10xi>=0I=1,2,3引例：某種原料總數(shù)為a分配給n種產(chǎn)品，分配數(shù)量Xi用于生產(chǎn)第i種產(chǎn)品，效益為gi(xi)動(dòng)態(tài)規(guī)劃應(yīng)用之二：資源分配問題類似P208例4順推法求解非線性規(guī)劃：

maxZ=4x1+9x2+2x32x1+x2+x3=10xi>=0I=1,2,3分析：理解為第一階段投資x1，第二階段投資x2

第三階段投資x3

求最大利潤maxZ=4x1+9x2+2x32

三階段投資總額共有10億元非線性規(guī)劃問題求解第一階段投資總額S1（狀態(tài)變量）第一二階段投資總額S2（狀態(tài)變量）第一二三階段投資總額S3（狀態(tài)變量）x1x2x3S3S2S1S1=

X1S2=

X1+X2

S3=

X1+X2+X3解:設(shè)狀態(tài)變量S1=X1,S2=S1+X2,S3=S2+X3.F1(S1)=4X1=4S1(

第一階段投資x1產(chǎn)生的效益4X1）第一二階段投資總量為S2產(chǎn)生的效益＝第一階段投資x1產(chǎn)生的效益＋第二階段投資X2產(chǎn)生的效益F2(S2)=9X2+F1(S1)=4S2+5X2X2<＝

S2當(dāng)X2=S2時(shí)maxF2(S2)=9S2解第一二三階段投資總量為S3產(chǎn)生的效益＝第一二階段投資S2產(chǎn)生的效益＋第三階段投資X2產(chǎn)生的效3S2=S3-X3F3(S3)=2X32+F2(S2)=2X32+9(S3-X3)=2X32-9X3+9S3=h3(S3,X3)dh3(S3,X3)/dX3=4X3-9=0=>X3=9/40<=X3<=10在X3=9/4,F3(S3)有最小值,F3(S3)最大值X3＝10maxF3(S3)=2*102=200即X3=10,則X1,X2為0maxZ=200.X3H3(S3,X3)109/4在X3=9/4,F3(S3)有最小值,F3(S3)最大值X3

＝10最優(yōu)解的圖示

單價(jià)

概率5000.36000.37000.4P234例6某工廠在最近五周內(nèi)需要采購一批原料，估計(jì)五周內(nèi)有價(jià)格波動(dòng)如下表，求那一周以什么價(jià)格購買最好2.2不確定性的采購解YK為狀態(tài)變量，表示第K周實(shí)際價(jià)格Xk為決策變量，取0或者1，表示第K周購買或者不買動(dòng)態(tài)規(guī)劃方法的主要步驟1.階段5階段決策2.狀態(tài)3.決策4.策略5.狀態(tài)轉(zhuǎn)移方程6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)7.逆推或順推求解分析采購期5周分成5個(gè)階段：每周價(jià)格看成為狀態(tài)變量；Yk為狀態(tài)變量，表示第K周實(shí)際價(jià)格；Xk為決策變量，取0或者1，表示第K周購買或者不買；YKE表示第K周實(shí)際價(jià)格為YK時(shí)，而在以后采取最優(yōu)策略時(shí)，采購價(jià)格的期望值（最可能的值）；FK(YK)表示第K周實(shí)際價(jià)格為YK時(shí),從第K周到第5周采用最優(yōu)策略時(shí)，采購價(jià)格的最小期望值。從最后一周開始計(jì)算，對(duì)于最后一周如果還沒有購買，按市場價(jià)格購買，1.階段2.狀態(tài)3.決策4.策略5.狀態(tài)轉(zhuǎn)移方程6.指標(biāo)函數(shù)和最優(yōu)值函數(shù)7逆推法求解倒推法K=5,f5(500)=500,f5(600)=600,f5(700)=700根據(jù)YKE和FK(YK)的定義，K=4,期望價(jià)格Y4E=0.3f5(500)+0.3f5(600)+0.4f5(700)=610（價(jià)格為500的概率為0.3,價(jià)格為600的概率為0.3,價(jià)格為700的概率為0.4,）

500Y4=500F4(Y4)＝Min{Y4,Y4E}=Min{Y4,610}=600Y4=600610Y4=700

第四周最優(yōu)策略為X4=

1采購如Y4=500或者Y4=6000等待如Y4=700同理K=3,期望價(jià)格Y3E=0.3F4(500)+0.3F4(600)+0.4F4(700)=0.3×500+0.3×600+0.4×610＝574f4(Y4)表示第4周實(shí)際價(jià)格為Y4時(shí),從第4周到第5周采用最優(yōu)策略時(shí)，價(jià)格的最小期望值實(shí)際價(jià)格Y4期望價(jià)格Y4E逆推解法k=4500Y4=500F4(Y4)＝Min{Y4,Y4E}=Min{Y4,610}=600Y4=600610Y4=700第四周最優(yōu)策略為X4=

1采購如Y4=500或者Y4=6000等待如Y4=700同理K=3,期望價(jià)格Y3E=0.3F4(500)+0.3F4(600)+0.4F4(700)=0.3×500+0.3×600+0.4×610＝574Y3=500574Y3=600或者700第三周最優(yōu)策略為X3=

1采購如Y3=5000等待如Y3=600或者Y3=700F3(Y3)＝Min{Y3,Y3E}=Min{Y3,574}=f4(Y4)表示第4周實(shí)際價(jià)格為Y4時(shí),從第4周到第5周采用最優(yōu)策略時(shí)，價(jià)格的最小期望值實(shí)際價(jià)格Y4期望價(jià)格Y4E實(shí)際價(jià)格Y3期望價(jià)格Y3E500Y4=500F4(Y4)＝Min{Y4,Y4E}=Min{Y4,610}=600Y4=600610Y4=700第四周最優(yōu)策略為X4=

1采購如Y4=500或者Y4=6000等待如Y4=700同理K=3,期望價(jià)格Y3E=0.3F4(500)+0.3F4(600)+0.4F4(700)=0.3×500+0.3×600+0.4×610＝574Y3=500574Y3=600或者700第三周最優(yōu)策略為X3=

1采購如Y3=5000等待如Y3=600或者Y3=700F3(Y3)＝Min{Y3,Y3E}=Min{Y3,574}=f4(Y4)表示第4周實(shí)際價(jià)格為Y4時(shí),從第4周到第5周采用最優(yōu)策略時(shí)，價(jià)格的最小期望值實(shí)際價(jià)格Y4期望價(jià)格Y4E實(shí)際價(jià)格Y3期望價(jià)格Y3EF2(Y2)＝Min{Y2,Y2E}=Min{Y2,552}=Y2=500552Y2=600或者700第二周最優(yōu)策略為X2=

1采購如Y3=5000等待如Y3=600或者Y3=700F1(Y1)＝Min{Y1,Y1E}=Min{Y1,536}=Y2=500536Y2=600或者700第一周最優(yōu)策略為X2=

1采購如Y3=5000等待如Y3=600或者Y3=700動(dòng)態(tài)規(guī)劃解：開始一二三周時(shí)間充分，非最低價(jià)不買，第四周有點(diǎn)著急中等價(jià)也買，第五周則沒有談判的余地。實(shí)際價(jià)格Y2期望價(jià)格Y2E實(shí)際價(jià)格Y1期望價(jià)格Y1E答案的確滿足：開始幾周時(shí)間充分，非最低價(jià)不買，到中間幾周有點(diǎn)著急中等價(jià)也買，最后時(shí)刻則沒有談判的余地。期望價(jià)格Y2E=0.3F3(500)+0.3F3(600)+0.4F3(700)=