动态规划例题

.

实用文档. 动态规划讲解大全

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep

decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对根本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对假设干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

根本模型

多阶段决策过程的最优化问题。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成假设干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程到达最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的开展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如下图：〔看词条图〕

电容器动态分析经典例题

一、多选题

1．如图所示，C为中间插有电介质的电容器，a和b为其两极板；a板接地；P和Q为两竖直放置的平行金属板，在两板间用绝缘线悬挂一带电小球；P板与b板用导线相连，Q板接地．开始时悬线静止在竖直方向，在b板带电后，悬线偏转了角度α．在以下方法中，能使悬线的偏角α变大的是

A．缩小a、b间的距离 B．加大a、b间的距离

C．取出a、b两极板间的电介质 D．换一块形状大小相同、介电常数更大的电介质

【答案】BC

【解析】

要使悬线的偏角α变大，需要增加F电，即增加PQ两极板间的电场强度，PQ两极板距离不变，所以只需增加PQ两极板间的电压即可。

两个电容器并联在一起，所以两个电容器极板间的电压相同，此时：C并对两个电容器：总电量Q不变，由：QCU

得：增加U，需要将电容C并减小，CPQ不变；

由：4SCkd得：减小电容Cab可有三个方法：

①增大极板距离d

②减小正对面积s，如将ab板错开

③换介电常数小的电介质

故选：BC。=Cab+CPQ。

【名师点睛】本题主要考察电容器的“孤岛效应”，即电荷守恒，在分析电容器动态变化时，需要根据4SCkd判断电容器的电容变化情况，然后结合UEd，QCU等公式分析

2．如图所示，一平行板电容器充电后与电源断开，正极板与静电计连接，负极板接地，现将负极板缓慢向右平移一小段距离，下列说法正确的是（ ）

A．静电计指针张角变小

B．静电计指针张角不变

C．电容器的电容变小

D．电容器两板间的电场强度不变

【答案】AD

【详解】

ABC．电容器充电后与电源断开，电量不变，负极板缓慢向右平移一小段距离，板间距减小，根据

4SCkd

得到电容变大，根据

QCU

可得电压减小，即静电计指针张角变小，A正确，BC错误；

D．根据场强公式

UEd

结合上面公式可得

4kQES

电容器两板间的电场强度不变，D正确。

动态规划讲解大全

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。

基本模型

多阶段决策过程的最优化问题。

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图）

一．用动态规划方法手工求解以下问题：

有 8 万元的投资可以投给3 个项目，每个项目在不同投资数额下（以万元为单位）的利润如下表。

投资额

盈利

项目

0

1

2

3

4

5

6

7

8

项目1 0 5 15 40 80 90 95 98 100

项目2 0 5 15 40 60 70 73 74 75

项目3 0 4 26 40 45 50 51 52 53

请安排投资计划，使总的利润最大。

写出你所设的状态变量、决策变量、状态转移方程与递推关系式，和手工求解的详细步

骤及结果。

设状态变量kx表示投资给项目k至项目n的投资额。

决策变量ku表示投资给项目k的投资额，则状态转移方程为：1kkkxxu 其中1kx表示投资给项目1k至项目n的投资额。

允许决策集合：(){|0}kkkkkDxuux

()kkfx表示把kx的钱投资给项目k至项目n，盈利的最大额。

递推关系式：

其中()kkgu表示上表格中项目k的投资额为ku时盈利。

10()max{()()}1,......,1()()kkkkkkkkkuxnnnnfxgufxuknfxgx针对这个例子，3n，kx最大取8

手工详解过程：

1）初始化3k

333333333(0)0;(1)4;(2)26;(3)40;(4)45;(5)50;(6)51;(7)52;(8)53fffffffff

2）2k

223223232232323223232323(0)max{(0)(0)}0(1)max{(0)(1),(1)(0)}max{04,50}5(2)max{(0)(2),(1)(1),(2)(0)}max{026,54,150}26(3)max{(0)(3),(1)(2),(2)(1),(3)(0)}fgffgfgffgfgfgffgfgfgfgf2232323232322323232323max{040,526,154,400}40(4)max{(0)(4),(1)(3),(2)(2),(3)(1),(4)(0)}max{045,540,1526,404,600}60(5)max{(0)(5),(1)(4),(2)(3),(3)(2),(4)(1)fgfgfgfgfgffgfgfgfgfgf232232323232323232,(5)(0)}max{050,545,1540,4026,604,700}70(6)max{(0)(6),(1)(5),(2)(4),(3)(3),(4)(2),(5)(1),(6)(0)}max{051,550,1545,4040,6026,704,730}86(7)mgffgfgfgfgfgfgfgff232323232323232322323232ax{(0)(7),(1)(6),(2)(5),(3)(4),(4)(3),(5)(2),(6)(1),(7)(0)}max{052,551,1550,4045,6040,7026,734,740}100(8)max{(0)(8),(1)(7),(2)(6),gfgfgfgfgfgfgfgffgfgfgfg32323232323(3)(5),(4)(4),(5)(3),(6)(2),(7)(1),(8)(0)}max{053,552,1551,4050,6045,7040,7326,744,750}110fgfgfgfgfgf3）1k