動態(tài)規(guī)劃的基本概念和基本定.ppt

p13-1,引言,動態(tài)規(guī)劃(Dynamic Programming)是解決多階段決策問題 最優(yōu)化的一種數(shù)學方法. 1951年, 美國數(shù)學家貝爾曼(R. Bellman)等人提出了“最優(yōu) 化原理”,把多階段決策問題變換為一系列相互聯(lián)系的單階 段決策問題，逐階段加以求解, 創(chuàng)建了動態(tài)規(guī)劃方法. 名著動態(tài)規(guī)劃于1957年出版, 是該領域的第一本著作. 動態(tài)規(guī)劃應用廣泛. 如求解最短路問題、生產(chǎn)計劃問題、存 儲問題、資源分配問題、推銷商問題等.,第11章 動態(tài)規(guī)劃的基本概念和基本定理,p13-2, 動態(tài)決策問題分類 1. 按數(shù)據(jù)給出的形式分為： 離散型動態(tài)決策問題 連續(xù)型動態(tài)決策問題 2. 按決策過程演變的性質(zhì)分為： 確定型動態(tài)決策問題 隨機型動態(tài)決策問題,引言,第11章 動態(tài)規(guī)劃的基本概念和基本定理,p13-3,11.2 動態(tài)規(guī)劃的基本概念和模型構成,一、動態(tài)規(guī)劃的基本概念 以求最短路為例,1. 階段（stage） 通常根據(jù)時間順序或空間特征把所給問題的全過程恰當?shù)胤?為若干個相互聯(lián)系的階段, 以便按階段的次序逐段解決整個 過程的優(yōu)化問題.,p13-4,一、動態(tài)規(guī)劃的基本概念 以求最短路為例,1. 階段（stage） 通常根據(jù)時間順序或空間特征把所給問題的全過程恰當?shù)胤?為若干個相互聯(lián)系的階段, 以便按階段的次序逐段解決整個過程的優(yōu)化問題.,描述階段的變量稱為階段變量, 通常用 k 表示, k = 1 , , n,p13-5,一、動態(tài)規(guī)劃的基本概念,1. 階段（stage） 通常根據(jù)時間順序或空間特征把所給問題的全過程恰當?shù)胤?為若干個相互聯(lián)系的階段, 以便按階段的次序逐段解決整個過程的優(yōu)化問題.,描述階段的變量稱為階段變量, 用 k 表示, k = 1 , , n,2. 狀態(tài)（state） 描述每個階段開始時所處的自然狀況或客觀條件. 描述狀態(tài)的變量稱為狀態(tài)變量, 用 xk表示第 k 階段的狀態(tài)變 量. 第 k 階段所有狀態(tài)的集合稱為第 k 階段可達狀態(tài)的集合, 用 Xk表示. 如X3= C1 ,C2 ,C3,p13-6,一、動態(tài)規(guī)劃的基本概念,1. 階段（stage）,2. 狀態(tài)（state） 描述每個階段開始時所處的自然狀況或客觀條件. 描述狀態(tài)的變量稱為狀態(tài)變量, 用 xk表示第 k 階段的狀態(tài)變 量. 第 k 階段所有狀態(tài)的集合稱為第 k 階段可達狀態(tài)集合, 用 Xk表示. 如X3= C1 ,C2 ,C3,3. 決策（decision） 決策的實質(zhì)是關于狀態(tài)的選擇, 是從一個階段某狀態(tài)演變到 下一個階段某狀態(tài)的選擇. 決策變量 uk(xk) , 如u2(B1) =C2,p13-7,一、動態(tài)規(guī)劃的基本概念,1. 階段（stage）,2. 狀態(tài)（state）,3. 決策（decision） 決策的實質(zhì)是關于狀態(tài)的選擇, 是從一個階段某狀態(tài)演變到 下一個階段某狀態(tài)的選擇.,4. 策略（policy） 策略也叫決策序列. 從第1階段至第n階段的一個策略稱為全過程子策略, 簡稱策略, 記作p1,n(x1). 從第k階段至第n階段的一個策略稱為后部子策略, 記作pk,n(xk).,p13-8,一、動態(tài)規(guī)劃的基本概念,1. 階段（stage）,2. 狀態(tài)（state）,3. 決策（decision）,4. 策略（policy） 全過程子策略, 簡稱策略,記作p1,n(x1). 后部子策略, 記作pk,n(xk).,5. 指標函數(shù)（objective function） 用來衡量決策或策略效果的某種數(shù)量指標, 稱為指標函數(shù). 第k階段的指標函數(shù)記作 vk(xk,uk,). 從第k階段至第n階段的指標函數(shù)記作 Vk,n(xk , pk,n). 從第1階段至第n階段的指標函數(shù)記作 V1,n(x1 , p1,n).,p13-9,一、動態(tài)規(guī)劃的基本概念,1. 階段（stage）,2. 狀態(tài)（state）,3. 決策（decision）,4. 策略（policy）,5. 指標函數(shù)（objective function） 用來衡量決策或策略效果的某種數(shù)量指標, 稱為指標函數(shù). 第k階段的指標函數(shù)記作 vk(xk,uk,). 從第k階段至第n階段的指標函數(shù)記作 Vk,n(xk , pk,n). 從第1階段至第n階段的指標函數(shù)記作 V1,n(x1 , p1,n).,指標函數(shù)的最優(yōu)值稱為最優(yōu)指標函數(shù), 記作 fk(xk)或 f1(x1).,二、動態(tài)規(guī)劃的模型構成,1. 正確選擇階段變量k; 2. 正確選擇狀態(tài)變量xk要保證無后效性, 即某階段的狀 態(tài)一旦確定, 則此后過程的演變不受此前各狀態(tài)及決策的 影響; 3. 正確選擇決策變量uk; 4. 列出狀態(tài)轉(zhuǎn)移方程xk+1= Tk(xk, uk); 5. 列出指標函數(shù)Vk,n要滿足按階段可分性, 并滿足遞推關系 Vk,n= Vk,n(xk, pk,n)= vk(xk,uk,)+ Vk+1,n(xk+1, pk+1,n),p13-11,11.3 基本理論和基本方程,一、最優(yōu)化原理 最優(yōu)策略的任一后部子策略都是最優(yōu)的.,二、基本方程 1. 逆序遞推的基本方程(以求min為例),式中xk+1=Tk(xk, uk).,p13-12,11.3 基本理論和基本方程,一、最優(yōu)化原理 最優(yōu)策略的任一后部子策略都是最優(yōu)的.,二、基本方程 2. 順序遞推的基本方程(以求min為例),式中xk=Tk(xk+1, uk).,p13-13,12.1 生產(chǎn)與存儲問題,例 某廠生產(chǎn)某種產(chǎn)品，每千件的成本費為2千元；每季度開工的固定費用為3千元，第1、2、3季度市場對該產(chǎn)品的需求量分別為2、4、2千件，工廠每一季度的最大生產(chǎn)能力為6千件，設每季度每千件的存儲費為1千元（按每季度初的庫存量計算存儲費），還規(guī)定年初和第3季度末無庫存。問：如何安排各季度的產(chǎn)量，使全年的總費用最?。?p13-14,補充: 機器任務分配問題,例 某工廠有200臺機器,擬分4個周期使用，在每一周期有兩種 生產(chǎn)任務. 若機器投入第一種生產(chǎn)任