動態(tài)規(guī)劃課件

1、1.5 動態(tài)規(guī)劃動態(tài)規(guī)劃是一類多階段決策過程的最優(yōu)化方法?；痉椒ㄊ牵喊措A段把一個大問題化成一系列相互有聯(lián)系的子問題，建立相應(yīng)的遞推公式，解一系列的子問題，最后求得整個問題的最優(yōu)解。例 最短路問題一、動態(tài)規(guī)劃的基本概念和基本方法7117846340111234階段從A到E的路有：求A到E的最短路。457891012131. 概念 階段：根據(jù)時間或空間劃分。 狀態(tài)：某階段出發(fā)的位置。既是某支路本階段的起點，又是前一階段的終點。本例按空間分成4個階段本例4個階段的狀態(tài)集： 狀態(tài)變量 sk :描述狀態(tài)的變量。# 決策：從給定狀態(tài)到下一階段某狀態(tài)的選擇。 決策變量 xk=xk(sk)：描述決策的變量。

2、如：有：容許決策集合 狀態(tài)轉(zhuǎn)移方程：描述狀態(tài)轉(zhuǎn)移規(guī)律的函數(shù)關(guān)系 策略：決策序列24 目標(biāo)（指標(biāo)）函數(shù)：衡量策略好壞的函數(shù)。從 出發(fā)到終點的目標(biāo)函數(shù)記為：視 為確定狀態(tài)， 是變化的。 從 出發(fā)到終點的最優(yōu)目標(biāo)值：例中：為A 到E 的最短路程，相應(yīng)的策略為所求的最優(yōu)策略 最短路。對應(yīng)的策略為 到終點最優(yōu)子策略。262. 最優(yōu)化原理例中：有最優(yōu)策略即A到E的最短路，路長為子策略： B2到E的最短路，路長為 C1到E的最短路，路長為27#利用該原理得尋優(yōu)方法：問題：子問題：行進(jìn)方向?qū)?yōu)方向先求出“最小子問題”中，各狀態(tài)到E的最優(yōu)子策略，將問題化成一系列相互有聯(lián)系的子問題，再求出“次小子問題”中（第3階

3、段），各狀態(tài)到 E的最優(yōu)子策略，如此向前推進(jìn)，而每次都利用后部子問題中已得到的最優(yōu)子策略。如：已得C1到E的最優(yōu)子策略：在求B2到E的最佳走法時，如果該階段取29則后面的最佳走法是：即得最優(yōu)子策略：在第1階段，若取 ，則得A到E的最佳走法：如果是 ，則利用B1到E的最佳走法得：或 減少了計算量，即不必再驗證后面走法的最優(yōu)性； 豐富了結(jié)果，即得從任何一點出發(fā)到終點的最短路。2103. 動態(tài)規(guī)劃的數(shù)學(xué)模型根據(jù)最優(yōu)化原理，可得 從 出發(fā)到終點的最優(yōu)目標(biāo)值：例中，211最短路問題的解 （列表）第4階段：第3階段：212第2階段：第1階段： 最優(yōu)策略：路長：213二、應(yīng)用根據(jù)問題的特點，確定：階段、狀態(tài)

4、變量、決策變量、狀態(tài)轉(zhuǎn)移方程、目標(biāo)函數(shù)遞推公式。例 （例1.7） （生產(chǎn)存儲問題）用動態(tài)規(guī)劃方法求解。解假設(shè)與例1.7同月份單位成本(元)銷售量(件)按月份分4個階段；（1）. 建模K=3:求X3:X3的增函數(shù)從而得：故K=2:可得K=1:（3）靈敏度分析如: 2月份的庫存損失了20件（即s2=20），則 24 月份的最優(yōu)生產(chǎn)計劃如下：費用增加：又如：2月份出現(xiàn)10件廢品（ x2=90,s3=60），類似可求3、4月份的最優(yōu)生產(chǎn)計劃。注: 當(dāng)目標(biāo)函數(shù)是線性函數(shù)或二次函數(shù)等簡單函數(shù)時， 容易求出 的表達(dá)式，否則可求數(shù)值解。（2）當(dāng) 取少數(shù)離散值時，可列表計算。如上例中還要求每10個產(chǎn)品為一批地生

5、產(chǎn)，則 、 的可能取值為0、10、20、100這些離散值。2. 一維資源分配問題a 資源總量 第k個使用者的效益數(shù)學(xué)規(guī)劃模型：總效益化為動態(tài)規(guī)劃模型：xk 分配給第 k個使用者的資源量關(guān)鍵求：階段，狀態(tài)變量，決策變量，狀態(tài)轉(zhuǎn)移方程。階段 將資源分配給一個使用者視為一個階段，決策變量：xk 分配給第 k個使用者的資源量狀態(tài)變量：sk 前k-1個使用者分配后的剩余量即狀態(tài)轉(zhuǎn)移方程：使用者：資源量：狀態(tài)變量：允許決策集合：報酬函數(shù)：動態(tài)規(guī)劃模型：效益函數(shù)一般是增函數(shù)注：若原目標(biāo)函數(shù)為連乘積則動態(tài)規(guī)劃目標(biāo)函數(shù)為：例（P.41）如何分配2萬元補(bǔ)加研制費，使三種新產(chǎn)品都不成功的概率最小。有關(guān)數(shù)據(jù)如表。產(chǎn)品研制費不