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

一、多階段決策問題 (Multi-Stagedecisionprocess)多階段決策過(guò)程特點(diǎn):狀態(tài)

s1階段1T1決策u1狀態(tài)

s2決策u2階段2T2狀態(tài)

s3...狀態(tài)

sk決策uk階段kTk狀態(tài)

sk+1...狀態(tài)

sn決策un階段nTn狀態(tài)

sn+11.多階段決策過(guò)程的最優(yōu)化11.多階段決策過(guò)程的最優(yōu)化

二、動(dòng)態(tài)規(guī)劃求解的多階段決策問題的特點(diǎn)通常多階段決策過(guò)程的發(fā)展是通過(guò)狀態(tài)的一系列變換來(lái)實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過(guò)去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問題的求解就比較困難復(fù)雜。而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無(wú)后效性”的多階段決策過(guò)程。所謂無(wú)后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無(wú)關(guān)。2例l

設(shè)從A到E鋪設(shè)輸油管道,中間經(jīng)過(guò)三個(gè)站。

AB1EB2B3C1C2C3C4D1D2435547653522256321735(3)(5)(5)(8)(5)(12)(10)(7)(12)(10)1.多階段決策過(guò)程的最優(yōu)化

動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個(gè)比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過(guò)程分為兩個(gè)階段，先按整體最優(yōu)的思想逆序地求出各個(gè)子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個(gè)問題的最優(yōu)策略和最優(yōu)路線。計(jì)算過(guò)程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。4

1.動(dòng)態(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合sk

Xk②

決策變量及其允許集合ukUk

③

狀態(tài)轉(zhuǎn)移方程

sk+1=Tk

(sk,uk

)④

階段效應(yīng)dk

(sk,uk

)

5

2.動(dòng)態(tài)規(guī)劃基本方程

fn+1(sn+1)=0(邊界條件)

fk(sk)=opt

u{dk

(sk,uk

)+fk+1(sk+1)}

k=n,…,16

2.動(dòng)態(tài)規(guī)劃的基本概念

(一)階段和階段變量為了便于求解和表示決策及過(guò)程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問題，通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數(shù)等于多段決策過(guò)程從開始到結(jié)束所需作出決策的數(shù)目。7

2.動(dòng)態(tài)規(guī)劃的基本概念

（二）狀態(tài)、狀態(tài)變量和可能狀態(tài)集

1.狀態(tài)與狀態(tài)變量。用以描述事物(或系統(tǒng))在某特定的時(shí)間與空間域中所處位置及運(yùn)動(dòng)特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。按照過(guò)程進(jìn)行的先后，每個(gè)階段的狀態(tài)可分為初始狀態(tài)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。但為了清楚起見，通常定義階段的狀態(tài)即指其初始狀態(tài)。8

2.動(dòng)態(tài)規(guī)劃的基本概念

2．可能狀態(tài)集一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達(dá)狀態(tài)集?？赡軤顟B(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定．在圖5—1所示的最短路問題中，第一階段狀態(tài)為v1，狀態(tài)變量s1的狀態(tài)集合S1={v1}；第二階段則有三個(gè)狀態(tài)：v2,v3,v4

,狀態(tài)變量s2的狀態(tài)集合S2={v2,v3,v4}

；第三階段也有三個(gè)狀態(tài):v5,v6,v7

，狀態(tài)變量s3的狀態(tài)集合S3={v5,v6,v7}

；第四階段則有二個(gè)狀態(tài)：v8,v9,狀態(tài)變量s4的狀態(tài)集合S4={v8,v9}

；9（三）決策、決策變量和允許決策集合所謂決策，就是確定系統(tǒng)過(guò)程發(fā)展的方案。決策的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對(duì)下一階段狀態(tài)作出的選擇。用以描述決策變化的量稱之決策變量。和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來(lái)描述，也可以是狀態(tài)變量的函數(shù)，記以u(píng)k=uk(sk)，表示于階段k狀態(tài)sk時(shí)的決策變量。決策變量的取值往往也有一定的允許范圍，稱之允許決策集合。決策變量uk(sk)的允許決策集用Uk(sk)表示,uk(sk)∈Uk(sk)允許決策集合實(shí)際是決策的約束條件。

2.動(dòng)態(tài)規(guī)劃的基本概念

10

（四）、策略和允許策略集合策略(Policy)也叫決策序列．策略有全過(guò)程策略和k部子策略之分，全過(guò)程策略是指具有n個(gè)階段的全部過(guò)程，由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列，簡(jiǎn)稱策略，表示為p1,n{u1,u2,…,un}。從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略,表示為pk,n{uk,uk+1,…,un}，顯然當(dāng)k=1時(shí)的k部子策略就是全過(guò)程策略。在實(shí)際問題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n

，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。

2.動(dòng)態(tài)規(guī)劃的基本概念

11（五）狀態(tài)轉(zhuǎn)移方程系統(tǒng)在階段k處于狀態(tài)sk，執(zhí)行決策uk(sk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即系統(tǒng)由階段k的初始狀態(tài)sk轉(zhuǎn)移到終止?fàn)顟B(tài)sk+1

，或者說(shuō)，系統(tǒng)由k階段的狀態(tài)sk轉(zhuǎn)移到了階段k+1的狀態(tài)sk+1

，多階段決策過(guò)程的發(fā)展就是用階段狀態(tài)的相繼演變來(lái)描述的。對(duì)于具有無(wú)后效性的多階段決策過(guò)程,系統(tǒng)由階段k到階段k+1的狀態(tài)轉(zhuǎn)移完全由階段k的狀態(tài)sk和決策uk(sk)所確定，與系統(tǒng)過(guò)去的狀態(tài)s1,s2,…,sk-1及其決策u1(s1),u2(s2)…uk-1(sk-1)無(wú)關(guān)。系統(tǒng)狀態(tài)的這種轉(zhuǎn)移，用數(shù)學(xué)公式描述即有：

2.動(dòng)態(tài)規(guī)劃的基本概念

(5-1)12通常稱式(5-1)為多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程。有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。

(六)指標(biāo)函數(shù)用來(lái)衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過(guò)程或各子過(guò)程或各階段上的確定數(shù)量函數(shù)。對(duì)不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。例如：圖5—1的指標(biāo)就是運(yùn)費(fèi)。

2.動(dòng)態(tài)規(guī)劃的基本概念

13

(1)階段指標(biāo)函數(shù)（也稱階段效應(yīng)）。用dk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時(shí)的指標(biāo)，則它就是第k段指標(biāo)函數(shù)，簡(jiǎn)記為dk

。圖5-1的dk值就是從狀態(tài)sk到狀態(tài)sk+1的距離。譬如，dk(v2,v5)=3,即v2到v5的距離為3。

(2)過(guò)程指標(biāo)函數(shù)（也稱目標(biāo)函數(shù)）。用Vk,n(sk,uk)表示第k子過(guò)程的指標(biāo)函數(shù)。如圖5-1的Vk,n(sk,uk)表示處于第k段sk狀態(tài)且所作決策為uk時(shí)，從sk點(diǎn)到終點(diǎn)v10的距離。由此可見，Vk,n(sk,uk)不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過(guò)程策略u(píng)k(sk)有關(guān)，因此它是sk和uk(sk)的函數(shù)，嚴(yán)格說(shuō)來(lái)，應(yīng)表示為:

2.動(dòng)態(tài)規(guī)劃的基本概念

14不過(guò)實(shí)際應(yīng)用中往往表示為Vk,n(sk,uk)或Vk,n(sk)。還跟第k子過(guò)程上各段指標(biāo)函數(shù)有關(guān)，過(guò)程指標(biāo)函數(shù)Vk(sk)通常是描述所實(shí)現(xiàn)的全過(guò)程或k后部子過(guò)程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)dk(sk,uk)累積形成的，適于用動(dòng)態(tài)規(guī)劃求解的問題的過(guò)程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式．對(duì)于部子過(guò)程的指標(biāo)函數(shù)可以表示為：式中，表示某種運(yùn)算，可以是加、減、乘、除、開方等。

2.動(dòng)態(tài)規(guī)劃的基本概念

(5-2)15多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:

(5-3)

有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如：

(5-4)

總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。

2.動(dòng)態(tài)規(guī)劃的基本概念

16

(七)最優(yōu)解用fk(sk)表示第k子過(guò)程指標(biāo)函數(shù)在狀態(tài)sk下的最優(yōu)值,即

稱fk(sk)為第k子過(guò)程上的最優(yōu)指標(biāo)函數(shù)；與它相應(yīng)的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構(gòu)成該子策賂的各段決策稱為該過(guò)程上的最優(yōu)決策，為；有簡(jiǎn)記為

2.動(dòng)態(tài)規(guī)劃的基本概念

17特別當(dāng)k=1且s1取值唯一時(shí)，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。如例只有唯一始點(diǎn)v1即s1取值唯一,故f1(s1)=18就是例的最優(yōu)值，而就是例的最優(yōu)策略。但若取值不唯一,則問題的最優(yōu)值記為f0有

最優(yōu)策略即為s1=s1*狀態(tài)下的最優(yōu)策略：

我們把最優(yōu)策略和最優(yōu)值統(tǒng)稱為問題的最優(yōu)解。

2.動(dòng)態(tài)規(guī)劃的基本概念18按上述定義，所謂最優(yōu)決策是指它們?cè)谌^(guò)程上整體最優(yōu)(即所構(gòu)成的全過(guò)程策略為最優(yōu))，而不一定在各階段上單獨(dú)最優(yōu)。

(八)多階段決策問題的數(shù)學(xué)模型綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無(wú)后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:

2.動(dòng)態(tài)規(guī)劃的基本概念

（5-5）19式中“OPT”表示最優(yōu)化，視具體問題取max或min。

上述數(shù)學(xué)模型說(shuō)明了對(duì)于給定的多階段決策過(guò)程，求取一個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策序列，使之既滿足式(5-5)給出的全部約束條件，又使式(5-5)所示的目標(biāo)函數(shù)取得極值，并且同時(shí)指出執(zhí)行該最優(yōu)策略時(shí)，過(guò)程狀態(tài)演變序列即最優(yōu)路線

2.動(dòng)態(tài)規(guī)劃的基本概念20二、動(dòng)態(tài)規(guī)劃的最優(yōu)化原理與基本方程

1．標(biāo)號(hào)法為進(jìn)一步闡明動(dòng)態(tài)規(guī)劃方法的基本思路，我們介紹一種只適用于例這類最優(yōu)路線問題的特殊解法——標(biāo)號(hào)法。標(biāo)號(hào)法是借助網(wǎng)絡(luò)圖通過(guò)分段標(biāo)號(hào)來(lái)求出最優(yōu)路線的一種簡(jiǎn)便、直觀的方法。通常標(biāo)號(hào)法采取“逆序求解”的方法來(lái)尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。

2.動(dòng)態(tài)規(guī)劃的基本原理

21下面給出標(biāo)號(hào)法的一般步驟：

1.從最后一段標(biāo)起，該段各狀態(tài)(即各始點(diǎn))到終點(diǎn)的距離用數(shù)字分別標(biāo)在各點(diǎn)上方的方格內(nèi)，并用粗箭線連接各點(diǎn)和終點(diǎn)。

2.向前遞推，給前一階段的各個(gè)狀態(tài)標(biāo)號(hào)。每個(gè)狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點(diǎn)的最短距離。即為該狀態(tài)到該階段已標(biāo)號(hào)的各終點(diǎn)的段長(zhǎng)，再分別加上對(duì)應(yīng)終點(diǎn)上方的數(shù)字而取其最小者。將剛標(biāo)號(hào)的點(diǎn)沿著最短距離所對(duì)應(yīng)的已標(biāo)號(hào)的點(diǎn)用粗箭線連接起來(lái)，表示出各剛標(biāo)號(hào)的點(diǎn)到終點(diǎn)的最短路線。

2.動(dòng)態(tài)規(guī)劃的基本原理22

3.逐次向前遞推，直到將第一階段的狀態(tài)(即起點(diǎn))也標(biāo)號(hào)，起點(diǎn)方格內(nèi)的數(shù)字就是起點(diǎn)到終點(diǎn)的最短距離，從起點(diǎn)開始連接終點(diǎn)的粗箭線就是最短路線。

2.動(dòng)態(tài)規(guī)劃的基本原理23例l

設(shè)從A到E鋪設(shè)輸油管道,中間經(jīng)過(guò)三個(gè)站。

AB1EB2B3C1C2C3C4D1D2435547653522256321735(3)(5)(5)(8)(5)(12)(10)(7)(12)(10)最短路問題的特性:如果最短路通過(guò)點(diǎn)p，則這條路線從p至終點(diǎn)的部分，對(duì)于從p至終點(diǎn)的所有路線（稱為p的后部路線）而言，必定也是最短的路線。

2．最優(yōu)化原理（貝爾曼最優(yōu)化原理）作為一個(gè)全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過(guò)程中的任意狀態(tài)而言，無(wú)論其過(guò)去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過(guò)程最優(yōu)策略為：

2.動(dòng)態(tài)規(guī)劃的基本原理則對(duì)上述策略中所隱含的任一狀態(tài)而言，第k子過(guò)程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過(guò)程最優(yōu)策略p1*中，即為25如第一節(jié)所述，基于上述原理，提出了一種逆序遞推法；這里可以指出，該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的函數(shù)基本方程。

3.函數(shù)基本方程在例中，用標(biāo)號(hào)法求解最短路線的計(jì)算公式可以概括寫成：(5-6)

其中，在這里表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離,是邊界條件，表示全過(guò)程到第四階段終點(diǎn)結(jié)束。

2.動(dòng)態(tài)規(guī)劃的基本原理26一般地，對(duì)于n個(gè)階段的決策過(guò)程，假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下：

(1)當(dāng)過(guò)程指標(biāo)函數(shù)為下列“和”的形式時(shí)，

相應(yīng)的函數(shù)基本方程為

（5—7）

2.動(dòng)態(tài)規(guī)劃的基本原理27

(2)當(dāng)過(guò)程指標(biāo)函數(shù)為下列“積”的形式時(shí),

相應(yīng)的函數(shù)基本方程為

（5—8）可以看出，和、積函數(shù)的基本方程中邊界條件(即的取值)是不同的。

2.動(dòng)態(tài)規(guī)劃的基本原理283.動(dòng)態(tài)規(guī)劃方法的基本步驟

標(biāo)號(hào)法僅適用于求解象最短路線問題那樣可以用網(wǎng)絡(luò)圖表示的多階段決策問題。但不少多階段決策問題不能用網(wǎng)絡(luò)圖表示。此時(shí),應(yīng)該用函數(shù)基本方程來(lái)遞推求解.一般來(lái)說(shuō),要用函數(shù)基本方程逆推求解,首先要有效地建立動(dòng)態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.然而,要把一個(gè)實(shí)際問題用動(dòng)態(tài)規(guī)劃方法來(lái)求解,還必須首先根據(jù)問題的要求。把它構(gòu)造成動(dòng)態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個(gè)動(dòng)態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個(gè)正確的動(dòng)態(tài)規(guī)劃模型,應(yīng)該滿足哪些條件呢?293.動(dòng)態(tài)規(guī)劃方法的基本步驟

1．應(yīng)將實(shí)際問題恰當(dāng)?shù)胤指畛蒼個(gè)子問題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n，即k=n。

2．正確地定義狀態(tài)變量sk，使它既能正確地描述過(guò)程的狀態(tài)，又能滿足無(wú)后效性．303.動(dòng)態(tài)規(guī)劃方法的基本步驟

3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗(yàn)，一般將問題中待求的量，選作動(dòng)態(tài)規(guī)劃模型中的決策變量。或者在把靜態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取前者的變量xj為后者的決策變量uk。

4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk

,uk)313.動(dòng)態(tài)規(guī)劃方法的基本步驟

5．根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)：

(1)可分性，即對(duì)于所有k后部子過(guò)程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策uk

,uk+1,┈,un,就是說(shuō)它是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)。

(2)要滿足遞推關(guān)系，即

(3)函數(shù)對(duì)其變?cè)猇k+1,n，來(lái)說(shuō)要嚴(yán)格單調(diào)。32

6．寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程例如常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式

其中表示第i階段的指標(biāo)，它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成：3.動(dòng)態(tài)規(guī)劃方法的基本步驟33

例5.3:有某種機(jī)床,可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn),在高負(fù)荷下生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量為g,與年初投入生產(chǎn)的機(jī)床數(shù)量u1的關(guān)系為g=g(u1)=8u1,這時(shí),年終機(jī)床完好臺(tái)數(shù)將為au1,(a為機(jī)床完好率，0<a<1,設(shè)a=0.7).在低負(fù)荷下生產(chǎn)時(shí),產(chǎn)品的年產(chǎn)量為h,和投入生產(chǎn)的機(jī)床數(shù)量u2的關(guān)系為h=h(u2)=5u2,相應(yīng)的機(jī)床完好率為b(0<b<1,設(shè)b=0,9),一般情況下a<b。假設(shè)某廠開始有x=1000臺(tái)完好的機(jī)床，現(xiàn)要制定一個(gè)五年生產(chǎn)計(jì)劃，問每年開始時(shí)如何重新分配完好的機(jī)床在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，以使在5年內(nèi)產(chǎn)品的總產(chǎn)量為最高。34

解：首先構(gòu)造這個(gè)問題的動(dòng)態(tài)規(guī)劃模型。

1．變量設(shè)置

(1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=5。

(2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺(tái)數(shù)，同時(shí)也是第k-1年度末時(shí)的完好機(jī)床數(shù)量。

(3)決策變量uk，表示第k年度中分配于高負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù)。于是sk-uk便為該年度中分配于低負(fù)荷下生產(chǎn)的機(jī)床臺(tái)數(shù)．35

這里sk與uk均取連續(xù)變量，當(dāng)它們有非整數(shù)數(shù)值時(shí)．可以這樣理解：如sk＝0.6，就表示一臺(tái)機(jī)器在k年度中正常工作時(shí)間只占6/10；uk=0.4時(shí)，就表示一臺(tái)機(jī)床在

k年度只有4/10的時(shí)間于高負(fù)荷下工作．

2．狀態(tài)轉(zhuǎn)移方程為

k=1，2，…,636

3．允許決策集合,在第k段為

4．目標(biāo)函數(shù)。設(shè)dk(sk,uk)為第k年度的產(chǎn)量，則dk(sk,uk)=8uk+5(sk-uk),因此，目標(biāo)函數(shù)為k＝1,2,．．．,5

5．條件最優(yōu)目標(biāo)函數(shù)遞推方程。令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第5年度結(jié)束這段時(shí)間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系：

k=1,2,3,4,537

6.邊界條件為下