《動態(tài)規(guī)劃方法》PPT課件

《《動態(tài)規(guī)劃方法》PPT課件》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、數(shù)學建模方法及其應用韓中庚編著數(shù)學建模教學片第十三章動態(tài)規(guī)劃方法設計制作：主要內容第十三章動態(tài)規(guī)劃方法32021年10月6日動態(tài)規(guī)劃的基本問題；動態(tài)規(guī)劃的基本概念與條件；動態(tài)規(guī)劃的基本方程；動態(tài)規(guī)劃的求解方法；動態(tài)規(guī)劃的應用案例分析。一、動態(tài)規(guī)劃的一般問題42021年10月6日動態(tài)規(guī)劃（DP)是一種用于處理多階段決策問題的數(shù)學方法。主要是先將一個復雜的問題分解成相互聯(lián)系的若干階段，每個階段即為一個小問題，然后逐個解決，當每個階段的決策確定之后，整個過程的決策也就確定了。階段一般用時間段表示(即與時間有關)，這就是“動態(tài)”的含義，把這種處理問題的方法稱為動態(tài)規(guī)劃方法。52

2、021年10月6日1.引例：最短路線問題(1)問題的提出62021年10月6日(2)問題的分析1.引例：最短路線問題72021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮1.引例：最短路線問題82021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮92021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮102021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮112021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮（4)求四個階段最優(yōu)選擇：122021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮132021年10月6日2.用動態(tài)規(guī)劃的方法分步考慮14資源分配問題（背包問題）資源分配問題是動態(tài)規(guī)劃的典

3、型問題之一，它的一般提法是：有某種資源，總量為a，用于n個項目，若分配數(shù)量ui用于第i個項目，則第i個項目所產生的效果（收益）為gi（ui）。問題是如何分配資源總量a才能獲得n個項目所產生的總效果（收益）最優(yōu)（max）？靜態(tài)規(guī)劃問題maxZ=g1（u1）+g2（u2）+…+gn（un）u1+u2+…+un≤（=）aui≥015例1某公司新引進了6臺高效率生產設備，該設備可用于生產4種不同的產品，當生產每種產品所投入的設備數(shù)量不同時所帶來的利潤也不相同。其詳細資料如下：利潤表單位：萬元設備數(shù)量4種產品產品1產品2產品3產品4012345602042607585900254

4、55765707301839617890950284765748085162021年10月6日二.動態(tài)規(guī)劃的基本概念與條件1.動態(tài)規(guī)劃的基本概念(1)階段（stage）和階段變量階段是指一個問題需要作出決策的步驟，即把問題的過程分為若干個相互聯(lián)系的階段，使能按階段的次序求解。描述階段的變量稱為階段變量,常用k表示。172021年10月6日在多階段決策過程中，每一階段都具有一些特征（自然狀況，或客觀條件），這就是狀態(tài)，用來描述狀態(tài)的變量稱為狀態(tài)變量。(2)狀態(tài)與狀態(tài)變量182021年10月6日(3)決策和決策變量19(3)決策(decision)表示在某一階段處于某種狀態(tài)

5、時，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值范圍稱為決策集，用Dk(sk)表示。T1s1s2v1u1T2s3v2u2Tksksk+1vkukTnsnsn+1vnun……多階段決策過程如下：202021年10月6日策略是一個按順序排列的決策組成的集合。(4)策略與子策略212021年10月6日(4)策略與子策略222021年10月6日狀態(tài)函數(shù)是在確定多階段決策過程中，由一個狀態(tài)到另個狀態(tài)的演變過程。(5)狀態(tài)轉移函數(shù)23(5)狀態(tài)轉移方程(6)指標函數(shù)和最優(yōu)值函數(shù)指標函數(shù)分為階段指標函數(shù)和過程指標函數(shù)。階

6、段指標函數(shù)是對某一階段的狀態(tài)和決策產生的效益值的度量,用vk(sk,uk)表示。若第k階段的狀態(tài)變量值為sk，當決策變量uk的取值決定后，下一階段狀態(tài)變量sk+1的值也就完全確定。即sk+1的值對應于sk和uk的值。這種對應關系記為:sk+1=Tk(sk,uk)稱為狀態(tài)轉移方程。狀態(tài)轉移方程描述了由一個階段的狀態(tài)到下一階段的狀態(tài)的演變規(guī)律。242021年10月6日在多階段決策過程中，用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)。(6)指標函數(shù)（回收函數(shù)）252021年10月6日常見的兩種指標函數(shù)262021年10月6日常見的兩種指標函數(shù)272021年10月6日(7

7、)最優(yōu)值函數(shù)282021年10月6日2.動態(tài)規(guī)劃的基本條件二.動態(tài)規(guī)劃的基本概念與條件*無后效性：如果某階段狀態(tài)已給定，則以后過程的發(fā)展不受以前各階段狀態(tài)的影響，也就是說當前狀態(tài)就是未來過程的初始狀態(tài)；**可知性：規(guī)定的各階段狀態(tài)變量的值，由直接或間接都是可以知道的。292021年10月6日2.動態(tài)規(guī)劃的基本條件1)它是過程各階段狀態(tài)變量和決策變量的函數(shù)；301)加法型逆序法:三.動態(tài)規(guī)劃的基本方程31其中：fk(sk)表示第k階段初始狀態(tài)為sk時，k后部子過程的最優(yōu)值函數(shù)。狀態(tài)轉移方程：（邊界條件）k=1,2,…,n由此得加法型逆序算法