1、第七章第七章 動態(tài)規(guī)劃動態(tài)規(guī)劃第一節(jié)第一節(jié) 多階段決策過程優(yōu)化多階段決策過程優(yōu)化第二節(jié)第二節(jié) 基本概念和原理基本概念和原理第三節(jié)第三節(jié) 模型與求解模型與求解第四第四節(jié)節(jié) 在管理中應(yīng)用在管理中應(yīng)用1/151第七章第七章 動態(tài)規(guī)劃動態(tài)規(guī)劃n是是優(yōu)化優(yōu)化多階段決策過程的多階段決策過程的一種方法一種方法。1957年年，美國數(shù)學(xué)家貝爾曼美國數(shù)學(xué)家貝爾曼(R. Bellman) 發(fā)表發(fā)表了了該領(lǐng)域第一本專著該領(lǐng)域第一本專著動態(tài)規(guī)劃動態(tài)規(guī)劃(Dynamic Programming)。n用于用于解決最優(yōu)解決最優(yōu)路徑、資源分配、生產(chǎn)與路徑、資源分配、生產(chǎn)與庫庫存、投資、裝載、排序存、投資、裝載、排序等等以以及過

2、程最優(yōu)控及過程最優(yōu)控制等制等問題問題。思路獨特，。思路獨特，對于對于某些問題，某些問題，比比線性或線性或非線性規(guī)劃非線性規(guī)劃方法有效。方法有效。2/1513/151Born: 26 August 1920 in Brooklyn, New York CityDied: 19 March 1984 in Los Angeles Richard Ernest Bellman completed his doctoral studies in Princeton and remained there as Assistant Professor of Mathematics after the aw

3、ard of his doctorate but in 1948 he left to take up the position of Associate Professor of Mathematics at Stanford University. During the following summer he worked at RAND.n動態(tài)規(guī)劃動態(tài)規(guī)劃模型的分類模型的分類：n離散確定型離散確定型；n離散隨機型離散隨機型；n連續(xù)確定型連續(xù)確定型；n連續(xù)連續(xù)隨機型。隨機型。n本章主要本章主要介紹介紹離散確定型，思想離散確定型，思想、原理和、原理和方法方法，為解決為解決其他類型問題其他類型

4、問題打基礎(chǔ)打基礎(chǔ)。4/151第一節(jié)第一節(jié) 多階段決策過程最優(yōu)化多階段決策過程最優(yōu)化 有些有些過程，可按過程，可按先后先后分解分解成成若若干干相互相互聯(lián)聯(lián)系系的的“時段時段”，每一時段，每一時段都要都要做出做出的的決策，決策，構(gòu)構(gòu)成成一一個個決策決策序列序列，這就是這就是多多階段決策階段決策問題。問題。 多階段決策多階段決策要要達到整個過程總體效果達到整個過程總體效果最最優(yōu)。優(yōu)。某階某階段決策影響下段決策影響下階階段決策段決策及及總體效果總體效果。 每每一階一階段決策段決策，不僅不僅應(yīng)謀取應(yīng)謀取本本階段最優(yōu)階段最優(yōu)，還應(yīng)，還應(yīng)考慮考慮對對最終最終目目標標的影響，從而做出對的影響，從而做出對全全局

5、局來講是最優(yōu)的決策來講是最優(yōu)的決策。5/151 動態(tài)規(guī)劃動態(tài)規(guī)劃就是就是隨著時間的隨著時間的推移逐段做出推移逐段做出決策。決策。 如果研究對象可分離為若干部分，分別如果研究對象可分離為若干部分，分別考慮，就考慮，就可可視這若干部分為若干時段，用視這若干部分為若干時段，用動態(tài)動態(tài)規(guī)劃方法規(guī)劃方法處理處理之之。 現(xiàn)舉例現(xiàn)舉例如次如次。6/151例例1 生產(chǎn)與存貯問題生產(chǎn)與存貯問題 某廠某廠每月需供應(yīng)市場一每月需供應(yīng)市場一定量產(chǎn)品，余定量產(chǎn)品，余者者存存入入倉庫。倉庫。一般一般說來，各說來，各月月適當(dāng)適當(dāng)增加增加產(chǎn)量可降低產(chǎn)量可降低生產(chǎn)成本，生產(chǎn)成本，但存但存入入倉庫倉庫會增加庫存費用會增加庫存費用

6、。如何如何安排各安排各月產(chǎn)月產(chǎn)量量，才能既才能既滿足滿足市場市場需求，需求，又減少又減少全全年生產(chǎn)年生產(chǎn)與與存存儲儲費用費用總總和和呢？呢？ 可逐月可逐月考慮，但要顧及考慮，但要顧及全年全年生產(chǎn)與存生產(chǎn)與存儲儲費費用用總總和。和。7/151例例2 投資決策問題投資決策問題 某公司有某公司有資金資金Q萬元萬元，今后，今后5年年要投入要投入A、B、C和和D四四個項目個項目。各。各項項目目投資回收期投資回收期和收和收益率益率不同不同，問問：如何如何安排各安排各年投資額，年投資額，才能才能使使第第5年末年末的的資金總額資金總額最大。最大。 該問題可按該問題可按5階段階段決策決策問題問題處理處理。8/1

7、51例例3 設(shè)備更新問題設(shè)備更新問題 設(shè)備越設(shè)備越到后來，到后來，維修費越多維修費越多。但買但買新新設(shè)備設(shè)備一次性一次性支出支出較較多多。企業(yè)要。企業(yè)要制訂制訂一一臺設(shè)備未來臺設(shè)備未來8年的更新年的更新計劃計劃。經(jīng)。經(jīng)預(yù)測預(yù)測，第第j年的年的買買價為價為Kj，設(shè)設(shè)Gj為為用用過過j年后的殘值年后的殘值，Cj為連續(xù)用為連續(xù)用j-1年年后后第第j年的維修費年的維修費(j=1，2，8)，問問：哪哪一一年年更新總更新總費用費用最小最小？ 可視為可視為8階段決策問題，每年年初要做出階段決策問題，每年年初要做出決決定定，是是繼續(xù)用，繼續(xù)用，還是購買還是購買新新的的。9/151第二節(jié)第二節(jié) 動態(tài)規(guī)劃基本概念

8、和原理動態(tài)規(guī)劃基本概念和原理一一、基本、基本概念概念 用用動態(tài)規(guī)劃模型動態(tài)規(guī)劃模型表達和解決表達和解決實際問題實際問題，要要用用到以下概念：到以下概念：(1)階段；階段；(2)狀態(tài)；狀態(tài)；(3)決策和決策和策略策略。 下面下面以實例以實例說明說明之之。10/15111/151例例4 最短路線問題最短路線問題 要要從從A向向F鋪鋪輸油管道，輸油管道，問問管線如何走，管線如何走，總總長度才長度才最短最短？線線上的數(shù)字表示上的數(shù)字表示距離距離。(1)階段階段 將將過程或整體過程或整體，按時間或按時間或空間分解空間分解成若干成若干互相聯(lián)系互相聯(lián)系的的時時段段或部分或部分，以便，以便逐一逐一求解，用求解

9、，用k表示階段表示階段(k=1, 2, , 5)。從。從A到到F可分可分5階段階段，每一階段之初都有多個選擇。每一階段之初都有多個選擇。 請注意，并不是所有的問題都能分解。請注意，并不是所有的問題都能分解。12/15113/151(2)狀態(tài)狀態(tài) 用用sk表示表示各各階段階段開始狀態(tài)開始狀態(tài)，稱為狀態(tài)變量稱為狀態(tài)變量。 sk取值取值全體全體稱為稱為狀態(tài)集合，狀態(tài)集合，用用Sk表示表示。 當(dāng)當(dāng)某某階段階段sk給給定后，以后定后，以后過程的過程的發(fā)發(fā)展不展不受受該階段該階段以前各以前各階階段段狀態(tài)的影響狀態(tài)的影響。當(dāng)前狀態(tài)。當(dāng)前狀態(tài)是過是過去歷史的一個完整總結(jié)，去歷史的一個完整總結(jié)，過程的歷史過程的

10、歷史只能通過只能通過當(dāng)前當(dāng)前狀態(tài)影響未來狀態(tài)影響未來的發(fā)展的發(fā)展，該性質(zhì)該性質(zhì)稱為稱為無后效無后效性性。不具備后效性的變量不能充當(dāng)狀態(tài)變量。不具備后效性的變量不能充當(dāng)狀態(tài)變量。14/151在在例例4中中， S1=A， S2=B1，B2 S3=C1, C2, C3, C4 S4=D1, D2, D3 S5=E1, E2當(dāng)當(dāng)某某段初始狀態(tài)段初始狀態(tài)已已選定時選定時，從這個點以后的鋪，從這個點以后的鋪管路線只與該點有關(guān)，不受管路線只與該點有關(guān)，不受以前以前的鋪管路線影的鋪管路線影響，所以滿足狀態(tài)的無后效性。響，所以滿足狀態(tài)的無后效性。15/15116/151整個決策序列構(gòu)成策略整個決策序列構(gòu)成策略，

11、用，用p1, nu1(s1), u2(s2), , un(sn)表示表示。可選策略可選策略全體全體稱為稱為允許策略允許策略集合，記作集合，記作P1, n，使使整整體體效果最優(yōu)的效果最優(yōu)的策略是策略是最最優(yōu)策略優(yōu)策略。 (4)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 本階段狀態(tài)是本階段狀態(tài)是上上階段階段狀態(tài)狀態(tài)和決策和決策的的結(jié)果。結(jié)果。若已知若已知第第k段狀態(tài)段狀態(tài)sk和和uk(sk)，則，則第第k+1段狀態(tài)段狀態(tài)sk+1也就確定，可表示也就確定，可表示為為： sk+1=Tk(sk, uk) (7-1)，稱為，稱為狀態(tài)狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)移方程。 例例4中，狀態(tài)轉(zhuǎn)移方程為中，狀態(tài)轉(zhuǎn)移方程為：sk+1=uk(sk)1

12、7/151(5)指標函數(shù)指標函數(shù) 衡量策略衡量策略優(yōu)劣的優(yōu)劣的數(shù)數(shù)值值稱為稱為指標函數(shù)指標函數(shù)。階段階段指標指標函數(shù)指第函數(shù)指第k段從狀態(tài)段從狀態(tài)sk出發(fā)出發(fā)，決策決策為為uk時時的的效效果果，用用d(sk, uk)表示表示。 從從1到到n叫做原叫做原過程過程，從第，從第k(1kn)段段到到第第n段段的過程稱為原的過程稱為原過程后部過程后部子過程子過程。 V1, n(s1, p1, n)表示表示初始狀態(tài)為初始狀態(tài)為s1，用用策略策略p1, n時時，原，原過程指標過程指標函數(shù)值函數(shù)值，Vk, n(sk, pk, n)表示表示k階階段段狀態(tài)狀態(tài)為為sk，用用策略策略pk, n時時，后部后部子子過程

13、指標過程指標函數(shù)值函數(shù)值。18/15119/151二、二、動態(tài)規(guī)劃基本動態(tài)規(guī)劃基本思想思想與原理與原理 求最短路線，求最短路線，可可求從求從A至至F的的所有所有可能可能鋪鋪設(shè)設(shè)的的長度，然后長度，然后比較。當(dāng)段數(shù)比較。當(dāng)段數(shù)和和各段狀態(tài)各段狀態(tài)都都很很多多時，窮舉時，窮舉法法效率低效率低。 動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法，從過程最后從過程最后一段開始一段開始，逆，逆序遞推，序遞推，逐步求出各逐步求出各段段、各各點到終點點到終點F的最短的最短路線，路線，最后求得最后求得A到到F的的最短路線。最短路線。 第第1步，從步，從k=5開始開始，s5可取可取E1和和E2，到到F點點的的距離分別為距離分別為4，3

14、。即。即： f5(E1)=4， f5(E2)=320/151第第2步，步，k=4，s4可取可取D1，D2和和D3，從，從D1到到F點點有兩條路線，取最短者有兩條路線，取最短者： f4(D1)=min d(D1, E1)+f5(E1) = 3+4 =7 d(D1, E2)+f5(E2) 5+3 相應(yīng)決策相應(yīng)決策為為u*4(D1)=E1。 f4(D2)=min d(D2, E1)+f5(E1) = 6+4 =5 d(D2, E2)+f5(E2) 2+3u*4(D2)=E2。 f4(D3)=min d(D3, E1)+f5(E1) = 1+4 =5 d(D3, E2)+f5(E2) 3+3u*4(D

15、3)=E1。 21/151類似地類似地，k=3時時， f3(C1)=12，u*3(C1)=D1。 f3(C2)=10，u*3(C2)=D2。 f3(C3)=8， u*3(C3)=D2。 f3(C4)=9， u*3(C4)=D3。k=2時時，有有 f2(B1)=13，u*2(B1)=C2。 f2(B2)=15，u*2(B2)=C3。k=1時時，有有f1(A)=min d(A, B1)+f2(B1) = 4+13 =17 d(A, B2)+f2(B2) 5+15u*1(A)=B1。 22/151 再再按按計算計算順序順序反反求求最最優(yōu)決策優(yōu)決策序列，即序列，即u*1(A)=B1，u*2(B1)=C

16、2，u*3(C2)=D2，u*4(D2)=E2，u*5(E2)=F。最短路線是最短路線是AB1C2D2E2F。 求解各階段，都用了如下關(guān)系：求解各階段，都用了如下關(guān)系： fk(sk)=min dk(sk, uk)+fk+1(sk+1) (7.3a) uk k=5, 4, 3, 2, 1 f6(s6)=0 (7.3b)23/151 (7.3a)稱為稱為動態(tài)規(guī)劃基本方程動態(tài)規(guī)劃基本方程，(7.3b)稱為終稱為終端條件。端條件。 各各結(jié)點結(jié)點上上方括號內(nèi)數(shù)，方括號內(nèi)數(shù)，是是該該點點到到F最最短距短距離離。連結(jié)各點到。連結(jié)各點到F的線的線是是最最短路徑短路徑。 在在圖上直接圖上直接計算計算，叫標號。叫

17、標號。比比窮舉法易算窮舉法易算，計算，計算量少量少。段數(shù)。段數(shù)越多，越越多，越復(fù)雜，復(fù)雜，越明顯。越明顯。不不僅僅算算得了得了從從A到到F的最短路線的最短路線，還還得到得到了了中間中間任任一點到一點到F的最的最短路線。短路線。24/15125/151圖圖7-226/1518838561310810131717若若d(E1, F)由由4改為改為8，標號過程如下。但，標號過程如下。但f(E1)應(yīng)應(yīng)當(dāng)是當(dāng)是7。請思考之。請思考之。動態(tài)規(guī)劃方法基本動態(tài)規(guī)劃方法基本思想思想總結(jié)：總結(jié)： (1)為為過程過程劃分階段，劃分階段，恰當(dāng)選取狀態(tài)恰當(dāng)選取狀態(tài)和和決策決策變量變量，定義定義最優(yōu)指標最優(yōu)指標函數(shù)，把函

18、數(shù)，把問題問題化化為若干為若干同同類型子類型子問題，然后逐個求解。問題，然后逐個求解。 (2)從從終終(始始)端端條件條件開始，逆開始，逆(或順或順)過程行進過程行進方向，逐方向，逐段尋段尋優(yōu)。優(yōu)。求解求解各各子子問題時，都問題時，都要用要用前前面子問題面子問題已得已得結(jié)果，結(jié)果，最最后后一個子問題的最優(yōu)解一個子問題的最優(yōu)解，就是整個就是整個問題的最優(yōu)解。問題的最優(yōu)解。 27/15128/151 動態(tài)規(guī)劃方法動態(tài)規(guī)劃方法的基礎(chǔ)是的基礎(chǔ)是貝爾曼等貝爾曼等人提出的人提出的最優(yōu)化最優(yōu)化原理：原理：“過程最過程最優(yōu)優(yōu)策略的性質(zhì)策略的性質(zhì)是是：無論：無論初始狀態(tài)及初初始狀態(tài)及初始決策如何，對于先前決策所

19、形成的狀態(tài)而言始決策如何，對于先前決策所形成的狀態(tài)而言，以后，以后的所有決策應(yīng)構(gòu)成最優(yōu)策略的所有決策應(yīng)構(gòu)成最優(yōu)策略”。 從從例例4（圖圖7-2）可可知知，無論從哪無論從哪一段一段哪一哪一狀態(tài)出發(fā)狀態(tài)出發(fā)，到終點到終點F的最短路線，只的最短路線，只與與該該狀態(tài)狀態(tài)有關(guān)，而有關(guān)，而與與其其以前狀態(tài)以前狀態(tài)、路線無關(guān)，、路線無關(guān)，即即與與從從A點到達這點到達這一一點點的路線無關(guān)的路線無關(guān)。 29/151第三節(jié)第三節(jié) 動態(tài)規(guī)劃模型與求解動態(tài)規(guī)劃模型與求解一一、動態(tài)規(guī)劃模型的建立、動態(tài)規(guī)劃模型的建立 建立基本方程建立基本方程，關(guān)鍵關(guān)鍵是劃分是劃分階段，將階段，將問問題題分解成分解成具有具有遞遞推推關(guān)系的

20、若關(guān)系的若干干子子問題，問題，而而查明查明遞遞推推關(guān)系的關(guān)系的關(guān)鍵又關(guān)鍵又在于選擇在于選擇狀態(tài)變量狀態(tài)變量，明確明確各各階階段狀態(tài)轉(zhuǎn)移關(guān)系段狀態(tài)轉(zhuǎn)移關(guān)系sk+1=Tk(sk, uk) 。 資源分配問題是動態(tài)規(guī)劃典型應(yīng)用資源分配問題是動態(tài)規(guī)劃典型應(yīng)用，可，可用于用于介紹動態(tài)規(guī)劃建介紹動態(tài)規(guī)劃建模模條件及解法。條件及解法。30/151例例5 現(xiàn)有現(xiàn)有10萬萬元元，第，第i個項目個項目投投入入xi時，收益為時，收益為g1(x1)=4x1；g2(x2)=9x2； g3(x3)=2x23。如何分如何分配配，總收益總收益才才最最多多? Max z=4x1+9x2+2x23 s.t. x1+x2+x3=10

21、， x1, x2, x3 0 按動態(tài)規(guī)劃求解。按動態(tài)規(guī)劃求解。先先在在項項目目1投資，投資，然后然后在在項目項目2，每每次次只只考慮一個考慮一個項目項目。 下面選擇下面選擇狀態(tài)變量狀態(tài)變量，找出找出各各后部子過程后部子過程之之間遞間遞推關(guān)系。推關(guān)系。31/151 可可以以原原NLP問題變量問題變量xk為決策變量為決策變量uk，即即設(shè)設(shè) uk=xk (k=1，2，3) 狀態(tài)和決策變量關(guān)系狀態(tài)和決策變量關(guān)系密切密切，狀態(tài)變量，狀態(tài)變量一一般般為累計量或為累計量或隨隨著著遞推變化遞推變化。 可可以各以各階段可用資金為狀態(tài)變量階段可用資金為狀態(tài)變量sk，初始，初始狀態(tài)狀態(tài)s1=10。32/151 u1

22、為為項項目目1可用資金，第可用資金，第1階段階段(k=1)，有，有s1=10， u1=x1， 第第2階段階段(k=2)，s2為為余下可余下可投投入入其余其余兩兩個個項目的資金，即項目的資金，即 s2=s1-u1，u2=x2， 一般一般地地，第，第k階段，有階段，有sk=sk-1-uk-1，uk=xk， 于是，于是，階段階段k， k=1，2，3狀態(tài)變量狀態(tài)變量sk：第：第k階段可投階段可投入入第第k到第到第3個項目個項目的資金。的資金。決策決策變量變量xk：投入第：投入第k個個項目的資金。項目的資金。33/15134/151 一般一般地，建立動態(tài)規(guī)劃模型的要點為：地，建立動態(tài)規(guī)劃模型的要點為：

23、1. 分析分析題意，識別題意，識別問題問題各各階段，按時空順階段，按時空順序適當(dāng)劃分滿足遞序適當(dāng)劃分滿足遞推推關(guān)系關(guān)系的的若若干干階段階段或部分或部分。 2. 正確正確的的狀態(tài)變量狀態(tài)變量應(yīng)有應(yīng)有兩個特征兩個特征： (1)能能直直接或接或間接確定各階段取值；間接確定各階段取值； (2)能能反映反映過程演變且過程演變且無無無后效無后效性。即由性。即由第第k階段狀態(tài)階段狀態(tài)sk出發(fā)出發(fā)的的后部后部子過程，子過程，可可視為視為以以sk為為初始狀態(tài)的獨立過程初始狀態(tài)的獨立過程。35/151 這這一點一點并并非非每個每個問題問題都容易滿足。都容易滿足。 3. 寫出寫出狀態(tài)狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)移方程 sk+1=

24、Tk(sk, uk)或轉(zhuǎn)移或轉(zhuǎn)移規(guī)則規(guī)則。 4. 明確明確指標指標函數(shù)函數(shù)Vk,n，最最優(yōu)指標優(yōu)指標函數(shù)函數(shù)fk(sk)以及階段指標以及階段指標vk(sk, uk)的含義的含義，列出，列出最優(yōu)指標最優(yōu)指標函數(shù)的遞推關(guān)系函數(shù)的遞推關(guān)系及及終端終端條件條件(即基本方程即基本方程)。 此外，此外，需經(jīng)驗與需經(jīng)驗與熟練熟練地地運用最優(yōu)化原理。運用最優(yōu)化原理。36/15137/151k012453二、逆序與順序解法二、逆序與順序解法 逆序逆序（順序順序）解法尋優(yōu)方向與過程行進方解法尋優(yōu)方向與過程行進方向向相反（相反（相同相同）。 例例4的的順序解法計算順序解法計算步驟如下步驟如下：k=0， f0(s0)

25、=f0(A)=0，這是初始條件。，這是初始條件。k=1， f1(s1) f1(B1)=4， u1(B1)=A f1(B2)=5， u1(B2)=A38/151k=2， f2(s2) f2(C1)=d(B1, C1)+f1(B1)=2+4=6 u2(C1)=B1 f2(C2)=min d(B1, C2)+f1(B1) = min 2+4 =6 d(B2, C2)+f1(B2) 8+5 u2(C2)=B1， f2(C3)=min d(B1, C3)+f1(B1) = min 6+4 =10 d(B2, C3)+f1(B2) 7+5 u2(C3)=B1，39/151 f2(C4)=d(B2, C4)

26、+f1(B2)=7+5=12 u2(C4)=B2k=3， f3(s3) f3(D1)=11，u3(D1)=C1或或C2f3(D2)=12，u3(D2)=C2f3(D3)=14，u3(D3)=C3k=4， f4(s4) f4(E1)=14，u4(E1)=D1f4(E2)=14，u4(E2)=D2k=5， f5(s5) f5(F)=17，u5(F)=E240/15141/151414141112146710124517042/15114141112146710124517按按定義定義知知f5(F)=17為為所求最短路長，而路徑則所求最短路長，而路徑則為為AB1C2D2E2F，與逆序解法相同。，與逆

27、序解法相同。計算計算過程過程如如圖圖7-3。圖圖中節(jié)點中節(jié)點上方括號內(nèi)的上方括號內(nèi)的數(shù)數(shù)是是該該點點到到A點的最短距離點的最短距離，黑粗線，黑粗線是是該該點到點到A點的點的路徑。路徑。上述上述解法寫成解法寫成如如下下遞遞推推方程方程：fk(sk)=minvk(sk, uk)+fk-1(sk-1)， (7.5a) k=1, 2, 3, 4, 5f0(s0)=0 (7.5b)這里這里，sk=Tk(sk+1, uk)43/151 一般地說一般地說，當(dāng)給定初始狀態(tài)時可用逆序解，當(dāng)給定初始狀態(tài)時可用逆序解法法，當(dāng)給定當(dāng)給定終止狀態(tài)時終止狀態(tài)時可用順序解法可用順序解法。 若給定了若給定了一一個個初始狀態(tài)與

28、一個終止狀態(tài)初始狀態(tài)與一個終止狀態(tài)，兩種方法兩種方法均均可用可用，如例，如例4。 但若雖但若雖已給定初始狀態(tài)，終點狀態(tài)有多個已給定初始狀態(tài)，終點狀態(tài)有多個，需比較到達不同，需比較到達不同終點的各路徑終點的各路徑及最優(yōu)指標函及最優(yōu)指標函數(shù)值，以選取總效益最佳的終點狀態(tài)時數(shù)值，以選取總效益最佳的終點狀態(tài)時，用順，用順序解法較簡便。序解法較簡便。 總之，總之，應(yīng)應(yīng)針對針對問題問題的特點的特點，靈活選用。靈活選用。44/151 上述上述兩種兩種方法，建模方法，建模時要注意以下區(qū)別：時要注意以下區(qū)別： 1. 狀態(tài)狀態(tài)轉(zhuǎn)移方式不同轉(zhuǎn)移方式不同 如如圖圖7-4所示，逆序所示，逆序解法第解法第k段段的輸入的輸

29、入狀態(tài)狀態(tài)sk和決策和決策uk確定了確定了sk+1，狀態(tài)狀態(tài)轉(zhuǎn)移方程為：轉(zhuǎn)移方程為： sk+1=Tk(sk, uk) (7.6)式式(7.6)稱為稱為狀態(tài)狀態(tài)sk到到sk+1的的順序轉(zhuǎn)移方程。順序轉(zhuǎn)移方程。45/15146/151 順序解法第順序解法第k段段sk由由sk+1和和uk決定決定，見見圖圖7-5，狀態(tài)轉(zhuǎn)移方程，狀態(tài)轉(zhuǎn)移方程為：為： sk=Tk(sk+1, uk) (7.7)式式(7.7)稱逆序稱逆序狀態(tài)狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)移方程。 逆序逆序解法解法中階段指標中階段指標vk(sk, uk)在在順序解法中順序解法中應(yīng)表應(yīng)表為為vk(sk+1, uk)。 2. 指標指標函數(shù)的定義不同函數(shù)的定義不

30、同 逆序解法，最逆序解法，最優(yōu)指標優(yōu)指標函數(shù)函數(shù)fk(sk)表示第表示第k段段從從狀態(tài)狀態(tài)sk出發(fā)出發(fā)到終點后部到終點后部子子過程最優(yōu)效益值過程最優(yōu)效益值， f1(s1)是是整整體體最優(yōu)函數(shù)值最優(yōu)函數(shù)值。47/15148/15149/15150/15151/151三三、基本方程分段、基本方程分段求解幾種求解幾種常用算法常用算法 基本基本方程分段求解方程分段求解，須，須視視具體特點，靈活具體特點，靈活求解求解。大體大體有有以下方法以下方法。 1. 離散變量分段離散變量分段窮舉算法窮舉算法 狀態(tài)與狀態(tài)與決策變量決策變量若只取若只取離散值離散值，可用，可用分段分段窮舉法窮舉法，如，如例例4。求最。求

31、最優(yōu)優(yōu)指標函數(shù)值指標函數(shù)值時時，應(yīng)應(yīng)正確正確確定確定各各段段狀態(tài)變量狀態(tài)變量取值和取值和允許決策允許決策集合范圍集合范圍。52/151 2. 連續(xù)變量連續(xù)變量的解法的解法 狀態(tài)與決策變量狀態(tài)與決策變量若若連續(xù)，連續(xù)，可用可用解析法解析法、線線性性和和非線性規(guī)劃非線性規(guī)劃法或其他數(shù)值計算方法等。法或其他數(shù)值計算方法等。 例例5，狀態(tài)與，狀態(tài)與決策變量決策變量均連續(xù)，每均連續(xù)，每階段求優(yōu)階段求優(yōu)時不能時不能用窮舉法。用窮舉法。 (1)逆序逆序解法解法 例例5狀態(tài)變量狀態(tài)變量sk為第為第k段初可分配給第段初可分配給第k到到第第3個項目的資金；決策變量個項目的資金；決策變量xk為投為投入入第第k個個項

32、目的項目的資金；狀態(tài)轉(zhuǎn)移方程資金；狀態(tài)轉(zhuǎn)移方程為為sk+1=sk-xk，53/151 最最優(yōu)指標優(yōu)指標函數(shù)函數(shù)fk(sk)表示第表示第k階段，狀態(tài)為階段，狀態(tài)為sk時時，從，從第第k到到第第3個個項目項目的的最大最大收益收益， f1(s1)即即為為所所求總求總收益。遞推收益。遞推方程方程為：為： fk(sk)= max gk(xk)+fk+1(sk+1) k=3, 2, 1 0 xk sk f4(s4)=0k=3 f3(s3)= max 2x23= 2s23 0 x3 s3k=2 f2(s2)= max 9x2+f3(s3) 0 x2 s2 = max 9x2+2(s2-x2)2 0 x2 s

33、254/151令令h2=9x2+2(s2-x2)2，由，由dh2/dx2=9-4(s2-x2)=0，得，得x2=s2-9/4，而，而d2h2/dx22=40，所以，所以x2=s2-9/4是極是極小點。極大值只能在小點。極大值只能在x2=0或或x2=s2處取得。處取得。 f2(s2)|x2=s2 = 9s2 f2(s2)|x2=0 = 2s22當(dāng)當(dāng)f2(s2)|x2=s2 = f2(s2)|x2=0時，時，s2=9/2當(dāng)當(dāng)s29/2時時， f2(s2)|x2=s2 f2(s2)|x2=0，x*2=0當(dāng)當(dāng)s2 f2(s2)|x2=0，x*2=s255/151 k=1 f1(s1)= max 4x1

34、+f2(s2) 0 x1s1當(dāng)當(dāng)f2(s2)=9s2時，時， f1(10)= max 4x1+9s1-9x1 0 x110= max 9s1-5x1=9s1 ， x*1=0 0 x110但此時，但此時，s2=s1-x1=10-0=109/2，與，與s20，故，故x1=s1-1是是極小點。極大值只極小點。極大值只能在能在x1=0或或x1=s1=10處處取得。取得。 f1(s1)|x1=0 =2s21=200， f1(s1)|x1=10 = 40所以，所以， x*1=0，s2=s1-x*1=s1=10，因，因s29/2，所以，所以 x*2=0；s3=s2-x*2=s2=10，所以，所以， x*3=

35、s3=10全部全部資金投于第資金投于第3個項目個項目，收益，收益為為200萬元。萬元。57/151(2)順序解法順序解法 令可令可投入投入第第1到第到第k個個項目的金額項目的金額為為sk，則則狀態(tài)轉(zhuǎn)移方程為：狀態(tài)轉(zhuǎn)移方程為： s3=10，s2=s3-x3，s1=s2-x2， s0=s1-x1即即 sk=sk+1-xk+1， 令令投入投入第第1到到第第k個個項目項目的總的總額為額為sk時的時的最最大大總收益為總收益為fk(sk) 。基本基本方程為方程為： fk(sk)= max gk(xk)+fk-1(sk-1) k=1, 2, 3 0 xksk f0(s0)=0表示未投資時的最大收益。表示未投

36、資時的最大收益。58/151k=1 f1(s1)= max g1(x1)+f0(s0) 0 x1s1 = max 4x1= 4s1， x*1=s1 0 x1s1 k=2 f2(s2)= max 9x2+f1(s1) 0 x2s2 = max 9x2+4(s2-x2) 0 x2s2 = max 5x2+4s2=9s2， x*2=s2 0 x2s259/151k=3 f3(s3)= max 2x23+f2(s2) 0 x3s3 = max 2x23+9(s3-x3) 0 x3s3令令h(s3, x3)=2x23+9(s3-x3)dh(s3, x3)/dx3 =4x3-9=0，x3=9/4d2h(s

37、3, x3)/dx23 =40，x3=9/4為極小點，極大值為極小點，極大值應(yīng)當(dāng)在應(yīng)當(dāng)在x3=0或或x3=10處取得。處取得。f3(s3)|x3=0= 9s3，f3(s3)|x3=10=200， x*3=10， s2=s3 -x*3=10-10=0， s2=s3-x*3=s3-s3=0， s1=s2-x*1=s2-s2=0，60/151最最優(yōu)投資方案與逆序解法結(jié)果相同，只投資于優(yōu)投資方案與逆序解法結(jié)果相同，只投資于項項目目3，最大收益為，最大收益為200萬元萬元 對本對本例例而言而言，順序解法比逆序解法簡單。，順序解法比逆序解法簡單。61/15162/151狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程： sk+

38、1=sk-xksk與與xk是連續(xù)變量是連續(xù)變量。gk(xk)若若較復(fù)雜，較難求出較復(fù)雜，較難求出fk(sk)。常把連續(xù)變量離散化常把連續(xù)變量離散化，求數(shù)值解求數(shù)值解。具體。具體做法如下：做法如下：(1)令令sk=0，2，m=a， 大大小可小可依據(jù)依據(jù)要求的精度定。要求的精度定。(2)規(guī)定規(guī)定狀態(tài)變量狀態(tài)變量sk及決策變量及決策變量xk只只取取離散離散值值，遞遞推方程就推方程就變?yōu)樽優(yōu)椋?fk(sk)= max gk(p)+fk+1(sk-p) p=0, 1, , q fn+1(sn+1)=0其中，其中，q=sk, xk=p。63/151(3)按按逆序逆序解解法法，逐步遞，逐步遞推求推求fn(s

39、n)，fn-1(sn-1) ， f1(s1)，最后求最后求出出最優(yōu)最優(yōu)資金資金分配方案。分配方案。 現(xiàn)舉例說明。現(xiàn)舉例說明。 Max z=4x1+9x2+2x23 s.t. x1+x2+x3=10， x1, x2, x3 0解解 令令=2，則狀態(tài)空間，則狀態(tài)空間Sk=0, 2, 4, 6, 8, 10，決策集合為決策集合為0 xksk，64/151遞遞推推方程為方程為： fk(sk)= max gk(xk)+fk+1(sk-xk) 0 xksk f4(s4)=0k=3，f3(s3)= max 2x23，計算結(jié)果見表，計算結(jié)果見表7-1。 0 x3s3表表7-165/151s30246810f3

40、(s3)083272128200 x*30246810k=2，f2(s2)= max 9x2+f3(s2-x2) 0 x2s2表表7-266/151s20246x20 0 2 0 2 4 0 2 4 6g2+f30 8 18 32 26 3672 50 44 54f2(s2)0 18 3672x*20 2 4 0s30246810f3(s3)083272128200 x*30246810s2 810 x20 2 4 6 8 0 2 4 6 8 10g2+f3128 90 68 62 72 200 146 108 86 80 90f2(s2)128200 x*2 0 0s30246810f3(s

41、3)083272128200 x*30246810s2 810 x20 2 4 6 8 0 2 4 6 8 10g2+f3128 90 68 62 72 200 146 108 86 80 90f2(s2)128200 x*2 0 0k=1，f1(s1)= max 4x1+f2(s1-x1) 0 x110表表7-367/151s20246x20 0 2 0 2 4 0 2 4 6g2+f30 8 18 32 26 3672 50 44 54f2(s2)0 18 3672x*20 2 4 0s110 x10246810g1+f220013688605040f1(s1)200 x*10最最優(yōu)決策為

42、優(yōu)決策為：x*1=0， x*2=0， x*3=10，最最大大收收益益為為f1(s1)= 200，與例，與例5結(jié)論相同結(jié)論相同。 該該法法會會丟失丟失最優(yōu)解，最優(yōu)解，一般一般只是只是近似解近似解。68/15169/151設(shè)狀態(tài)變量為：設(shè)狀態(tài)變量為：sk=(Xk, Yk)，Xk：用于生產(chǎn)第：用于生產(chǎn)第k至至n種產(chǎn)品的第種產(chǎn)品的第1種資源量；種資源量；Yk：用于生產(chǎn)第用于生產(chǎn)第k至至n種產(chǎn)品的種產(chǎn)品的第第2種種資源量資源量；設(shè)決策變量設(shè)決策變量為為：uk=(xk, yk)，xk：用于生產(chǎn)第：用于生產(chǎn)第k種種產(chǎn)品的第產(chǎn)品的第1種資源量；種資源量；yk：用于生產(chǎn)第：用于生產(chǎn)第k種種產(chǎn)品的第產(chǎn)品的第2種資

43、源量；種資源量；狀態(tài)轉(zhuǎn)移方程為：狀態(tài)轉(zhuǎn)移方程為：Xk+1= Xk - xkYk+1= Yk - yk70/151允許決策集合為：允許決策集合為：Dk(Xk, Yk)=(xk, yk)|0 xkXk，0ykYk 最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(Xk, Yk)表示表示分配分配于于第第k種種產(chǎn)品至產(chǎn)品至第第n種種產(chǎn)品產(chǎn)品的兩種資源分別為的兩種資源分別為Xk和和Yk時的最大收時的最大收益。益。基本基本遞推方程為遞推方程為：fk(Xk, Yk)= max gk(xk, yk)+fk+1(Xk+1-xk, Yk-yk) 0 xkXk 0ykYk k=n, n-1, , 2, 1 fn+1(Xn+1, Yn+

44、1)=071/15172/15173/151第四節(jié)第四節(jié) 動態(tài)規(guī)劃動態(tài)規(guī)劃在管理在管理中中應(yīng)用應(yīng)用 本節(jié)本節(jié)介紹介紹一些例子。一些例子。一一、背包、背包問問題題 登山背包有登山背包有n種種物品物品要要裝，裝，但最多但最多裝裝a公公斤斤，第，第i種單種單件件重重ai公斤公斤，價值，價值ci(xi)(表明表明本物本物品對品對登山重要性登山重要性)是是件件數(shù)數(shù)xi的函數(shù)的函數(shù) (i=1, 2, , n)，問如何選問如何選裝裝各種物品件各種物品件數(shù)數(shù)，使，使總價值最大總價值最大?74/15175/151允許決策集合為：允許決策集合為：Dk(sk)=xk|0 xksk/ak, xk為整數(shù)為整數(shù) 最優(yōu)指標

45、函數(shù)最優(yōu)指標函數(shù)fk(sk)表示背包允許裝入物品總重表示背包允許裝入物品總重量不超過量不超過sk公斤，按最優(yōu)策略裝前公斤，按最優(yōu)策略裝前k種種物物品品時時的的最大價值。順序最大價值。順序遞遞推方程為：推方程為：fk(sk) = max ck(xk)+fk-1(sk-akxk) xk=0,1,sk/ak k=1,2,nf0(s0)=0，表示未裝入物品時最大價值。，表示未裝入物品時最大價值。76/151用用順序解順序解法逐步算出法逐步算出f1(s1)， f2(s2)， fn(sn)及相應(yīng)的決策及相應(yīng)的決策x1(s1)，x2(s2)， ， xn(sn)，最后最后得到得到的的fn(a)即為所求最大價值

46、。最優(yōu)策略即為所求最大價值。最優(yōu)策略反反向向推出推出。 當(dāng)當(dāng)xi僅僅表示裝入表示裝入(取取1)和不裝和不裝(取取0)第第i種物品種物品，則本模型，則本模型就是就是0-1背包問題。背包問題。77/151例例7 貨運量貨運量10t的卡車的卡車，可可裝裝3種貨物，每種貨物，每種單種單位位重量重量及價值如及價值如下下表。如何裝載總表。如何裝載總價值最大價值最大? 設(shè)第設(shè)第i種種貨物裝載的件數(shù)貨物裝載的件數(shù)為為xi(i=1, 2, 3)，則問題，則問題可表為：可表為： Max z =4x1+5x2+6x3 s.t. 3x1+4x2+5x3 10 xi 為為非負非負整數(shù)整數(shù) (i=1, 2, 3)78/1

47、51貨物編號貨物編號123單件重單件重t345單位價值單位價值456是是離散決策變量，離散決策變量，可列表求解可列表求解當(dāng)當(dāng)k=1時，時，f1(s1) = max 4x1+f0(s0)或或 03x1s1取整數(shù)取整數(shù) f1(s1) = max 4x1+f0(s0)=4s1/3 0 x1s1/3取整數(shù)取整數(shù)79/151s1012345678910f1(s1)0004448881212x*100011122233當(dāng)當(dāng)k=2時，時，f2(s2) = max 5x2+ f1(s2-4x2) 0 x2s2/4整數(shù)整數(shù)80/151s2012345x200000 10 1c2+f100044545f2(s2)

48、0004 5 5x*20000 1 1s1012345678910f1(s1)0004448881212x*100011122233s2678910 x20 10 10 1 20 1 20 1 2c2+f18 58 98 9 1012 9 1012 13 10f2(s2)8 9 1012 13x*20 1 2 0 1s2012345x200000 10 1c2+f100044545f2(s2)0004 5 5x*20000 1 1s2678910 x20 10 10 1 20 1 20 1 2c2+f18 58 98 9 1012 9 1012 13 10f2(s2)8 9 1012 13x*

49、20 1 2 0 1k=3，f3(s3) = max 6x3+ f2(s3-5x3) x3=0,1,2 = max f2(10), 6+f2(5), 12+f2(0) = max 13, 11, 12=13， x*3=0逆推逆推，可得全部策略為可得全部策略為：x*3=0， x*2=1， x*1=2。 當(dāng)當(dāng)約束條件兩個以上時約束條件兩個以上時，就是多維背包問就是多維背包問題題，解法與本例相似解法與本例相似，但狀態(tài)變量是多維的。但狀態(tài)變量是多維的。81/151二、生產(chǎn)經(jīng)營問題二、生產(chǎn)經(jīng)營問題例例8 生產(chǎn)與存儲問題生產(chǎn)與存儲問題某廠生產(chǎn)并銷售某種產(chǎn)品某廠生產(chǎn)并銷售某種產(chǎn)品，今后今后四個月需求量四個月

50、需求量預(yù)測如表預(yù)測如表7-7。每月生產(chǎn)每月生產(chǎn)j單位產(chǎn)品的單位產(chǎn)品的費用費用為：為： C(j)=0 j=0 =3+j (千元千元) j=1, 2, 3, 4, 5, 682/151i(月月)1234gi232 4月庫存費月庫存費E(j)=0.5j(千元千元)，最大，最大庫容庫容3單位單位，月，月最多最多產(chǎn)產(chǎn)6單位單位，期初期初和期末庫存都是和期末庫存都是零。零。試試訂訂四四個月計劃，個月計劃，既既滿足需求滿足需求，總費用總費用又又最小。設(shè)最小。設(shè)第第i+1月庫存是第月庫存是第i月月可可售售量量與需求量與需求量gk之之差；而差；而第第i月月可可售量是月初庫存量售量是月初庫存量sk與產(chǎn)量與產(chǎn)量uk

51、之之和。和。(1)階段：階段：每月每月為為一階段，一階段，k=1, 2, 3, 4。(2)狀態(tài)變狀態(tài)變量：量：sk為第為第k月初庫存量月初庫存量。(3)決策變決策變量量： uk為第為第k 月產(chǎn)量月產(chǎn)量。(4)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：sk+1=sk+uk-gk83/151(5)最最優(yōu)優(yōu)指標指標函數(shù)函數(shù)fk(sk)表示第表示第k月月初庫存初庫存sk時，按時，按最佳策略生產(chǎn)，從該月到第最佳策略生產(chǎn)，從該月到第4月末月末最低最低生產(chǎn)生產(chǎn)與與存存貯貯費費用。用。考慮考慮k=4，因因4月月末末庫存庫存應(yīng)應(yīng)為為零零，該該月需求月需求4，故故u4=4-s4，最大庫，最大庫容容為為3，s4只能取只能取0, 1

52、, 2, 3。f4(s4)=minC(u4)+E(s4)，f4(s4)與與u4(s4)如如下下表。表。表表7-884/151s40123f4(s4)76.565.5u4(s4)4321k=3， s3與與庫庫容、產(chǎn)能和容、產(chǎn)能和需求需求有關(guān)有關(guān)，在此，由在此，由庫庫容容量決定：量決定：s3=0, 1, 2, 3。u3至少為至少為g3-s3=2-s3，若，若s3大大于于2，則則u3應(yīng)取應(yīng)取0。為。為保證期末保證期末庫存庫存為為0，u3不能超過不能超過g3+g4-s3=6-s3，另外，另外，u3不能超不能超庫庫容容量量3，即不能超過即不能超過g3+3-s3=5-s3，也不能超產(chǎn)能，也不能超產(chǎn)能6，總

53、之，有，總之，有max0, 2-s3u3 min6, 5-s3, 6-s3的整數(shù)的整數(shù)f3(s3)=minC(u3)+E(s3)+f4(s3+u3-g3)85/151對對s3=0, 1, 2, 3求出求出f3(s3)，當(dāng)，當(dāng)s3=0時，時，f3(0)=min(3+u3)+0.50+f4(u3-2)， 2u35 u3=2: 5+7 = min u3=3: 6+6.5 = 12， u*3(0)=2, u3=4: 7+6 u3=5: 8+5.5這就是說，若這就是說，若第第3月初月初庫存為零，庫存為零，則則3、4二二月月最最低低費用費用為為12（千元），（千元），第第3月最月最優(yōu)產(chǎn)量為優(yōu)產(chǎn)量為2單位單

54、位。見見表表7-9。86/151s40123f4(s4)76.565.5u4(s4)4321當(dāng)當(dāng)s3=1時，時，f3(1)=min(3+u3)+0.51+f4(u3-1)， 1u34 u3=1: 4+0.5+7 = min u3=2: 5+0.5+6.5 = 11.5， u*3(1)=1, u3=3: 6+0.5+6 u3=4: 7+0.5+5.5這就是說，若這就是說，若第第3月初月初庫存庫存為為1，則，則3、4二二月月最最低低費用費用為為11.5（千元），（千元），第第3月最月最優(yōu)產(chǎn)量優(yōu)產(chǎn)量為為1單單位。位。87/151s40123f4(s4)76.565.5u4(s4)4321當(dāng)當(dāng)s3=2

55、時，時，f3(2)=minC(u3)+0.52+f4(u3)， 0u33 u3=0: 0+1+7 = min u3=1: 4+1+6.5 = 8， u*3(2)=0, u3=2: 5+1+6 u3=3: 6+1+5.5這就是說，若這就是說，若第第3月初月初庫存庫存為為2，則，則3、4二二月月最最低低費用費用為為8（千元），（千元），第第3月最月最優(yōu)產(chǎn)量優(yōu)產(chǎn)量為為0單位。單位。88/151s40123f4(s4)76.565.5u4(s4)4321當(dāng)當(dāng)s3=3時，時，f3(2)=minC(u3)+0.53+f4(u3+1)， 0u32 u3=0: 0+1.5+6.5 = min u3=1: 4+

56、1.5+6 = 8， u*3(3)=0, u3=2: 5+1.5+5.5 這就是說，若這就是說，若第第3月初月初庫存庫存為為3，則，則3、4二二月月最最低低費用費用為為8（千元），（千元），第第3月最月最優(yōu)產(chǎn)量優(yōu)產(chǎn)量為為0單位。單位。89/151s40123f4(s4)76.565.5u4(s4)432190/151s301u3(s3)23451234C+E+f41212.51313.511.51212.513f3(s3)1211.5u*3(s3)21s323u3(s3)0123012C+E+f4811.51212.5811.512f3(s3)88u*3(s3)00表表7-9s4=s3+u3-

57、g3=s3+u3-2k=2f2(s2)=minC(u2)+E(s2)+f3(s2+u2-g2)s2=0, 1, 2, 3決策變量決策變量u2為：為：max0, g2-s2u2min6, g2+3-s2, g2+g3+g4-s2的的整數(shù)，即整數(shù)，即max0, 3-s2u2min6, 6-s2, 9-s2的的整數(shù)整數(shù)本段計算結(jié)果見表本段計算結(jié)果見表7-10。91/15192/151s201u2(s2)34562345C+E+f31818.5161717.51815.516.5f2(s2)1615.5u*2(s2)54s323u3(s3)12340123C+E+f41717.5151613.5171

58、4.515.5f3(s3)1513.5u*3(s3)30表表7-10s3=s2+u2-g2=s2+u2-3k=1f1(s1)=minC(u1)+E(s1)+f2(s1+u1-g1)s1=0決策變量決策變量u1受本月需求量、庫存容量和生產(chǎn)能受本月需求量、庫存容量和生產(chǎn)能力限制，應(yīng)為力限制，應(yīng)為2u15的整數(shù)，的整數(shù)，f1(0)= min C(u1)+f2(u1-2) 2u15的的整數(shù)整數(shù)本本段計算結(jié)果見表段計算結(jié)果見表7-11。93/151表表7-11f1(s1)從表從表7-11可知，最低總費用為可知，最低總費用為f1(0)=21(千元千元)，第第1月最佳產(chǎn)量為月最佳產(chǎn)量為2單位，而需求為單位，

59、而需求為2單位，所以單位，所以，第，第2月初庫存為月初庫存為0，再由表，再由表7-10查查s2=0列，可列，可得，第得，第2月月最佳產(chǎn)量最佳產(chǎn)量為為5單位，同理查得，第單位，同理查得，第3月月最佳產(chǎn)量最佳產(chǎn)量為為0單位，第單位，第4月月最佳產(chǎn)量最佳產(chǎn)量為為4單位。單位。94/151s10u1(s1)2345C+f22121.52221.5f1(s1)21u*1(s1)2s2=s1+u1-g1=s1+u1-295/151例例9 采購與銷售問題采購與銷售問題 某商店未來某商店未來4個個月，準備用月，準備用一一個倉庫專銷個倉庫專銷某某種商品種商品，最，最多多貯存貯存1000單位。假定每月只能賣單位。

60、假定每月只能賣存存貨。貨。定定貨下月初貨下月初才能才能到。未來四個月買賣價到。未來四個月買賣價格格預(yù)測預(yù)測如如表表7-12。1月月初初庫庫存存500單位單位。若。若不計不計庫存庫存費，該店費，該店應(yīng)如何應(yīng)如何制訂制訂1至至4月購銷計劃月購銷計劃，使，使預(yù)期獲利最大預(yù)期獲利最大。 表表7-1296/151月份月份購價購價(ck) 售價售價(pk)110122983111341517解解 按按月劃月劃分分4階段階段，k=1, 2, 3, 4狀態(tài)變量狀態(tài)變量sk：第：第k月初庫存量月初庫存量。決策變量決策變量xk：第第k 月月賣賣出量出量。 yk：第：第k月訂購量月訂購量。狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：