管理运筹学课件第9章动态规划.ppt

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

1、第9章动态规划8/17/20211课件教学目标与要求【教学目标】1.理解下列基本概念：状态变量，决策变量，策略，状态转移方程，指标函数和最优值函数2.理解动态规划的基本方程和最优化原理3.理解动态规划模型建立过程5.掌握顺序算法与逆序算法解题方法【知识结构】8/17/20212课件[引例]马车驿站问题124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段44个阶段EED1D2D1D2D1D2D1D2C2C3C4C1C2C31D1E1D2E2C4D1C4D22C3D1

2、C3D22C2D1C2D22C1D1C1D23B2C2B2C3B2C43B1C1B1C2B1C3B1B22AB1AB2AB2B1C4C3C2C1D1D24321终点路线数可选路线起点阶段一共有2×3×2×1=12条不同的路线f(E)=0f(D1)=2f(D2)=1f(C1)=8f(C2)=5f(C3)=4f(C1)=5f(B1)=8f(B2)=11f(A)=13回顾分析过程:1.将分析对象划分成4阶段;2.每阶段始点状态与终点状态有关,而不考虑始终点状态如何形成(无记忆性);3.每阶段各始点状态为终点状态与始点至终点距离

3、之和的最小值(状态转移)这种最优化方法称为动态规划,由美国数学家贝尔曼等人于20世纪50年代创立.8/17/20213课件本章主要内容9.1动态规划的概念和原理9.1.1动态规划的基本概念9.1.2动态规划的最优化原理9.2动态规划的模型和求解9.2.1动态规划模型的建立9.2.2动态规划问题的解法9.3应用举例案例1资源分配问题案例2设备负荷问题案例3生产库存问题案例4背包问题本章小结8/17/20214课件9.1.1动态规划的基本概念1.阶段:把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量

4、，常用k表示。[导入案例]中k=1,2,3,42.状态变量:每个阶段开始所处的自然状况或客观条件(用点集表示).如引例:第1阶段的状态就是起点A,记为s1={A};第2阶段有2个状态{B1,B2},记为s2={B1,B2};第3阶段有4个状态{C1,C2,C3,C4},记为s3={C1,C2,C3,C4};第4阶段有2个状态{D1,D2},记为s4={D1,D2};3.决策变量:在某一阶段的某个状态时的不同选择,如引例中B1状态下有3种选择:B1—C1,B1—C2,B1—C3这3种选择构成了允许决策的集合。不同状态下允许决策的集合也不同，故

5、决策变量是状态变量的函数，即xk(sk)∈D(sk)124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段44个阶段4.策略按顺序排列的决策组成的集合，由过程的第k阶段开始到终止状态为止的过程(或k子过程),k子过程的策略称子策略，记为Pk,n(sk),即Pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}当k=1时，即为全过程的一个策略。如引例中：D—E，即4到5过程起始有2个状态，D1和D2，因此有P4,5={D1—E，D2—E}5.状态转移方程确定过程是由一个状态

6、到另一个状态的演变过程。第k阶段状态变量值给定后，如果确定决策变量，第k+1阶段状态变量值就完全确定。即：sk+1=T(sk,xk)如引例中：若对A—B1,A—B2选择了A—B1,则s2=5,B1到C有3种选择:B1—C1、B1—C2、B1—C3，若选择了B1—C2,则s3=s2+d(B1,C2)=86.指标函数用来衡量所实现过程优劣的一种数量指标。其基本方程有加法和乘法两种形式，通常加法形式用的较多，其公式为：7.边界条件起始或终止条件。8/17/20215课件5.1.2动态规划的基本原理124833538667863235AB2B1D2D1C3

7、C2C4C1EA—B—C—D—E阶段1阶段2阶段3阶段44个阶段最优化原理(Optimalityprinciple):最优策略具备这样的性质:无论初始状态与初始决策如何,以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言,必然构成最优策策略.通俗地说:最优策略的子策略也是最优的.例如，在导入案例中，最优策略是A—B1—C2—D1—E,最短距离为13,其子策略:B1—C2—D1—E,C2—D1—E,D1—E也是最优的。依据这一原理，从后往前推各阶段最优子过程，从而得到全程最优过程。设f(i)表示从点i到终点E的最短距离,d(i,j)表示点i

8、,j之间的距离.显然f(E)=0,为该问题的边界条件.k=4决策：D1Ek=3决策：D2E决策：C1D1决策：C2