運(yùn)籌學(xué)：第八章 動(dòng)態(tài)規(guī)劃

第八章動(dòng)態(tài)規(guī)劃第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型第二節(jié)一維動(dòng)態(tài)規(guī)劃求解方法第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型一、引例與動(dòng)態(tài)規(guī)劃的基本概念二、動(dòng)態(tài)規(guī)劃的原理三、動(dòng)態(tài)規(guī)劃模型的建立動(dòng)態(tài)規(guī)劃是50年初由美國(guó)數(shù)學(xué)家R.Bellman等人提出的解決多階段決策過(guò)程優(yōu)化問(wèn)題的“最優(yōu)化原理”基礎(chǔ)上建立起來(lái)的。動(dòng)態(tài)規(guī)劃是將一個(gè)較復(fù)雜的多階段決策問(wèn)題分解為若干相互關(guān)聯(lián)的較容易求解的子決策問(wèn)題，而每一個(gè)子決策問(wèn)題都有多種選擇，并且當(dāng)一個(gè)子決策問(wèn)題確定以后，將影響另一個(gè)子決策問(wèn)題，從而影響到整個(gè)問(wèn)題的決策。一、動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃模型分為（1）離散模型；（2）連續(xù)模型。本章只討論與離散模型有關(guān)的原理和方法。這對(duì)連續(xù)模型也適用。下面通過(guò)一個(gè)多階段決策過(guò)程的例子引入動(dòng)態(tài)規(guī)劃的基本概念、原理和方法。例8.1．（最短路問(wèn)題）某運(yùn)輸公司擬將一批貨物從A地運(yùn)往E地，其間的交通系統(tǒng)網(wǎng)絡(luò)如圖8-1所示。圖上節(jié)點(diǎn)表示地點(diǎn)，邊表示兩地之間的道路，邊上的數(shù)字表示兩地間的運(yùn)輸費(fèi)用，求運(yùn)輸費(fèi)用最低的運(yùn)輸路線。相關(guān)的概念:AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段5412331136444165798(1)階段將所給問(wèn)題的過(guò)程，按時(shí)間或空間特征分解成若干互相聯(lián)系的階段，按次序去求每階段的解，用字母k表示階段變量。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)第2階段的狀態(tài)第1階段541233113644416579s1狀態(tài)為A

，s2狀態(tài)？小寫(xiě)s表示狀態(tài)變量S1={A}，S2={B1、B2、B3}，S3={C1、C2、C3}，S4={D1、D2}。大寫(xiě)S表示狀態(tài)集合8(2)狀態(tài)狀態(tài)就是階段的起始位置。通常一個(gè)階段包含若干個(gè)狀態(tài)。第k階段的狀態(tài)就是該階段所有始點(diǎn)的集合。描述各階段狀態(tài)的變量稱(chēng)為狀態(tài)變量。常用sk表示第k階段的狀態(tài)變量。狀態(tài)變量的取值集合稱(chēng)為狀態(tài)集合，用Sk表示。3）決策決策是某階段狀態(tài)給定之后，從該狀態(tài)演變到下一階段某一狀態(tài)的選擇。表示決策的變量稱(chēng)為決策變量，用uk(sk)表示第k階段，狀態(tài)為sk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。實(shí)際問(wèn)題中，決策變量的選取往往受到某些條件的影響而限制于某一范圍，此范圍稱(chēng)為允許決策集合。如資金總量等。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)第2階段的狀態(tài)第1階段541233113644416579在例8.1中，u2(B1)就表示第2階段狀態(tài)為B1時(shí)的決策變量（它或等于C1或等于C3），即，從第2階段的狀態(tài)B1出發(fā)，可到達(dá)下一階段的C1或者C3，所以這一階段的允許決策集D2(B1)={C1,C3}。84）策略各階段決策確定后，組成的一個(gè)有序的決策序列就構(gòu)成了一個(gè)策略。稱(chēng)為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略。稱(chēng)為由第k階段開(kāi)始到最后階段止的一個(gè)子策略，簡(jiǎn)稱(chēng)后部子策略。使整個(gè)問(wèn)題到達(dá)最優(yōu)效果的策略稱(chēng)為最優(yōu)策略。

動(dòng)態(tài)規(guī)劃方法就是要從允許策略集中找出最優(yōu)策略！AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)第2階段的狀態(tài)第1階段541233113644416579pA,E{A,B2,C3,D2,E}就是一個(gè)策略（全過(guò)程策略）。8pB2,E{B2,C3,D2,E}就是一個(gè)子策略。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)第2階段的狀態(tài)第1階段541233113644416579此題的狀態(tài)轉(zhuǎn)移方程為sk+1=uk(sk)，即第k階段的決策將決定第k+1階段的狀態(tài)！85）狀態(tài)轉(zhuǎn)移方程它是確定過(guò)程由某一階段的一個(gè)狀態(tài)到下一階段另一狀態(tài)的演變過(guò)程，用sk+1=Tk(sk,uk)表示。該方程描述了由第k階段到第k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律。因此又稱(chēng)其為狀態(tài)轉(zhuǎn)移函數(shù)。

指標(biāo)函數(shù)是用來(lái)衡量多階段決策過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)。

一個(gè)n階段決策過(guò)程，從1到n稱(chēng)為問(wèn)題的原過(guò)程，對(duì)于任意一個(gè)給定的k（1≤k≤n），從第k階段到第n階段的過(guò)程稱(chēng)為原過(guò)程的一個(gè)后部子過(guò)程。用V1,n(s1,p1,n)表示初始狀態(tài)為s1，采用策略p1,n時(shí)，原過(guò)程的指標(biāo)函數(shù)值。

Vk,n(sk,pk,n)表示在第k

階段，狀態(tài)為sk，采用策略pk,n時(shí)，后部子過(guò)程的指標(biāo)函數(shù)值。從第k階段狀態(tài)sk，采用最優(yōu)策略p*k,n到過(guò)程終止時(shí)的最佳效益值，稱(chēng)為最優(yōu)指標(biāo)函數(shù)。記為fk(sk)。6）指標(biāo)函數(shù)

AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)第2階段的狀態(tài)第1階段541233113644416579V2,4(B1)：表示在第2階段，狀態(tài)為B1時(shí)，從B1到E的距離。f2(B1)則表示從B1到E的最短距離。8二、動(dòng)態(tài)規(guī)劃的原理在例8.1中，整個(gè)運(yùn)輸路程分為四個(gè)階段，見(jiàn)圖8.2。下面給出求解的全過(guò)程。這里我們采用倒推的方法，即從終點(diǎn)（E）到起點(diǎn)（A）。1．第4階段，即從E到D，從E出發(fā)倒推到下一站D，它可通過(guò)D1，也可通過(guò)D2，所需費(fèi)用分別為5和3。如果現(xiàn)處于狀態(tài)D1，到終點(diǎn)E的最佳路線費(fèi)用：f4(D1)=5，最優(yōu)策略：u4(D1)=E。如果現(xiàn)處于狀態(tài)D2，到終點(diǎn)E的最佳路線費(fèi)用：f4(D2)=3，最優(yōu)策略：u4(D2)=E。第3階段，當(dāng)從E到達(dá)D后，有兩個(gè)狀態(tài)D1和D2；

若處于狀態(tài)D1，則可到達(dá)C1或C2，則費(fèi)用分別為9或7。若處于狀態(tài)D2，則可到達(dá)C1或C2或C3，費(fèi)用分別為8或12或5。從E經(jīng)D1到達(dá)C1或C2

的費(fèi)用，應(yīng)加上E到達(dá)D1這段的費(fèi)用，所以費(fèi)用分別為5+9=14、5+7=12；從E經(jīng)D2到達(dá)C2或C2或C3

的費(fèi)用，應(yīng)加上E到達(dá)D2這段的費(fèi)用，所以費(fèi)用分別為3+8=11、3+12=15、3+5=8。如果現(xiàn)在處于C1，則到達(dá)終點(diǎn)E的最小費(fèi)用為：

最小費(fèi)用路線為相應(yīng)的最優(yōu)決策u3(C1)=D2。如果現(xiàn)在處于C2，則到達(dá)終點(diǎn)E的最小費(fèi)用為：

最小費(fèi)用路線為。相應(yīng)的最優(yōu)決策:如果現(xiàn)在處于C3，到達(dá)終點(diǎn)E的最小費(fèi)用為：

最小費(fèi)用路線為相應(yīng)的最優(yōu)決策3．第2階段，同上。如果現(xiàn)處于B1，到達(dá)終點(diǎn)E的最小費(fèi)用為：

最小費(fèi)用路線為相應(yīng)的最優(yōu)決策如果現(xiàn)處于B2，則到達(dá)終點(diǎn)E的最小費(fèi)用為：

最小費(fèi)用路線為相應(yīng)的最優(yōu)決策如果現(xiàn)處于B3，則到達(dá)終點(diǎn)E的最小費(fèi)用為：

最小費(fèi)用路線為相應(yīng)的最優(yōu)決策4．在第1階段A處，則到達(dá)終點(diǎn)E的最小費(fèi)用為：最小費(fèi)用路線為：相應(yīng)的最優(yōu)決策：所以，整個(gè)問(wèn)題的最小費(fèi)用路線為：最優(yōu)策略為：{，，，}。在每一階段的求解，都利用了第k階段和第k+1階段的如下關(guān)系：這種關(guān)系稱(chēng)為動(dòng)態(tài)規(guī)劃的基本方程。所謂最優(yōu)化原理是：（過(guò)去管不了，未來(lái)更美好）一個(gè)過(guò)程的最優(yōu)決策具有這樣的性質(zhì)：無(wú)論初始狀態(tài)及初始決策如何，對(duì)于先前決策所形成的狀態(tài)而言，其以后的所有決策應(yīng)構(gòu)成最優(yōu)策略。例8.1動(dòng)態(tài)規(guī)劃（最短路問(wèn)題）的圖解法（逆推）：天府廣場(chǎng)溫江邛崍崇州西嶺雪山大門(mén)0161214128123511解得最短路線為：A→B1→C3→D2→E，總長(zhǎng)16若將例8.1改為求最大利潤(rùn)動(dòng)態(tài)規(guī)劃的圖解法（逆推）：天府廣場(chǎng)溫江邛崍崇州西嶺雪山大門(mén)0261519178153514解得最優(yōu)路線為：A→B3→C1→D1→E，總利潤(rùn)26三、動(dòng)態(tài)規(guī)劃模型的建立用動(dòng)態(tài)規(guī)劃解決實(shí)際問(wèn)題，就要建立動(dòng)態(tài)規(guī)劃模型，為此需要解決如下問(wèn)題：1.劃分階段2.確定狀態(tài)變量和決策變量以及相應(yīng)的取值范圍3.建立狀態(tài)轉(zhuǎn)移方程4.確定指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃的基本方程5.確定邊界條件1.劃分階段按照時(shí)間、空間、變量劃分為若干階段。建立動(dòng)態(tài)規(guī)劃模型要求每個(gè)階段問(wèn)題具有同一模式。2.確定狀態(tài)變量和決策變量以及相應(yīng)的取值范圍決策過(guò)程可用狀態(tài)演變描述。狀態(tài)必須包含表示系統(tǒng)情況和確定決策所需要的全部信息，反映過(guò)程的演變特征。無(wú)后效性。找出狀態(tài)變量在各階段的取值范圍。決策變量由系統(tǒng)最優(yōu)化的目的所決定。3.建立狀態(tài)轉(zhuǎn)移方程根據(jù)狀態(tài)變量和決策變量的含義，寫(xiě)出狀態(tài)轉(zhuǎn)移方程。4.確定指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃的基本方程選取指標(biāo)函數(shù)，根據(jù)指標(biāo)函數(shù)建立最優(yōu)指標(biāo)函數(shù)遞推關(guān)系,即基本方程求距離、費(fèi)用時(shí)，min5.確定邊界條件求利潤(rùn)、產(chǎn)值時(shí)，max

增加研制費(fèi)：萬(wàn)元新產(chǎn)品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70例8.2.有一工廠研制甲、乙、丙三種新產(chǎn)品，估計(jì)這三種新產(chǎn)品研制成功的概率分別為：0.6、0.4、0.3。由于工廠急于推出新產(chǎn)品，決定再加撥2萬(wàn)元研制費(fèi)，以提高新產(chǎn)品研制成功的概率。據(jù)估計(jì)，把增加的研制費(fèi)用于各種新產(chǎn)品研制時(shí)，研制成功的概率見(jiàn)下表?，F(xiàn)把這批研制費(fèi)分配給各新產(chǎn)品（不分配、分配給1萬(wàn)元或分配給2萬(wàn)元），使這三種新產(chǎn)品都研制成功的概率最大。應(yīng)怎樣分配。劃分階段把對(duì)某一種新產(chǎn)品增加研制費(fèi)用作為一個(gè)階段，將整個(gè)過(guò)程分為三個(gè)階段。對(duì)甲產(chǎn)品增加研制費(fèi)用記為第1階段、對(duì)乙產(chǎn)品增加研制費(fèi)用記為第2階段、對(duì)丙產(chǎn)品增加研制費(fèi)用記為第3階段。K=1,2,3。狀態(tài)變量把有可能提供的研制費(fèi)用作為狀態(tài)變量，記為sk，它的取值范圍是：0、1、2決策變量把給第k種新產(chǎn)品的研制費(fèi)用的數(shù)量作為決策變量uk，它由決策者決定，不能超過(guò)當(dāng)時(shí)擁有的金額sk建立狀態(tài)轉(zhuǎn)移方程sk+1=sk-uk

確定指標(biāo)函數(shù)

確定邊界條件由于開(kāi)始時(shí)可用的金額為2萬(wàn)元，而最后將全部用完，所以s1=2，s4=0第二節(jié)一維動(dòng)態(tài)規(guī)劃求解方法一、逆推法二、順推法逆推法是從最后一個(gè)階段開(kāi)始，逐階段向前，直至第一階段，即可求出全過(guò)程最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。例8.3．用逆推法求解例8.2。

一、逆推法

增加研制費(fèi)（萬(wàn)元）uk各階段狀態(tài)sk（可提供的資金）、決策變量uk的取值第一階段第二階段第三階段012uk=sk-sk+1s1=0s1=1s1=2u1=s1-s2s2=0s2=1s2=2u2=s2-s3s3=0s3=1s3=2u3=s3-s4,s4=0

增加研制費(fèi)（萬(wàn)元）新產(chǎn)品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70第三階段

s3=0

s3=1

s3=2第二階段

s2=0

s2=1

s2=2第一階段只有S1=2s2=s1-0=2s3=s2-1=1最優(yōu)解0-1-1

從最后一個(gè)階段開(kāi)始，逐階段向前，直至第一階段，即可求出全過(guò)程最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。

二、順推法逆推法是從最后一個(gè)階段開(kāi)始，逐階段向前，直至第一階段，即可求出全過(guò)程最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。如果過(guò)程是可逆的，即對(duì)每一狀態(tài)，都可從狀態(tài)轉(zhuǎn)移方程得到，則可用順推法，由第一階段開(kāi)始，逐階段向后，直至最后一個(gè)階段。

下面再用順推法求解例8.2。

例8.4．用順推法求解例8.2基本方程為：

第1階段：最優(yōu)策略是：第2階段：最優(yōu)策略是：第3階段：最優(yōu)策略是：第2階段：

最優(yōu)策略是：最優(yōu)策略是：最優(yōu)策略是：第3階段：

最優(yōu)策略是：故，最優(yōu)策略是：一維動(dòng)態(tài)規(guī)劃求解方法——

順推法s3=s4+1=1s2=s3+1=2最優(yōu)解0-1-1

由第一階段開(kāi)始，逐階段向后，直至最后一個(gè)階段，同樣可求出最優(yōu)策略和指標(biāo)函數(shù)的最優(yōu)值。第一階段

s2=0

s2=1

s2=2第二階段

s3=0s3=1

s3=2第三階段第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用一、背包問(wèn)題二、生產(chǎn)計(jì)劃問(wèn)題三、貨物存儲(chǔ)問(wèn)題四、設(shè)備更新問(wèn)題五、資源分配問(wèn)題六、復(fù)合系統(tǒng)可靠性問(wèn)題一、背包問(wèn)題第一階段：只裝第一種物品允許裝入前1種物品的總重量s2

允許裝入前2種物品的總重量s3

第二階段：只裝第二種物品該段可裝入x1w1該段可裝入x2w2s2=s3-x1w1價(jià)值：p1(x1)+p2(x2)+…一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現(xiàn)有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi

千克，其價(jià)值是攜帶數(shù)量xi

的函數(shù)pi(xi)。問(wèn)旅行者應(yīng)如何選擇攜帶物品的件數(shù)，使總價(jià)值最大？劃分階段將可裝入物品按1,2,…,n排序，每段裝一種物品，共劃分為n個(gè)階段，k=1,2,……,n.狀態(tài)變量在第k階段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量，記為sk+1決策變量裝入第k種物品的件數(shù)，記為xk建立狀態(tài)轉(zhuǎn)移方程sk=sk+1-wkxk允許決策集合

確定指標(biāo)函數(shù)

fk(sk+1)表示在背包中允許裝入物品的總重量不超過(guò)sk+1千克，并采用最優(yōu)策略只裝前k種物品時(shí)的最大使用價(jià)值。確定邊界條件背包所能承受的重量為w千克貨物種類(lèi)k單件重量wk單件價(jià)值ck123132308065例8.5：有一最大載重量為5噸的船，將裝載3種貨物，每種貨物的單件重量和單件價(jià)值見(jiàn)表，怎樣裝載才能使裝載的總價(jià)值最大？設(shè)第k種貨物裝載的件數(shù)為xk(k=1,2,3)，劃分為3個(gè)階段，每一階段裝一種物品。Sk+1表示在第k階段開(kāi)始時(shí)，允許裝入前k種物品的總重量。則

sk=sk+1-wkxk0123450010120123012340123450306090120150012345K=1貨物種類(lèi)k單件重量wk單件價(jià)值ck12313230806501234500001010103060900120301506003060901201500000000123450010120123012340123450306090120150012345K=20123450000101010306090012030150600306090120150000000K=3

s4=5X*3=2所以最優(yōu)策略是：第1種貨物裝載1件，第2種貨物不裝，第3種貨物裝載2件。最優(yōu)價(jià)值是

s4=5S2012345f1(s2)0306090120150x1*012345s3012345f2(s3)0306090120150x2*000000二、生產(chǎn)計(jì)劃問(wèn)題

已知企業(yè)產(chǎn)品的生產(chǎn)費(fèi)用、存儲(chǔ)費(fèi)用和市場(chǎng)的需求量，在其生產(chǎn)能力和存儲(chǔ)能力許可的前提下，怎樣制定各個(gè)時(shí)期的生產(chǎn)計(jì)劃，既能完成交貨任務(wù)，又使總支出最小。某中轉(zhuǎn)倉(cāng)庫(kù)要按月在月初供應(yīng)一定數(shù)量的某種部件給總裝車(chē)間，由于生產(chǎn)條件的變化，生產(chǎn)車(chē)間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用。已知總裝車(chē)間的各個(gè)月份的需求量以及在加工車(chē)間生產(chǎn)該部件每單位數(shù)量所需工時(shí)見(jiàn)表設(shè)倉(cāng)庫(kù)容量為H=9，開(kāi)始庫(kù)存量為2，最終庫(kù)存量為0，要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既滿足需要和倉(cāng)庫(kù)容量的限制，又使生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)最少。月份K0123456需求量dk0853274單位工時(shí)ak111813172010第k月庫(kù)存量為sk生產(chǎn)量為uk庫(kù)存量為sk+1需求量為dksk+1=sk+uk-dk當(dāng)月生產(chǎn)當(dāng)月入庫(kù)sk為第k月需求送出之前，上階段產(chǎn)品送入之后劃分階段

按月份劃分階段，每個(gè)月為一個(gè)階段，k=1,2,……,6.狀態(tài)變量

第k階段開(kāi)始時(shí)（即本階段需求送出之前，上階段產(chǎn)品送入之后）部件庫(kù)存量，記為sk決策變量

第k階段內(nèi)的部件生產(chǎn)量，記為uk建立狀態(tài)轉(zhuǎn)移方程

sk+1=sk+uk-dk，最優(yōu)指標(biāo)函數(shù)

fk(sk)表示在第k階段開(kāi)始的庫(kù)存量為sk時(shí)，從第k階段到最后一階段生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)?；痉匠?/p>

確定邊界條件

so=開(kāi)始庫(kù)存量2，s7=0，u6=0K=6K=5最優(yōu)決策為：

最小累計(jì)工時(shí)數(shù)為：

K=4第4階段的最優(yōu)決策為：

最小累計(jì)工時(shí)數(shù)為：

sk+1=sk+uk-dk,so=2，s7=0，u6=0第6階段不生產(chǎn)，故u6=0K=3u3的允許集合：

K=2sk+1=sk+uk-dk,u>0,s<9d4=2,d3=3K=1sk+1=sk+uk-dkK=0故各月最優(yōu)生產(chǎn)計(jì)劃為：7，4，9，3，0，4。

sk+1=sk+uk-dkd1=8,H=9,s0=2三、貨物存儲(chǔ)問(wèn)題例8.7．考慮下面三個(gè)月的庫(kù)存問(wèn)題，在每月初，公司必須決定在本月內(nèi)，應(yīng)生產(chǎn)多少產(chǎn)品。在一個(gè)月內(nèi)生產(chǎn)x

單位的產(chǎn)品，所需成本為，其中，當(dāng)時(shí)，。每月最多生產(chǎn)4個(gè)單位，每月的需求是隨機(jī)的，或?yàn)?或?yàn)?單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫(kù)存。每個(gè)月末檢查庫(kù)存，1個(gè)單位的庫(kù)存費(fèi)用是1元。因?yàn)閹?kù)存能力有限，每月末的庫(kù)存量不能超過(guò)3單位。但同時(shí)要求必須及時(shí)滿足需求。在第3個(gè)月末要把現(xiàn)有的庫(kù)存以每單位2元的價(jià)格售出。在第1月的月初，公司有1單位的庫(kù)存。如何制定生產(chǎn)策略使三個(gè)月內(nèi)的期望費(fèi)用最小。解：劃分階段：將三個(gè)月份為三個(gè)階段，每個(gè)月為一個(gè)階段狀態(tài)變量：sk表示第k個(gè)月初的庫(kù)存數(shù)。則s1=1。決策變量：xk表示第k月生產(chǎn)的單位數(shù)。顯然有狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xk-ak，其中ak為一隨機(jī)需求量或?yàn)?或?yàn)?。fk(sk)表示第k個(gè)月初的庫(kù)存是sk時(shí)，第k個(gè)月至第3個(gè)月內(nèi)的最小期望費(fèi)用。則第3個(gè)月的期望費(fèi)用是：其中當(dāng)k=1，2時(shí)，有動(dòng)態(tài)規(guī)劃的基本方程：其中用逆序法求解得最優(yōu)策略是即第一個(gè)月生產(chǎn)3個(gè)單位，第二、第三個(gè)月不生產(chǎn)。最小成本是元。四、設(shè)備更新問(wèn)題現(xiàn)有一臺(tái)效益函數(shù)為r(t)的設(shè)備，其維修費(fèi)用為u(t)、更新費(fèi)用為c(t)，需要在n年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更換一臺(tái)新設(shè)備，使n年總效益最大。設(shè)r(t)：在第k年設(shè)備已使用過(guò)t年，再使用1年時(shí)的效益。uk(t)：在第k年設(shè)備已使用過(guò)t年，再使用1年時(shí)的維修費(fèi)用。ck(t)：在第k年賣(mài)掉一臺(tái)已使用t年的設(shè)備，買(mǎi)進(jìn)一臺(tái)新設(shè)備的更新凈費(fèi)用。a：折扣因子（0≤a≤

1），表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)年的a單位。如果年初決定把使用t年的舊設(shè)備再繼續(xù)使用1年，則在這一年內(nèi)所得回收額為：如果年初決定把使用t年的舊設(shè)備賣(mài)掉購(gòu)買(mǎi)一臺(tái)新設(shè)備，則在這一年內(nèi)所得回收額為：建立動(dòng)態(tài)規(guī)劃模型劃分階段：k（k=1,…,n）表示計(jì)劃使用該設(shè)備的年限數(shù)。狀態(tài)變量sk：第k年初，設(shè)備已使用過(guò)的年數(shù)。決策變量xk：第k年初更新，還是繼續(xù)使用舊設(shè)備，分別用R和K表示。狀態(tài)轉(zhuǎn)移方程為：動(dòng)態(tài)規(guī)劃的基本方程為：五、資源分配問(wèn)題設(shè)有一原料，總量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其產(chǎn)生的效益為ri(xi)。問(wèn)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？建立動(dòng)態(tài)規(guī)劃劃分階段：將n

種產(chǎn)品按的序號(hào)排列，每種產(chǎn)品為一個(gè)階段，分為n個(gè)階段，k=1,…,n。狀態(tài)變量：sk表示分配給第k個(gè)產(chǎn)品至第n

種產(chǎn)品的資源數(shù)。決策變量：xk表示分配給第k個(gè)產(chǎn)品的資源數(shù)。狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xkfk(sk)表示在擁有資源sk，分配給第k種產(chǎn)品至第n

種產(chǎn)品所得到的最大總收入。則有動(dòng)態(tài)規(guī)劃的基本方程：邊界條件：因?yàn)樵诘?階段時(shí)的資源為總資源，到第n+1階段時(shí)資源已分配完畢，所以s1=a，sn+1=0，fn+1(sn+1)=0。六、復(fù)合系統(tǒng)可靠性問(wèn)題例8.9．某廠設(shè)計(jì)一種電子設(shè)備，由三種元件D1，D2，D3組成，已知這三種元件的價(jià)格和可靠性如表8-8所示。要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過(guò)105元，試問(wèn)應(yīng)如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大(不考慮重量的限制)。表8-8解：按元件種類(lèi)劃分為三個(gè)階段，設(shè)狀態(tài)變量sk(k=1,2,3)表示能容許用在Dk元件至D3元件的總費(fèi)用；決策變量xk表示在Dk元件上的并聯(lián)個(gè)數(shù)；Pk表示一個(gè)元件正常工作的概率，則為xk個(gè)Dk元件不正常工作的概率，令最優(yōu)值函數(shù)fk(sk)表示由狀態(tài)sk開(kāi)始從Dk元件至D3元件組成的系統(tǒng)的最大可靠性，因而有由于s1=105，故此問(wèn)題求只要出f1(105)即可.同理從而求得最優(yōu)方案：，即D1元件用1個(gè)，D2元件用2個(gè)，D3元件用2個(gè)，其總費(fèi)用為100元，可靠性為0.648。第四節(jié)Lingo軟件對(duì)幾類(lèi)特殊動(dòng)態(tài)規(guī)劃問(wèn)題的實(shí)現(xiàn)略不確定性單目標(biāo)決策：當(dāng)某決策者針對(duì)一件事情有多個(gè)方案可供選擇，而每個(gè)方案在面對(duì)未來(lái)的多個(gè)狀態(tài)都有不同的收益時(shí)，就需要作出決策，到底選擇哪一個(gè)方案？！決策準(zhǔn)則，即決策者選擇最優(yōu)方案的標(biāo)準(zhǔn)，有以下幾種：樂(lè)觀主義決策準(zhǔn)則悲觀主義決策準(zhǔn)則