管理运筹学-动态规划

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

1、第7章DynamicProgrammingDP动态规划1第7章动态规划7.1引言7.2基本概念7.3离散确定型典例7.4其他典例第7章动态规划2第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}子程最优3第7章动态规划7.1引言二、动态规划方法的基本思路例1最短路问题1234340476117811阶段A124374632441514633334A3B

2、1QA2B2B3TC1C2——标号法4第7章动态规划三、决策是指人们对某一阶段活动中各种不同的行为或方案或途径等的一种选择。用xk表示第k段的决策，称为第k段决策变量。由于决策随状态而变,所以决策变量xk是状态变量sk的函数,记为xk=xk(sk)7.2基本概念7.2.1动态规划的基本概念一、阶段把所研究的问题恰当的划分成若干个相互联系的阶段。用k=1，2，…，n表示阶段序号，称为阶段变量。二、状态状态表示某段的初始条件。用sk表示第k段的状态，称为第k段状态变量。sk∈Sk∈Xk5第7章动态规划7.2基本概念四、状态转移方程sk+1与sk,xk之间必须能够建立一种

3、明确的数量对应关系，记为Tk(sk,xk),即有sk+1=Tk(sk,xk)这种明确的数量关系称为状态转移方程。五、策略由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为p1(s1),有p1(s1)={x1(s1),x2(s2),…,xn(sn)}pk(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}∈Pk称为第k子过程策略，简称子策略。∈P1而6第7章动态规划7.2基本概念六、指标函数(1)阶段指标函数用vk(sk,xk)表示第k段处于sk状态且所作决策为xk时的指标，则它就是第k段指标函数，简记为vk。∈P1(2)过程指标函数用fk(

4、sk,xk)表示第k子过程的指标函数。它是各vk的累积效应。常用函数：fk(sk,xk)=vi(si,xi)ni=kfk(sk,xk)=vi(si,xi)ni=k积函数和函数7第7章动态规划七、最优解(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)最优决策构成最优策略的决策称为最优决策，

5、记为xk*。(4)最优值：最优策略对应的最优指标f*17.2基本概念8第7章动态规划7.2基本概念7.2.2动态规划的基本方程一、最优化原理作为一个全过程最优策略具有这样的性质：无论过去的状态和决策如何，对前面所形成的状态而言，余下的诸决策必构成最优策略。二、函数基本方程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,19第7章动态规划7.2基本概念7.2

6、.3动态规划的基本方法1°建立模型(1)划分阶段，设定k(2)设定状态变量sk(3)设定决策变量xk(4)建立状态转移方程(5)确定指标函数vk，fk*(6)建立函数基本方程2°递推(逆推)求解3°得出(顺推)结论10第7章动态规划7.2基本概念7.2.4动态规划的基本类型一、按阶段变量k划分(1)定期型:k=1,2,…,n(2)不定期型:k=1,2,…,n(解前未知)(3)无期型:k=1,2,…,n,…二、按状态变量sk划分确定型随机型离散型连续型11第7章动态规划7.3离散确定型典例7.3.1定价问题例2某厂要确定一种新产品在今后五年内的价格，并已拟定只在5、6

7、、7、8元这四种单价中进行选择。据预测，今后五年不同价格下每年盈利如表所示,但是各相邻年度价格增减不超过1元。问今后五年内每年定价各为多少,可预期五年总利润最大？价格年(元)12345592458675864765973887664盈利：万元12第7章动态规划7.3离散确定型典例年132价格4556789768255748965676843413141110182223172428283037353638p1*={8,8,7,6,5}(元)f*1=38万元13第7章动态规划7.3离散确定型典例7.3.2资源分配问题例3某厂为扩大生产能力，拟定购某种成套设备4~6