管理运筹学-动态规划课件.ppt

《管理运筹学-动态规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.1引言7.2基本概念7.3离散确定型典例7.4其他典例第7章动态规划…S’k+1……S27.1.1多阶段决策问题阶段、决策、策略7.1.2动态规划的基本特性一、多阶段决策问题的基本特性7.1引言SkSk+1SnTS’nQ=S1反证法容易得证。若{S2,…,Sk,Sk+1,…,Sn,T}全程最优则{Sk+1,…,Sn,T}子程最优7.1引言二、动态规划方法的基本思路例1最短路问题1234340476117811阶段A124374632441514633334A3B1QA2B2B3TC1C2——标号法三、决策是指人们对某一阶段活动中各种不同的行为或方案或途

2、径等的一种选择。用xk表示第k段的决策，称为第k段决策变量。由于决策随状态而变,所以决策变量xk是状态变量sk的函数,记为xk=xk(sk)7.2基本概念7.2.1动态规划的基本概念一、阶段把所研究的问题恰当的划分成若干个相互联系的阶段。用k=1，2，…，n表示阶段序号，称为阶段变量。二、状态状态表示某段的初始条件。用sk表示第k段的状态，称为第k段状态变量。sk∈Sk∈Xk7.2基本概念四、状态转移方程sk+1与sk,xk之间必须能够建立一种明确的数量对应关系，记为Tk(sk,xk),即有sk+1=Tk(sk,xk)这种明确的数量关系称为状态转移方程。五

3、、策略由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为p1(s1),有p1(s1)={x1(s1),x2(s2),…,xn(sn)}pk(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}∈Pk称为第k子过程策略，简称子策略。∈P1而7.2基本概念六、指标函数(1)阶段指标函数用vk(sk,xk)表示第k段处于sk状态且所作决策为xk时的指标，则它就是第k段指标函数，简记为vk。∈P1(2)过程指标函数用fk(sk,xk)表示第k子过程的指标函数。它是各vk的累积效应。常用函数：fk(sk,xk)=vi(si,xi)ni=kf

4、k(sk,xk)=vi(si,xi)ni=k积函数和函数七、最优解(1)最优指标函数fk*(sk)=opt{fk(sk,pk(sk))},k=1,2,…,npk∈Pk(2)最优策略能使上式成立的子策略pk*称为最优子策略，记为pk*(sk)={xk*(sk),…,xn*(sn)}特别当k=1时,称为最优策略，记为p1*(s1)={x1*(s1),…,xk*(sk),…,xn*(sn)}(3)最优决策构成最优策略的决策称为最优决策，记为xk*。(4)最优值：最优策略对应的最优指标f*17.2基本概念7.2基本概念7.2.2动态规划的基本方程一、最优化原理作

5、为一个全过程最优策略具有这样的性质：无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略。二、函数基本方程f*n+1(sn+1)=0f*k(sk)=opt{vk(sk,xk)+fk+1*(sk+1)}xk∈Xkf*n+1(sn+1)=1f*k(sk)=opt{vk(sk,xk)×fk+1*(sk+1)}xk∈Xk和积k=n,n-1,…,2,1k=n,n-1,…,2,17.2基本概念7.2.3动态规划的基本方法1°建立模型(1)划分阶段，设定k(2)设定状态变量sk(3)设定决策变量xk(4)建立状态转移方程(5)确定指标函数vk，f

6、k*(6)建立函数基本方程2°递推(逆推)求解3°得出(顺推)结论7.2基本概念7.2.4动态规划的基本类型一、按阶段变量k划分(1)定期型:k=1,2,…,n(2)不定期型:k=1,2,…,n(解前未知)(3)无期型:k=1,2,…,n,…二、按状态变量sk划分确定型随机型离散型连续型7.3离散确定型典例7.3.1定价问题例2某厂要确定一种新产品在今后五年内的价格，并已拟定只在5、6、7、8元这四种单价中进行选择。据预测，今后五年不同价格下每年盈利如表所示,但是各相邻年度价格增减不超过1元。问今后五年内每年定价各为多少,可预期五年总利润最大？价格年(元)

7、12345592458675864765973887664盈利：万元7.3离散确定型典例年132价格4556789768255748965676843413141110182223172428283037353638p1*={8,8,7,6,5}(元)f*1=38万元7.3离散确定型典例7.3.2资源分配问题例3某厂为扩大生产能力，拟定购某种成套设备4~6套,以分配给其所辖三个分厂使用。预计各分厂分得不同套数的设备后每年创造的利润如下表所示。该厂应订购几套设备并如何分配，才能使每年预计创利总额最大？盈利：万元套数分厂01234561035676520467

8、8910302598877.3离散确定型典例解1.建立DP模型以k