2  预备知识
2.1  单边切比雪夫不等式
引理1(马尔可夫Markov不等式):设X为只取非负值的随机变量, 数学期望 , 则对于任意正数 , 成立不等式:
 .证明  构造随机变量
因为 ,所以 .
两边取数学期望有 ,
由此即得结论 .
引理2:设随机变量X的数学期望 ,方差 则对于任意正数 , 成立不等式:
 .证明  对任意的实数 ,利用马尔可夫不等式,有
则 时 达到最小值,此时 ,
命题得证。
定理(单边切比雪夫不等式):设随机变量X的数学期望 ,方差 ,则对于任意正数 ,成立不等式:
证明  因为 与 的期望都是0,方差都是 ,由引理2有
即知定理成立。(文献[8])
2.2  动态规划
动态规划是运筹学的一个分支,它是解决一类多阶段决策问题的一种方法,它将多阶段决策问题转化为一系列比较简单的最优化问题。动态规划首先将复杂的问题分解成相互关联的若干阶段,每一个阶段都是最优化子问题,然后逐阶段进行决策,当所有阶段决策都确定了,整个问题的也就确定了。
2.2.1  基本概念和符号
阶段  在处理问题时,通常把所要求解的问题划分成若干个相互联系的小问题。原问题被看作一个过程,小问题就是过程的几个阶段。阶段往往按时间顺序划分,通常用t表示阶段变量,t取自然数1,2,…。
状态  表示某一阶段出发位置的状态,它既是上一阶段的输出又是本阶段的输入,并用向量 表示第t阶段的状态,称为状态变量。状态的取值都有一个范围,称为状态集合,记为 。
决策和策略  对于给定的最优化过程,决策就是某段状态给定以后,从该状态演变到下一阶段某状态的选择。描述决策的变量称为决策变量,用 表示第t阶段当状态处于 时的决策变量。决策变量一般都有一个允许取值的集合,称为允许决策集合,第t阶段的允许决策集合记为 .给定了某阶段的状态,选定了与此状态相应的决策,则下一阶段的状态就完全确定了,这就是所谓的决策过程的确定性。
指标函数和最优指标函数  在多阶段决策过程最优化问题中,指标函数是用来衡量所实现过程的优劣的一种数量指标,也称目标函数。常用 表示t子过程的指标函数,即
            (2.2.1)
指标函数 的最优值,称为相应的最优指标函数,记为
        (2.2.2)
其中opt表示取最优,可根据实际问题取最大(max)或最小(min)。
状态转移方程  在确定性决策过程中,可以把状态 、决策 ,以及下一阶段的状态 的对应关系表现为
该式就称为状态转移方程。
2.2.2  最优化原理和基本方程
动态规划的最优化原理是由美国贝尔曼(bellman)首先提出来的。具体叙述为:“作为整个过程的最优策略具有这样的性质:即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。”
利用这个原理,可以把多阶段决策问题的求解过程看成是一个连续的递推过程,由后向前逐步推算。在求解时,在各阶段以前的状态和决策,对其后面的子问题来说,只不过相当于其初始条件而已,并不影响后面过程的最优策略。因此,可以把一个问题按阶段分解成许多相互联系的子问题,其中每一个子问题均是比原问题简单得多的优化问题,且每个子问题的求解仅利用它的下一阶段子问题的优化结果,这样依次求解,最后可求得原问题的最优解。于是,对于一个确定的离散T阶段决策过程,根据最优化原理,可以给出其动态规划的基本方程,也称动态规划递推关系。
上一篇:关于拓扑空间的定义+文献综述
下一篇:Matlab求解旅行商问题的算法应用

基于决策树算法的篮球联赛预测

基于t分布对还黄金期货的投资风险分析

基于长时间序列MODIS数据的...

基于小学生视角的数学作业批改现状的调查

基于高分影像的钱塘江主要污染区域遥感监测

基于鹰鸽博弈的动物行为博弈论模型

基于logit模型的大学生金融投资理财行为研究

10万元能开儿童乐园吗,我...

中国学术生态细节考察《...

国内外图像分割技术研究现状

C#学校科研管理系统的设计

神经外科重症监护病房患...

AT89C52单片机的超声波测距...

志愿者活动的调查问卷表

医院财务风险因素分析及管理措施【2367字】

公寓空调设计任务书

承德市事业单位档案管理...