運籌學7動態(tài)規(guī)劃課件

第七章動態(tài)規(guī)劃主要內容:71多階段決過程的量優(yōu)化動態(tài)的基本念和基本原求解74動應器教學要求1.掌握動態(tài)規(guī)劃的基本概念:階段、狀態(tài)、決策、策略、狀夵轉移方程、指標函數(shù)和最優(yōu)值函數(shù)、最優(yōu)策略L線2.了解動態(tài)規(guī)劃的基本理論:最優(yōu)性定理和最優(yōu)性原理3.掌握動態(tài)規(guī)劃基本思想和基本方程4.牢固掌握動態(tài)規(guī)劃的順序解法和逆序解法。會處理動態(tài)與靜態(tài)規(guī)劃的關系5.了解和掌握若干典型問題的動態(tài)規(guī)劃模型及求解技巧:如最短路線、資源分配、生產計劃、貨物存儲設備更新與系統(tǒng)可靠性問題、背包問題、推銷商問題6.了解多維動態(tài)規(guī)劃降維方法和減少離散狀態(tài)點數(shù)方法7.了解隨機性問題的動態(tài)規(guī)劃求解方法重點:動態(tài)規(guī)劃順序解法和逆序解法;若干典型問題動態(tài)規(guī)劃模型及求解技巧;難點:建立動態(tài)規(guī)劃數(shù)學模型的狀態(tài)轉移方程。87.1多階段決策過程的最優(yōu)化動態(tài)規(guī)劃(DynamicProgramming)是運籌學的一個重要分支,它是解決多階段決策過程最優(yōu)化的一種方法。美國數(shù)學家貝爾曼(RE.Bellman)等人在50年代初提出了解決多階段決策問題的“最優(yōu)性原理”(PrincipleofOptimality)。1957年貝爾曼出版了專著“動態(tài)規(guī)劃”,該書是動態(tài)規(guī)劃的第一本著作。目前動態(tài)規(guī)劃已經用于解決最優(yōu)路徑問題、資源分配問題、生產調度問題、設備更新問題、復合系統(tǒng)可靠性問題及生產過程最優(yōu)控制等,并且取得了顯著的效果回本章目錄動態(tài)規(guī)劃是求解問題的一種方法,而不是算法(線性規(guī)劃是一種算法),因而沒有標準的數(shù)學表達式,對于具體問題需要具體分析。、多階段決策問題在生產經營活動中,某些問題決策過程可以劃分為若于相互聯(lián)系的階段,每個階段需要做出決策,從而使整個過程取得最優(yōu)。由于各個階段不是孤立的,而是有機聯(lián)系的,也就是說,本階段的決策將影響過程下一階段的發(fā)展從而影響整個過程效果,所以決策者在進行決策時不能夠僅考慮選擇的決策方案使本階段最優(yōu),還應該考慮本階段決策對最終目標產生的影響,從而做出對全局來講是最優(yōu)的決策。當每個階段的決策確定以后,全部過程的決策就是這些階段決策所組成的一個決策序列,所以多階段決策趣也稱為序貫決策問題。決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策多階段決策問題中,各個階段一般是按照時間來劃分的,隨著時間的發(fā)展而產生各個階段的決策,從而形成決策序列,這就是動態(tài)的含義。在一些與時間無關的靜態(tài)問題中(如非線性規(guī)劃等),可以人為地賦予時間的概念,使其成為一個多階段決策問題,再用動態(tài)規(guī)劃方法處理二、多階段決策問題舉例屬于多階段決策類的問題很多,例如例1工廠生產過程:由于市場需求是隨著時間而變化的因素,因此,為了取得全年最佳經濟效益,就要在全年的生產過程中,逐月或者還季度地根據庫存和需求情況決定生產計劃安排例2設備更新問題:一般企業(yè)用于生產活動的設備,剛買來時故障少,經濟效益高,即使進行轉讓,處理價值也高,隨著使用年限的增加,就會逐漸變?yōu)楣收隙?維修費用增加,可正常使用的工時減少,加工質量下降,經濟效益差,并且,使用的年限越長、處理價值也越低,自然,如果賣去舊的買新的,還需要付出更新費.因此就需要綜合權衡決定設備的使用年限,使總的經濟效益最好。例3連續(xù)生產過程的控制問題:一般化工生產過程中,常包含一系列完成生產過程的設備,前一工序設備的輸出則是后一工序設備的輸入,因此,應該如何