




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、第八章動態(tài)規(guī)劃,導論,動態(tài)規(guī)劃是解決多階段決策過程優(yōu)化的一種方法。這種方法是由美國數學家貝爾曼在20世紀50年代初提出的。并成功地解決了生產管理和工程技術中的許多問題,從而建立了運籌學的一個新分支,即動態(tài)規(guī)劃。貝爾曼在1957年出版了動態(tài)規(guī)劃,這是動態(tài)規(guī)劃領域的第一本書。動態(tài)規(guī)劃與其他規(guī)劃方法的區(qū)別在于,動態(tài)規(guī)劃是解決某一類問題(多階段決策問題)的方法,是研究問題的一種方式,而不是具體的算法。因此,與線性規(guī)劃不同,它沒有標準的數學表達式和一套明確定義的(算法)規(guī)則,但必須分析和管理具體問題。因此,在學習動態(tài)規(guī)劃時,不僅要正確理解基本概念和方法,還要在積累一定經驗的基礎上,用豐富的想象力建立模型
2、,用創(chuàng)造性的技巧解決問題。提綱,1個動態(tài)規(guī)劃的例子,2個動態(tài)規(guī)劃的基本概念,3個動態(tài)規(guī)劃的基本思想和原則,4個逆序解和順序解,學習目標:1闡明什么是多階段決策問題,并特別注意如何將沒有明顯時間背景的問題轉化為多階段決策問題。P156例1動態(tài)規(guī)劃,P156例2機器負荷分配問題(時間階段問題)有某種機器設備用來完成兩種工作A和B.如果k開始時完整機器的數量是xk,如果uk的數量用于A,剩余的(xkuk)用于工作B,則該年的預期收入是g(uk) h(xkuk)。G(uk)和h(xkuk)是已知函數,g(0)=h(0)=0。此外,機器和設備在使用中會損壞。當機器用于工作A時,一年后可繼續(xù)使用的完好機器
3、數量占年初投入的70%;如果在作業(yè)B中使用,一年后可以繼續(xù)使用的完整機器數量占年初輸入的90%。明年年初,可繼續(xù)用于A和B的設備數量為xk 1=0.7uk 0.9(xk uk)。讓第一年年初的完好機器總數為1000臺,并詢問連續(xù)五年每年A和B的機器數量如何分配,以使五年的總收入最大化。1動態(tài)規(guī)劃的例子,相應的問題稱為多階段決策問題。這是一個多階段的決策過程。這個過程可以分為幾個相互關聯的階段,每個階段都需要做出一個決定,從而在整個過程中形成一個決定。第一年,u1,x2=0.7u10.9 (x1-u1),U2,x3=0.7u20.9 (x2-U2),u3,第四年,u4,x5=0.7u4 0.9(
4、x4-u4),u5,P156例1最短路線問題(空間從A到E有很多路線可供選擇,且各點之間的距離如圖所示。問旅行者選擇哪條路線,這樣從A到E的總距離是最短的。1,2,3,4,決策1,決策2,決策3,決策4可以看作是一個四階段決策問題。從以上兩個例子中,我們可以知道,所謂的多階段決策問題就是指這樣一個決策問題:這個過程可以分為相互關聯的階段,每個階段對應一組備選決策,而每個決策的選擇取決于當前的狀態(tài)并影響未來的整體結果。當每個階段的決策被選定時,它就構成了一個決策序列,稱為策略,它對應于某個效果。多階段決策問題是尋找最佳策略。多階段決策過程的特點1。每個階段的決策都是相互關聯的。多階段決策過程優(yōu)化
5、的目的是實現整個活動過程的最佳整體效果,而不是某一階段的最佳“局部”效果。因此,每個階段的決策選擇不是任意的。前一個決策的選擇決定了當前的狀態(tài),從而影響到決策后下一階段的狀態(tài)和決策,從而影響整體效果。因此,在每個階段做出決策時,決策者不僅要考慮這一階段的最佳方案,還要考慮對最終目標的影響,從而做出總體上最佳的決策。動態(tài)規(guī)劃是滿足這一要求的優(yōu)化方法。2.每個階段的決策通常與“時間”相關。動態(tài)規(guī)劃方法與“時間”密切相關。隨著時間進程的發(fā)展,每個階段的決策都是決定的,從而產生一個決策序列,這就是“動態(tài)”的含義。但是,一些與時間無關的靜態(tài)問題,只要人為地將“時間”因素引入到問題中,也可以被視為多階段決
6、策問題,可以用動態(tài)規(guī)劃方法來處理。學習目標:1 .準確、熟練掌握動態(tài)規(guī)劃的基本概念,尤其是狀態(tài)變量、決策變量、狀態(tài)轉移規(guī)律、指標函數和基本方程。2.動態(tài)規(guī)劃的基本概念是,為了解決和表達決策和過程的發(fā)展順序,把給定的問題分成幾個相互關聯的不同的子問題,稱為多階段決策問題階段。階段是需要做出決定的子問題。通常,根據決策的時間或空間順序來劃分階段。描述一個階段的變量稱為階段變量,通常記錄為k,k=1,2和n。例如,解可以根據空間分為四個階段,k=1,2,3,4。(1)階段、狀態(tài):每個階段開始時的客觀條件。描述每個階段狀態(tài)的變量稱為狀態(tài)變量,而xk通常用來表示第k階段的狀態(tài)。(2)狀態(tài)。在示例1中,狀
7、態(tài)是某個階段的起始位置。根據狀態(tài)變量的值是連續(xù)的還是離散的,動態(tài)規(guī)劃問題可以分為離散型和連續(xù)型。動態(tài)規(guī)劃中的狀態(tài)應滿足無后效性(Markov屬性):所謂無后效性是指系統(tǒng)達到某一狀態(tài)之前的過程決策不會影響到該狀態(tài)之后的決策。它是指系統(tǒng)從某一階段到未來的發(fā)展,它只由這一階段的狀態(tài)及其未來的決策所決定,而與系統(tǒng)以前的狀態(tài)和決策(歷史)無關。該過程的過去歷史只能通過當前狀態(tài)影響其未來發(fā)展。在示例1中,當在某個階段的狀態(tài)中選擇了某個點時,該點之后的路線僅與該點相關,并且不受該點之前的路線的影響,因此該狀態(tài)沒有后效。狀態(tài)集:狀態(tài)變量xk的值集稱為狀態(tài)集,它實際上是一個關于狀態(tài)的約束條件。通常,Sk用來表示
8、狀態(tài)集xkSk。第一階段S1=a;第二階段有三個國家B1,B2和B3,所以S2=B1,B2和B3。(3)決策,當過程在某一階段處于某一狀態(tài)時,可以作出不同的決策來確定下一階段的狀態(tài),這叫做決策。描述決策的變量稱為決策變量,當狀態(tài)為xk時,uk(xk)通常用于表示k階段的決策變量,xk是狀態(tài)變量的函數。在示例1中,從第二階段的狀態(tài)B1,可以選擇下一階段的C1、C2和C3。如果我們決定選擇C1,它可以表示為u2(B1)=C1。B1,C1,C2,C3,決策集:當狀態(tài)為xk時,決策變量uk(xk)的值范數稱為決策集,通常用Dk(xk)表示。在示例1中,從第二階段的狀態(tài)B1,可以選擇下一階段的C1、C2
9、和C3。也就是說,D2(B1)=C1、C2和C3;B1、C1、C2、C3,決策集實際上是決策的約束條件,uk(xk) Dk(xk)??偨Y階段k、狀態(tài)xk、狀態(tài)集Sk、決策集uk(xk)和決策集Dk(xk)。(4)狀態(tài)轉移定律(方程):從某個狀態(tài)值xk開始,當確定了決策變量uk(xk)的值時,也就確定了下一階段狀態(tài)變量xk 1的值。描述從xk到xk 1轉變的定律稱為狀態(tài)轉變定律(方程式)。從第二階段的狀態(tài)B1開始,如果我們明確選擇C2(即確認下一階段的狀態(tài))。在上面的例子中,u2(B1)=C2的狀態(tài)轉移定律是:xk 1=uk(xk)。一般來說,下一階段狀態(tài)變量xk 1的值是前一階段的某個狀態(tài)變量
10、xk和前一階段的決策變量uk(xk)的函數,表示為xk 1=Tk(xk,uk(xk),(5)策略:由N個決策階段組成的決策序列依次構成一個策略,由P1U1 (x1)、U2 (x2)和UN (xn)表示。在本例中,p14u1 (a)=B1,U2 (B1)=C2,u3 (C2)=D1,U4 (D1)=e代表策略之一,其總距離為2 5 6 3=16。策略集:在實際問題中,由于每個階段都有許多可供選擇的決策,它們的不同組合構成了許多可供選擇的決策序列(策略),由它們組成的集合稱為策略集,被記錄為P1n。從策略集合來看,效果最好的策略稱為最優(yōu)策略。子策略:從K階段到N階段,由依次做出的階段決策組成的決策
11、序列稱為K子策略,表示為PKN=英國(XK)、英國1 (XK 1)、聯合國(XN),例如,從第三階段C2狀態(tài)開始的子策略可以表示為P34=U3 (C2),它是在整個過程或子過程或階段中定義的一個確定的數量函數。對于不同的問題,指標函數可以是成本、成本、產值、利潤、產量、消耗、距離、時間、效用等。階段指數函數、過程指數函數、階段指數函數:是指在K階段從狀態(tài)xk進行決策uk時產生的收益,用vk(xk,uk)表示。在示例1中,索引函數是距離。例如,v2(B1,C2)表示從B1開始,采用從判定點到C2的兩點之間的距離,即v2(B1,C2)=5。過程指數函數:是指在第K階段從某個狀態(tài)xk取子策略pkn時
12、所獲得的收益,在例1中記錄為Vkn(xk,uk,xk 1,uk 1,xn),如V34 (C2,U3 (C2)=D1,D1,U4 (D1)=E,E)。過程指數函數Vkn通常是描述整個過程或后K子過程的優(yōu)劣的量化指標,它是由階段指數函數vk(1)累加而成的(1)可分性:適用于動態(tài)規(guī)劃求解問題的過程指標函數(即目標函數)必須具有關于階段指標的可分形式,即后子過程的指標函數可以表示為:vkn (xk,uk,xk1,uk 1,xn)=vk (xk,uk) vk1 (xk1,uk 1) VN在多階段決策問題中,一種常見的目標函數形式是每個階段的效果之和,即對于某些問題, 例如系統(tǒng)可靠性,目標函數是每個階段
13、的效果的產物,例如,簡而言之,特定問題的目標函數的表達形式需要依賴于特定問題。 (2)遞歸:過程指標函數Vkn應滿足遞歸關系,即遞歸,VKN (xk,uk,xk1,uk 1,xn),kxk,uk,v (k 1) n (xk1,uk 1,xn),vk (xk,uk) vk1 Uk),V(k 1)n(xk 1,uk 1,xn),最優(yōu)指標函數:它表示當kth階段的狀態(tài)為xk至終止時,采用最優(yōu)策略pkn*的最優(yōu)收益值寫為fk(xk)。Fk (xk)=vkn (xk,pkn *)=optvkn (xk,pkn),例如1,f3(C2)=3 4=7。其中opt可以根據具體情況采用最大值或最小值。,C2,動態(tài)
14、規(guī)劃的目標是什么?最優(yōu)解:最優(yōu)策略p1n最優(yōu)值:最優(yōu)指標f1(A),多階段決策問題的數學模型綜上所述,一類適用于動態(tài)規(guī)劃方法的多階段決策問題的數學模型是如下形式: f1=opt V1n(x1,p1n)最優(yōu)指標函數xk 1=Tk(xk,Uk(xk)狀態(tài)轉移方程ukDk決策變量xkSk狀態(tài)變量k=1,2,n,階段變量,St,上述數學模型表明,對于給定的多得到一個(或多個)最優(yōu)策略或最優(yōu)決策序列u1、u2、un,它不僅滿足左表達式給出的所有約束,而且使左表達式所示的目標函數得到極值。summary :index function form : sum,product,no aftereffect,r
15、ecursion,fk (xk)=vkn (xk,pkn *)=optvkn (xk,pkn),vkn (xk,uk,xk1,uk 1,xn),kxk,Xn),解決多階段決策過程的問題,找出,u1*、u2*、un*、x1*、x2*、xn*、1。劃分階段,2。正確選擇狀態(tài)變量,3。確定決策變量和允許的決策集,4。確定狀態(tài)轉移方程,5。確定階段指標函數和最優(yōu)指標函數,建立靜態(tài)問題應人工給出“時間”的概念,以便劃分階段。在建立動態(tài)規(guī)劃模型的步驟中,狀態(tài)變量的選擇不僅要準確描述過程的演化,而且要滿足無后效的要求,并且每個階段的狀態(tài)變量的值都是可以確定的。通常選擇待解決問題的關鍵變量作為決策變量,并給出決策變量的取值范圍,即確定允許的決策集。根據k階段狀態(tài)變量和決策變量,編寫了k-1階段狀態(tài)變量,狀態(tài)轉移方程應該具有遞歸關系。階段指數函數指的是第k階段的收入,最優(yōu)指數函數指的是從第k階段到第n階段結束所獲得的收入的最優(yōu)值。最后,寫出了動態(tài)規(guī)劃的基本方程。以上五個步驟是建立動態(tài)規(guī)劃數學模型的一般步驟。由于動態(tài)規(guī)劃模型不同于線性規(guī)劃模型,在
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國鹽酸左氧氟沙星片行業(yè)現狀規(guī)模與需求趨勢研究報告
- 2025至2030中國皮褲行業(yè)供需分析及發(fā)展前景報告
- 2025至2030中國環(huán)氧地坪行業(yè)市場發(fā)展分析及發(fā)展趨勢與投資前景預測報告
- 2025至2030中國特色農產品行業(yè)市場占有率及投資前景評估規(guī)劃報告
- 2025特殊危險作業(yè)安全管理培訓
- 推動教育改革建設教育生態(tài)系統(tǒng)
- 醫(yī)療手術中虛擬現實的模擬與輔助
- 打造高效健康宣教體系推動醫(yī)療產品銷售增長
- 技術如何賦能商業(yè)發(fā)展以縮小數字鴻溝
- 基于教育大數據的教學質量提升策略
- 【公開課】三角形的邊+課件+2025-2026學年人教版八年級數學上冊
- 2025年廣東省普通高中學業(yè)水平合格性考試模擬一歷史試題(含答案)
- 【公開課】+分子動理論的初步知識(教學課件)2025-2026學年初中物理人教版(2024)九年級全一冊
- 2025年4月自考03346項目管理試題
- 2024年度醫(yī)患溝通課件
- YY/T 0500-2021心血管植入物血管假體管狀血管移植物和血管補片
- GB 14934-2016食品安全國家標準消毒餐(飲)具
- 后進生轉化情況記錄表2
- 國際節(jié)能效果測量和驗證規(guī)程
- 灌陽地質概況學習教案
- 門式腳手架專項施工方案完成
評論
0/150
提交評論