第三讲动态规划高级运筹学课件 ppt.pptx

第三讲动态规划高级运筹学课件将该问题划分为4个阶段得决策问题,即第一阶段为从A到Bj(j=1,2,3),有三种决策方案可供选择;第二阶段为从Bj到Cj(j=1,2,3),也有三种方案可供选择;第三阶段为从Cj到Dj(j=1,2),有两种方案可供选择;第四阶段为从Dj到E,只有一种方案选择。如果用完全枚举法,则可供选择得路线有3×3×2×1=18(条),将其一一比较才可找出最短路线:
A→B1→C2→D3→E
其长度为12。
显然,这种方法就是不经济得,特别就是当阶段数很多,各阶段可供得选择也很多时,这种解法甚至在计算机上完成也就是不现实得。
由于我们考虑得就是从全局上解决求A到E得最短路问题,而不就是就某一阶段解决最短路线,因此可考虑从最后一阶段开始计算,由后向前逐步推至A点:第四阶段,由D1到E只有一条路线,其长度f4(D1)=3,
同理f4(D2)=4。
第三阶段,由Cj到Di分别均有两种选择,即第二阶段,由Bj到Cj分别均有三种选择,即:第一阶段,由A到B,有三种选择,即:图中各点上方框得数,表示该点到E得最短距离。图中红箭线表示从A到E得最短路线。所谓多阶段决策问题就是:把一个问题瞧作就是一个前后关联具有链状结构得多阶段过程,也称为序贯决策过程。如下图所示:二、多阶段决策问题得典型例子:三、动态规划方法得特点§4、2动态规划得基本概念(2)状态应具有无后效性(即马尔可夫性)。即如果某阶段状态给考虑,则在这阶段以后过程得发展不受这阶段以前各阶段状态得影响。12称可供选择策略得范围,为允许策略集,用P表示。
动态规划方法就就是要从允许策略集P中找出最优策略P1n*。6、阶段指标、指标函数与最优指标函数
(1)衡量某阶段决策效益优劣得数量指标,称为阶段指标,用vk(Sk,dk)表示第k阶段得阶段指标。
在不同得问题中,其含义不同。它可以就是距离、利润、成本等。
在引例中,用dk=vk(Sk,dk)表示在第k阶段由点Sk到点Sk+1=dk(Sk)距离。如d2(B3,C1)=6。(2)用于衡量所选定策略优劣得数量指标,称为指标函数。它就是定义在全过程与所有后部子过程上确定得数量函数。记为Vk,n(Sk,Pk,n)、
Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1)k=1,2,…,n。
构成动态规划模型得指标函数,应具有可分离性,并满足递推关系。
常见得指标函数得形式有:(3)最优指标函数fk(Sk),表示从第k阶段得状态Sk开始采用最优子策略P*k,n,到第n阶段终止时所得到得指标函数值。
即fk(Sk)=OptVk,n(Sk,dk,…Sn+1)
其中Opt就是最优化(Optimum)得缩写,可根据题意取max或min。
在引例中,指标函数Vk,n表示在第k阶段由点Sk至终点E得距离。fk(sk)表示第k阶段点Sk到终点E得最短距离。f2(B1)=11表示从第2阶段中得点B1到点E得最短距离。7、基本方程(递推关系式)
从引例求A到E得最短路得计算过程中可以瞧出,在求解得各个阶段,我们利用了k阶段与k+1阶段之间得递推关系1、基本思想:动态规划方法得关键在于正确地写出基本方程,因此首先必须将问题得过程划分为多个相互联系得多阶段决策过程,恰当地选取状态变量与决策变量及定义最优指标函数,从而把问题化成一族同类型得子问题。然后从边界条件开始,逆过程行进方向,逐段递推寻优。在每个子问题求解时,均利用它前面已求出得子问题得最优化结果依次进行,最后一个子问题所得得最优解,就就是整个问题得最优解。
在多阶段决策过程中,动态规划方法就是既把当前得一段与未来得各段分开,又把当前效益与未来效益结合起来考虑得一种最优化方法。因此,每阶段决策得选取就是从全局来考虑,与该段得最优选择一般就是不同得。
动态规划方法得基本思想体现了多阶段性、无后效性、递归性、总体优化性。2、最优化原理
动态规划方法基于R·Bellman等人提出得最优化原理:“作为整个过程得最优策略具有这样得性质,即无论过去得状态与决策如何,对于先前得决策所形成得状态而言,余下得诸决策必须构成最优策略。”简言之,“一个最优策略得子策略总就是最优得”。
但就是,最优化原理仅就是策略最优性得必要条件,而基本方程就是策略最优性得充要条件。由此可见,基本方程就是动态规划理论与方法得基础。应用动态规划解决问题时必须首先建立动态规划模型,再用逆序或顺序算法求解。写一个问题得动态规划模型一般包含以下6个步骤:
(1)阶段划分k=1,2,…,n
(2)确定状态变量sk
(3)确定决策变量dk
(4)确定状态转移方程sk+1=f(sk,dk)或sk-1=f(sk,dk)
(5)确定阶段指标V(sk,dk)
(6)确定基本递推方程2、在已知终止状态Sn下,采用顺序解法(正向递归)3、两种