首页 > 其他分享 >动态规划(一)

动态规划(一)

时间:2024-08-21 23:52:12浏览次数:11  
标签:决策 阶段 最优 动态 规划 最优化

动态规划(一)


多阶段决策问题


动态规划是运筹学的一个分支,是求解多阶段决策过程最优化问题的数学方法。

动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用,并且获得了显著的效果。

学习动态规划,我们首先要了解多阶段决策问题。


最短路径问题:

在这里插入图片描述

背包问题:

在这里插入图片描述

生产决策问题**:企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。

机器负荷分配问题:某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。

航天飞机飞行控制问题:由于航天飞机的运动的环境是不断变化的,因此就要根据航天飞机飞行在不同环境中的情况,不断地决定航天飞机的飞行方向和速度(状态),使之能最省燃料和完成飞行任务(如软着陆)。


多阶段决策过程的特点:

根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。

在每一个阶段都需要做出决策,从而使整个过程达到最好的效果。

各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展。

当各个阶段的决策确定后,就组成了一个决策序列,因而也就决定了整个过程的一条活动路线,这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。

动态规划


**针对多阶段决策过程的最优化问题,美国数学家 ** Bellman 等人在20世纪50年代初提出了著名的最优化原理,把多阶段决策问题转化为一系列单阶段最优化问题,从而逐个求解创立了解决这类过程优化问题的新方法:动态规划。

Bellman在1957年出版的《Dynamic Programming》是动态规划领域的第一本著作。

对最佳路径(最佳决策过程)所经过的各个阶段,其中每个阶段始点到全过程终点的路径,必定是该阶段始点到全过程终点的一切可能路径中的最佳路径(最优决策),这就是Bellman提出的著名的最优化原理。

简言之,一个最优策略的子策略必然也是最优的。

动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个 n 维决策问题变换为几个一维最优化问题,从而一个一个地去解决。

需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。

动态决策问题的特点:

  • 系统所处的状态和时刻是进行决策的重要因素;
  • 即在系统发展的不同时刻(或阶段)根据系统所处的状态,不断地做出决策;
  • 找到不同时刻的最优决策以及整个过程的最优策略。

1动态规划方法的关键:

  • 在于正确地写出基本的递推关系式和恰当的边界条件(简称基本方程)。

  • 要做到这一点,就必须将问题的过程分成几个相互联系的阶段,恰当的选取状态变量和决策变量及定义最优值函数,从而把一个大问题转化成一组同类型的子问题,然后逐个求解。

  • 即从边界条件开始,逐段递推寻优,在每一个子问题的求解中,均利用了它前面的子问题的最优化结果,依次进行,最后一个子问题所得的最优解,就是整个问题的最优解。

    2、在多阶段决策过程中,动态规划方法是既把当前一段和未来一段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法。因此,每段决策的选取是从全局来考虑的,与该段的最优选择答案一般是不同的.

3、在求整个问题的最优策略时,由于初始状态是已知的,而每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可逐段变换得到,从而确定了最优路线

最优化原理:作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,相对于前面的决策所形成的状态而言,余下的决策序列必然构成最优子策略。也就是说,一个最优策略的子策略也是最优的。


动态规划求解的多阶段问题的特点:

每个阶段的最优决策过程只与本阶段的初始状态有关,而与以前各阶段的决策(即为了到达本阶段的初始状态而采用哪组决策路线无关)。换言之,本阶段之前的状态与决策,只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说,系统过程的历史只能通过系统现阶段的状态去影响系统的未来。

具有这种性质的状态称为无后效性(即马尔科夫性)状态。

动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。

动态规划求解最短路径问题:


在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

标签:决策,阶段,最优,动态,规划,最优化
From: https://blog.csdn.net/m0_47498690/article/details/141405347

相关文章

  • Eureka中的多实例配置:如何处理微服务实例动态扩展与缩减
    Eureka中的多实例配置:如何处理微服务实例动态扩展与缩减1.引言在微服务架构中,服务的动态扩展与缩减是确保系统弹性和高可用性的关键因素。Eureka,作为一个服务注册和发现的组件,扮演着至关重要的角色。它由Netflix开源,广泛应用于SpringCloud生态系统,用于管理微服务实例的......
  • AcWing 1078. 旅游规划 (DFS找树的直径+直径中点性质求解,无DP)
    原题链接题目描述算法引用自树的直径-OI-Wiki:若树上所有边边权均为正,则树的所有直径中点重合证明:使用反证法。设两条中点不重合的直径分别为\(\delta(s,t)与\delta(s',t')\),中点分别为\(x\)与\(x'\)。显然,\(\delta(s,x)=\delta(x,t)=\delta(s',x')=\delta(......
  • 面试+算法之动态规划(Java):斐波那契、背包问题、走棋盘、分苹果、连续子数组最大和、
    概述Dynamicprogramming,简称DP,动态规划,基础算法之一,维基百科的解释:是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时......
  • Ansible roles 动态变更
    目录role动态变更当Apache的配置文件发生变化时重启Apache进程编排roles目录结构编辑roles/apache/handlers/main.yaml编辑roles/apache/files/httpd.conf编辑roles/apache/tasks/restart.yaml编辑roles/apache/tasks/main.yaml编辑roles/apache.yamlroles文件传输role模板替换......
  • 【C语言入门】如何使用动态内存分配来模拟“大小未知”的数组
    如何使用动态内存分配来模拟“大小未知”的数组引子举例应用结语引子在C语言中,定义一个“大小未知”的数组直接是不可行的,因为数组在声明时必须有确定的大小,要么是在编译时确定的常量表达式,要么是在C99或更高标准下,允许运行时确定大小的变长数组(VLA)。变长数组(Varia......
  • Apache SeaTunnel数据处理引擎适配的演进和规划
    作者|ChaoTian(tyrantlucifer),ApacheSeaTunnelPMCMember摘要ApacheSeaTunnel作为一个高性能数据同步工具,以其高效的数据处理能力,为数据集成领域带来了创新。在引擎上,ApacheSeaTunnel除了支持自身的Zeta引擎外,还支持Spark和Flink。在2024年的CommunityOverCodeAsia,Apa......
  • Echarts 5 动态按需引入图表
    官网提供的按需引入方法为全量按需引入,在打包分离中,仍旧存在使用不到的图表被打包进去。例如:组件A使用了折线图、柱状图,组件B只用到了折线图,但是打包组件B的时候,柱状图也就被打包进去。本文提供一种动态按需引入的思路,使得只用到折线图的组件B,打包的时候只打包折线图,不会将组件A......
  • 动态规划:不相交的线
    目录题目思路解题过程复杂度code 题目        在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足: nums1[i]==nums2[j]且绘制的直线不与任何其他连......
  • 【CSP:202312-1】仓库规划(Java)
    题目链接202312-1仓库规划题目描述求解思路暴力求解:由于数据量较小,对每个仓库进行遍历求解即可。需要注意只有一个仓库的特殊情况。(n=1......
  • [Lgxの归纳] 动态规划算法
    参考文章:dp题方法总汇-YeahPotato组合问题选讲-command_block前言2023NOI大纲中,写明了动态规划入门算法为四级难度,属于CSP-J的考察范围。在联合省选2024中,D1T3/D2T1/D2T2,以及NOI2024中,D1T2/D2T2都以不同的形式考察了动态规划算法。甚至在IOI含金量最高......