動(dòng)態(tài)規(guī)劃習(xí)題

1、第七章第七章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃規(guī)劃問題的最終目的就是確定各決策變量的取值，以使目標(biāo)函數(shù)達(dá)到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的；然而，有時(shí)我們也會(huì)面對(duì)決策變量需分期、分批處理的多階段決策問題。所謂多階段決策問題多階段決策問題是指這樣一類活動(dòng)過程：它可以分解為若干個(gè)互相聯(lián)系的階段，在每一階段分別對(duì)應(yīng)著一組可供選取的決策集合；即構(gòu)成過程的每個(gè)階段都需要進(jìn)行一次決策的決策問題。將各個(gè)階段的決策綜合起來構(gòu)成

2、一個(gè)決策序列，稱為一個(gè)策略。顯然，由于各個(gè)階段選取的決策不同，對(duì)應(yīng)整個(gè)過程可以有一系列不同的策略。當(dāng)過程采取某個(gè)具體策略時(shí)，相應(yīng)可以得到一個(gè)確定的效果，采取不同的策略，就會(huì)得到不同的效果。多階段的決策問題，就是要在所有可能采取的策略中選取一個(gè)最優(yōu)的策略，以便得到最佳的效果。動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃（dynamicprogramming）同前面介紹過的各種優(yōu)化方法不同，它不是一種算法，而是考察問題的一種途徑。動(dòng)態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)

3、技術(shù)，可以說它橫跨整個(gè)規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。當(dāng)然，由于動(dòng)態(tài)規(guī)劃不是一種特定的算法，因而它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，動(dòng)態(tài)規(guī)劃必須對(duì)具體問題進(jìn)行具體的分析處理。在多階段決策問題中，有些問題對(duì)階段的劃分具有明顯的時(shí)序性，動(dòng)態(tài)規(guī)劃的“動(dòng)態(tài)”二字也由此而得名。動(dòng)態(tài)規(guī)劃的主要?jiǎng)?chuàng)始人是美國(guó)數(shù)學(xué)家貝爾曼（Bellman）。20世紀(jì)40年代末50年代初，當(dāng)時(shí)在蘭德公司（RCpation）從事研究工作的貝爾曼首

4、先提出了動(dòng)態(tài)規(guī)劃的概念。1957年貝爾曼發(fā)表了數(shù)篇研究論文，并出版了他的第一部著作《動(dòng)態(tài)規(guī)劃》。該著作成為了當(dāng)時(shí)唯一的進(jìn)一步研究和應(yīng)用動(dòng)態(tài)規(guī)劃的理論源泉。1961年貝爾曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同時(shí)，其他一些學(xué)者也對(duì)動(dòng)態(tài)規(guī)劃的發(fā)展做出了重大的貢獻(xiàn)，其中最值得一提的是愛爾思（Aris）和梅特頓（Mitten）。愛爾思先后于1961年和

5、1964年出版了兩部關(guān)于動(dòng)態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（Nemhauser）、威爾德（Wild）一道創(chuàng)建了處理分枝、循環(huán)性多階段決策系統(tǒng)的一般性理論。梅特頓提出了許多對(duì)動(dòng)態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎(chǔ)性觀點(diǎn)，并且對(duì)明晰動(dòng)態(tài)規(guī)劃路徑的數(shù)學(xué)性質(zhì)做出了巨大的貢獻(xiàn)。動(dòng)態(tài)規(guī)劃在工程技術(shù)、經(jīng)濟(jì)管理等社會(huì)各個(gè)領(lǐng)域都有著廣泛的應(yīng)用，并且獲得了顯著的效果。在經(jīng)濟(jì)管理方面，動(dòng)態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫(kù)存管理

6、問題、排序問題、設(shè)備更新問題以及生產(chǎn)過程最優(yōu)控制問題等，是經(jīng)濟(jì)管理中一種重要的決策技術(shù)。許多規(guī)劃問題用動(dòng)態(tài)規(guī)劃的方法來處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對(duì)于離散的問題，由于解析數(shù)學(xué)無法發(fā)揮作用，動(dòng)態(tài)規(guī)劃便成為了一種非常有用的工具。動(dòng)態(tài)規(guī)劃可以按照決策過程的演變是否確定分為確定性動(dòng)態(tài)規(guī)劃確定性動(dòng)態(tài)規(guī)劃和隨機(jī)性動(dòng)態(tài)規(guī)劃隨機(jī)性動(dòng)態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動(dòng)態(tài)規(guī)劃連續(xù)性動(dòng)態(tài)規(guī)劃和離散性動(dòng)態(tài)規(guī)劃離散性動(dòng)態(tài)規(guī)劃。本

7、教材主要介紹動(dòng)態(tài)規(guī)劃的基本概念、理論和方法，并通過典型的案例說明這些理論和方法的應(yīng)用。7.17.1動(dòng)態(tài)規(guī)劃的基本理論動(dòng)態(tài)規(guī)劃的基本理論1.1多階段決策過程的數(shù)學(xué)描述多階段決策過程的數(shù)學(xué)描述有這樣一類活動(dòng)過程，其整個(gè)過程可分為若干相互聯(lián)系的階段，每一階段都要作出相應(yīng)的決策，以使整個(gè)過程達(dá)到最佳的活動(dòng)效果。任何一個(gè)階段（stage，即決策點(diǎn)）都是由輸入（input）、決策（decision）、狀態(tài)轉(zhuǎn)移律（transfmationfuncti

8、on）和輸出（output）構(gòu)成的，如圖71（a）所示。其中輸入和輸出也稱為狀態(tài)（state），輸入稱為5策略（policy）與子策略（subpolicy）由所有階段決策所組成的一個(gè)決策序列稱為一個(gè)策略，具有N個(gè)階段的動(dòng)態(tài)規(guī)劃問題的策略可表示為：)()()(2211NNSdSdSd?從某一階段開始到過程終點(diǎn)為止的一個(gè)決策子序列，稱為過程子策略過程子策略或子策略子策略。從第k個(gè)階段起的一個(gè)子策略可表示為：)()()(11NNkkkkSdS

9、dSd???6指標(biāo)函數(shù)指標(biāo)函數(shù)有階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)過程指標(biāo)函數(shù)之分。階段指標(biāo)函數(shù)是對(duì)應(yīng)某一階段決策的效率度量，用gk=r（Sk，dk）來表示；過程指標(biāo)函數(shù)是用來衡量所實(shí)現(xiàn)過程優(yōu)劣的數(shù)量指標(biāo)，是定義在全過程（策略）或后續(xù)子過程（子策略）上的一個(gè)數(shù)量函數(shù)，從第k個(gè)階段起的一個(gè)子策略所對(duì)應(yīng)的過程指標(biāo)函數(shù)常用GkN來表示，即：)(11NNkkkkNkdSdSdSRG????構(gòu)成動(dòng)態(tài)規(guī)劃的過程指標(biāo)函數(shù)，應(yīng)具有可分性并滿足遞推關(guān)

10、系；即：NkkNkGgG1???這里的表示某種運(yùn)算，最常見的運(yùn)算關(guān)系有如下二種：?（1）過程指標(biāo)函數(shù)是其所包含的各階段指標(biāo)函數(shù)的“和”，即：???NkjjNkgG于是NkkNkGgG1???（2）過程指標(biāo)函數(shù)是其所包含的各階段指標(biāo)函數(shù)的“積”，即：???NkjjNkgG于是NkkNkGgG1???7最優(yōu)指標(biāo)函數(shù)從第個(gè)階段起的最優(yōu)子策略最優(yōu)子策略所對(duì)應(yīng)的過程指標(biāo)函數(shù)稱為最優(yōu)指標(biāo)函數(shù)，可以用式k（72）加以表示：（72）)(1~Nkkdkk