第六章動態規劃

(DynamicProgramming)教學要求：

了解動態規劃的基本思想

掌握一維離散動態規劃的建模和求解方法應用

會運用動態規劃方法解決一些基本應用問題。1可編輯ppt動態規劃是運籌學的一個分支，是求解多階段決策過程最優化問題的數學方法。動態規劃在經濟管理、工程技術、工農業生產及軍事部門中都有著廣泛的應用，并且獲得了顯著的效果。學習動態規劃，首先要了解多階段決策問題。§6.1動態規劃原理和模型2可編輯ppt例1：最短路徑問題：給定一個交通網絡圖如下，其中兩點之間的數字表示距離（或運費），試求從A點到G點的最短距離（總運輸費用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566433可編輯ppt用窮舉法的計算量:從A到G的6個階段，一共有48條路線，比較47次。4可編輯ppt例2：背包問題

有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使其背包所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛星內的物品裝載問題等。5可編輯ppt

生產決策問題：企業在生產過程中，由于需求是隨時間變化的，因此企業為了獲得全年的最佳生產效益，就要在整個生產過程中逐月或逐季度地根據庫存和需求決定生產計劃。機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產的數量，使在五年內產品的總產量達到最高。航天飛機飛行控制問題：由于航天飛機的運動的環境是不斷變化的，因此就要根據航天飛機飛行在不同環境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態），使之能最省燃料和完成飛行任務（如軟著陸）。6可編輯ppt根據過程的特性可以將過程按空間、時間等標志分為若干個互相聯系又互相區別的階段。在每一個階段都需要做出決策，從而使整個過程達到最好的效果。各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態，又影響以后的發展。當各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線，這樣的一個前后關聯具有鏈狀結構的多階段過程就稱為多階段決策問題。多階段決策過程：7可編輯ppt針對多階段決策過程的最優化問題，美國數學家Bellman等人在20世紀50年代初提出了著名的最優化原理，把多階段決策問題轉化為一系列單階段最優化問題，從而逐個求解，創立了解決這類過程優化問題的新方法：動態規劃。對最佳路徑（最佳決策過程）所經過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優決策），這就是Bellman提出的著名的最優化原理。簡言之，一個最優策略的子策略必然也是最優的。Bellman在1957年出版的《DynamicProgramming》是動態規劃領域的第一本著作。8可編輯ppt動態規劃的基本概念最短路問題：某運輸公司擬將一批貨物從A地運往E地，其間的交通系統網絡如下圖所示。圖上節點表示地點，邊表示兩地之間的道路，邊上的數字表示兩地間的運輸費用，求運輸費用最低的運輸路線。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態決策：某階段狀態給定之后，從該狀態演變到下一階段某一狀態的選擇。比如從第一階段到第二階段選擇什么路線。

策略：各階段決策確定后，組成的一個有序的決策序列。第2階段的狀態第1階段一、動態規劃的基本概念9可編輯ppt

1、階段（k）

將所給問題的過程，按時間或空間特征分解成若干相互聯系的階段，以便按次序求解。2、狀態sk

能表示決策順序的離散的量，階段可以確定地表示決策過程當前特征的量。狀態可以是數量，也可以是字符，數量狀態可以是連續的，也可以是離散的。

10可編輯ppt

3、決策uk從某一狀態向下一狀態過渡時所做的選擇。表示決策的變量為決策變量，用uk(sk)表示第k階段，狀態為sk時的決策變量。決策允許集合Dk(sk)：在狀態sk下，允許采取決策的全體。

4、策略Pk,n(sk)從第k階段開始到最后第n階段的決策序列，稱k子策略。PA,E(s1)即為全過程策略。11可編輯ppt5、狀態轉移方程是確定過程由階段的一個狀態到下一階段另一狀態下的演變過程，用公式sk+1=Tk(sk,uk)表示。該公式描述了由第k階段到第k+1階段的狀態轉移規律。12可編輯ppt

6、階段指標函數vk(sk,uk)

從狀態sk出發，選擇決策uk所產生的第k階段指標。過程指標函數Vk,n(sk,uk,uk+1,…,un)：從狀態sk出發，選擇決策uk,uk+1,…,un所產生的過程指標。動態規劃要求過程指標具有可分離性，即Vk,n(sk,uk,uk+1,…,un)=Vk(sk,uk)+Vk+1(sk+1,uk+1,…,un)稱指標具有可加性。Vk,n(sk,uk,uk+1,…,un)=Vk(sk,uk)×Vk+1(sk+1,uk+1,…,un)稱指標具有可乘性。13可編輯ppt

基本方程最優指標函數fk(sk)：從狀態sk出發，對所有的策略Pk,n，過程指標Vk,n的最優值，即

14可編輯ppt

對于可加性指標函數，上式可以寫為

上式中“opt”表示“max”或“min”。對于可乘性指標函數，上式可以寫為

以上式子稱為動態規劃最優指標的遞推方程，是動態規劃的基本方程。

終端條件：為了使以上的遞推方程有遞推的起點，必須要設定最優指標的終端條件，一般最后一個狀態n+1下最優指標，

fn+1(sn+1)=0。15可編輯ppt例3：某公司打算在三個不同的地區設置四個銷售點，據市場預測部門估計，在不同的地區設置不同數量的銷售點，每月可獲得的利潤如下表所示。試問在各個地區應該如何設置銷售點，才能使每月獲得的總利潤最大？其值是多少？請用動態規劃方法分析求解。地區銷售點01234A036810B045811C067912各地區不同銷售點數量利潤表（單位：百萬元）16可編輯ppt解：根據多階段決策問題的特征，將此問題轉化為三個階段的決策問題。1.階段k=1，2，3，分別代表A，B，C三地區。2.狀態變量Sk：表示第k個地區設置銷售點時還可設置的銷售點數量。3.決策變量Uk：表示第k個地區的銷售點數量。6.最優指標函數f（Sk）。4.狀態轉移方程：Sk+1=Sk-Uk。5.階段指標值：利潤如表V（Sk，Uk）。17可編輯ppt7.動態遞推方程：

f（Sk）=Max

V（Sk，Uk）+f（Sk+1）

k=2，1

f（S3）=Max

V（S3，U3）

18可編輯ppt階段k=3V（S3，U3）f（S3）U3*U3=0U3=1U3=2U3=3U3=4S3=0000S3=10661S3=206772S3=3067993S3=40679121248.逆序遞推求解動態方程：表119可編輯ppt階段k=2V（S2，U2）+f（S3）f（S2）U2*U2=0U2=1U2=2U2=3U2=4S2=00+000S2=10+64+060S2=20+74+65+0101S2=30+94+75+68+0111，2S2=40+124+95+78+612+0143表220可編輯ppt階段k=1V（S1，U1）+f（S2）f（S1）U1*U1=0U1=1U1=2U1=3U1=4S1=40+143+116+108+610+0162決策方案：地區A——設置2個銷售點；地區B——設置1個銷售點；地區C——設置1個銷售點。此時公司可以獲得最大總利潤16（百萬元）。表321可編輯ppt例2：從A地到E地要鋪設一條煤氣管道,其中需經過三級中間站，兩點之間的連線上的數字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？

AB2B1B3C1C3D1D2E52141126101043121113965810521C222可編輯ppt

解：整個計算過程分四個階段，從最后一個階段開始。

第四階段（D→E）：D有兩條路線到終點E。顯然有AB2B1B3C1C3D1D2E52141126101043121113965810521C223可編輯ppt首先考慮經過的兩條路線第三階段（C→D）：C到D有6條路線。(最短路線為)AB2B1B3C1C3D1D2E5214126101043121113965810521C224可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經過的兩條路線25可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經過的兩條路線26可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第二階段（B→C）：B到C有9條路線。首先考慮經過的3條路線27可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經過的3條路線28可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)考慮經過的3條路線29可編輯pptAB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為)第一階段（A→B）：A到B有3條路線。（最短距離為19）30可編輯ppt

動態規劃是用來解決多階段決策過程最優化的一種數量方法。其特點在于，它可以把一個n維決策問題變換為幾個一維最優化問題，從而一個一個地去解決。需指出：動態規劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態規劃的原理和方法，建立相應的模型，然后再用動態規劃方法去求解。二.動態規劃的原理最優化原理：作為整個過程的最優策略具有這樣的性質：無論過去的狀態和決策如何，相對于前面的決策所形成的狀態而言，余下的決策序列必然構成最優子策略。也就是說，一個最優策略的子策略也是最優的。31可編輯ppt

動態規劃方法的關鍵：在于正確地寫出基本的遞推關系式和恰當的邊界條件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯系的階段，恰當的選取狀態變量和決策變量及定義最優值函數，從而把一個大問題轉化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優，在每一個子問題的求解中，均利用了它前面的子問題的最優化結果，依次進行，最后一個子問題所得的最優解，就是整個問題的最優解。32可編輯ppt動態規劃適用于求解哪一類問題？每個階段的最優決策過程只與本階段的初始狀態有關，而與以前各階段的決策（即為了到達本階段的初始狀態而采用哪組決策路線無關）。換言之，本階段之前的狀態與決策，只是通過系統在本階段所處的初始狀態來影響本階段及以后各個階段的決策。或者說，系統過程的歷史只能通過系統現階段的狀態去影響系統的未來。具有這種性質的狀態稱為無后效性（即馬爾科夫性）狀態。動態規劃方法只適用于求解具有無后效性狀態的多階段決策問題。33可編輯ppt練習1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑334可編輯pptk=5，出發點E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1G,f6(F1)=4F2G,f6(F2)=335可編輯pptk=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E236可編輯ppt增加研制費（萬元）新產品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70例3：有一工廠研制甲、乙、丙三種新產品，估計這三種新研制成功的概率分別為：0.6、0.4、0.3。由于工廠急于推出新產品，決定再加撥2萬元研制費，以提高新產品研制成功的概率。據估計，把增加的研制費用于各種新產品研制時，研制成功的概率見下表。現把這批研制費分配給各新產品（不分配、分配給1萬元或分配給2萬元），使這三種新產品都研制成功的概率最大。應怎樣分配。37可編輯ppt解：1.劃分階段根據問題的性質，按照時間、空間、變量劃分為若干階段，這是用多階段決策過程描述一個實際問題的第一步。一個階段表示需要做出一次決策的子問題，建立動態規劃模型要求每個階段問題具有同一模式。描述階段的變量稱為階段變量，常用自然數k表示。

可劃分為3個階段求解，對甲產品增加研制費記為第1階段，對乙產品增加研制費記為第2階段，對丙產品增加研制費記為第3階段，k=1，2，3。38可編輯ppt2.確定狀態變量及相應的取值范圍

多階段決策過程的進展，可用各階段的狀態演變來描述。狀態必須包含表示系統情況和確定決策所需要的全部信息，使其能反映過程的演變特征。同時還要狀態滿足無后效性，即若已知過程現在處于某一階段的某一狀態，則該階段以后過程的演變，不再受以前各階段狀態的影響。確定狀態變量之后，根據具體問題的性質，找出狀態變量在各階段的取值范圍。

把有可能提供的研制費用作狀態變量，記為sk，取值為0，1，2（萬元）39可編輯ppt3.確定決策變量決策變量一般由系統最優化的目的所決定。把給第K種新產品的研制費用的數量作為決策變量uk,顯然，uk不能超過當時擁有的金額sk

即：uk≤sk40可編輯ppt4.建立狀態轉移方程根據狀態變量和決策變量的含義，寫出狀態轉移方程。根據以上對狀態變量和決策變量的規定，有：41可編輯ppt5.確定邊界條件過程開始和結束的狀態。由于開始時可用的金額為2萬元，而最后將全部用完，有S1=2,S4=042可編輯ppt6.確定指標函數，建立動態規劃的基本方程選取指標函數，根據指標函數建立最優指標函數遞推關系,即基本方程。

定義各階段研制成功概率pk(sk,uk)的乘積為指標函數，并求指標函數最大化。基本方程為43可編輯ppt第三階段

s3=0

s3=1

s3=2第二階段

s2=0

s2=1

s2=2第一階段只有S1=2s2=s1-u1*=2-0=2s3=s2-u2*=2-1=1最優解0-1-1從最后一個階段開始，逐階段向前，直至第一階段，即可求出全過程最優策略和指標函數的最優值。§6.2一維動態規劃求解方法

1、逆推法44可編輯ppt2、順推法

s3=s4+1=1s2=s3+1=2最優解0-1-1由第一階段開始，逐階段向后，直至最后一個階段，同樣可求出最優策略和指標函數的最優值。Sk+1表示第k階段的狀態變量。第一階段

s2=0

s2=1

s2=2第二階段

s3=0s3=1

s3=2第三階段45可編輯ppt有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使背包其所起作用（使用價值）最大？物品12…j…n重量（公斤/件）a1

a2

…

aj…

an每件使用價值c1

c2

…cj…

cn一、背包問題§6.3動態規劃在經濟和管理中的應用46可編輯ppt設xj為第j種物品的裝件數（非負整數）則問題的數學模型如下：用動態規劃方法求解，令fk(y)為總重量不超過y公斤，包中只裝有前k種物品時的最大使用價值。其中y≥0，k＝1,2,…,n。所以問題就是求fn(a)47可編輯ppt其遞推關系式為：當k=1時，有：48可編輯ppt例3：求下面背包問題的最優解物品(xi)

x1

x2

x3重量（ai）325使用價值8512解：a＝5，問題是求f3(5)49可編輯ppt物品(xi)

x1

x2

x3重量（ai）325使用價值851250可編輯ppt物品(xi)

x1

x2

x3重量（ai）325使用價值851251可編輯ppt物品(xi)

x1

x2

x3重量（ai）325使用價值851252可編輯ppt53可編輯ppt所以，最優解為X＝（1.1.0），最優值為Z=13。總結：解動態規劃的一般方法:從終點逐段向始點方向尋找最小(大)的方法。54可編輯ppt現有數量為a（萬元）的資金，計劃分配給n個工廠，用于擴大再生產。假設：xi為分配給第i個工廠的資金數量（萬元）；gi(xi)為第i個工廠得到資金后提供的利潤值（萬元）。問題：如何確定各工廠的資金數，使得總的利潤為最大。據此，有下式：二.投資分配問題55可編輯ppt

令：fk(x)表示以數量為x的資金分配給前k個工廠，所得到的最大利潤值。用動態規劃求解，就是求

fn(a)的問題。

當k=1時，f1(x)=g1(x)（因為只給一個工廠）

當1＜k≤n時，其遞推關系如下：設：y為分給第k個工廠的資金（其中0≤y≤x），此時還剩x－y（萬元）的資金需要分配給前k－1個工廠，如果采取最優策略，則得到的最大利潤為fk－1(x－y)，因此總的利潤為：

gk(y)＋fk－1(x－y)56可編輯ppt如果a是以萬元為資金分配單位，則式中的y只取非負整數0，1，2，…，x。上式可變為：所以，根據動態規劃的最優化原理，有下式：57可編輯ppt例4：設國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數如下表所示。投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據題意，是要求f4(60)。58可編輯ppt按順序解法計算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優策略0102030405060第二階段：求f2(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。59可編輯ppt最優策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)的值。60可編輯ppt最優策略為（30，20），此時最大利潤為105萬元。61可編輯ppt最優策略為（20，20），此時最大利潤為90萬元。最優策略為（20，10），此時最大利潤為70萬元。62可編輯ppt最優策略為（10，0）或（0，10），此時最大利潤為20萬元。

f2(0)＝0。最優策略為（0，0），最大利潤為0萬元。得到下表最優策略為（20，0），此時最大利潤為50萬元。63可編輯ppt

投資利潤0102030405060f2(x)020507090105120最優策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。64可編輯ppt最優策略為（20，10，30），最大利潤為155萬元。同理可求得其它f3(x)的值。得到下表65可編輯ppt

投資利潤0102030405060f3(x)0256085110135155最優策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四階段：求f4(60)。即問題的最優策略。66可編輯ppt最優策略為（20，0，30，10），最大利潤為160萬元。67可編輯ppt排序問題指n種零件經過不同設備加工是的順序問題。其目的是使加工周期為最短。1.n×1排序問題

即n種零件經過1種設備進行加工，如何安排？14682023交貨日期（d）45173加工時間（t）零件代號例：三、排序問題68可編輯ppt（1）平均通過設備的時間最小按零件加工時間非負次序排列順序，其時間最小。（即將加工時間由小到大排列即可）零件加工順序工序時間13457實際通過時間1481320交貨時間82314620平均通過時間延遲時間=13–6=769可編輯ppt（2）按時交貨排列順序零件加工順序工序時間13457實際通過時間56101720交貨時間82314620平均通過時間延遲時間=070可編輯ppt（3）既滿足交貨時間，又使平均通過時間最小零件加工順序工序時間13457實際通過時間1691320交貨時間82314620延遲時間=0平均通過時間71可編輯ppt

2.n×2排序問題

即n種零件經過2種設備進行加工，如何安排？例：49523B53786A零件設備ABT72可編輯ppt經變換為49523B53786A零件設備加工順序圖如下：ABT3756895432+2+2-5

加工周期T=3+7+5+6+8+2=3173可編輯ppt

3.n×3排序問題

即n種零件經過3種設備進行加工，如何安排？例：3468564683579310CBAABCT74可編輯pptABCT變換4+36+45+86+56+48+65+37+53+910+3B+CA+B75可編輯ppt排序4+36+45+86+56+48+65+37+53+910+3B+CA+B復原3468564683579310CBA76可編輯ppt計算T=6+10+8+7+6+4+3=44計算依據：77可編輯ppt練習：11851079827746CBAT=4578可編輯ppt練習：求投資分配問題得最優策略，其中a＝50萬元，其余資料如表所示。投資利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)0256065687079可編輯ppt例：某公司打算在3個不同的地區設置4個銷售點，根據市場部門估計，在不同地區設置不同數量的銷售點每月可得到的利潤如表所示。試問在各地區如何設置銷售點可使每月總利潤最大。地區銷售點01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=4780可編輯ppt練習1：某廠生產三種產品，各種產品重量與利潤的關系如表所示。現將此三種產品運往市場出售，運輸能力總重量不超過6噸，問如何安排運輸，使總利潤最大？種類123重量（噸/公斤）234單件利潤（元）80130180最優方案：X1

=（0.2.0）X2=（1.0.1）Z=26081可編輯ppt練習2：求下列問題的最優解

X=(2.1.0)

最優值為

Z=1382可編輯ppt背包問題

一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi千克，其價值是攜帶數量的函數。問旅行者應如何選擇攜帶物品的件數，使總價值最大？

劃分階段

將可裝入物品按排序，每段裝一種物品，共劃分為n個階段，k=1,2,……,n.

狀態變量

表示在第k階段開始時，背包中允許裝入前k種物品的總重量，記為sk

決策變量

裝入第k種物品的件數xk

建立狀態轉移方程

sk+1=sk-wkxk

允許決策集合

確定指標函數

確定邊界條件

背包所能承受的重量為w千克83可編輯ppt生產計劃問題

已知企業產品的生產費用、存儲費用和市場的需求量，在其生產能力和存儲能力許可的前提下，怎樣制定各個時期的生產計劃，既能完成交貨任務，又使總支出最小。某中轉倉庫要按月在月初供應一定數量的某種部件給總裝車間，由于生產條件的變化，生產車間在各月份中生產每單位這種部件所需耗費的工時不同，各月份的生產量于當月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及在加工車間生產該部件每單位數量所需工時，倉庫容量和開始庫存量，要求最終庫存量為0，要制定一個半年的逐月生產計劃，既滿足需要和倉庫容量的限制，又使生產這種部件的總耗費工時數最少。

84可編輯ppt生產計劃問題劃分階段

按月份劃分階段，每個月為一個階段，k=1,2,……,n.

狀態變量

第k階段開始時（即本階段需求送出之前，上階段產品送入之后）部件庫存量，記為sk

決策變量

第k階段內的部件生產量，記為uk

建立狀態轉移方程

sk+1=sk+uk-dk

最優指標函數

fk(sk)表示在第k階段開始的庫存量為sk時，從第k階段到最后一階段生產部件的最小累計工時數。

基本方程

確定邊界條件

so=開始庫存量，sn=085可編輯ppt貨物存儲問題考慮下面三個月的庫存問題，在每月初，公司必須決定在本月內，應生產多少產品。在一個月內生產x單位的產品，所需成本為c(x)，其中c(0)=0，當x>0時，c(x)=3+2x。每月最多生產4個單位，每月的需求是隨機的，或為1或為2單位。如果生產的數量大于需求，就出現庫存。每個月末檢查庫存，1個單位的庫存費用是1元。因為庫存能力有限，每月末的庫存量不能超過3單位。但同時要求必須及時滿足需求。在第3個月末要把現有的庫存以每單位2元的價格售出。在第1月的月初，公司有1單位的庫存。如何制定生產策略使三個月內的期望費用最小。

劃分階段

將三個月分為三個階段，每個月為一個階段

狀態變量

sk表示第k個月初的庫存數

決