第七章動(dòng)態(tài)規(guī)劃

第七章動(dòng)態(tài)規(guī)劃第一頁(yè)，共六十一頁(yè)，編輯于2023年，星期四Chapter7動(dòng)態(tài)規(guī)劃

(DynamicProgramming)多階段決策問(wèn)題動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的求解步驟動(dòng)態(tài)規(guī)劃模型的建立運(yùn)用動(dòng)態(tài)規(guī)劃求解實(shí)際問(wèn)題本章主要內(nèi)容：第二頁(yè)，共六十一頁(yè)，編輯于2023年，星期四引言動(dòng)態(tài)規(guī)劃作為運(yùn)籌學(xué)的一個(gè)重要分支是解決多階段決策過(guò)程最優(yōu)化的一種非常有效的方法。1951年，美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人，根據(jù)一類(lèi)多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列相互聯(lián)系的單階段決策問(wèn)題，然后分階段逐個(gè)加以解決。貝爾曼等人在研究和解決了大量實(shí)際問(wèn)題之后，提出了解決這類(lèi)問(wèn)題的——所謂“最優(yōu)性原理”，通常稱(chēng)為“貝爾曼最優(yōu)化原理”，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新的方法——

動(dòng)態(tài)規(guī)劃——（DynamicProgramming）。貝爾曼的名著《動(dòng)態(tài)規(guī)劃》于1957年出版，這成了動(dòng)態(tài)規(guī)劃的第一本著作。第三頁(yè)，共六十一頁(yè)，編輯于2023年，星期四引言動(dòng)態(tài)規(guī)劃的方法，在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門(mén)中有著廣泛的應(yīng)用，并且獲得了顯著的效果。在經(jīng)濟(jì)管理方面，動(dòng)態(tài)規(guī)劃可以用來(lái)解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存問(wèn)題、裝載問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題、生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等等，它是現(xiàn)代企業(yè)管理中的一種重要的決策方法。許多實(shí)際問(wèn)題采用動(dòng)態(tài)規(guī)劃方法去處理，常比線性規(guī)劃或非線性規(guī)劃更加有效。特別對(duì)于離散性的問(wèn)題，由于解析數(shù)學(xué)無(wú)法施展其術(shù)，而動(dòng)態(tài)規(guī)劃的方法就成為一種非常有效的工具。第四頁(yè)，共六十一頁(yè)，編輯于2023年，星期四引言應(yīng)特別指出的是，動(dòng)態(tài)規(guī)劃是解決某一類(lèi)問(wèn)題的一種方法，是分析問(wèn)題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。因此，在學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除了對(duì)基本概念和方法正確地理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。正如貝爾曼本人所說(shuō)：“由于動(dòng)態(tài)規(guī)劃的最優(yōu)化原理僅僅是一種基本原理，正是它的某種不確定性為你提供了發(fā)揮你創(chuàng)造性思維的巨大空間!本章我們?cè)趯W(xué)習(xí)動(dòng)態(tài)規(guī)劃基本概念、理論和方法的基礎(chǔ)上，在通過(guò)一些典型的應(yīng)用問(wèn)題來(lái)說(shuō)明它的應(yīng)用。第五頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法多階段決策過(guò)程整個(gè)決策過(guò)程可按時(shí)間或空間順序分解成若干相互聯(lián)系的階段，每一階段都需作出決策，全部過(guò)程的決策是一個(gè)決策序列。多階段決策過(guò)程最優(yōu)化的目標(biāo)：達(dá)到整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu)，而非各單個(gè)階段最優(yōu)的簡(jiǎn)單總和。請(qǐng)看如下典型案例——最短路線問(wèn)題第六頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一階段第二階段第三階段第四階段第五階段第六階段531368766835342138223335526643437597681310912131618該點(diǎn)到G點(diǎn)的最短距離第七頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法動(dòng)態(tài)規(guī)劃方法的基本術(shù)語(yǔ)：1、階段和階段變量對(duì)整個(gè)決策過(guò)程的自然劃分，通常根據(jù)時(shí)間順序或空間特征來(lái)劃分階段，以便按階段的次序逐段解決整個(gè)過(guò)程的優(yōu)化問(wèn)題。階段變量通常用k表示（k=1，2，3，…，n）。2、狀態(tài)與狀態(tài)變量每個(gè)階段開(kāi)始時(shí)過(guò)程所處的自然狀況或客觀條件成為該階段的狀態(tài)。每個(gè)階段的初始狀況又是前一個(gè)階段的終止?fàn)顩r（第一階段除外）。因此，一旦各個(gè)階段的狀態(tài)確定之后，整個(gè)過(guò)程也完全確定。從這個(gè)意義上說(shuō)，多階段決策過(guò)程也是各個(gè)狀態(tài)的演變過(guò)程。第八頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法狀態(tài)具有“無(wú)后效性”，即當(dāng)前階段狀態(tài)給定時(shí)，這個(gè)階段以后過(guò)程的演變與該階段以前各階段的狀態(tài)無(wú)關(guān)。一般把描述階段狀態(tài)的變量稱(chēng)為狀態(tài)變量。通常用sk表示第k階段的狀態(tài)。第k階段狀態(tài)變量的允許取值范圍稱(chēng)為階段k的狀態(tài)集合。記作Sk。3、決策與決策變量當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出不同的決定或選擇，從而演變到下一階段的某個(gè)狀態(tài)，這種決定或選擇稱(chēng)為決策。描述決策的變量稱(chēng)為決策變量，通常用uk表示，前面已經(jīng)說(shuō)過(guò)，決策要依據(jù)該階段的狀態(tài)，因此通常用uk(sk)表示第k階段處于狀態(tài)sk時(shí)的決策。決策變量的取值范圍稱(chēng)為決策集合，表示為Dk(sk)。第九頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法4、策略與子策略一組有序的決策序列構(gòu)成一個(gè)策略，從第k階段至第n階段的一個(gè)策略稱(chēng)為后部子策略記為pk，n→（uk，uk+1，…，un）。5、狀態(tài)轉(zhuǎn)移方程在確定型多階段決策過(guò)程中，一旦某階段的狀態(tài)和決策為已知，下一階段的狀態(tài)便完全確定，用狀態(tài)轉(zhuǎn)移方程反映這種狀態(tài)間的演變規(guī)律，寫(xiě)作：

（7.1）第十頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法6、指標(biāo)函數(shù)衡量決策效果優(yōu)劣的數(shù)量指標(biāo)稱(chēng)為指標(biāo)函數(shù)，具體可以是收益、成本、距離等指標(biāo)，可以分為k階段指標(biāo)函數(shù)，子過(guò)程指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)。從k階段狀態(tài)sk出發(fā)，做出決策uk所產(chǎn)生的第k階段指標(biāo)稱(chēng)為k階段指標(biāo)函數(shù)，記為vk(sk,uk)。從k階段狀態(tài)sk出發(fā)，選擇決策uk，uk+1，…，un所產(chǎn)生的過(guò)程指標(biāo)，稱(chēng)為k子過(guò)程指標(biāo)函數(shù)或簡(jiǎn)記為過(guò)程指標(biāo)函數(shù)，記為Vk(sk,uk,uk+1,…,un)或Vk,n。從k階段狀態(tài)sk出發(fā)，對(duì)所有的子策略，最優(yōu)的過(guò)程指標(biāo)函數(shù)稱(chēng)為最優(yōu)指標(biāo)函數(shù)，記為fk(sk)，通常取Vk的最大值或最小值。第十一頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法通常要求動(dòng)態(tài)規(guī)劃的子過(guò)程指標(biāo)滿足遞推關(guān)系常用的有連加和連乘的形式，分別為（7.2）（7.3）第十二頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法最有指標(biāo)函數(shù)fk(sk)取式（7.2）和（7.3）的最優(yōu)值，分別為：式（7.4）和（7.5）稱(chēng)為動(dòng)態(tài)規(guī)劃的基本方程。為了使遞推方程有遞推起點(diǎn)，需要確定最后一個(gè)狀態(tài)sn的最優(yōu)指標(biāo)函數(shù)fn(sn)的值，稱(chēng)為終端條件。一般情況下，連和形式fn(sn)=0，連乘形式fn(sn)=1。動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型由式(8.4)或(8.5)，邊界條件及狀態(tài)轉(zhuǎn)移方程構(gòu)成，如連加形式的數(shù)學(xué)模型為：（7.4）（7.5）第十三頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法由式（7.4）和使（7.5）的形式知，計(jì)算順序是從最后一個(gè)階段開(kāi)始到第一個(gè)階段結(jié)束，這種方法稱(chēng)為逆序算法。也可以將基本方程改為前向遞推：這時(shí)計(jì)算順序是從第一階段開(kāi)始到最后一個(gè)階段結(jié)束，這種算法稱(chēng)為順序算法。第十四頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法總結(jié)在明確了動(dòng)態(tài)規(guī)劃的基本概念和基本思想之后，在解決一個(gè)實(shí)際問(wèn)題建立動(dòng)態(tài)規(guī)劃模型時(shí)，步驟如下：（1）將問(wèn)題的過(guò)程劃分為恰當(dāng)?shù)碾A段；（2）正確選擇狀態(tài)變量sk，使它既能描述過(guò)程的演變，又能滿足無(wú)后效性；（3）正確寫(xiě)出決策變量uk及每階段的允許決策集合Dk(sk)；（4）正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程；（5）正確寫(xiě)出指標(biāo)函數(shù)Vk,n的關(guān)系，它滿足下面三個(gè)性質(zhì)：第十五頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃的基本概念和基本方法①是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)；②具有可分離性，并滿足遞推關(guān)系。即：③函數(shù)對(duì)于變量Vk+1,n要嚴(yán)格單調(diào)。以上五點(diǎn)是構(gòu)造動(dòng)態(tài)規(guī)劃模型的基礎(chǔ)，是正確寫(xiě)出動(dòng)態(tài)規(guī)劃基本方程的基本要素。而一個(gè)問(wèn)題的動(dòng)態(tài)規(guī)劃模型是否正確給出，它集中反映在恰當(dāng)?shù)囟x最優(yōu)值函數(shù)和正確寫(xiě)出遞推關(guān)系式及邊界條件。簡(jiǎn)而言之，要正確寫(xiě)出動(dòng)態(tài)規(guī)劃的基本方程。第十六頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃舉例下面我們舉一個(gè)動(dòng)態(tài)規(guī)劃的實(shí)際例子。例7.1（基建投資問(wèn)題）一家公司有三個(gè)工廠，每個(gè)工廠都需要進(jìn)行擴(kuò)建。公司用于擴(kuò)建的資金總額為7萬(wàn)元。各工廠的投資方案及擴(kuò)建后預(yù)期可得到的利潤(rùn)如下表：現(xiàn)在公司要確定對(duì)各廠投資多少，才能使公司的總利潤(rùn)達(dá)到最大？廠名方案1方案2方案3方案4投資數(shù)利潤(rùn)投資數(shù)利潤(rùn)投資數(shù)利潤(rùn)投資數(shù)利潤(rùn)一廠二廠三廠0000001125372338911344101113第十七頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃舉例解.（1）劃分階段：我們把每個(gè)工廠獲得投資作為一個(gè)階段，k=1,2,3。（2）選擇狀態(tài)變量：選取第k階段可用的資金總額作為狀態(tài)變量，記為sk。（3）確定決策變量：選擇分配給階段k的投資數(shù)作為決策變量，記為uk，決策集合記為Dk。（4）狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk（5）定義fk(sk)：第k階段投資時(shí)可用的資金為sk，第k階段至第3階段按最優(yōu)投資策略分配所余的資金，第k階段至第3階段所創(chuàng)造的利潤(rùn)總和。第十八頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃舉例（6）建立動(dòng)態(tài)規(guī)劃基本方程：（逆序遞推方程）（7）用逆序遞推求解動(dòng)態(tài)規(guī)劃方程。

k=3，狀態(tài)集合S3={0,1,2,3,4,5,6,7}s301234567u3000,20,2,30,2,3,40,2,3,40,2,3,40,2,3,4v3(u3)000,70,7,110,7,11,130,7,11,130,7,11,130,7,11,13f3(u3)000,70,7,110,7,11,130,6,11,130,6,11,130,6,11,13u*300234444第十九頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃舉例

k=2，狀態(tài)集合S2={0,1,2,3,4,5,6,7}

k=1時(shí)，狀態(tài)集合S1={7}s201234567u200,10,10,1,30,1,3,40,1,3,40,1,3,40,1,3,4v2(u2)00,30,30,3,90,3,9,110,3,9,110,3,9,110,3,9,11S301,02,13,2,04,3,1,05,4,2,16,5,3,27,6,4,3f300,07,011,7,013,11,0,013,13,7,013,13,11,713,13,13,11f2(u2)00,37,311,10,913,14,9,1113,16,16,1113,16,20,1813,16,20,24u*3010011334s17u10,1,2,3v1(u1)0,5,8,10S27,6,5,4f224,20,16,14f1(u1)24,25,24,24u*11請(qǐng)問(wèn)最優(yōu)投資方案是什么？采用順序算法如何求解？第二十頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例例7.2生產(chǎn)與存儲(chǔ)問(wèn)題一個(gè)工廠生產(chǎn)的某種產(chǎn)品，在一定的時(shí)期內(nèi)，增大生產(chǎn)批量，能夠降低產(chǎn)品的單位成本，但若超過(guò)市場(chǎng)的需求量，就會(huì)造成產(chǎn)品的擠壓而增加存儲(chǔ)的費(fèi)用。因此如何正確地制定生產(chǎn)計(jì)劃，使得在整個(gè)計(jì)劃期內(nèi)，生產(chǎn)和存儲(chǔ)的總費(fèi)用最小，這就是生產(chǎn)與存儲(chǔ)問(wèn)題。舉例如下：假設(shè)某廠生產(chǎn)的一種產(chǎn)品，以后四個(gè)月的訂單如下表所示。合同規(guī)定月底前交貨，生產(chǎn)每批產(chǎn)品的固定成本為3千元，每批生產(chǎn)的產(chǎn)品件數(shù)不限。每件產(chǎn)品的可變成本為1千元，每批產(chǎn)品的最大生產(chǎn)生產(chǎn)能力為5件。產(chǎn)品每月的存儲(chǔ)費(fèi)為0.5千元。設(shè)1月初有庫(kù)存產(chǎn)品1件，四月底不再留下產(chǎn)品。試在滿足需要的前提下，如何組織生產(chǎn)才能使總的成本費(fèi)用最低。第二十一頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例解按時(shí)間將問(wèn)題的過(guò)程劃分為4個(gè)階段，即k=1,2,3,4。設(shè)狀態(tài)變量sk為第k月初的庫(kù)存量；決策變量uk為第k月的生產(chǎn)量。依據(jù)題意，已知s1=1，s5=0。狀態(tài)轉(zhuǎn)移方程為：階段指標(biāo)函數(shù)v(sk,uk)為各階段的生產(chǎn)存儲(chǔ)總成本，即月份1234訂貨量bk3324第二十二頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例當(dāng)k=4時(shí)，s4的雖小可能值為0，即四月份沒(méi)有存貨，s4的最大可能值為，所以s4={0,1,2,3,4}。當(dāng)k=3時(shí)，s3=min{0,1,2,3,…,min{5×2+1-6,6}={0,1,2,3,4,5}。計(jì)算如下：s4本階段費(fèi)用s5f5(s5)d(s4,u4)+f5(s5)f4(s4)u4生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s4,u4)01234432103+43+33+23+1000.511.5276.565.52000000000076.565.5276.565.52第二十三頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

s3本階段費(fèi)用s4f4(s4)d(s3,u3)+f4(s4)f3(s3)u3生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s3,u3)023453+23+33+43+505678012376.565.51212.51313.5121123453+13+23+33+43+50.54.55.56.57.58.50123476.565.5211.51212.51310.510.5第二十四頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

s3本階段費(fèi)用s4f4(s4)d(s3,u3)+f4(s4)f3(s3)u3生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s3,u3)20123403+13+23+33+41156780123476.565.52811.51212.51083012303+13+23+31.51.55.56.57.512346.565.52811.5129.58第二十五頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

當(dāng)k=2時(shí)s3本階段費(fèi)用s4f4(s4)d(s3,u3)+f4(s4)f3(s3)u3生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s3,u3)401203+13+2226723465.52811.59850103+12.52.56.5345.5288.58第二十六頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

s2本階段費(fèi)用s3f3(s3)d(s2,u2)+f3(s3)f2(s2)u2生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s2,u2)03453+33+43+506780121210.581817.51616123453+23+33+43+50.55.56.57.58.501231210.58817.51715.516.515.5第二十七頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

s2本階段費(fèi)用s3f3(s3)d(s2,u2)+f3(s3)f2(s2)u2生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s2,u2)2123453+13+23+33+43+5156789012341210.58881716.515161715301234503+13+23+33+43+51.51.55.56.57.58.59.50123451210.5888813.51614.515.516.517.513.5第二十八頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例k=1時(shí)通過(guò)以上例子可以看出，利用動(dòng)態(tài)規(guī)劃方法求解多階段問(wèn)題，之所以減少計(jì)算量，原因之一是充分利用了前階段已計(jì)算好的結(jié)果。s1本階段費(fèi)用s2f2(s2)d(s1,u1)+f2(s2)f1(s1)u1生產(chǎn)費(fèi)用存儲(chǔ)費(fèi)用d(s1,u1)123453+23+33+43+50.55.56.57.58.501231615.51513.521.52222.52221.5第二十九頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例例7.3假定某廠在明年頭4個(gè)月對(duì)燃料的需求量以及各月的固定訂貨費(fèi)和單位存儲(chǔ)費(fèi)用如下表。如果每噸燃料的價(jià)格是800元，該廠每個(gè)月開(kāi)始時(shí)采購(gòu)，問(wèn)每月應(yīng)采購(gòu)多少，才能在保證供應(yīng)的情況下使總成本最少？月份i需求量ξi固定訂貨費(fèi)Ki單位存儲(chǔ)費(fèi)hi1234214220015010010050404040第三十頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例解設(shè)zi和ui(i=1,2,3,4)分別是月份i的訂貨量和期末存貨量，則在采用順序計(jì)算時(shí)，其基本方程是：下面按各階段分別計(jì)算如下（為了簡(jiǎn)單起見(jiàn)，金額以百元為單位）：階段1：ξ1=2，0≤u1≤1+4+2=7，見(jiàn)下表：第三十一頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例u1f1(z1|u1)=c1(z1)+0.5u1最優(yōu)值最優(yōu)解z1=23456789f1(u1)z1*012345671826.53543.55260.56977.51826.53543.55260.56977.523456789階段2：ξ2=1，0≤u2≤4+2=6，見(jiàn)下表：第三十二頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例u2f2(z2|u2)=c2(z2)+0.4u2+f2(u2+ξ2-z2)最優(yōu)值最優(yōu)解z2=01234567f2(u2)z2*01234560+26.5=25.60.4+35=35.40.8+43.5=44.31.2+52=53.21.6=60.5=62.12+69=712.4+77.5=79.99.5+18=27.59.9+26.5=36.410.3+35=45.310.7+43.5=54.211.1+52=63.111.5+60.5=7211.9+69=80.935.944.853.762.671.580.444.353.258.17179.952.761.670.379.461.17078.969.578.477.926.535.444.352.761.169.577.9000,34567第三十三頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例階段3：ξ3=4，0≤u3≤2，見(jiàn)下表：階段4：ξ4=2，u4=0，見(jiàn)下表：u3f3(z3|u3)=c3(z3)+0.4u3+f3(u3+ξ3-z3)最優(yōu)值最優(yōu)解z3=0123456f3(u3)z3*0120+61.1=61.10.4+69.5=69.90.8+77.9=78.79+52.7=61.79.4+61.1=70.59.8+69.5=79.361.370.178.960.469.778.559.568.878.167.977.276.359.567.976.3456u4f4(z4|u4)=c4(z4)+0.4u4+f3(u4+ξ4-z4)最優(yōu)值最優(yōu)解z4=012f4(u4)z4*00+76.3=76.39+67.9=76.917+59.5=76.576.30第三十四頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例例7.4資源分配問(wèn)題設(shè)某種資源，如資金、材料、機(jī)器設(shè)備、勞動(dòng)力等，可以投入n種生產(chǎn)。如果以數(shù)量為xi的資源投入第i種產(chǎn)品的生產(chǎn)，所得的效益為g（xi）(i=1,2,…,n)。問(wèn)如何分配這種資源，才能使總的經(jīng)濟(jì)效益最大。公司有資金8萬(wàn)元，投資A、B、C三個(gè)項(xiàng)目單位投資為2萬(wàn)元。每個(gè)項(xiàng)目的投資效益率與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目的投資項(xiàng)目（萬(wàn)元）與投入資金（萬(wàn)元）的關(guān)系如下表。求對(duì)三個(gè)項(xiàng)目的最有投資分配，使總投資收益最大。

ABC2萬(wàn)元4萬(wàn)元6萬(wàn)元8萬(wàn)元8910152028303535384043項(xiàng)目投入資金第三十五頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例解階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段，k=1,2,3,4。k=4為虛設(shè)的階段狀態(tài)變量sk：投資第k項(xiàng)目前的資金數(shù)決策變量uk：第k階段的投資額狀態(tài)轉(zhuǎn)移方程：sk+1=sk-uk階段指標(biāo)：vk(sk,xk)見(jiàn)上表中的數(shù)據(jù)遞推方程：fk(uk)=max{vk(sk,uk)+fk+1(sk+1)}終端條件：f4(s4)=0數(shù)學(xué)模型為：第三十六頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例k=4，終端條件f4(s4)=0。k=3，0≤u3≤s3，s4=s3-u3。第3階段表示投資項(xiàng)目A、B后再投資項(xiàng)目C，s3表示按最優(yōu)投資策略投資完A、B后將剩余資金全部投入項(xiàng)目C。k=2，0≤u2≤s2，s3=s2-u2k=1，0≤u1≤s1，s2=s1-u1，第1階段開(kāi)始投資項(xiàng)目A，有資金8萬(wàn)元，計(jì)算過(guò)程見(jiàn)下表：第三十七頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例狀態(tài)s3決策u3(s3)狀態(tài)轉(zhuǎn)移方程s4=s3-u3階段指標(biāo)v3(s3,u3)過(guò)程指標(biāo)v3(s3,u3)+f4(s4)最優(yōu)指標(biāo)f3(s3)最優(yōu)決策u*300000+0=00020200+0=0102201010+0=1040400+0=0284221010+0=10402828+0=2860600+0=0356241010+0=10422828+0=28603535+0=3580800+0=043826100+10=10442828+0=28623535+0=35804343+0=43第三十八頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例s2u2(s2)s3v2(s2,u2)f3(s3)v2(s2,u2)+f3(s3)f2(s2)u*2000000+0=0002020100+10=1010020909+0=94040280+28=28280229109+10=194020020+0=206060350+35=35372249289+28=3742201020+10=306035035+0=358080430+43=43484269359+35=4444202820+28=4862351035+10=458040040+0=40第三十九頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

最優(yōu)解為：s1=8，u1=0，s2=s1-u1=8，u2=4，s3=s2-u2=4，u3=4，s4=s3-u3=0。s1u1(s1)s2v1(s1,u12)f2(s2)v1(s1,u1)+f2(s2)f1(s1)u*18080480+48=48480268378+37=4544152815+28=4362301030+10=408038038+0=38第四十頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例例7.5某種設(shè)備可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，設(shè)在高負(fù)荷下投入生產(chǎn)的設(shè)備數(shù)量x，產(chǎn)量g=10x，設(shè)備年完好率為a=0.75；在低負(fù)荷下投入生產(chǎn)的設(shè)備數(shù)為y，產(chǎn)量為h=8y，年完好率為b=0.9。假定開(kāi)始生產(chǎn)時(shí)完好的設(shè)備數(shù)量s1=100。制定一個(gè)5年計(jì)劃，確定每年投入高低兩種負(fù)荷下生產(chǎn)的設(shè)備數(shù)量，使5年內(nèi)的總產(chǎn)量最大。解：階段k：運(yùn)行年份(k=1,2,3,4,5,6)，k=1表示第1年年初，k=6表示第5年年末(即第6年年初）狀態(tài)變量sk：第k年年初的完好機(jī)器數(shù)(k=1,2,3,4,5,6)，也是第k-1年年末完好的機(jī)器數(shù)，其中s6表示第5年年末（即第6年年初）的完好機(jī)器數(shù)，s1=100決策變量uk：第k年年初投入高負(fù)荷運(yùn)行的機(jī)器數(shù)狀態(tài)轉(zhuǎn)移方程：sk+1=0.75uk+0.9(sk-uk)第四十一頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例階段指標(biāo)：vk(sk,uk)=10uk+8(sk-uk)終端條件：f6(s6)=0遞推方程：

fk(sk)表示第k年年初分配uk臺(tái)設(shè)備用于高負(fù)荷生產(chǎn)時(shí)到第5年年末的最大產(chǎn)量。計(jì)算過(guò)程如下：第四十二頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例第四十三頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例第四十四頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例由于s1=100，5年的最大總產(chǎn)量為f1(s1)=3443.74。由x1*=x2*=x3*=0，x4*=s4，x5*=s5，設(shè)備的最優(yōu)分配策略是：第1至第3年將設(shè)備全部用于低負(fù)荷運(yùn)行，第4年和第5年將設(shè)備全部用于高負(fù)荷運(yùn)轉(zhuǎn)。每年投入高負(fù)荷的機(jī)器數(shù)及每年年初完好的機(jī)器數(shù)為：s1=100x1*=0,s2=0.75x1+0.9(s1-x1)=90x2*=0,s3=0.75x2+0.9(s2-x2)=81x3*=0,s4=0.75x3+0.9(s3-x3)=73x4*=s4=73,s5=0.75x4+0.9(s4-x4)=55x5*=s5=55,s6=0.75x5+0.9(s5-x5)=41第四十五頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例例7.6設(shè)備更新問(wèn)題

在工業(yè)和交通運(yùn)輸企業(yè)中，經(jīng)常遇到設(shè)備陳舊或部分損壞因而需要重新購(gòu)置的更新問(wèn)題。因此，每隔一個(gè)時(shí)期，就要做出一項(xiàng)決策，是繼續(xù)使用，還是把它更新。如果設(shè)備使用得太久，就必然影響生產(chǎn)效率和產(chǎn)品質(zhì)量，因而影響到利潤(rùn)。所以，在這兩者之間要做出最佳選擇。如果在一個(gè)有限時(shí)期內(nèi)考慮這類(lèi)設(shè)備問(wèn)題，就可以用動(dòng)態(tài)規(guī)劃來(lái)解決。舉例如下：

假定要考慮某種設(shè)備被在今后3年內(nèi)的更新問(wèn)題。在每年年初作出一項(xiàng)決策，是繼續(xù)使用還是更新。新的設(shè)備成本是10（單位千元，下同）。使用t年后的殘值在t≤3時(shí)是s(t)=3-t；在t>3時(shí)是零。另一方面，使用t年后每年所創(chuàng)造的利潤(rùn)在t≤3時(shí)，是p(t)=9-t2；而在t>3時(shí)，是零。問(wèn)這3年的每一年年初應(yīng)第四十六頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例如何做出決策，才能使3年內(nèi)總的利潤(rùn)達(dá)到最大？假定在第一年年初設(shè)備已使用了1年。

解：將每一年作為一個(gè)階段，共三個(gè)階段。每個(gè)階段的方案只有兩個(gè)：繼續(xù)使用和更新。相應(yīng)的數(shù)量指標(biāo)是這個(gè)階段的利潤(rùn)，如果按逆序計(jì)算，則可規(guī)定階段i(i=1,2,3)的狀態(tài)是第i年年初設(shè)備已使用的年限Ti。設(shè)階段i的最優(yōu)指標(biāo)函數(shù)是fi(Ti)，于是，基本方程是：繼續(xù)使用更新繼續(xù)使用更新第四十七頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例

化簡(jiǎn)得：

分段計(jì)算如下：階段3：見(jiàn)下表。

繼續(xù)使用更新繼續(xù)使用更新第四十八頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例T3對(duì)設(shè)備所作出的決策最優(yōu)值最優(yōu)解繼續(xù)使用更新f3(T3)決策12395-321951繼續(xù)使用繼續(xù)使用更新T2對(duì)設(shè)備所作出的決策最優(yōu)值最優(yōu)解繼續(xù)使用更新f2(T2)決策1238+5=135+1=6-1+9=100+9=9-1+9=81398繼續(xù)使用更新更新階段2：見(jiàn)下表。第四十九頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例T1對(duì)設(shè)備所作出的決策最優(yōu)值最優(yōu)解繼續(xù)使用更新f1(T1)決策18+9=171+13=1417繼續(xù)使用階段1：見(jiàn)下表。故第1年應(yīng)繼續(xù)使用，第2年應(yīng)更新，第3年繼續(xù)使用。這樣，3年的總利潤(rùn)17萬(wàn)元達(dá)到最大值。第五十頁(yè)，共六十一頁(yè)，編輯于2023年，星期四動(dòng)態(tài)規(guī)劃應(yīng)用舉例例7.7背包問(wèn)題

有一個(gè)人帶背包上山，他可帶物品重量的限度為α千克。設(shè)有n種物品可供他選擇裝入背包中，這n種物品編號(hào)為1,2…,n。已知第i種物品每件重量為ωi千克，在上山過(guò)程