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

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

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

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

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

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

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

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

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

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

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