數(shù)學(xué)方法動態(tài)規(guī)劃第1頁，共163頁，2023年，2月20日，星期六動態(tài)規(guī)劃(D.P.–DynamicProgram)是解決多階段決策過程最優(yōu)化問題的一種方法。

動態(tài)的含義：動態(tài)規(guī)劃方法與“時間”關(guān)系很密切，隨著時間過程的發(fā)展而決定各時段的決策，產(chǎn)生一個決策序列，這就是“動態(tài)”的意思。一、多階段決策問題的最優(yōu)化第2頁，共163頁，2023年，2月20日，星期六動態(tài)規(guī)劃的起源：

1951年,(美)數(shù)學(xué)家R.Bellman等人，根據(jù)多階段序貫決策問題的特點，提出了著名的“最優(yōu)性原理”。將多階段決策問題轉(zhuǎn)變?yōu)橐幌盗械幕ハ嗦?lián)系的單階段決策問題，然后，逐個階段予以解決，最后再形成總體解決。從而創(chuàng)建了求解優(yōu)化問題的新方法——動態(tài)規(guī)劃。1957年，他的名著《動態(tài)規(guī)劃》出版。一、多階段決策過程的最優(yōu)化第3頁，共163頁，2023年，2月20日，星期六最優(yōu)性原理:作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)子策略。簡言之，最優(yōu)策略的子策略總是最優(yōu)的。一、多階段決策過程的最優(yōu)化第4頁，共163頁，2023年，2月20日，星期六動態(tài)決策問題分類：1、按數(shù)據(jù)給出的形式分為：離散型動態(tài)決策問題。連續(xù)型動態(tài)決策問題。2、按決策過程演變的性質(zhì)分為：確定型動態(tài)決策問題。隨機(jī)型動態(tài)決策問題。一、多階段決策過程的最優(yōu)化第5頁，共163頁，2023年，2月20日，星期六例1生產(chǎn)與存貯問題要求確定一個逐月的生產(chǎn)計劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最小？

例2投資決策問題某公司現(xiàn)有資金Q萬元，在今后5年內(nèi)考慮給A，B，C，D4個項目投資？例3設(shè)備更新問題現(xiàn)企業(yè)要決定一臺設(shè)備未來8年的更新計劃，問應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最小？一、多階段決策過程的最優(yōu)化第6頁，共163頁，2023年，2月20日，星期六例4基建投資問題一家公司有三個工廠，每個廠都需要進(jìn)行擴(kuò)建。公司用于擴(kuò)建的資金總共為7萬元。各個廠的投資方案及擴(kuò)建后預(yù)期可獲得的利潤如表所示(單位：萬元)?，F(xiàn)在公司要確定各廠投資多少才能使公司的總利潤達(dá)到最大？

廠名方案1方案2方案3方案4投資數(shù)利潤投資數(shù)利潤投資數(shù)利潤投資數(shù)利潤一廠001528510二廠001339411三廠0027311413一、多階段決策過程的最優(yōu)化第7頁，共163頁，2023年，2月20日，星期六例5貨船裝運(yùn)問題有四種貨物準(zhǔn)備裝到一艘貨船上。第i(i＝1．2，3，4)種貨物的每一箱重量是wi(單位：噸)，其價值是vi(單位：干元)，如表所示。假定這艘貨船的總載重量是10噸，現(xiàn)在要確定這四種貨物應(yīng)各裝幾箱才能使裝載貨物的總價值達(dá)到最大？

貨物i單位重量wi單位價值vi124212347435一、多階段決策過程的最優(yōu)化第8頁，共163頁，2023年，2月20日，星期六例6

最短路程問題假定從A地到E地要鋪設(shè)一條管道，其中要經(jīng)過若干個中間點(如圖)。圖中兩點之間連線上的數(shù)字表示兩地間的距離，現(xiàn)在要選擇一條鋪設(shè)管道的路線使總長度最短。AB1B2B3C1C2C3D1D2E367769523835436943一、多階段決策過程的最優(yōu)化第9頁，共163頁，2023年，2月20日，星期六

動態(tài)規(guī)劃是解決多階段決策問題的一種方法。所謂多階段決策問題是指這樣的決策問題：其過程可分為若干個相互聯(lián)系的階段，每一階段都對應(yīng)著一組可供選擇的決策，每一決策的選定即依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。當(dāng)每一階段的決策選定以后，就構(gòu)成一個決策序列，稱為一個策略，它對應(yīng)著一個確定的效果。多階段決策問題就是尋找使此效果最好的策略。二、基本概念和基本原理第10頁，共163頁，2023年，2月20日，星期六二、基本概念和基本原理1、階段：將所給問題的過程，按時間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用字母k表示階段變量。動態(tài)規(guī)劃模型要用到的概念：(1)階段;(2)狀態(tài);(3)決策和策略;(4)狀態(tài)轉(zhuǎn)移;(5)指標(biāo)函數(shù)。第11頁，共163頁，2023年，2月20日，星期六2、狀態(tài)：各階段開始時的客觀條件叫做狀態(tài)。狀態(tài)變量：描述各階段狀態(tài)的變量，用sk表示第k階段的狀態(tài)變量。狀態(tài)集合：狀態(tài)變量的取值集合，用Sk表示。一階段：S1＝{A}二階段：S2＝{B1,B2,B3}三階段：S3＝{C1,C2,C3}四階段：S4＝{D1,D2}AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理第12頁，共163頁，2023年，2月20日，星期六3、決策：當(dāng)各段的狀態(tài)取定以后，就可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。決策變量：表示決策的變量，稱為決策變量，常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時的決策變量。允許決策集合：決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。D2(B1)={C1,C2}D2(B2)={C1,C2,C3}如狀態(tài)為B1時選擇C2，可表示為：u2(B1)=C2二、基本概念和基本原理第13頁，共163頁，2023年，2月20日，星期六策略：各段決策確定后，整個問題的決策序列就構(gòu)成一個策略，用p1,n{u1(s1),u2(s2),...un(sn)}表示。允許策略集合：對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。AB1B2B3C1C2C3D1D2E367769523835436943p1,4{B1,C1,D1,E}二、基本概念和基本原理第14頁，共163頁，2023年，2月20日，星期六4、狀態(tài)轉(zhuǎn)移方程：動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。第k段的狀態(tài)sk，本階段決策為uk(sk)，則第k+1段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可用公式表示：sk+1=Tk(sk,uk)sk+1=uk(sk)AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理第15頁，共163頁，2023年，2月20日，星期六

5、指標(biāo)函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。它分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。

階段指標(biāo)函數(shù)是指第k段，從狀態(tài)sk出發(fā)，采取決策uk時的效益，用d(sk,uk)表示。d(B1,C2)一個n段決策過程，從1到n叫作問題的原過程，對于任意一個給定的k(1≤k≤n)，從第k段到第n段的過程稱為原過程的一個后部子過程。V1,n(s1,p1,n)表示初始狀態(tài)為s1采用策略p1,n時原過程的指標(biāo)函數(shù)值;Vk,n(sk,pk,n)表示在第k段，狀態(tài)為sk采用策略pk,n時,后部子過程的指標(biāo)函數(shù)值。

最優(yōu)指標(biāo)函數(shù)記為fk(sk)：表示從第k段狀態(tài)sk采用最優(yōu)策略到過程終止時的最佳效益值。二、基本概念和基本原理第16頁，共163頁，2023年，2月20日，星期六最簡單的方法－－窮舉法。共有多少條路徑，依次計算并比較。動態(tài)規(guī)劃方法－－本方法是從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點到終點的最短路線，最后求得起始點到終點的最短路線。二、基本概念和基本原理第17頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2練習(xí)：求從A到E的最短路徑。二、基本概念和基本原理第18頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0二、基本概念和基本原理第19頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0二、基本概念和基本原理第20頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5二、基本概念和基本原理第21頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5二、基本概念和基本原理第22頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8二、基本概念和基本原理第23頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7二、基本概念和基本原理第24頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8二、基本概念和基本原理第25頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21二、基本概念和基本原理第26頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14二、基本概念和基本原理第27頁，共163頁，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21二、基本概念和基本原理第28頁，共163頁，2023年，2月20日，星期六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二、基本概念和基本原理第29頁，共163頁，2023年，2月20日，星期六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二、基本概念和基本原理第30頁，共163頁，2023年，2月20日，星期六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二、基本概念和基本原理第31頁，共163頁，2023年，2月20日，星期六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二、基本概念和基本原理第32頁，共163頁，2023年，2月20日，星期六可以看出，在求解的各階段，都利用了第k段和第k+1段的如下關(guān)系:這種遞推關(guān)系稱為動態(tài)規(guī)劃的基本方程，第二個式子稱為邊界條件。這種在圖上直接計算的方法稱為標(biāo)號法。二、基本概念和基本原理第33頁，共163頁，2023年，2月20日，星期六動態(tài)規(guī)劃標(biāo)號法較之窮舉法的優(yōu)點:第一，容易算出;其次，動態(tài)規(guī)劃的計算結(jié)果不僅得到了從起始點到最終點的最短路線，而且得到了中間段任一點到最終點的最短路線。二、基本概念和基本原理第34頁，共163頁，2023年，2月20日，星期六動態(tài)規(guī)劃方法的基本思想：(1)將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)．從而把問題化成一族同類型的子問題，然后逐個求解。(2)求解時從邊界條件開始，逆(或順)過程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。(3)動態(tài)規(guī)劃方法是既把當(dāng)前一段與未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。二、基本概念和基本原理第35頁，共163頁，2023年，2月20日，星期六三、動態(tài)規(guī)劃模型的建立與求解（一）動態(tài)規(guī)劃模型的建立（二）逆序解法與順序解法（三）基本方程分段求解時的幾種常用算法第36頁，共163頁，2023年，2月20日，星期六（一）動態(tài)規(guī)劃模型的建立建立動態(tài)規(guī)劃的模型關(guān)鍵，在于識別問題的多階段特征，將問題分解成為可用遞推關(guān)系式聯(lián)系起來的若干子問題，或者說正確地建立具體問題的基本方程。而正確建立基本遞推關(guān)系方程的關(guān)鍵又在于正確選擇狀態(tài)變量，保證各階段的狀態(tài)變量具有遞推的狀態(tài)轉(zhuǎn)移關(guān)系sk+1=Tk(sk,uk)下面以資源分配問題為例介紹動態(tài)規(guī)劃的建模條件及解法。三、動態(tài)規(guī)劃模型的建立與求解第37頁，共163頁，2023年，2月20日，星期六例5某公司有資金10萬元．若投資于項目i(i＝1，2，3）的投資額為xi時，其收益分別為g1(x1)＝4x1，g2(x2)＝9x2，g3(x3)＝2x32，問應(yīng)如何分配投資數(shù)額才能使總收益最大?可以人為地賦予時段，把問題轉(zhuǎn)化為一個3段決策過程。關(guān)鍵問題是如何正確選擇狀態(tài)變量，使各后部子過程之間具有遞進(jìn)關(guān)系。三、動態(tài)規(guī)劃模型的建立與求解第38頁，共163頁，2023年，2月20日，星期六K=1K=2第k段時所以，建立動態(tài)規(guī)劃模型：階段k：本例中取1，2，3狀態(tài)變量sk：第k段可以投資于第k項到第3個項目的資金數(shù)決策變量xk：決定給第k個項目投資的資金數(shù)。狀態(tài)轉(zhuǎn)移方程：sk+1＝sk-xk最優(yōu)指標(biāo)函數(shù)fk(sk)：當(dāng)可投資金額數(shù)為sk時，投資第k-3項所得的最大收益數(shù)?；痉匠虨椋喝?、動態(tài)規(guī)劃模型的建立與求解第39頁，共163頁，2023年，2月20日，星期六建立動態(tài)規(guī)劃模型的要點1、分析題意，識別問題的多階段特性，按時間或空間的先后順序適當(dāng)?shù)貏澐譃闈M足遞推關(guān)系的若干階段。2、正確地選擇狀態(tài)變量，使其具備兩個必要待征：(1)可知性；(2)能夠確切地描述過程的演變且滿足無后效性。3、根據(jù)狀態(tài)變量與決策變量的含義，正確寫出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)或轉(zhuǎn)移規(guī)則。4、根據(jù)題意明確指標(biāo)函數(shù)vk,n最優(yōu)指標(biāo)函數(shù)fk(sk)以及k階段指標(biāo)vk(sk,uk)的含義，并正確列出最優(yōu)指標(biāo)函數(shù)的遞推關(guān)系及邊界條件(即基本方程)。三、動態(tài)規(guī)劃模型的建立與求解第40頁，共163頁，2023年，2月20日，星期六（二）逆序解法與順序解法如果尋優(yōu)的方向與多階段決策過程的實際行進(jìn)方向相反，從最后一段開始計算逐段前推，求得全過程的最優(yōu)策略，稱為逆序解法。順序解法的尋優(yōu)方向同于過程的行進(jìn)方向，計算時從第一段開始逐段向后遞推，計算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計算的結(jié)果就是全過程的最優(yōu)結(jié)果。三、動態(tài)規(guī)劃模型的建立與求解第41頁，共163頁，2023年，2月20日，星期六第一步：k=0狀態(tài)：s1＝Af0(A)＝0求解步驟三、動態(tài)規(guī)劃模型的建立與求解第42頁，共163頁，2023年，2月20日，星期六第二步：k=1狀態(tài)：B1B2u1*(B1)=Au1*(B2)=Af1(B1)＝4f2(B2)＝5(4)(5)三、動態(tài)規(guī)劃模型的建立與求解第43頁，共163頁，2023年，2月20日，星期六第三步：k=2狀態(tài)：C1C2C3C4u2*(C1)=B1u2*(C2)=B1u2*(C3)=B1f2(C1)＝6f2(C2)＝7f2(C3)＝10u2*(C4)=B2f2(C4)＝12(4)(5)(6)(7)(10)(12)三、動態(tài)規(guī)劃模型的建立與求解第44頁，共163頁，2023年，2月20日，星期六(4)(5)(6)(7)(10)(12)第四步：k=3狀態(tài)：D1D2D3u3*(D1)=C1或C2u3*(D2)=C2u3*(D3)=C3f3(D1)＝11f3(D2)＝12f3(D3)＝14(11)(12)(14)三、動態(tài)規(guī)劃模型的建立與求解第45頁，共163頁，2023年，2月20日，星期六第五步：k=4狀態(tài)：E1E2u4*(E1)=D1u4*(E2)=D2f4(E1)＝14f4(E2)＝14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)三、動態(tài)規(guī)劃模型的建立與求解第46頁，共163頁，2023年，2月20日，星期六第六步：k=5狀態(tài)：Fu5*(F)=E2f5(F)＝17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即從A到F的最短距離為17。最優(yōu)路線為：A－B1－C2－D2－E2－F三、動態(tài)規(guī)劃模型的建立與求解第47頁，共163頁，2023年，2月20日，星期六逆序解法與順序解法建模的不同點1．狀態(tài)轉(zhuǎn)移方式不同sk+1=Tk(sk,uk)sk=Tk(sk+1,uk)1狀態(tài)s1決策u1效益v1(s1,u1)s2kskukvk(sk,uk)Sk+1nsnunvn(sn,un)Sn+11狀態(tài)s1決策u1效益v1(s2,u1)s2kskukvk(sk+1,uk)Sk+1nsnunvn(sn+1,un)Sn+1三、動態(tài)規(guī)劃模型的建立與求解第48頁，共163頁，2023年，2月20日，星期六2．指標(biāo)函數(shù)的定義不同逆序解法中，我們定義最優(yōu)指標(biāo)函數(shù)fk(sk)表示第k段從狀態(tài)sk出發(fā)，到終點后部子過程最優(yōu)效益值，f1(s1)是整體最優(yōu)函數(shù)值。順序解法中，定義最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示第k段時從起點到狀態(tài)sk+1的前部子過程最優(yōu)效益值。fn(sn+1)是整體最優(yōu)函數(shù)值。三、動態(tài)規(guī)劃模型的建立與求解第49頁，共163頁，2023年，2月20日，星期六3，基本方程形式不同(1)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)和形式逆序解法則基本方程為：則基本方程為：順序解法三、動態(tài)規(guī)劃模型的建立與求解第50頁，共163頁，2023年，2月20日，星期六(2)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)積形式逆序解法基本方程為：基本方程為：順序解法三、動態(tài)規(guī)劃模型的建立與求解第51頁，共163頁，2023年，2月20日，星期六B1C1D1235843三、動態(tài)規(guī)劃模型的建立與求解第52頁，共163頁，2023年，2月20日，星期六逆序遞推方程：（1）k=5時，狀態(tài)它們到F點的距離即為最短路。第53頁，共163頁，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4時，狀態(tài)它們到F點需經(jīng)過中途點E，需一一分析從E到F的最短路：先說從D1到F的最短路有兩種選擇：經(jīng)過E1,E2,比較最短。第54頁，共163頁，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143這說明由D1到F的最短距離為7，其路徑為相應(yīng)的決策為：第55頁，共163頁，2023年，2月20日，星期六這說明由D2到F的最短距離為5，其路徑為相應(yīng)的決策為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第56頁，共163頁，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距離為5，其路徑為相應(yīng)的決策為：第57頁，共163頁，2023年，2月20日，星期六（3）k=3時，狀態(tài)這說明由C1到F的最短距離為12，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第58頁，共163頁，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距離為10，相應(yīng)的決策為第59頁，共163頁，2023年，2月20日，星期六即由C3到F的最短距離為8，相應(yīng)的決策為即由C4到F的最短距離為9，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第60頁，共163頁，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時，狀態(tài)這說明由B1到F的最短距離為13，相應(yīng)的決策為第61頁，共163頁，2023年，2月20日，星期六即由B2到F的最短距離為15，相應(yīng)的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第62頁，共163頁，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1時，只有一個狀態(tài)點A,則即由A到F的最短距離為17，相應(yīng)的決策為第63頁，共163頁，2023年，2月20日，星期六所以最優(yōu)路線為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按計算順序反推可得最優(yōu)決策序列：第64頁，共163頁，2023年，2月20日，星期六順序遞推方程：AB1B2C1C2C3C4D1D2D3E1E2F4523687758453484356231431階段2階段3階段4階段5階段行走方向第65頁，共163頁，2023年，2月20日，星期六最短路徑：最短路長：注：順序解法與逆序解法無本質(zhì)區(qū)別，一般來說，當(dāng)初始狀態(tài)給定時用逆序解法，當(dāng)終止?fàn)顟B(tài)給定時用順序解法。若問題給定了一個初始狀態(tài)與一個終止?fàn)顟B(tài)，則兩種方法均可使用。第66頁，共163頁，2023年，2月20日，星期六1．離散變量的分段窮舉算法

動態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值，則可采用分段窮舉法。如前面例4的求解方法就是分段窮舉算法，由于每段的狀態(tài)變量和決策變量離散取值個數(shù)較少，所以動態(tài)規(guī)劃的窮舉法要比一般的窮舉法有效。用分段窮舉法求最優(yōu)指標(biāo)函數(shù)值時，最重要的是正確確定每段狀態(tài)變量取值范圍和允許決策集合的范圍。（三）基本方程分段求解時的幾種常用算法三、動態(tài)規(guī)劃模型的建立與求解第67頁，共163頁，2023年，2月20日，星期六2．連續(xù)變量的解法當(dāng)動態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據(jù)方程的具體情況靈活選取求解方法，如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計算方法等。如在例5中，狀態(tài)變量與決策變量均可取連續(xù)值而不是離散值，所以每階段求優(yōu)時不能用窮舉方法處理。下面分別用逆序解法求解。三、動態(tài)規(guī)劃模型的建立與求解第68頁，共163頁，2023年，2月20日，星期六例5：某公司有資金10萬元．若投資于項目i(i＝1，2，3）的投資額為xi時，其收益分別為g1(x1)＝4x1,g2(x2)＝9x2,g3(x3)＝2x32，問應(yīng)如何分配投資數(shù)額才能使總收益最大?三、動態(tài)規(guī)劃模型的建立與求解第69頁，共163頁，2023年，2月20日，星期六其動態(tài)規(guī)劃模型已建立如下：階段k：本例中取1，2，3狀態(tài)變量sk：第k段可以投資于第k項到第3個項目的資金數(shù)決策變量xk：決定給第k個項目投資的資金數(shù)。狀態(tài)轉(zhuǎn)移方程：sk+1＝sk-xk最優(yōu)指標(biāo)函數(shù)fk(sk)：當(dāng)可投資金數(shù)為sk時，投資第k-3項所得的最大收益數(shù)?；痉匠虨椋喝?、動態(tài)規(guī)劃模型的建立與求解第70頁，共163頁，2023年，2月20日，星期六k＝3時三、動態(tài)規(guī)劃模型的建立與求解第71頁，共163頁，2023年，2月20日，星期六k＝2時三、動態(tài)規(guī)劃模型的建立與求解第72頁，共163頁，2023年，2月20日，星期六k＝1時三、動態(tài)規(guī)劃模型的建立與求解第73頁，共163頁，2023年，2月20日，星期六k＝1時最優(yōu)投資方案為全部資金投于第3個項目，可得最大收益200萬元。三、動態(tài)規(guī)劃模型的建立與求解第74頁，共163頁，2023年，2月20日，星期六例用動態(tài)規(guī)劃解決下面問題解：此問題分三個階段；取第k階段決策變量為xk；狀態(tài)變量sk表示從第k階段到第3階段“消耗”的數(shù):指標(biāo)函數(shù)為目標(biāo)第k項之后部分的和式:三、動態(tài)規(guī)劃模型的建立與求解第75頁，共163頁，2023年，2月20日，星期六狀態(tài)轉(zhuǎn)移方程：允許決策集合為允許狀態(tài)集合最優(yōu)值函數(shù)和邊界條件三、動態(tài)規(guī)劃模型的建立與求解第76頁，共163頁，2023年，2月20日，星期六逆向遞歸求解：三、動態(tài)規(guī)劃模型的建立與求解第77頁，共163頁，2023年，2月20日，星期六最優(yōu)函數(shù)值最優(yōu)解是（指標(biāo)函數(shù)最優(yōu)值）回代求最優(yōu)決策三、動態(tài)規(guī)劃模型的建立與求解第78頁，共163頁，2023年，2月20日，星期六四、在經(jīng)濟(jì)管理中的應(yīng)用（一）背包問題背包問題的一般提法是：一位旅行者攜帶背包去登山,已知他所能承受的背包重量限度為a千克，現(xiàn)有n種物品可供他選擇裝入背包。第i種物品的單件重量為ai干克、其價值(可以是表明本物品對登山的重要性的數(shù)量指標(biāo))是攜帶數(shù)量xi的函數(shù)ci(xi)(i＝1，2，…n)，問旅行者應(yīng)如何選擇攜帶各種物品的件數(shù)，以使總價值最大？其他如車、船、飛機(jī)、潛艇、人造衛(wèi)星等工具的最優(yōu)裝載問題，機(jī)床加工中零件最優(yōu)加工、下料問題、投資決策問題，均等同于背包問題。第79頁，共163頁，2023年，2月20日，星期六背包問題的動態(tài)規(guī)劃模型1階段k：將可裝入物品按1，2，...，n排序，共劃分為n個階段，即k＝1，2，...，n。2狀態(tài)變量sk+1：在第k段開始時，背包中允許裝入前k種物品的總重量。3決策變量xk：裝入第k種物品的件數(shù)。4狀態(tài)轉(zhuǎn)移方程：sk=sk+1-akxk5允許決策集合為：Dk(sk+1)＝{xk|o≤xk≤[sk+1/ak]，xk為整數(shù)}6最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示在背包中允許裝入物品的總重量不超過sk+1千克，采用最優(yōu)策略只裝前k種物品時的最大使用價值。7順序遞推方程：四、在經(jīng)濟(jì)管理中的應(yīng)用第80頁，共163頁，2023年，2月20日，星期六例:有一輛最大貨運(yùn)量為10噸的卡車，用以裝載3種貨物．每種貨物的單位重量及相應(yīng)單位價值如表所示。應(yīng)如何裝載可使總價值最大?設(shè)第i種貨物裝載的件數(shù)為xi(i＝1，2，3)，則問題可表為貨物編號I123單位重量（t）345單位價值ci456四、在經(jīng)濟(jì)管理中的應(yīng)用第81頁，共163頁，2023年，2月20日，星期六K=1s2012345678910f1(s2)0004448881212x1*00011122233s2f1(s2)x1*建立動態(tài)規(guī)劃模型，用列表法求解四、在經(jīng)濟(jì)管理中的應(yīng)用第82頁，共163頁，2023年，2月20日，星期六K=2s3012345678910x2000001010101012012012c2+f2000445458589891012910121310f2(s3)00045589101213x2*00001101201s3x2c2+f2f2(s3)x2*四、在經(jīng)濟(jì)管理中的應(yīng)用第83頁，共163頁，2023年，2月20日，星期六K=3所以x3*=0s3=s4-5x3=10-5*0=10所以x2*=1s2=s3-4x2=10-4*1=6所以x1*=2全部策略為：x1*=2x2*=1x3*=0，最大價值為13。四、在經(jīng)濟(jì)管理中的應(yīng)用第84頁，共163頁，2023年，2月20日，星期六（二）生產(chǎn)經(jīng)營問題—生產(chǎn)與存貯問題

在生產(chǎn)和經(jīng)營管理中．經(jīng)常遇到如何合理地安排生產(chǎn)計劃、采購計劃以及倉庫的存貨計劃和銷售計劃，使總效益最高的問題。四、在經(jīng)濟(jì)管理中的應(yīng)用第85頁，共163頁，2023年，2月20日，星期六例：某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月市場需求預(yù)測如表，又每月生產(chǎn)單位產(chǎn)品費(fèi)用為：每月庫存j單位產(chǎn)品的費(fèi)用為E(j)＝0.5j(干元)，該廠最大庫存容量為3單位，每月最大生產(chǎn)能力為6單位，計劃開始和計劃期末庫存量都是零。試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第j+1個月的庫存量是第j個月可銷售量與該月用戶需求量之差；而第i個月的可銷售量是本月初庫存量與產(chǎn)量之和。i（月）1234gi（需求）2324四、在經(jīng)濟(jì)管理中的應(yīng)用第86頁，共163頁，2023年，2月20日，星期六(1)階段：每個月為一個階段，k＝1，2，3，4。(2)狀態(tài)變量:sk為第k個月初的庫存量。(3)決策變量:uk為第k個月的生產(chǎn)量。(4)狀態(tài)轉(zhuǎn)移方程：sk+1=sk+uk-gk(5)最優(yōu)指標(biāo)函數(shù)：fk(sk)表示第k月狀態(tài)為sk時，采用最佳策略生產(chǎn)，從本月到計劃結(jié)束（第4個月末）的生產(chǎn)與存貯最低費(fèi)用。(6)基本方程：解：建立動態(tài)規(guī)劃模型四、在經(jīng)濟(jì)管理中的應(yīng)用第87頁，共163頁，2023年，2月20日，星期六K=4u4=4-s4s40123f4(s4)76.565.5u4(s4)4321s4f4(s4)u4(s4)四、在經(jīng)濟(jì)管理中的應(yīng)用第88頁，共163頁，2023年，2月20日，星期六s30123u3(s3)234512340123012C+E+f41212.51313.511.51212.513811.51212.5811.512f3(s3)1211.588u3*(s3)2100K=3s3={0,1,2,3}s3u3(s3)C+E+f4f3(s3)u3*(s3)四、在經(jīng)濟(jì)管理中的應(yīng)用第89頁，共163頁，2023年，2月20日，星期六s20123u2(s2)3456234512340123C+E+f31818.5161717.51815.516.51717.5151613.51714.515.5f2(s2)1615.51513.5u2*(s2)5430K=2s2={0,1,2,3}s2u2(s2)C+E+f3f2(s2)u2*(s2)四、在經(jīng)濟(jì)管理中的應(yīng)用第90頁，共163頁，2023年，2月20日，星期六s10u1(s1)2345C+f22121.52221.5f1(s1)21u1*(s1)2K=1s1={0}s1u1(s1)C+f2f1(s1)u1*(s1)可得最佳生產(chǎn)計劃為：第一個月生產(chǎn)2單位，第二個月生產(chǎn)5單位，第三個月不生產(chǎn)，第四個月生產(chǎn)4單位。四、在經(jīng)濟(jì)管理中的應(yīng)用第91頁，共163頁，2023年，2月20日，星期六（三）設(shè)備更新問題企業(yè)中經(jīng)常會遇到一臺設(shè)備應(yīng)該使用多少年更新最合算的問題。一般來說，一臺設(shè)備在比較新時，年運(yùn)轉(zhuǎn)量大，經(jīng)濟(jì)收入高，故障少，維修費(fèi)用少，但隨著使用年限的增加，年運(yùn)轉(zhuǎn)量減少因而收入減少，故障變多，維修費(fèi)用增加。如果更新可提高年凈收入，但是當(dāng)年要支出一筆數(shù)額較大的購買費(fèi)。設(shè)備更新的一般提法為：在已知一臺設(shè)備的效益函數(shù)，維修費(fèi)用函數(shù)及更新費(fèi)用函數(shù)條件下，要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使使n年總效益最大。四、在經(jīng)濟(jì)管理中的應(yīng)用第92頁，共163頁，2023年，2月20日，星期六例11某臺新設(shè)備的年效益及年均維修費(fèi)、更新凈費(fèi)用如表7-15所示。試確定今后5年內(nèi)的更新策略，使總收益最大。表7-15單位：萬元

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5第93頁，共163頁，2023年，2月20日，星期六解：以年限劃分階段k：1，2，3，4，512345決策變量:第k年初保留使用(keep)第k年初更新(replacement)狀態(tài)變量:第k年初，設(shè)備已使用過的年數(shù)，稱役齡。狀態(tài)轉(zhuǎn)移方程：第94頁，共163頁，2023年，2月20日，星期六在第k年設(shè)備已使用過t年（或役齡為t年），再使用1年時的效益。在第k年設(shè)備已使用過t年（或役齡為t年），再使用1年時的維修費(fèi)用。在第k年賣掉一臺役齡為t年的設(shè)備，買進(jìn)一臺新的設(shè)備的更新凈費(fèi)用。

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5第95頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5即：“買一部新機(jī)器的費(fèi)用”－“賣一部t年役齡的舊機(jī)器的收益”。階段指標(biāo)函數(shù)：第96頁，共163頁，2023年，2月20日，星期六最優(yōu)指標(biāo)函數(shù)：第k年初，使用一臺已用了年的設(shè)備，到第5年末的最大效益，有按逆序建立遞推式：下面用逆序法求解：第97頁，共163頁，2023年，2月20日，星期六K=5時：此時，的所有可能取值為：1，2，3，4。下分別求最優(yōu)指標(biāo)函數(shù)值：12345第98頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第99頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第100頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第101頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第102頁，共163頁，2023年，2月20日，星期六

12343.532.52.31.7520.51.53.52.521.5第103頁，共163頁，2023年，2月20日，星期六12343.52.521.5K=5時最優(yōu)值表第104頁，共163頁，2023年，2月20日，星期六K=4時：此時，的所有可能取值為：1，2，3。下分別求最優(yōu)指標(biāo)函數(shù)值：12345第105頁，共163頁，2023年，2月20日，星期六12343.52.521.5K=5時最優(yōu)值表

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第106頁，共163頁，2023年，2月20日，星期六12343.52.521.5K=5時最優(yōu)值表

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第107頁，共163頁，2023年，2月20日，星期六12343.52.521.5K=5時最優(yōu)值表

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第108頁，共163頁，2023年，2月20日，星期六1236.55.85.5K=4時最優(yōu)值表第109頁，共163頁，2023年，2月20日，星期六K=3時：此時，的所有可能取值為：1，2。下分別求最優(yōu)指標(biāo)函數(shù)值：12345第110頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，1236.55.85.5K=4時最優(yōu)值表第111頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，1236.55.85.5K=4時最優(yōu)值表第112頁，共163頁，2023年，2月20日，星期六129.58.8K=3時最優(yōu)值表第113頁，共163頁，2023年，2月20日，星期六K=2時：此時，只能取1。所以12345第114頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，129.58.8K=3時最優(yōu)值表第115頁，共163頁，2023年，2月20日，星期六K=1時：此時，只能取0。所以12345第116頁，共163頁，2023年，2月20日，星期六

役齡項目012345效益54.543.7532.5維修費(fèi)0.511.522.53更新費(fèi)0.51.52.22.533.5此時，第117頁，共163頁，2023年，2月20日，星期六12345狀態(tài)轉(zhuǎn)移方程：上述計算遞推回去，當(dāng)時，由狀態(tài)轉(zhuǎn)移方程：知查得第118頁，共163頁，2023年，2月20日，星期六12345狀態(tài)轉(zhuǎn)移方程：有知129.58.8K=3時最優(yōu)值表查知第119頁，共163頁，2023年，2月20日，星期六12345狀態(tài)轉(zhuǎn)移方程：查知1236.55.85.5K=4時最優(yōu)值表第120頁，共163頁，2023年，2月20日，星期六12345狀態(tài)轉(zhuǎn)移方程：查12343.52.521.5K=5時最優(yōu)值表第121頁，共163頁，2023年，2月20日，星期六故本題最優(yōu)策略為，即第一年初購買的設(shè)備到第二、三、四、年初各更新一次，用到第5年末，其總效益為17萬元。第122頁，共163頁，2023年，2月20日，星期六例2資源分配問題（離散型）例：設(shè)有6萬元資金用于4個工廠的擴(kuò)建，已知每個工廠的利潤增長額同投資額的大小有關(guān)，見下表。問應(yīng)如何確定對這四個工廠的投資額，使總利潤增長額最大？投資額(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤增長額

（百元）第123頁，共163頁，2023年，2月20日，星期六解：把對四個工廠的投資依次看成4個階段的決策過程，確定對第k個工廠的投資額看成第k個階段的決策，k=1,2,3,4。圖示如下：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)狀態(tài)變量：可用于第k,k+1,…n個工廠的投資額。決策變量：第k階段對第k個工廠的投資額。允許決策集：第124頁，共163頁，2023年，2月20日，星期六狀態(tài)轉(zhuǎn)移方程：其中階段指標(biāo)函數(shù)：第k階段投資元時所產(chǎn)生的利潤。（見上表）最優(yōu)指標(biāo)函數(shù)：第k階段狀態(tài)為且采取最佳投資策略，從第k個工廠以及以后的最大總利潤。逆序法基本遞推方程：第125頁，共163頁，2023年，2月20日，星期六工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）解：（1）k=4時考慮：若到最后一個，第4個工廠投資時，還有資金，若投資于第4個工廠的資金為，則最大利潤為第126頁，共163頁，2023年，2月20日，星期六工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）（注意到此時=0）第127頁，共163頁，2023年，2月20日，星期六自然問：現(xiàn)在還有多少錢？即=？=0，100，200，300，400，500，600都有可能。下面分情況討論：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)狀態(tài)狀態(tài)投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）第128頁，共163頁，2023年，2月20日，星期六時，時，其他種情況類似討論，我們把所有的結(jié)果匯總成一個表2。投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）第129頁，共163頁，2023年，2月20日，星期六01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時決策表投資額(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤增長額

（百元）第130頁，共163頁，2023年，2月20日，星期六（2）k=3時到第三個工廠投資時，可利用的資金還有，若向第三個工廠投資（萬元），則自此即以后最大利潤為：

表1利潤增長額

（百元）投資額(j)工廠(i)010020030040050060030183961789095同樣問：=？，即現(xiàn)在還有多少錢？它是允許決策集上界。同理第131頁，共163頁，2023年，2月20日，星期六僅舉一例：投資額(j)工廠(i)010020030040050060030183961789095

表1利潤增長額

（百元）第132頁，共163頁，2023年，2月20日，星期六01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時決策表投資額(j)工廠(i)010020030040050060030183961789095表1利潤增長額（百元）第133頁，共163頁，2023年，2月20日，星期六所有情況討論結(jié)果匯總成下表：010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表第134頁，共163頁，2023年，2月20日，星期六（3）k=2時僅舉一例：第135頁，共163頁，2023年，2月20日，星期六投資額(j)工廠(i)010020030040050060020254557657073表1利潤增長額（百元）第136頁，共163頁，2023年，2月20日，星期六010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表第137頁，共163頁，2023年，2月20日，星期六關(guān)于的其它取值情況及相應(yīng)的最優(yōu)決策列于下表010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時決策表第138頁，共163頁，2023年，2月20日，星期六（4）k=1時，此時第139頁，共163頁，2023年，2月20日，星期六投資額(j)工廠(i)010020030040050060010204260758590表1利潤增長額（百元）第140頁，共163頁，2023年，2月20日，星期六010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+89