決策理論與方法教學(xué)第四章課件

決策理論與方法

（DecisionMakingTheoryandMethods）

《決策理論與方法》編寫組教育部高等學(xué)校管理科學(xué)與工程類學(xué)科專業(yè)教學(xué)指導(dǎo)委員會推薦教材決策理論與方法

（DecisionMakingTheor第四章動態(tài)決策分析第四章動態(tài)決策分析學(xué)習(xí)目的了解多階段決策、序貫決策的概念及特點；掌握動態(tài)規(guī)劃與決策樹方法及其在多階段決策、序貫決策中的應(yīng)用。學(xué)習(xí)目的了解多階段決策、序貫決策的概念及特點；本講內(nèi)容4.1動態(tài)決策的基本原理4.2多屬性決策本講內(nèi)容4.1動態(tài)決策的基本原理4.1多階段決策問題的提出4.1.1動態(tài)規(guī)劃概述

規(guī)劃問題的最終目的就是確定各決策變量的取值，以使目標函數(shù)達到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的；然而，有時我們也會面對決策變量需分期、分批處理的多階段決策問題。所謂多階段決策問題是指這樣一類活動過程：它可以分解為若干個互相聯(lián)系的階段，在每一階段分別對應(yīng)著一組可供選取的決策集合，即構(gòu)成過程的每個階段都需要進行一次決策。將各個階段的決策綜合起來構(gòu)成一個決策序列，稱為一個策略。顯然，由于各個階段選取的決策不同，對應(yīng)整個過程可以有一系列不同的策略。當過程采取某個具體策略時，相應(yīng)可以得到一個確定的效果，采取不同的策略，就會得到不同的效果。多階段的決策問題，就是要在所有可能采取的策略中選取一個最優(yōu)策略，以便得到最佳的效果。動態(tài)規(guī)劃同前面介紹過的各種優(yōu)化方法不同，它不是一種算法，而是考察問題的一種途徑。動態(tài)規(guī)劃是一種求解多階段決策問題的系統(tǒng)技術(shù)，可以說它橫跨整個規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。當然，由于動態(tài)規(guī)劃不是一種特定的算法，因而它不像線性規(guī)劃那樣有一個標準的數(shù)學(xué)表達式和明確定義的一組規(guī)則，動態(tài)規(guī)劃必須對具體問題進行具體的分析處理。在多階段決策問題中，有些問題對階段的劃分具有明顯的時序性，動態(tài)規(guī)劃的“動態(tài)”二字也由此而得名。4.1多階段決策問題的提出4.1.1動態(tài)規(guī)劃概述

動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學(xué)家貝爾曼。20世紀40年代末50年代初，當時在蘭德公司從事研究工作的貝爾曼首先提出了動態(tài)規(guī)劃的概念。1951年貝爾曼首先提出了動態(tài)規(guī)劃中解決多階段決策問題的最優(yōu)化原理，并給出了許多實際問題的解法。1957年貝爾曼出版了他的第一部著作《動態(tài)規(guī)劃》，標志著運籌學(xué)這一重要分支的誕生。該著作成為當時唯一的進一步研究和應(yīng)用動態(tài)規(guī)劃的理論源泉。1961年貝爾曼出版了他的第二部著作，并于1962年同杜瑞佛思合作出版了第三部著作。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同時，其他一些學(xué)者也對動態(tài)規(guī)劃的發(fā)展作了巨大的貢獻，其中最值得一提的是愛爾思和梅特頓。愛爾思先后于1961年和1964年出版了兩部關(guān)于動態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾、威爾德一道創(chuàng)建了處理分支、循環(huán)性多階段決策系統(tǒng)的一般性理論。梅特頓提出了許多對動態(tài)規(guī)劃后來發(fā)展有著重要意義的基礎(chǔ)性觀點，并且對明晰動態(tài)規(guī)劃路徑的數(shù)學(xué)性質(zhì)作出了巨大的貢獻。動態(tài)規(guī)劃從創(chuàng)立到現(xiàn)在50多年來，無論在工程技術(shù)、企業(yè)管理還是在工農(nóng)業(yè)生產(chǎn)及軍事等部門都有著廣泛的應(yīng)用，并取得了顯著的效果。在管理方面，動態(tài)規(guī)劃可用于資源分配問題、最短路徑問題、庫存問題、背包問題、設(shè)備更新問題、最優(yōu)控制問題等等，所以動態(tài)規(guī)劃是現(xiàn)代管理學(xué)中進行科學(xué)決策不可缺少的工具。動態(tài)規(guī)劃的優(yōu)點在于，它把一個多維決策問題轉(zhuǎn)化為若干個一維最優(yōu)化問題，而對一維最優(yōu)化問題一個一個地去解，這種方法是許多求極值方法所做不到的，它幾乎優(yōu)于所有現(xiàn)存的優(yōu)化方法。除此之外，動態(tài)規(guī)劃能求出全局極大或極小，這一點也優(yōu)于其他優(yōu)化方法。需要指出的是，動態(tài)規(guī)劃是求解最優(yōu)化問題的一種方法，是解決問題的一種途徑，而不是一種算法。在前面我們學(xué)習(xí)了用單純形法解線性規(guī)劃問題，凡是具有線性規(guī)劃問題那樣統(tǒng)一的數(shù)學(xué)模型都可以用單純形法去求解，而動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學(xué)家貝爾曼。20動態(tài)規(guī)劃問題的求解卻沒有統(tǒng)一的方法（類似于單純形法）。因此在用動態(tài)規(guī)劃求解最優(yōu)化問題中，必須對具體問題具體分析，針對不同的問題，使用動態(tài)規(guī)劃最優(yōu)化原理和方法，建立起與其相應(yīng)的數(shù)學(xué)模型，然后再用動態(tài)規(guī)劃方法去求解。根據(jù)動態(tài)規(guī)劃這些特點，要求我們在學(xué)好動態(tài)規(guī)劃的基本原理和方法的同時，還應(yīng)具有豐富的想象力，只有這樣才能建好模型求出問題的最優(yōu)解。動態(tài)規(guī)劃問題的求解卻沒有統(tǒng)一的方法（類似于單純形法）。因此在4.1動態(tài)決策的基本原理4.1.1動態(tài)規(guī)劃

動態(tài)規(guī)劃（dynamicProgramming，DP）是解決多階段決策過程最優(yōu)化的一種方法，其基本思路是將多階段決策過程轉(zhuǎn)化為一系列相互關(guān)聯(lián)的單階段問題，并依次求解。

DP是離散系統(tǒng)最優(yōu)化的一種有效工具，目前動態(tài)規(guī)劃已廣泛用于工業(yè)、農(nóng)業(yè)、工程技術(shù)、資源、環(huán)境、經(jīng)濟、社會等領(lǐng)域。

4.1動態(tài)決策的基本原理4.1.1動態(tài)規(guī)劃4.1動態(tài)決策的基本原理4.1.1動態(tài)規(guī)劃例4-1-1最優(yōu)線路問題。由水源地向城市的輸水線路需通過3個控制點，每個控制點均有兩個可選方案，每段線路的輸水費用如下圖所示。選出一條輸水線路，使得總輸水費用最小。4.1動態(tài)決策的基本原理4.1.1動態(tài)規(guī)劃4.1動態(tài)決策的基本原理4.1.1動態(tài)規(guī)劃

最優(yōu)性原理（theprincipleofoptimality）也稱為Bellman原理，是R.Bellman提出的DP的基本原理，其表述為：“一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論初始狀態(tài)和初始決策如何，對于由前面的決策所形成的狀態(tài)來說，其后各階段的決策序列必定構(gòu)成相應(yīng)子過程的最優(yōu)策略”。4.1動態(tài)決策的基本原理4.1.1動態(tài)規(guī)劃4.1動態(tài)決策的基本原理4.1.2決策樹

決策樹(decisiontree)就是將決策過程各個階段之間的結(jié)構(gòu)繪制成一張箭線圖，每個決策或事件（即自然狀態(tài)）都可能引出兩個或多個事件，導(dǎo)致不同的結(jié)果。決策樹的構(gòu)成有四個要素：1)決策結(jié)點；2)方案枝；3)狀態(tài)結(jié)點；4)概率枝。

4.1動態(tài)決策的基本原理4.1.2決策樹4.1動態(tài)決策的基本原理4.1.2決策樹

方案枝方案枝決策結(jié)點概率枝概率枝狀態(tài)結(jié)點概率枝概率枝概率枝狀態(tài)結(jié)點概率枝4.1動態(tài)決策的基本原理4.1.2決策樹方案枝方案枝決策4.1動態(tài)決策的基本原理4.1.2決策樹決策樹法的決策程序如下：

1)繪制樹狀圖，根據(jù)已知條件排列出各個方案和每一方案的各種自然狀態(tài)。

2)將各狀態(tài)概率及損益值標于概率枝上。

3)計算各方案期望值并將其標于該方案對應(yīng)的狀態(tài)結(jié)點上。

4)進行剪枝，比較各個方案的期望值，并標于方案枝上，將期望值小的(即劣等方案剪掉)所剩的最后方案為最佳方案。

4.1動態(tài)決策的基本原理4.1.2決策樹4.2多階段決策

多階段決策有以下三個特點，第一，決策者需要做出時間上有先后之別的多個決策；第二，前一次決策的選擇將直接影響到后一次決策，后一次決策的狀態(tài)取決于前一次決策的結(jié)果；第三，決策者關(guān)心的是多次決策的總結(jié)果，而不是各次決策的即時后果。

4.2多階段決策4.2多階段決策4.2.1多階段決策過程的基本概念（1）階段（2）狀態(tài)（3）決策與策略（4）指標函數(shù)與目標函數(shù)（5）多階段決策過程4.2多階段決策4.2.1多階段決策過程的基本概念4.2多階段決策4.2.2多階段決策問題的決策方法多階段決策問題包括確定型與隨機型兩大類，在確定型多階段決策中，目標值都是確定值，在風(fēng)險型多階段決策中，目標值用期望值作為評價的標準。下面分別以兩個例子說明其決策方法。4.2多階段決策4.2.2多階段決策問題的決策方法4.2多階段決策4.2.2多階段決策問題的決策方法例4-2-1某公司考慮為某新產(chǎn)品定價，該產(chǎn)品的單價擬從每件5元、6元、7元、8元這四個價格中選取其中之一，每年年初允許變動價格，但幅度不能超過1元。該公司預(yù)計該產(chǎn)品暢銷只有五年，五年后將被淘汰，另據(jù)銷售情況的預(yù)測，在價格不同的情況下各年的預(yù)計利潤額見右表。單價第1年第2年第3年第4年第5年5元10121520256元1213162024716151514144.2多階段決策4.2.2多階段決策問題的決策方法單價第4.2多階段決策4.2.2多階段決策問題的決策方法例4-2-1決策圖

736045845元1012152025736045846元1213162024736045847元1414161818736045848元16151514144.2多階段決策4.2.2多階段決策問題的決策方法734.2多階段決策4.2.2多階段決策問題的決策方法

例4-2-2為了更正確地掌握市場情況，正式投產(chǎn)公司打算先生產(chǎn)少量產(chǎn)品試銷，試銷費需要5000元。試銷結(jié)果分為產(chǎn)品受歡迎(H1)，一般(H2)和不受歡迎(H3)三種。由于試銷面不寬，試銷結(jié)果的準確性有限。其準確度（似然分布矩陣）見下表：θP(θ)P(H1︱θ)P(H2︱θ)P(H3︱θ)θ10.60.60.30.1θ20.30.20.60.2θ30.10.20.30.54.2多階段決策4.2.2多階段決策問題的決策方法θP4.2多階段決策4.2.2多階段決策問題的決策方法例4-2-2的表格（0.6）（0.3）（0.1）4000020000-300003000030000-20000100001000010000

（0.6）（0.3）（0.1）0.60.20.20.30.60.30.10.20.54.2多階段決策4.2.2多階段決策問題的決策方法（0如不買此項專利，把這筆費用用在其他方面，在同樣的時期可獲利1.1萬元。那么，該公司應(yīng)該如何決（1）是否買專利？（2）如果買專利，是否采取試銷辦法？（3）如果不試銷，應(yīng)大批生產(chǎn)，中批生產(chǎn)還是小批生產(chǎn)？如果試銷，又應(yīng)該如何根據(jù)試銷結(jié)果決定其行動？如不買此項專利，把這筆費用用在其他方面，在同樣的時期可獲利1第一階段127買專利不買專利試銷不試銷3456H1H2H38910a1a2a3θ1θ2θ3（略）第二階段第三階段例4-2-2第一階段127買專利不買專利試銷不試銷3456H1H2H38例4-2-2解：這是一個三階段決策問題，采用逆序歸納法進行決策分析，先要計算在一定的試銷結(jié)果下的各后驗概率。由全概率公式：計算得：例4-2-2解：這是一個三階段決策問題，采用逆序歸納法進行決例4-2-2再由貝葉斯公式：計算得：例4-2-2再由貝葉斯公式：計算得：例4-2-2當試銷結(jié)果為H1時：故當試銷結(jié)果為H1時，應(yīng)選擇大批生產(chǎn)a1，截去方案a2、a3，結(jié)點4的值為3.406萬元。----結(jié)點8----結(jié)點9----結(jié)點10例4-2-2當試銷結(jié)果為H1時：故當試銷結(jié)果為H1時，應(yīng)例4-2-2當試銷結(jié)果為H2時：故當試銷結(jié)果為H2時，應(yīng)選擇中批生產(chǎn)a2，截去方案a1、a3，結(jié)點5的值為2.62萬元

。例4-2-2當試銷結(jié)果為H2時：故當試銷結(jié)果為H2時，應(yīng)例4-2-2當試銷結(jié)果為H3時：故當試銷結(jié)果為H3時，也應(yīng)選擇中批生產(chǎn)a2，截去方案a1、a3，結(jié)點6的值為1.53萬元。例4-2-2當試銷結(jié)果為H3時：故當試銷結(jié)果為H3時，也例