專題講座動態(tài)規(guī)劃與層次分析法_第1頁
專題講座動態(tài)規(guī)劃與層次分析法_第2頁
專題講座動態(tài)規(guī)劃與層次分析法_第3頁
專題講座動態(tài)規(guī)劃與層次分析法_第4頁
專題講座動態(tài)規(guī)劃與層次分析法_第5頁
已閱讀5頁,還剩41頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

專題講座動態(tài)規(guī)劃與層次分析法內容說明以下內容在《數(shù)學建模與數(shù)學實驗(第二版)》(汪曉銀,周保平主編)第6章、第9章。動態(tài)規(guī)劃內容提要動態(tài)規(guī)劃的最優(yōu)化原理動態(tài)規(guī)劃的基本概念及遞推公式動態(tài)規(guī)劃模型舉例動態(tài)規(guī)劃程序例1最短路問題五十年代貝爾曼(B.E.Bellman)為代表的研究成果屬于現(xiàn)代控制理論的一部分以長遠利益為目標的一系列決策最優(yōu)化原理,可歸結為一個遞推公式動態(tài)規(guī)劃的最優(yōu)化原理可以枚舉出20條路徑,其中最短的路徑長度為16決策樹法動態(tài)規(guī)劃的最優(yōu)化原理最優(yōu)性原理“最優(yōu)策略的一部分也是最優(yōu)的。因此我們可以從B向回搜索最短路表現(xiàn)為明顯的階段性動態(tài)規(guī)劃的最優(yōu)化原理基本概念及遞推公式狀態(tài)最短路問題中,各個節(jié)點就是狀態(tài)。生產(chǎn)庫存問題中,庫存量是狀態(tài)。物資分配問題中,剩余的物資量是狀態(tài)控制變量(決策變量)最短路問題中,走哪條路。生產(chǎn)庫存問題中,各階段的產(chǎn)品生產(chǎn)量。物資分配問題中,分配給每個地區(qū)的物資量。階段的編號與遞推的方向一般采用反向遞推,所以階段的編號也是逆向的當然也可以正向遞推動態(tài)規(guī)劃的步驟1、確定問題的階段和編號2、確定狀態(tài)變量用Sk

表示第k階段的狀態(tài)變量及其值3、確定決策變量用xk表示第k階段的決策變量,并以xk*表示該階段的最優(yōu)決策4、狀態(tài)轉移方程sk-1=g(sk,xk)反向編號sk+1=g(sk,xk)正向編號5、直接效果直接一步轉移的效果dk(sk,xk)6、總效果函數(shù)指某階段某狀態(tài)下到終端狀態(tài)的總效果,它是一個遞推公式終端的邊際效果一般為f0(s0,x0)=0(2)如串聯(lián)系統(tǒng)可靠性問題,是連乘形式,此時有終端的邊際效果一般為f0(s0,x0)=1從第1階段開始,利用邊際效果和邊界條件,可以遞推到最后階段hk是一般表達形式,求當前階段當前狀態(tài)下的階段最優(yōu)總效果(1)如最短路問題,是累加形式,此時有動態(tài)規(guī)劃的步驟動態(tài)規(guī)劃模型舉例例1產(chǎn)品生產(chǎn)計劃安排問題

某工廠生產(chǎn)某種產(chǎn)品的月生產(chǎn)能力為10件,已知今后四個月的產(chǎn)品成本及銷售量如表所示。如果本月產(chǎn)量超過銷售量時,可以存儲起來備以后各月銷售,一件產(chǎn)品的月存儲費為2元,試安排月生產(chǎn)計劃并做到:1、保證滿足每月的銷售量,并規(guī)定計劃期初和期末庫存為零;2、在生產(chǎn)能力允許范圍內,安排每月生產(chǎn)量計劃使產(chǎn)品總成本(即生產(chǎn)費用加存儲費)最低。第一階段:(即第4月份)由邊界條件和狀態(tài)轉移方程s0=s1+x1-y1=s1+x1–6=0得

s1+x1=6或x1=6–s1估計第一階段,即第4月份初庫存的可能狀態(tài):s1

[0,5]設xk為第k階段生產(chǎn)量,則有直接成本

dk(sk,xk)=ckxk+2sk狀態(tài)轉移公式為

sk-1=sk+xk-yk總成本遞推公式動態(tài)規(guī)劃模型舉例第一階段最優(yōu)決策表第二階段:最大可能庫存量7件由狀態(tài)轉移方程:s1=s2+x2-120及x210,可知s2[2,7],minx2=5由階段效果遞推公式有:f2(2,10)=d2(2,10)+f1*(0,6) =22+8010+456=1260得第二階段最優(yōu)決策表,如下動態(tài)規(guī)劃模型舉例第二階段最優(yōu)決策表第三階段:最大可能庫存量4件由狀態(tài)轉移方程:s2=s3+x3-72及x310,可知s3[0,4],minx3=5由階段效果遞推公式有:f3(1,10)=d3(1,10)+f2*(4,8) =21+7210+1104=1826得第三階段最優(yōu)決策表,如下動態(tài)規(guī)劃模型舉例第三階段最優(yōu)決策表第四階段:初始庫存量s4=0由狀態(tài)轉移方程:s3=s4+x4-60可知x46,由階段效果遞推公式有:f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322得第四階段最優(yōu)決策表,如下回溯得此表動態(tài)規(guī)劃模型舉例解四個季度為四個階段,采用階段編號與季度順序一致。設sk

為第k季初的庫存量,則邊界條件為s1=s5=0設xk

為第k季的生產(chǎn)量,設yk

為第k季的訂貨量;sk,xk,yk都取實數(shù),狀態(tài)轉移方程為sk+1=sk+xk-yk仍采用反向遞推,但注意階段編號是正向的

目標函數(shù)為例2生產(chǎn)–庫存管理問題設某廠計劃全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤,700公斤,500公斤和1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費用與產(chǎn)品的平方成正比,系數(shù)為0.005。廠內有倉庫可存放產(chǎn)品,存儲費為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成本最小。動態(tài)規(guī)劃模型舉例第一步:(第四季度)總效果f4(s4,x4)=0.005x42+s4

由邊界條件有:s5=s4+x4–y4=0,解得:x4*=1200–s4

將x4*代入f4(s4,x4)得:

f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步:(第三、四季度)總效果f3(s3,x3)=0.005x32+s3+f4*(s4)將s4=s3+x3–500代入f3(s3,x3)得:動態(tài)規(guī)劃模型舉例第三步:(第二、三、四季度)總效果

f2(s2,x2)=0.005x22+s2+f3*(s3)將s3=s2+x2-700代入f2(s2,x2)得:

注意:最優(yōu)階段總效果僅是當前狀態(tài)的函數(shù),與其后的決策無關動態(tài)規(guī)劃模型舉例第四步:(第一、二、三、四季度)總效果

f1(s1,x1)=0.005x12+s1+f2*(s2)將s2=s1+x1–600=x1–600代入f1(s1,x1)得:由此回溯:得最優(yōu)生產(chǎn)–庫存方案

x1*=600,s2*=0;x2*=700,s3*=0;x3*=800,s4*=300;x4*=900。動態(tài)規(guī)劃模型舉例例3

資源分配問題某公司有9個推銷員在全國三個不同市場推銷貨物,這三個市場里推銷人員數(shù)與收益的關系如下表,試作出使總收益最大的分配方案。解:設分配人員的順序為市場1,2,3,采用反向階段編號。設sk

為第k階段尚未分配的人員數(shù),邊界條件為s3=9設xk

為第k階段分配的推銷人員數(shù);仍采用反向遞推,狀態(tài)轉移方程為sk–1=sk–xk

目標函數(shù)為動態(tài)規(guī)劃模型舉例s1有0~9種可能,第一階段(第三市場)最優(yōu)決策表如下:為什么與例1的第一階段的表有差別?動態(tài)規(guī)劃模型舉例s2有0~9種可能,第二階段最優(yōu)決策表如下:動態(tài)規(guī)劃模型舉例

由邊界條件s3=9,第三階段最優(yōu)決策表如下:得決策過程:x3*=2,x2*=0,x1*=7,f3*=218即市場1分配2人,市場2不分配,市場3分配7人最優(yōu)解與分配的順序有關嗎?動態(tài)規(guī)劃模型舉例層次分析法背景層次分析法的基本步驟層次分析法的廣泛應用層次分析法內容提要

日常工作、生活中的決策問題

涉及經(jīng)濟、社會等方面的因素

作比較判斷時人的主觀選擇起相當大的作用,各因素的重要性難以量化

Saaty于1970年代提出層次分析法AHP(AnalyticHierarchyProcess)

AHP——一種定性與定量相結合的、系統(tǒng)化、層次化的分析方法背景目標層O(選擇旅游地)P2黃山P1桂林P3北戴河準則層方案層C3居住C1景色C2費用C4飲食C5旅途層次分析法的基本步驟例.選擇旅游地如何在3個目的地中按照景色、費用、居住條件等因素選擇.“選擇旅游地”思維過程的歸納

將決策問題分為3個層次:目標層O,準則層C,方案層P;每層有若干元素,

各層元素間的關系用相連的直線表示。

通過相互比較確定各準則對目標的權重,及各方案對每一準則的權重。將上述兩組權重進行綜合,確定各方案對目標的權重。層次分析法將定性分析與定量分析結合起來完成以上步驟,給出決策問題的定量結果。層次分析法的基本步驟成對比較陣和權向量元素之間兩兩對比,對比采用相對尺度設要比較各準則C1,C2,…,Cn對目標O的重要性A~成對比較陣A是正互反陣要由A確定C1,…,Cn對O的權向量選擇旅游地層次分析法的基本步驟成對比較的不一致情況一致比較不一致允許不一致,但要確定不一致的允許范圍成對比較陣和權向量層次分析法的基本步驟考察完全一致的情況層次分析法的基本步驟成對比較完全一致的情況滿足的正互反陣A稱一致陣,如成對比較陣和權向量層次分析法的基本步驟

A的秩為1,A的唯一非零特征根為n

A的任一列向量是對應于n的特征向量

A的歸一化特征向量可作為權向量對于不一致(但在允許范圍內)的成對比較陣A,建議用對應于最大特征根的特征向量作為權向量w,即一致陣性質層次分析法的基本步驟2468比較尺度aij

Saaty等人提出1~9尺度——aij

取值1,2,…,9及其互反數(shù)1,1/2,…,1/9尺度13579相同稍強強明顯強絕對強aij=1,1/2,,…1/9的重要性與上面相反

便于定性到定量的轉化:成對比較陣和權向量層次分析法的基本步驟

心理學家認為成對比較的因素不宜超過9個用1~3,1~5,…1~17,…,1p~9p

(p=2,3,4,5),d+0.1~d+0.9(d=1,2,3,4)等27種比較尺度對若干實例構造成對比較陣,算出權向量,與實際對比發(fā)現(xiàn),1~9尺度較優(yōu)。層次分析法的基本步驟一致性檢驗對A確定不一致的允許范圍已知:n階一致陣的唯一非零特征根為n可證:n階正互反陣最大特征根

n,且

=n時為一致陣定義一致性指標:CI越大,不一致越嚴重層次分析法的基本步驟RI000.580.901.121.241.321.411.451.491.51

n1234567891110為衡量CI的大小,引入隨機一致性指標RI——隨機模擬得到aij,形成A,計算CI即得RI。定義一致性比率CR=CI/RI當CR<0.1時,通過一致性檢驗Saaty的結果如下層次分析法的基本步驟“選擇旅游地”中準則層對目標的權向量及一致性檢驗準則層對目標的成對比較陣最大特征根權向量(特征向量)w=(0.263,0.475,0.055,0.090,0.110)T一致性指標隨機一致性指標RI=1.12(查表)一致性比率CR通過一致性檢驗層次分析法的基本步驟組合權向量記第2層(準則)對第1層(目標)的權向量為同樣求第3層(方案)對第2層每一元素(準則)的權向量方案層對C1(景色)的成對比較陣方案層對C2(費用)的成對比較陣…Cn…Bn最大特征根1

2

n

權向量w1(3)w2(3)…

wn(3)層次分析法的基本步驟第3層對第2層的計算結果k10.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.082230.1420.4290.42933.0090.1750.1930.633430.6680.1660.1665組合權向量RI=0.58(n=3),

CIk

均可通過一致性檢驗w(2)

方案P1對目標的組合權重為方案層對目標的組合權向量為(0.300,0.246,0.456)T層次分析法的基本步驟組合權向量第1層O第2層C1,…Cn第3層P1,…Pm第2層對第1層的權向量第3層對第2層各元素的權向量構造矩陣則第3層對第1層的組合權向量第s層對第1層的組合權向量其中W(p)是由第p層對第p-1層權向量組成的矩陣層次分析法的基本步驟1)建立層次分析結構模型深入分析實際問題,將有關因素自上而下分層(目標—準則或指標—方案或對象),上層受下層影響,而層內各因素基本上相對獨立。2)構造成對比較陣用成對比較法和1~9尺度,構造各層對上一層每一因素的成對比較陣。3)計算權向量并作一致性檢驗對每一成對比較陣計算最大特征根和特征向量,作一致性檢驗,若通過,則特征向量為權向量。4)計算組合權向量(作組合一致性檢驗*)組合權向量可作為決策的定量依據(jù)。層次分析法的基本步驟

應用領域:經(jīng)濟計劃和管理,能源政策和分配,人才選拔和評價,生產(chǎn)決策,交通運輸,科研選題,產(chǎn)業(yè)結構,教育,醫(yī)療,環(huán)境,軍事等。

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論