【正文】 以用單純形法去求解 ， 而 動態(tài)規(guī)劃問題的求解卻沒有統(tǒng)一的方法 （ 類似于單純形法 ） 。 除此之外 ， 動態(tài)規(guī)劃能求出全局極大或極小 ， 這一點也優(yōu)于其他優(yōu)化方法 。 在管理方面 ， 動態(tài)規(guī)劃可用于資源分配問題 、最短路徑問題 、 庫存問題 、 背包問題 、 設(shè)備更新問題 、 最優(yōu)控制問題等等 ， 所以動態(tài)規(guī)劃是現(xiàn)代管理學(xué)中進(jìn)行科學(xué)決策不可缺少的工具 。 梅特頓提出了許多對動態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎(chǔ)性觀點 ， 并且對明晰動態(tài)規(guī)劃路徑的數(shù)學(xué)性質(zhì)作出了巨大的貢獻(xiàn) 。 在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同時 ， 其他一些學(xué)者也對動態(tài)規(guī)劃的發(fā)展作了巨大的貢獻(xiàn) ， 其中最值得一提的是愛爾思和梅特頓 。 該著作成為當(dāng)時唯一的進(jìn)一步研究和應(yīng)用動態(tài)規(guī)劃的理論源泉 。 1951年貝爾曼首先提出了動態(tài)規(guī)劃中解決多階段決策問題的最優(yōu)化原理 ， 并給出了許多實際問題的解法 。 動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學(xué)家貝爾曼 。 當(dāng)然 ， 由于動態(tài)規(guī)劃不是一種特定的算法 ， 因而它不像線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則 ，動態(tài)規(guī)劃必須對具體問題進(jìn)行具體的分析處理 。 動態(tài)規(guī)劃同前面介紹過的各種優(yōu)化方法不同 ， 它不是一種算法 ，而是考察問題的一種途徑 。 當(dāng)過程采取某個具體策略時 ， 相應(yīng)可以得到一個確定的效果 ， 采取不同的策略 ， 就會得到不同的效果 。 將各個階段的決策綜合起來構(gòu)成一個決策序列 ， 稱為一個策略 。 在線性規(guī)劃和非線性規(guī)劃中 ， 決策變量都是以集合的形式被一次性處理的；然而 ，有時我們也會面對決策變量需分期 、 分批處理的多階段決策問題 。決策理論與方法 （ Decision Making Theory and Methods） 《 決策理論與方法 》 編寫組 教育部高等學(xué)校管理科學(xué)與工程類學(xué)科專業(yè)教學(xué)指導(dǎo)委員會推薦教材 第四章 動態(tài)決策分析 學(xué)習(xí)目的 ? 了解多階段決策、序貫決策的概念及特點； ? 掌握動態(tài)規(guī)劃與決策樹方法及其在多階段決策、序貫決策中的應(yīng)用。 本講內(nèi)容 多階段決策問題的提出 動態(tài)規(guī)劃概述 規(guī)劃問題的最終目的就是確定各決策變量的取值 ， 以使目標(biāo)函數(shù)達(dá)到極大或極小。 所謂多階段決策問題是指這樣一類活動過程：它可以分解為若干個互相聯(lián)系的階段 ， 在每一階段分別對應(yīng)著一組可供選取的決策集合 ， 即構(gòu)成過程的每個階段都需要進(jìn)行一次決策 。 顯然， 由于各個階段選取的決策不同 ， 對應(yīng)整個過程可以有一系列不同的策略 。 多階段的決策問題 ， 就是要在所有可能采取的策略中選取一個最優(yōu)策略 ， 以便得到最佳的效果 。 動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術(shù) ， 可以說它橫跨整個規(guī)劃領(lǐng)域 （ 線性規(guī)劃和非線性規(guī)劃 ） 。 在多階段決策問題中 ， 有些問題對階段的劃分具有明顯的時序性 ， 動態(tài)規(guī)劃的 “ 動態(tài) ” 二字也由此而得名 。 20世紀(jì) 40年代末 50年代初 ， 當(dāng)時在蘭德公司從事研究工作的貝爾曼首先提出了動態(tài)規(guī)劃的概念 。 1957年貝爾曼出版了他的第一部著作 《 動態(tài)規(guī)劃 》 ， 標(biāo)志著運籌學(xué)這一重要分支的誕生 。 1961年貝爾曼出版了他的第二部著作 ， 并于 1962年同杜瑞佛思合作出版了第三部著作 。 愛爾思先后于1961年和 1964年出版了兩部關(guān)于動態(tài)規(guī)劃的著作 ， 并于 1964年同尼母霍思爾 、 威爾德一道創(chuàng)建了處理分支 、 循環(huán)性多階段決策系統(tǒng)的一般性理論 。 動態(tài)規(guī)劃從創(chuàng)立到現(xiàn)在 50多年來 ， 無論在工程技術(shù) 、 企業(yè)管理還是在工農(nóng)業(yè)生產(chǎn)及軍事等部門都有著廣泛的應(yīng)用 ， 并取得了顯著的效果 。 動態(tài)規(guī)劃的優(yōu)點在于 ， 它把一個多維決策問題轉(zhuǎn)化為若干個一維最優(yōu)化問題 ， 而對一維最優(yōu)化問題一個一個地去解 ， 這種方法是許多求極值方法所做不到的 ， 它幾乎優(yōu)于所有現(xiàn)存的優(yōu)化方法 。 需要指出的是 ， 動態(tài)規(guī)劃是求解最優(yōu)化問題的一種方法 ， 是解決問題的一種途徑 ， 而不是一種算法 。 因此在用動態(tài)規(guī)劃求解最優(yōu)化問題中 ， 必須對具體問題具體分析 ， 針對不同的問題 ， 使用動態(tài)規(guī)劃最優(yōu)化原理和方法 ， 建立起與其相應(yīng)的數(shù)學(xué)模型 ， 然后再用動態(tài)規(guī)劃方法去求解 。 動態(tài)決策的基本原理 動態(tài)規(guī)劃 動態(tài)規(guī)劃（ dynamic Programming， DP）是解決多階段決策過程最優(yōu)化的一種方法，其基本思路是將多階段決策過程轉(zhuǎn)化為一系列相互關(guān)聯(lián)的單階段問題，并依次求解。 動態(tài)決策的基本原理 動態(tài)規(guī)劃 例 411 最優(yōu)線路問題 。 選出一條輸水線路 ， 使得總輸水費用最小 。 ? ? ? ?22,r a E f E? 動態(tài)決策的基本原理 決策樹 決策樹 (decision tree)就是將決策過程各個階段之間的結(jié)構(gòu)繪制成一張箭線圖，每個決策或事件（即自然狀態(tài)）都可能引出兩個或多個事件，導(dǎo)致不同的結(jié)果。 ? ? ? ?22,r a E f E? 動態(tài)決策的基本原理 決策樹 ? ? ? ?22,r a E f E?方案枝 方案枝 決策結(jié) 點 概率枝 概率枝 狀態(tài)結(jié)點 概率枝 概率枝 概率枝 狀態(tài)結(jié)點 概率枝 動態(tài)決策的基本原理 決策樹 決策樹法的決策程序如下： 1)繪制樹狀圖，根據(jù)已知條件排列出各個方案和每一方案的各種自然狀態(tài)。 3)計算各方案期望值并將其標(biāo)于該方案對應(yīng)的狀態(tài)結(jié)點上。 多階段決策 多階段決策有以下三個特點， 第一，決策者需要做出時間上有先后之別的多個決策； 第二，前一次決策的選擇將直接影響到后一次決策，后一次決策的狀態(tài)取決于前一次決策的結(jié)果； 第三，決策者關(guān)心的是多次決策的總結(jié)果，而不是各次決策的即時后果。 下面分別以兩個例子說明其決策方法 。該公司預(yù)計該產(chǎn)品暢銷只有五年，五年后將被淘汰，另據(jù)銷售情況的預(yù)測，在價格不同的情況下各年的預(yù)計利潤額見右表。試銷結(jié)果分為產(chǎn)品受歡迎 (H1)，一般 (H2)和不受歡迎(H3)三種。其準(zhǔn)確度（似然分布矩陣）見下表： θ P(θ) P(H1︱ θ) P(H2︱ θ) P(H3︱ θ) θ1 θ2 θ3 多階段決策 多階段決策問題的決策方法 例 422的表格 ?a12（ ） （ 0. 3） （ ） 40000 20230 30000 30000 30