1、引言,動(dòng)態(tài)規(guī)劃Dynamic Programming 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法。 1951年，美國(guó)數(shù)學(xué)家貝爾曼等人提出了 “最優(yōu)性原理”，即根據(jù)一類多階段決策問題的特點(diǎn)，把多階段決策問題變換為一系列相互聯(lián)系的單階段決策問題，然后分階段逐個(gè)加以解決。 從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法 動(dòng)態(tài)規(guī)劃。,引言,動(dòng)態(tài)規(guī)劃是解決某一類問題的一種方法，是分析問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因此，在學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除了對(duì)基本概念和方法正確地理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。,引言,本部分我們主要研究離散決策過程

2、， 介紹動(dòng)態(tài)規(guī)劃的基本概念、理論和方法， 通過一些典型的應(yīng)用問題來說明它的應(yīng)用。,多階段決策過程及實(shí)例,多階段決策過程（Multi-Stage decision process） 整個(gè)決策過程可按時(shí)間或空間順序分解成若干相互聯(lián)系的階段，每一階段都需作出決策，全部過程的決策是一個(gè)決策序列。 多階段決策過程最優(yōu)化的目標(biāo)： 達(dá)到整個(gè)活動(dòng)過程的總體效果最優(yōu)，而非各單個(gè)階段最優(yōu)的簡(jiǎn)單總和。,多階段決策過程及實(shí)例,多階段決策問題的典型例子,多階段決策問題的典型例子： 1 . 生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地根據(jù)庫(kù)

3、存和需求決定生產(chǎn)計(jì)劃。 2. 機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為 g=g(u1),多階段決策問題的典型例子,3. 航天飛機(jī)飛行控制問題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問題）。 4 . 線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。,多階段決策過程及實(shí)例,請(qǐng)看如下典例最短路線問題,多階段決策過程及實(shí)例,貪心算法 每一步都走最短

4、的線路： AB2C4D3E2F2-G，長(zhǎng)度為21 。不是最優(yōu)： 最短的線路: AB1C2D1E2F2-G，長(zhǎng)度為18,枚舉法,列出每條可能的路線，然后算出每條路的長(zhǎng)度，從中選擇最優(yōu)路線。 缺點(diǎn)是線路太多，隨點(diǎn)數(shù)增加很快。,標(biāo)號(hào)法,標(biāo)號(hào)法：只適用于這類最優(yōu)路線問題的特殊解法。 標(biāo)號(hào)法是借助網(wǎng)絡(luò)圖通過分段標(biāo)號(hào)來求出最優(yōu)路線的一種簡(jiǎn)便、直觀的方法。 通常標(biāo)號(hào)法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。,多階段決策過程及實(shí)例,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,該點(diǎn)到G點(diǎn)的最短距離,從G到A的解法稱為逆

5、序解法。,從A 到G的解法稱為順序解法。,最短路問題,該方法比枚舉法簡(jiǎn)單，計(jì)算的路遠(yuǎn)少于枚舉法 計(jì)算過程分了六個(gè)階段。 每個(gè)階段都是一個(gè)子問題，有出發(fā)點(diǎn)和選擇，并有不同的獲得。 后一階段的出發(fā)點(diǎn)由前階段的出發(fā)點(diǎn)和選擇確定 前一階段的獲得不僅與本階段的選擇有關(guān)還與后一階段的獲得有關(guān)。 這類問題稱之為多階段決策問題。,動(dòng)態(tài)規(guī)劃的基本概念和基本原理,1、階段（stage） 把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題，通常根據(jù)時(shí)間順序或空間特征來劃分，以便按階段的次序逐段解決整個(gè)過程的優(yōu)化問題。 描述階段的變量叫作階段變量，階段變量通常用k表示（k = 1，2，3，n）。,動(dòng)態(tài)規(guī)劃的基本概念

6、和基本原理,2、狀態(tài)（state） 用以描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱為狀態(tài)。它應(yīng)能描述過程的特征并具有“無后效性”，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。 狀態(tài)變量 sk（state variable） 狀態(tài)集合 Sk（set of admissible states）,動(dòng)態(tài)規(guī)劃的基本概念和基本原理,3、決策（decision） 決策：確定系統(tǒng)過程發(fā)展的方案。 決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。 決策變量 uk（sk）（

7、decision variable） 決策集合 Dk（sk）（set of admissible decision）,動(dòng)態(tài)規(guī)劃的基本概念和基本原理,4、策略（policy） 策略也叫決策序列。 一組有序的決策序列構(gòu)成一個(gè)策略， 從第k階段至第n階段的一個(gè)策略稱為后部子策略。,動(dòng)態(tài)規(guī)劃的基本概念和基本原理,5、狀態(tài)轉(zhuǎn)移方程（equation of state transition） 系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移， 即系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了k+1階段的狀態(tài)sk+1 ， 對(duì)于具有無后效性的多階段決策過程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的

8、狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過去的狀態(tài)及其決策無關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有： sk+1 = Tk（sk，uk） k =1，2，n,動(dòng)態(tài)規(guī)劃的基本概念和基本原理,6、指標(biāo)函數(shù)（objective function） 用來衡量策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。 對(duì)不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。通常表示為 vk（sk，uk）。,多階段決策過程及實(shí)例,從A點(diǎn)鋪設(shè)一條煤氣管道到E點(diǎn)，由于距離過長(zhǎng)，必須經(jīng)過三次加壓才能保證終端用戶的壓力。經(jīng)過前期調(diào)查確定每個(gè)加壓站的三個(gè)備選位置，由于地理?xiàng)l件限制某些地點(diǎn)之間

9、不適合建管道，可選地及其管線連接關(guān)系如下圖：,貪心算法,每一步都走最短的線路： A-B1-C3-D1E，長(zhǎng)度為14，不是最優(yōu)： 最優(yōu)：AB2C1-D1E，長(zhǎng)度為11,枚舉法,列出每條可能的路線共21條，然后算出每條路的長(zhǎng)度，從中選擇最優(yōu)路線。 缺點(diǎn)是線路太多，隨點(diǎn)數(shù)增加很快。,最短路問題,確定三個(gè)加壓站本質(zhì)上是選擇一條從A到E的路使總長(zhǎng)度最短。 從A到E的任一條路都必然是先從A到B1、B2、B3中某一個(gè)點(diǎn)，然后從該點(diǎn)到E點(diǎn)。 假設(shè)從A到E最短路是從A先到B1，然后從B1到E，那么到達(dá)B1后必然沿著從B1到E的最短路走。 如果分別求出B1、B2、B3到E點(diǎn)的最短路，就可以求出A到E的最短路，以f

10、(i)表示點(diǎn)i到點(diǎn)E的最短路的長(zhǎng)度，則有,最短路問題求解思路,最短路問題,為了求出B1、B2、B3到E點(diǎn)的最短路，就需要求出C1、C2、C3到E點(diǎn)的最短路,最短路問題,為了求出C1、C2、C3到E點(diǎn)的最短路，就需要求出D1、D2、D3到E點(diǎn)的最短路。,最短路問題,由于D1、D2、D3到E點(diǎn)只有一條路，所以,最短路問題,由f(D1)、f(D2)、f(D3)可計(jì)算出 f(C1)、f(C2)、f(C3),最短路問題,由f(C1)、f(C2)、f(C3)可計(jì)算出f(B1)、f(B2)、f(B3),最短路問題,由f(B1)、f(B2)、f(B3)可計(jì)算出f(A),標(biāo)號(hào)法,0,3,5,4,4,8,6,11

11、,7,8,11,從E到A的解法稱為逆序解法。,從A 到E的解法稱為順序解法。,最短路徑問題舉例,下圖表示從起點(diǎn)A到終點(diǎn)E之間各點(diǎn)的距離。求A到E的最 短路徑。,最短路問題,從上面的計(jì)算過程中可以看出，在求解的各個(gè)階段，我們利用了K階段與K+1階段之間的遞推關(guān)系：,動(dòng)態(tài)規(guī)劃的基本方程,動(dòng)態(tài)規(guī)劃的基本思想,基本思想總結(jié)：例最短路線問題 1、劃分階段。 2、求解從邊界條件開始，逆向逐段遞推。 3、每段的最優(yōu)是從全局考慮的，并非僅考慮本階段。,動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理,基本思想： 動(dòng)態(tài)規(guī)劃方法的關(guān)鍵:正確地寫出基本方程。 1、將問題的過程劃分為多個(gè)相互聯(lián)系的多階段決策過程，恰當(dāng)?shù)剡x取狀態(tài)變量和

12、決策變量及定義最優(yōu)指標(biāo)函數(shù)，把問題轉(zhuǎn)化成一組同類型的子問題。 2、從邊界條件開始，逆過程行進(jìn)方向，逐段遞推尋優(yōu)。 3、在每個(gè)子問題求解時(shí)，均利用它前面已求出的子問題的最優(yōu)化結(jié)果依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。,動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理,在多階段決策過程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前的一段和未來的各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。 因此，每階段決策的選取是從全局來考慮，與該段的最優(yōu)選擇一般是不同的。 動(dòng)態(tài)規(guī)劃方法的基本思想體現(xiàn)了 多階段性、無后效性、遞歸性、總體優(yōu)化性。,動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理,Bellman 最優(yōu)化原理： “

13、一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)， 即無論開始的狀態(tài)及決策如何，對(duì)先前的決策所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略” 簡(jiǎn)言之，一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。,動(dòng)態(tài)規(guī)劃求解方法,逆推解法（Backward Induction Method） 將尋優(yōu)過程看做連續(xù)遞推的過程，從最終階段開始，逆著實(shí)際決策過程的進(jìn)展方向逐段求解，在每一段求解中都要利用剛剛求解完那段的結(jié)果，直到初始階段求出結(jié)果回到始點(diǎn)為止。 順推解法（Forward Induction Method） 從初始階段向前遞推，直到最終階段為止。 一般地，當(dāng)過程的終點(diǎn)給定時(shí)，用順推法比較方便。,基本方程（遞推關(guān)系式）,假定過程的總效益

14、（指標(biāo)函數(shù)）與各階段效益的關(guān)系為：,基本方程（遞推關(guān)系式）,由于初始狀態(tài)s1已知，故可逐步確定出每階段的決策及效益。,基本方程（遞推關(guān)系式）,假定過程的總效益（指標(biāo)函數(shù)）與各階段效益的關(guān)系為：,例3 用逆推解法求解問題,例3 用逆推解法求解問題,例3 用逆推解法求解問題,用逆推解法，從后先前依次有,例3 用逆推解法求解問題,例3 用逆推解法求解問題,例3 用逆推解法求解問題,利用微分法易知：,已知s1=c，可得各階段的最優(yōu)決策和最優(yōu)值。 即,例3 用逆推解法求解問題,例3 用逆推解法求解問題,建立 動(dòng)態(tài)規(guī)劃 模型,建立動(dòng)態(tài)規(guī)劃模型的步驟： 1、正確、明確地劃分階段 k， k =1，2，3，n。

15、 依據(jù)決策過程的時(shí)間和空間的順序關(guān)系。 2、正確選擇并確定狀態(tài)變量 sk 及狀態(tài)集合 Sk 。 狀態(tài)變量的確定有時(shí)并非顯而易見，要確定它，通?？蓪?duì)問題作如下分析而幫助確定狀態(tài)變量 a. 什么關(guān)系將各個(gè)階段聯(lián)系在一起？ b. 為了決定今后的最優(yōu)（子）策略，需要事件現(xiàn)狀的哪些信息？,建立 動(dòng)態(tài)規(guī)劃 模型,3、確定決策變量 uk 及決策集合 Dk（sk）。 4、寫出狀態(tài)轉(zhuǎn)移方程 sk+1 = Tk（sk，uk）。 5、定義階段指標(biāo)值（函數(shù)） vk（sk，uk）。 6、定義第 k至 n 階段（后部子過程）的最優(yōu)指標(biāo)（目標(biāo)）函數(shù)fk（sk）。 7、作出動(dòng)態(tài)規(guī)劃結(jié)構(gòu)圖：,建立 動(dòng)態(tài)規(guī)劃 模型,8、建立動(dòng)態(tài)

16、規(guī)劃基本方程：（逆序遞推方程）,9、逆序遞推求解動(dòng)態(tài)規(guī)劃基本方程。 求出最優(yōu)決策序列 u*n，u*n-1，u*2，u*1 10、順序確定最優(yōu)策略。 p*1n = u*1，u*2，u*n ,例 分配投資問題,某公司有資金 10 萬(wàn)元，若投資于項(xiàng)目 k （k = 1，2，3）的投資額為 xk 時(shí)， 其收益分別為 g1（x1）= 4x1 ， g2（x2）= 9x2 ， g3（x3）= 2x32 ， 問應(yīng)該如何分配投資數(shù)額才能使總收益最大？ 該問題表面上看與時(shí)間無明顯關(guān)系，其靜態(tài)模型：,Max z = 4x1 + 9x2 + 2x32 x1 + x2 + x3 = 10 xi 0 （i = 1，2，3

17、）,建立動(dòng)態(tài)規(guī)劃模型與求解,建立 DP 模型與求解 階段 k = 1，2，3，分別表示項(xiàng)目1，2，3 狀態(tài)變量 sk ：第 k 段初擁有的資金總量（分配給第 k 至第 3 個(gè)項(xiàng)目的資金數(shù)量） 決策變量 xk ：第 k 段的投資量（分配給第 k 個(gè)項(xiàng)目的資金數(shù)量）， 決策集合 Dk（sk）= xk 0 xk sk ,建立動(dòng)態(tài)規(guī)劃模型與求解,4、狀態(tài)轉(zhuǎn)移方程 sk+1 = sk - xk,建立動(dòng)態(tài)規(guī)劃模型與求解,5、階段指標(biāo)值（函數(shù)）： vk（sk，xk）= gk（xk） 所以指標(biāo)函數(shù)為： 6、fk（sk）： 第 k 段初擁有的資金總量為 sk 時(shí)， 第 k 至第3段按最優(yōu)投資策略所獲得的第 k

18、至第3段的總收益。,g1（x1）= 4x1 g2（x2）= 9x2 g3（x3）= 2x32,建立動(dòng)態(tài)規(guī)劃模型與求解,7. 建立動(dòng)態(tài)規(guī)劃基本方程：（逆序遞推方程）,8.逆序遞推求解動(dòng)態(tài)規(guī)劃基本方程 k = 3,f3 *（s3）= 2s32 x3* = s3,建立動(dòng)態(tài)規(guī)劃模型與求解,可以證明極大值只可能在端點(diǎn)取得，即： 1、 s2 9/2 時(shí)， f2（0） f2（s2），此時(shí) x2* = s2 f2（s2）= 9s2 2、 s2 9/2 時(shí)， f2（0） f2（s2），此時(shí) x2* = 0 f2（0）= 2s22,建立動(dòng)態(tài)規(guī)劃模型與求解,k = 1 第一種情況,當(dāng)f2（s2 ）= 9s2 ， f

19、1（10）= Max 4x1 + f2(s2)= Max 4x1 + 9s2,0 x1 10,=Max 4x1 + 9(s1 x1 ) = Max 9s1 5x1 = 9s1 ， x1* = 0,但此時(shí) s2 = s1 x1 =10 - 0 9/2 與s2 9/2 矛盾，故舍去。,0 x1 10,建立動(dòng)態(tài)規(guī)劃模型與求解,k = 1 第二種情況,同樣可以證明極大值只可能在端點(diǎn)取得，比較兩個(gè)端點(diǎn)： x1 = 0 時(shí)， f1（10）= 200 ， x1 = 10 時(shí)， f1（10）= 40 所以 x1* = 0,建立動(dòng)態(tài)規(guī)劃模型與求解,10、順序確定最優(yōu)策略。,最優(yōu)投資方案為全部資金投資于第 3 個(gè)

20、項(xiàng)目， 可獲最大收益 200 萬(wàn)元。,資源分配問題,分配問題就是將一定數(shù)量的一種或者若干種資源，適當(dāng)?shù)胤峙浣o若干個(gè)使用者，而使目標(biāo)函數(shù)為最優(yōu)。 設(shè)有某種原料，總數(shù)量為a， 若分配數(shù)量 xi用于生產(chǎn)i種產(chǎn)品，收益為gi(xi)，問應(yīng)如何分配，才能使n種產(chǎn)品的總收入最大？,資源分配問題,數(shù)學(xué)模型如下：,可將它看作一個(gè)多階段決策問題， 用動(dòng)態(tài)規(guī)劃方法求解。,資源分配問題,設(shè)： 決策變量Xk:投資第k個(gè)項(xiàng)目的資金數(shù) 狀態(tài)變量sk：分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量。 狀態(tài)轉(zhuǎn)移方程： sk+1=sk-xk。,資源分配問題,最優(yōu)值函數(shù)fk(sk):投資第k至n項(xiàng)所得的最大收益數(shù)。 動(dòng)態(tài)規(guī)劃基本方

21、程：,利用這個(gè)遞推關(guān)系式進(jìn)行逐段計(jì)算，最后求得f1(a), 即為所求問題的最大總收入,資源分配問題,例6 某工業(yè)部門根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效的設(shè)備5臺(tái)分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國(guó)家提供的盈利如表所示。 問這5臺(tái)設(shè)備如何分配給工廠才能使國(guó)家得到的盈利最大。,盈利表,資源分配問題,解：將問題按工廠分3個(gè)階段。 Sk:分配給第k個(gè)工廠到第n個(gè)工廠的設(shè)備臺(tái)數(shù)。 Xk:分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。 Sk+1= Sk- xk:分配給第k+1個(gè)工廠到第n個(gè)工廠的設(shè)備臺(tái)數(shù)。,資源分配問題,Pk(xk):xk臺(tái)設(shè)備分到第k個(gè)工廠所得的盈利值。 fk(Sk):Sk臺(tái)設(shè)

22、備分配給第k個(gè)工廠到第n個(gè)工廠所得到的最大盈利值。 因而可以寫出遞推關(guān)系式為：,資源分配問題,逆序法： 當(dāng)k=3時(shí)， 設(shè)將S3臺(tái)設(shè)備（ S3 =0，1，2，3，4，5）全部分配給工廠丙時(shí)，則最大盈利值為：,因?yàn)榇藭r(shí)只有一個(gè)工廠，有多少設(shè)備就全部分配給丙工廠，故它的盈利值就是該段的最大盈利值， 其數(shù)值計(jì)算如表6-2所示：,資源分配問題,表6-2,資源分配問題,當(dāng)k=2時(shí)： 把x2臺(tái)設(shè)備分配給工廠乙和工廠丙時(shí)， 則對(duì)每個(gè)x2值，有一種最優(yōu)的分配方案， 使最大盈利值為：,資源分配問題,表6-3,資源分配問題,當(dāng)k=1時(shí)： 設(shè)把S1(S1=5)臺(tái)設(shè)備分配給工廠甲、工廠乙和工廠丙時(shí)，則最大盈利值為：,資

23、源分配問題,表6-4,資源分配問題,最優(yōu)分配方案有兩個(gè)： X1*=0，根據(jù)S2=S1-x1*=5-0=5,查表6-3知，x2*=2； S3=S2-x2*=5-2=3,查表6-2知x3*= S3=3， 即：甲工廠0臺(tái)；乙工廠2臺(tái)；丙工廠3臺(tái)。 X1*=2，根據(jù)S2=S1-x1*=5-2=3,查表6-3知，x2*=2； S3=S2-x2*=3-2=1,查表6-2知x3*= S3=1， 即：甲工廠2臺(tái)；乙工廠2臺(tái)；丙工廠1臺(tái)。,生產(chǎn)與存儲(chǔ)問題,例10：某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車間， 由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同， 各月份的生產(chǎn)量與當(dāng)

24、月的月底前，全部要存入倉(cāng)庫(kù)以備后用。 已知總裝車間的各個(gè)月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如表6-7所示。,生產(chǎn)與存儲(chǔ)問題,設(shè)倉(cāng)庫(kù)容量限制為H=9，開始庫(kù)存量為2，期終庫(kù)存量為0。 需要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，即滿足需要和庫(kù)容量的限制，又使生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)為最少。,生產(chǎn)與存儲(chǔ)問題,解：按月份劃分階段K。 狀態(tài)變量Sk：第k段開始時(shí)部件庫(kù)存量。 決策變量uk：第k段內(nèi)的部件生產(chǎn)量。 狀態(tài)轉(zhuǎn)移方程：,允許決策集合Dk(sk)：,生產(chǎn)與存儲(chǔ)問題,最優(yōu)值函數(shù)fk(sk)：在第k段開始的庫(kù)存量為sk時(shí)，從第k段至第6段所生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。 逆推關(guān)系式：,生產(chǎn)與

25、存儲(chǔ)問題,因要求期終庫(kù)存量為0，所以s7=0。 因每月的生產(chǎn)是供應(yīng)下月的需要， 所以u(píng)6=0，f6(s6) =0 由,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,生產(chǎn)與存儲(chǔ)問題,習(xí)題6-7,解：將問題按零售店分為4個(gè)階段。 狀態(tài)變量sk：分配給第k至第4個(gè)零售店的貨物箱數(shù)。 決策變量xk：分配給第k個(gè)零售店的貨物箱數(shù)。 狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk 階段指標(biāo)pk(xk):將xk箱貨物分配給第k個(gè)零售店的盈利。 最優(yōu)值函數(shù)fk(sk)：將sk箱貨物分配給第k至第4個(gè)零售店的最大盈利。,習(xí)題6

26、-7,習(xí)題6-7,習(xí)題6-7,習(xí)題6-7,習(xí)題6-7,習(xí)題6-8,解：將問題按糧田數(shù)分為4個(gè)階段。 狀態(tài)變量sk：分配給第k至第4塊糧田的肥料重量。 決策變量xk：分配給第k塊糧田的肥料重量。 狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk 階段指標(biāo)pk(xk):將xk單位肥料分配給第k個(gè)糧田增產(chǎn)糧食的數(shù)量。 最優(yōu)值函數(shù)fk(sk)：將sk單位肥料分配給第k至第4塊糧田的最大數(shù)量。,習(xí)題6-8,做題步驟與方法與習(xí)題6-7相同。,習(xí)題6-9,解：將問題按營(yíng)業(yè)區(qū)分為3個(gè)階段。 狀態(tài)變量sk：第k至第3個(gè)區(qū)增設(shè)的店數(shù)。 決策變量xk：第k個(gè)區(qū)增設(shè)的店數(shù)。 狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk 階段指標(biāo)pk(xk)

27、:第k個(gè)區(qū)增設(shè)xk店所取得的利潤(rùn)。 最優(yōu)值函數(shù)fk(sk)：從第k至第3個(gè)區(qū)增設(shè)sk店所取得的最大利潤(rùn)。,習(xí)題6-9,做題步驟與方法與習(xí)題6-7相同。,習(xí)題6-10,解：將問題按周期分為4個(gè)階段。 狀態(tài)變量sk：第四年初完好的機(jī)器數(shù)。 決策變量xk：第k年度用于第一種任務(wù)的機(jī)器數(shù)。 sk-xk：表示該年度用于第二種任務(wù)的機(jī)器數(shù)。 狀態(tài)轉(zhuǎn)移方程： sk+1=(1-1/3)xk+ (1-1/10)(sk-xk) = 2/3xk+ 9/10(sk-xk),習(xí)題6-10,最優(yōu)值函數(shù)fk(sk)：第k至第4個(gè)周期的總收益的最大值。,習(xí)題6-10,習(xí)題6-12,解:設(shè)3種產(chǎn)品其運(yùn)輸重量分別為x1,x2,x

28、3。由題意得模型為：,最大利潤(rùn)為260，運(yùn)輸方案有兩個(gè)： （0，2，0）或（1，0，1）,WinQSB軟件解題,生產(chǎn)準(zhǔn)備成本,生產(chǎn)和存儲(chǔ)成本,WinQSB軟件解題,階段初庫(kù)存量,各階段生產(chǎn)量,階段末庫(kù)存量,各階段生產(chǎn)庫(kù)存費(fèi)用,各階段總費(fèi)用,本章結(jié)束,生產(chǎn)與存儲(chǔ)問題,例8：某工廠要對(duì)一種產(chǎn)品制定今后四年的生產(chǎn)計(jì)劃，根據(jù)估計(jì)在今后四年內(nèi)，市場(chǎng)對(duì)該產(chǎn)品的需求量如表6-5所示： 表6-5,生產(chǎn)與存儲(chǔ)問題,假定該廠生產(chǎn)每批產(chǎn)品的固定成本為3（千元），若不生產(chǎn)即為0； 每單位產(chǎn)品成本為1（千元）； 每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量不超過6個(gè)單位； 每個(gè)時(shí)期未售出的產(chǎn)品，每個(gè)單位需付存貯費(fèi)0.5（千元）。 假定在第一個(gè)時(shí)期的初始庫(kù)存量為0，第四個(gè)時(shí)期末的庫(kù)存量也為0。 試問該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存， 才能