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

2024-01-15 23:44

本文主要是介绍运筹说 第67期 | 动态规划模型的建立与求解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

动态规划模型的建立

 概述

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

成功地应用动态规划方法的关键,在于识别问题的多阶段特征,将问题分解成为可用递推关系式联系起来的若干子问题,而正确建立基本递推关系方程的关键又在于正确选择状态变量,保证各阶段的状态变量具有递推的状态转移关系s_{k+1}=T_{k}(s_{k},u_{k})

 例题展示

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

例1:某公司有资金10万元,若投资于项目i(i=1,2,3)的投资额为x_{i}时,其收益分别为g_{1}(x_{1})=4x_{1},g_{2}(x_{2})=9x_{2},g_{3}(x_{3})=2x_{3}^{2},问应如何分配投资数额才能使总收益最大?

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

x_{1},x_{2},x_{3},使maxz=4x_{1}+9x_{2}+2x_{3}^{2},且满足约束

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

状态变量和决策变量有密切关系,状态变量一般为累计量或随递推过程变化的量。针对本例,可以把每阶段可供使用的资金定为状态变量s_{k},初始状态s_{1}=10u_{1}为可分配用于第一种项目的最大资金,则当第一阶段(k=1)时,有

第二阶段(k=2)时,状态变量为余下可投资于其余两个项目的资金,即

一般地,当第k段时

于是有

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

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

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

状态转移方程:s_{k+1}=s_{k}-x_{k}

指标函数:v_{k,3}=\sum_{i=k}^{3}{g_{i}(x_{i}})

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

基本方程为

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

三 模型建立要点

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

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

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

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

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

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

逆序解法与顺序解法

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

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

一 例题展示

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

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

图1

由于此问题的始点A与终点F都是固定的,计算由A点到F点的最短路线与由F点到A点的最短路线没有什么不同。若设f_{k}(s_{k+1})表示从起点A到第k阶段状态的最短距离,我们就可以由前向后逐步求出起点A到各阶段起点的最短距离,最后求出A点到F点的最短距离及路径。计算步骤如下:

k=0时,f_{0}(s_{1})=f_{0}(A)=0,这是边界条件。

k=1时,按f_{1}(s_{2})的定义有

k=2时,

 

类似地,可算得

按定义知 f_{5}(F)=17 为所求最短路长,而路径则为A\rightarrow B_{1}\rightarrow C_{2}\rightarrow D_{2}\rightarrow E_{3}\rightarrow F ,全部计算情况如图2所示。图中每节点上方括号内的数表示该点到A点的最短距离,粗黑线表示该点到A点的路径。

图2

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

状态转移方程为: s_{k}=T_{k}(s_{k+1},u_{k})

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

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

二 建模注意事项

  1. 状态转移方式不同

如图3所示,逆序解法中第k段的输入状态为 s_{k} ,决策为 u_{k} ,由此确定输出为s_{k+1},即第k+1段的状态,所以状态转移方程为 s_{k+1}=T_{k}(s_{k+1},u_{k}) ,该式称为状态s_{k}s_{k+1}的顺序转移方程。

图3

顺序解法中第k段的输入状态为s_{k+1},决策为u_{k} ,输出为 s_{k},如图4所示,此时的状态转移方程为 s_{k}=T_{k}(s_{k+1},u_{k}),该式称为由状态 s_{k+1}s_{k} 的逆序状态转移方程。

图4

同样的道理,逆序解法中的阶段指标v_{k}(s_{k},u_{k})在顺序解法中应为v_{k}(s_{k+1},u_{k})

2.指标函数的定义不同

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

顺序解法中,应定义最优指标函数f_{k}(s_{k+1})表示第k段从起点到状态s_{k+1} 的前部子过程最优效益值,f_{n}(s_{n+1})是整体最优函数值。

3.基本方程形式不同

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

则基本方程为

顺序解法中

基本方程为

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

则基本方程为

在顺序解法中,

基本方程为

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

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

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

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

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

二 连续变量的解法

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

(1)用逆序解法

由前面分析可知,例1为三段决策问题,状态变量s_{k} 为第k段初拥有的可以分配给第k到第3个项目的资金;决策变量 x_{k} 为决定投给第k个项目的资金;状态转移方程为 s_{k+1}=s_{k}-x_{k} ;最优指标函数f_{k}(s_{k}) 表示第k阶段,初始状态为 s_{k} 时,从第k到第3个项目所获最大收益,f_{1}(s_{1})) 即为所求的总收益。递推方程为

这是一个简单的函数求极值问题,易知当 x_{3}^{*}=s_{3} 时,取得极大值,即

所以x_{2}=s_{2}-9/4是极小点。

极大值只可能在 [0,s_{2}] 端点取得,

f_{2}(0)=f_{2}(s_{2})时,解得s_{2}=9/2

s_{2}>9/2 时, f_{2}(0)>f_{2}(s_{2}) ,此时x_{2}^{*}=0

s_{2}<9/2 时,f_{2}(0)<f_{2}(s_{2}),此时x_{2}^{*}=s_{2}

但此时 s_{2}=s_{1}-x_{1}=10-0=10>9/2

s_{2}<9/2 矛盾,所以舍去。

所以 x_{1}=s_{1}-1是极小点。

比较[0,10]两个端点, x_{1}=0时,f_{1}(10)=200

x_{1}=10时,f_{1}(10)=40

所以 x_{1}^{*}=0

再由状态转移方程顺推 s_{2}=s_{1}-x_{1}^{*}=10

因为 s_{2}>9/2

所以s_{3}=s_{2}-x_{2}^{*}=10

由此 x_{3}^{*}=s_{3}=0

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

(2)用顺序解法

阶段划分和决策变量的设置同逆序解法,令状态变量s_{k+1}表示可用于第1到第k个项目投资的金额,则有状态转移方程为s_{k}=s_{k+1}-x_{k}

令最优指标函数 f_{k}(s_{k+1}) 表示第k段投资额为s_{k+1}时第1到第k项目所获的最大收益,此时顺序解法的基本方程为

当k=1时,有

当k=2时,有

当k=3时,有

所以,此点为极小点。

极大值应在端点 [0,s_{4}]=[0,10] 取得

x_{3}=0时,f_{3}(10)=90

x_{3}=10时,f_{3}(10)=200

所以 x_{3}^{*}=10

再由状态转移方程逆推: s_{3}=10-x_{3}^{*}=0 ,x_{2}^{*}=0,s_{2}=10-x_{2}^{*}=0,x_{1}^{*}=0

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

三 连续变量的离散化解法

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

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

其状态转移方程为s_{k+1}=s_{k}-x_{k}

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

(1)令s_{k}=0,\Delta ,2,\Delta ,...,m\Delta, \Delta =a ,把区间 [0,a] 进行分割, Δ 的大小可依据问题所要求的精度以及计算机的容量来定。

(2)规定状态变量s_{k}以及决策变量 x_{k} 只在离散点0,\Delta ,2,\Delta ,...,m\Delta上取值,相应的指标函数 f_{k}(s_{k}) 就被定义在这些离散值上,于是递推方程就变为

(3)按逆序方法,逐步递推求出 f_{n}(s_{n}),…,f_{1}(s_{1}),最后求出最优资金分配方案。

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

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

允许决策集合为0\leq x_{k}\leq s_{k}x_{k}s_{k} 均在分割点上取值。

动态规划基本方程为

当k=3时,

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

表1

当k=2时,

计算结果见表2

表2

当k=1时,

计算结果见表3

表3

​​​​​​​

计算结果表明,最优决策为:x_{1}^{*}=0,x_{2}^{*}=0,x_{3}^{*}=0 ,最大收益为f_{1}(10)=200 ,与上述用逆序和顺序算法得到的结论完全相同。

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

作者 | 张宇 刘智厅

责编 | 刘文志

审核 | 徐小峰

这篇关于运筹说 第67期 | 动态规划模型的建立与求解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610597

相关文章

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI(简称 RVC)模型是一个基于 VITS(Variational Inference with adversarial learning for end-to-end Text-to-Speech)的简单易用的语音转换框架。 具有以下特点 简单易用:RVC 模型通过简单易用的网页界面,使得用户无需深入了

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同