运筹说 第67期 | 动态规划模型的建立与求解

这篇具有很好参考价值的文章主要介绍了运筹说 第67期 | 动态规划模型的建立与求解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

通过前一期的学习,我们已经学会了动态规划的基本概念和基本原理。本期小编带大家学习动态规划模型的建立与求解。

动态规划模型的建立

 概述

建立动态规划的模型,就是分析问题并建立问题的动态规划基本方程。

成功地应用动态规划方法的关键,在于识别问题的多阶段特征,将问题分解成为可用递推关系式联系起来的若干子问题,而正确建立基本递推关系方程的关键又在于正确选择状态变量,保证各阶段的状态变量具有递推的状态转移关系运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

 例题展示

接下来小编将以资源分配问题为例介绍动态规划的建模条件及解法,详见例1。资源分配问题是动态规划的典型应用之一,资源可以是资金、原材料、设备、劳力等,资源分配就是将一定数量的一种或几种资源恰当地分配给若干使用者,以获取最大效益。

例1:某公司有资金10万元,若投资于项目的投资额为时,其收益分别为,问应如何分配投资数额才能使总收益最大?

首先这是一个与时间无明显关系的静态最优化问题,可列出其静态模型:

求,使运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法,且满足约束

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

为了应用动态规划方法求解,可以人为地赋予它“时段”的概念。将投资项目排序,依次对项目1、2、3投资,即把问题划分为3个阶段,每个阶段只决定对一个项目应投资的金额,从而转化为一个3段决策过程。通常可以把决策变量定为原静态问题中的变量  ,即设

状态变量和决策变量有密切关系,状态变量一般为累计量或随递推过程变化的量。针对本例,可以把每阶段可供使用的资金定为状态变量,初始状态。为可分配用于第一种项目的最大资金,则当第一阶段(k=1)时,有运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

第二阶段(k=2)时,状态变量为余下可投资于其余两个项目的资金,即运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

一般地,当第k段时运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

于是有

阶段k:本例中取1,2,3。

状态变量:第k段可以投资于第k项到第3个项目的资金。

决策变量 :决定给第k个项目投资的资金。

状态转移方程:运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

指标函数:

最优指标函数 :当可投资金为时,投资第k-3项所得的最大收益。

基本方程为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

用动态规划方法逐段求解,便可得到各项目最佳投资金额, 就是所求的最大收益。

三 模型建立要点

1.分析题意,识别问题的多阶段特性,按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段,对非时序的静态问题要人为地赋予“时段”概念。

2.正确地选择状态变量,使其具备两个必要特征:

(1)可知性;即过程演变的各阶段状态变量的取值,能直接或间接地确定。

(2)能够确切地描述过程的演变且满足无后效性。即由第阶段的状态出发的后部子过程,可以看作是一个以为初始状态的独立过程。

3.根据状态变量与决策变量的含义,正确写出状态转移方程或转移规则。

4.根据题意明确指标函数 ,最优指标函数 以及阶段指标 的含义,并正确列出最优指标函数的递推关系及边界条件(即基本方程)。

逆序解法与顺序解法

动态规划的求解有两种基本方法:逆序解法(后向动态规划方法)、顺序解法(前向动态规划方法)。

上一期的例题求解实际使用的就是逆序解法,即寻优的方向与多阶段决策过程的实际行进方向相反,从最后一段开始计算逐段前推,求得全过程的最优策略。与之相反,顺序解法的寻优方向与过程的行进方向相同,计算时从第一段开始逐段向后递推,计算后一阶段要用到前一阶段的求优结果,最后一段计算的结果就是全过程的最优结果。

一 例题展示

小编接下来将用例2来说明顺序解法。

例2:给定一个线路网格图(图1),要从A地向F地铺设一条输油管道,各点间连线上的数字表示距离,问应该选择什么路线,可使总距离最短?

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

图1

由于此问题的始点A与终点F都是固定的,计算由A点到F点的最短路线与由F点到A点的最短路线没有什么不同。若设运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法表示从起点A到第k阶段状态的最短距离,我们就可以由前向后逐步求出起点A到各阶段起点的最短距离,最后求出A点到F点的最短距离及路径。计算步骤如下:

k=0时,,这是边界条件。

k=1时,按的定义有

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

k=2时,

 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

类似地,可算得

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

按定义知 为所求最短路长,而路径则为 ,全部计算情况如图2所示。图中每节点上方括号内的数表示该点到A点的最短距离,粗黑线表示该点到A点的路径。

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

图2

上述解法可以写成如下的递推方程:

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

状态转移方程为: 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

顺序解法与逆序解法本质上并无区别,一般来说,当初始状态给定时可用逆序解法,当终止状态给定时可用顺序解法。若问题给定了一个初始状态与一个终止状态,则两种方法均可使用,如例2。但若初始状态虽已给定,终点状态有多个,需比较到达不同终点状态的各个路径及最优指标函数值,以选取总效益最佳的终点状态时,使用顺序解法比较简便。

总之,针对问题的不同特点,灵活地选用这两种方法之一,可以使求解过程简化。

二 建模注意事项

  1. 状态转移方式不同

如图3所示,逆序解法中第k段的输入状态为 ,决策为 ,由此确定输出为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法,即第k+1段的状态,所以状态转移方程为 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法 ,该式称为状态 到 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法的顺序转移方程。

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

图3

顺序解法中第k段的输入状态为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法,决策为 ,输出为 ,如图4所示,此时的状态转移方程为 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法,该式称为由状态 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法到 的逆序状态转移方程。

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

图4

同样的道理,逆序解法中的阶段指标在顺序解法中应为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

2.指标函数的定义不同

逆序解法中,我们定义最优指标函数表示第k段从状态出发,到终点后部分子过程最优效益值, 是整体最优函数值。

顺序解法中,应定义最优指标函数运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法表示第k段从起点到状态运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法 的前部子过程最优效益值,运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法是整体最优函数值。

3.基本方程形式不同

(1)当指标函数为阶段指标和形式,在逆序解法中

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

则基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

顺序解法中

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

(2)当指标函数为阶段指标积形式,在逆序解法中

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

则基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

在顺序解法中,

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

特别指出的是,这里有关顺序解法的表达式,是在原状态变量符号不变条件下得出的,若将状态变量记法改为 ,则最优指标函数也可表示为,即符号等同于逆序解法,但含义不同。

基本方程分段求解时的几种常用算法

动态规划模型建立后,对基本方程分段求解,不像线性规划或非线性规划那样有固定的解法,必须根据具体问题的特点,结合数学技巧灵活求解,大体有以下几种方法。

一 离散变量的分段穷举算法

动态规划模型中的状态变量与决策变量若被限定只能取离散值,则可采用分段穷举法。如例2的求解方法就是分段穷举算法,由于每段的状态变量和决策变量离散取值个数较少,所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时,最重要的是正确确定每段状态变量取值范围和允许决策集合的范围。

二 连续变量的解法

当动态规划模型中状态变量与决策变量为连续变量,就要根据方程的具体情况灵活选取求解方法,如经典解析方法、线性规划方法、非线性规划法或其他数值计算方法等。如在例1中,状态变量与决策变量均可取连续值而不是离散值,所以每阶段求优时不能用穷举方法处理。下面分别用逆序解法和顺序解法来求解例1。

(1)用逆序解法

由前面分析可知,例1为三段决策问题,状态变量 为第k段初拥有的可以分配给第k到第3个项目的资金;决策变量 为决定投给第k个项目的资金;状态转移方程为 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法 ;最优指标函数 表示第k阶段,初始状态为 时,从第k到第3个项目所获最大收益,) 即为所求的总收益。递推方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

这是一个简单的函数求极值问题,易知当 时,取得极大值,即

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

所以是极小点。

极大值只可能在 端点取得,

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当 时,解得 。

当 时, ,此时

时,,此时

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

但此时

与 矛盾,所以舍去。

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

所以 是极小点。

比较[0,10]两个端点, 时,

时,

所以

再由状态转移方程顺推

因为

所以

由此

最优投资方案为全部投资于第3个项目,可得最大收益200万元。

(2)用顺序解法

阶段划分和决策变量的设置同逆序解法,令状态变量运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法表示可用于第1到第k个项目投资的金额,则有状态转移方程为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

令最优指标函数 运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法 表示第k段投资额为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法时第1到第k项目所获的最大收益,此时顺序解法的基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当k=1时,有

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当k=2时,有

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当k=3时,有

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

所以,此点为极小点。

极大值应在端点 取得

当 时,,

当 时, ,

所以

再由状态转移方程逆推:

所以最优投资方案与逆序解法结果相同,只投资于项目3,最大收益为200万元。比较两种解法的过程,可以发现,对本题而言,顺序解法比逆序解法简单。

三 连续变量的离散化解法

接下来,小编还是利用投资分配问题先介绍连续变量离散化的概念,如投资分配问题的一般静态模型为:

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

建立它的动态规划模型,其基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

其状态转移方程为运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

由于 与 都是连续变量,当各阶段指标 没有特殊性质而较为复杂时,要求出 会比较困难,因而求全过程的最优策略也就相当不容易,这时常常采用把连续变量离散化的办法求解其数值解,具体做法如下:

(1)令 ,把区间 进行分割, Δ 的大小可依据问题所要求的精度以及计算机的容量来定。

(2)规定状态变量以及决策变量 只在离散点上取值,相应的指标函数 就被定义在这些离散值上,于是递推方程就变为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

(3)按逆序方法,逐步递推求出 ,最后求出最优资金分配方案。

小编仍使用例1作为离散化例子

解:规定状态变量和决策变量只在给出的离散点上取值,令 Δ=2 ,将区间[0,10]分割0,2,4,6,8,10成六个点,即状态变量集合为{0,2,4,6,8,10}。

允许决策集合为, 与 均在分割点上取值。

动态规划基本方程为

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当k=3时,

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

式中 和 的集合均为{0,2,4,6,8,10}。计算结果见表1。

表1

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当k=2时,

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

计算结果见表2

表2

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

当k=1时,

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法

计算结果见表3

表3

运筹说 第67期 | 动态规划模型的建立与求解,动态规划,算法​​​​​​​

计算结果表明,最优决策为: ,最大收益为 ,与上述用逆序和顺序算法得到的结论完全相同。

应指出的是,这种方法有可能丢失最优解,一般得到原问题的近似解。

作者 | 张宇 刘智厅

责编 | 刘文志

审核 | 徐小峰文章来源地址https://www.toymoban.com/news/detail-792631.html

到了这里,关于运筹说 第67期 | 动态规划模型的建立与求解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++算法 —— 动态规划(1)斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月10日
    浏览(44)
  • Python求解二次规划模型

            在学习司守奎老师编写的Pyhon数学实验与建模。学到第6.6求解二次规划模型的时候,忽然觉得很多地方又看不懂了,之前学的一些都忘记了,所以又赶紧查资料弥补一下知识。放在这里,给后面学习的小伙伴提供一些参考吧。          详细拆解一下当时遇到的问题

    2024年02月02日
    浏览(29)
  • 运筹系列82:使用动态规划求解TSP问题

    定义 c ( s , k ) c(s,k) c ( s , k ) 为当前在 k k k ,待访问点的集合 s s s ,最后返回城市0的最短路径,那么Bellman方程为: c ( s , k ) = min ⁡ i ∈ s { c ( s − { i } , i ) + d i , k } c(s,k)=min_{i in s}{c(s-{i},i)+d_{i,k}} c ( s , k ) = min i ∈ s ​ { c ( s − { i } , i ) + d i , k ​ } 为了使用方便,这里

    2024年02月06日
    浏览(38)
  • 运筹系列87:julia求解随机动态规划问题入门

    随机动态规划问题的特点是: 有多个阶段,每个阶段的随机性互不相关,且有有限个实现值 (finite realizations) 具有马尔可夫性质,即每个阶段只受上一个阶段影响,可以用状态转移方程来描述阶段与阶段之间的变化过程。 我们使用julia的SDDP算法包来求解随机动态规划问题。

    2024年01月16日
    浏览(40)
  • 【数学建模】Python+Gurobi求解非线性规划模型

    目录 1 概述 2 算例  2.1 算例 2.2 参数设置 2.3 Python代码实现 2.4 求解结果 如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题。 参考:(非线性规划Python)计及动态约束及节能减排环保要求的经济调度 2.1 算例 2.2 参数设置 求解NLP/非凸问题时,

    2024年02月09日
    浏览(43)
  • 带约束条件的运筹规划问题求解(模拟退火算法实现)

    超级简单的模拟退火算法实现ε٩(๑ ₃ )۶з搭配最简单的线性规划模型进行讲解!但是如果需要的话,可以直接修改程序求解非线性问题哦(´つヮ⊂︎) [max,f(x)=10x_1+9x_2] (s.t.) [6x_1+5x_2leq{60}tag{1}] [10x_1+20x_2leq{150}tag{2}] [0leq{x_1}leq{8}tag{3}] [0leq{x_2}leq{8}tag{4}] 对约束

    2023年04月18日
    浏览(43)
  • 【运筹优化】子集和问题(Subset Sum Problems , SSP)介绍 + 动态规划求解 + Java代码实现

    子集和问题(Subset Sum Problems , SSP),它是复杂性理论中最重要的问题之一。 SSP会给定一组整数 a 1 , a 2 , . . . . , a n a_1,a_2,....,a_n a 1 ​ , a 2 ​ , .... , a n ​ ,最多 n n n 个整数,我们需要判断是否存在一个非空子集,使得子集的总和为 M M M 整数?如果存在则需要输出该子集。

    2024年01月17日
    浏览(46)
  • 动态规划之多重背包模型

    前置知识:  01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客 完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客 给定一个有一定容量的背包,和 n 个物品,每个物品有 si 件; 每个物品有其对应的体积和价值; 问背包最多能装下的物品的最大价值

    2024年02月08日
    浏览(50)
  • 动态规划——最长上升子序列模型

    状态表示 f [ i ] : { 集合:所有以第 i 个数结尾的上升子序列  属性:子序列长度的 M a x 状态表示f[i]: begin{cases} 集合:所有以第 i 个数结尾的上升子序列\\\\ 属性:子序列长度的rm Max end{cases} 状态表示 f [ i ] : { 集合:所有以第 i 个数结尾的上升子序列   属性:子序列长

    2024年04月17日
    浏览(45)
  • 动态规划之二维费用的背包模型

    前置知识: 01背包问题:动态规划之01背包模型_如何何何的博客-CSDN博客 完全背包问题:动态规划之完全背包模型_如何何何的博客-CSDN博客 多重背包问题:动态规划之多重背包模型_如何何何的博客-CSDN博客 二维费用即背包问题有两个限制条件。 例题: 有 N 件物品和一个容

    2024年02月15日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包