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

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

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

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

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

4、55765707301839617890950284765748085162021年10月6日二.動(dòng)態(tài)規(guī)劃的基本概念與條件1.動(dòng)態(tài)規(guī)劃的基本概念(1)階段（stage）和階段變量階段是指一個(gè)問題需要作出決策的步驟，即把問題的過程分為若干個(gè)相互聯(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、時(shí)，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值范圍稱為決策集，用Dk(sk)表示。T1s1s2v1u1T2s3v2u2Tksksk+1vkukTnsnsn+1vnun……多階段決策過程如下：202021年10月6日策略是一個(gè)按順序排列的決策組成的集合。(4)策略與子策略212021年10月6日(4)策略與子策略222021年10月6日狀態(tài)函數(shù)是在確定多階段決策過程中，由一個(gè)狀態(tài)到另個(gè)狀態(tài)的演變過程。(5)狀態(tài)轉(zhuǎn)移函數(shù)23(5)狀態(tài)轉(zhuǎn)移方程(6)指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。階

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

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