《马尔可夫决策规划1.doc》由会员分享，可在线阅读，更多相关《马尔可夫决策规划1.doc（16页珍藏版）》请在金锄头文库上搜索。
1、运筹学概述：为什么要学运筹学？运筹学（Operational Research）是一类“以定量化为基础、服务于系统管理和决策”的科学方法，其强调的是“最优性”、“若不这样，则不会好于现在这样做”（即非劣性）或“满意性”；其使用的工具是各种模型，尤其是定量数学模型；研究处理的对象是社会经济系统。它是系统工程的理论基础。(Operations Research(美) or Operational Research (英)，运筹学(大陆)or作业研究(香港和台湾)The Methods of Operations Research, P.M.Morse 和 G.E.Kimball（1946）：“运筹
2、学是为领导机关对其控制下的事务、活动采取策略而提供定量依据的科学方法，它是在实行管理的领域，运用数学的方法，对需要进行管理的问题进行统筹规划、做出决策的一门应用学科”。也有人将其定义为“运筹学是一种适用于系统运行的方法和工具，它是一种科学方法，能对运行管理人员的问题提供最合适的解答。”（放松了“定量”要求）。另外，还可定义为“将科学技术具体、并最佳运用于生产和生活实践的一门学科”，如Operation Research。一般的线性规划运 筹 学线性规划对策论决策论排队论图与网络库存论可靠性理论非线性规划动态规划整数规划目标规划数学规划随机规划与马氏规划 确定 随机静态 LP、NP、IP 排队
3、多目标规划 库存 图与网络 对策 决策 随机规划动态 DP M本课主要内容： 线性规划、非线性规划、整数规划、多目标规划-最优化理论 对策论-经济博弈论 决策论-决策的理论和方法本课主讲内容第一部分 马尔科夫决策规划（1014）第二部分 排队论（810）第三部分 可靠性理论（1012）第四部分 随机规划（46）第五部分 存储论（68）第六部分 蒙特卡洛仿真（24）学习基础：线性代数、概率论和随机过程、数学规划主要参考书：1. 运筹学（修订版），钱颂迪主编，清华大学出版社，19902. 排队论及其应用, 陆凤山编著, 湖南科学技术出版社, 19843. 排队论与随机服务系统, 华兴（美）编著，上
4、海翻译出版公司，1987.74. 随机运筹学, 赵玮、王荫清，高等教育出版社，1993年5. 运筹学随机模型，严颖、成世学、程侃编著，中国人民大学出版社，19956. 实用网络计划技术，程国平、黄沛均，华中理工大学出版社，1991.67. 运筹学，李军、徐玖平编著，科学出版社，2003.118. 运筹学手册，美J.J.摩特、S.E.爱尔玛拉巴主编，上海科学技术出版社，19879. 运筹学的理论与实践，美菲利普斯等著，刘泉、万敏译，中国商业出版社，1987年10. 运筹学题库，美国教育协会编，晓园出版社，1993.6英文参考书：Introduction to Queuing Theory, R.
5、B.Cooper (1998)Operations Research: An Introduction, Hamdy A.Taha (2007)马尔可夫决策规划所谓决策，是指在若干个可行的行动方案中按照某种准则选出一个方案。其中，有一类多阶段决策问题称为序贯决策，即在系统的运行过程中，它不是作一次决策就结束，而是在一系列观察的时刻点上都要做出决策。例如，一家商店各种商品每月的进货量；一台机器定期的维修；一家工厂每月的生产计划等。在每个观察时刻点上，决策者首先根据所得的系统状态，从其所有被选方案中选择一个方案（即做出决策）执行，其结果是：（1）将获得一定效益；（2）能确定以后系统状态发展的概率规
6、律。然后，再观察下一时刻点上系统出现的状态，据此再做出新的决策，如此一步一步地进行下去。如果在序贯决策过程中，系统状态的转移服从已知的概率规律且与系统以前的发展历史无关，即具有无后效性（或Markov性），称此类序贯决策问题的数学模型为Markov决策规划（以下简称MDP）。Markov决策规划是解决随机性序贯决策问题的重要分支学科。它可以应用于许多领域，是解决随机动态最优化问题的重要工具，如排队系统的最优运行控制；随机库存系统的最优定货策略；设备的最优更换维修策略；水库的优化调度等均可以转化为一定的MDP来解决。可以说，凡是以Markov过程作为数学模型的问题，只要能够引入“行动”与“报酬”
7、结构，均可以应用Markov决策规划。主要讲授内容： 第一讲 概率与随机过程 第二讲 马尔可夫链与马尔可夫过程 第三讲 离散时间的马尔可夫决策规划 第四讲 F有限折扣模型 第五讲 有限阶段模型及其他第一讲 概率与随机过程1.1 概率空间随机试验是概率论的基本概念，试验的结果事先不能准确地预言，但具有如下三个特性：（1） 可以在相同的条件下重复进行；（2） 每次试验的结果不止一个，但预先知道试验的所有可能结果；（3） 每次试验前不能确定哪个结果会出现。 随机试验所有可能结果组成的集合称为这个试验的样本空间或基本事件空间，记为。中的元素e称为样本点或样本事件，的子集A称为事件，样本空间称为必然事件
8、，空集称为不可能事件。定义1.1：设是一个集合，F是的某些子集组成的集合簇。如果：（1）F；（2）若AF, 则F；（3）若AnF， n=1,2, 则F。 则称F为-代数，（, F）称为可测空间，F中的元素称为事件或的可测子集。定义1.2：设（,F）为一可测空间，定义在F上的实值函数称为上的测度，如果1）任意AF, ；（非负性）2）对两两互不相容事件A1, A2, (当时，),有；（可列可加性） 并称（, F, P）为测度空间。定义1.3：设（, F, P）为测度空间，如果，则称P是（,F）上的概率，（, F, P）称为概率空间，P(A)为事件A的概率。定义1.4：设（, F, P）为概率空间，
9、GF，如果对任意A1, A2, , AnG，n=1,2,，有，则称G为独立事件族。1.2 随机变量及其数学期望定义1.5：记为包含的最小-代数，则称为Borel域，中的元素为Borel集。 注：1）所有的区间、单点集 2）（R,）是一可测空间定义1.6：设（,F）为一可测空间，定义在上取值于R（Rn）的函数:称为是F可测函数，是指对任意都有。 注：1）将上述的事件称为事件B是可以的； 2）实现了两个对应：i. 与R的子集ii. F与的子集定义1.7：称为概率空间（, F, P）上的随机变量，如果它是从到R的F可测函数。 注：以后每提到随机变量，总意味着已给定了某个概率空间。定义1.8：由R到R
10、的可测的实函数称为是Borel可测函数。 注：1）如果为（, F, P）上的随机变量，f是可测函数，则也是（, F, P）上的随机变量； 2）所有至多有可列无穷多个不连续点的实函数都是 Borel可测函数；关于随机变量的数学期望的定义如下：定义1.9：设是（, F, P）上的随机变量，如果 存在的话，则称其为的数学期望，记为。 设，记，则为事件A的示性函数，也是一个随机变量，且 这意味着，利用示性函数可以将求概率转化为求数学期望。关于独立性有：定义1.10：如果，则称事件A与B是相互独立的；设（, F, P）是一概率空间，F1和F2是F的子-代数，如果对任意和任意都有，则称-代数F1和F2是相
11、互独立的。定义1.11：设是（, F, P）上的随机变量，记为包含的最小-代数，称为由产生的-代数；再设、都是（, F, P）上的随机变量，如果子-代数与是相互独立的，则称随机变量与是相互独立的。 具体地，可再定义：定义1.12：设是（, F, P）上的随机变量，称（其中）为随机变量的分布函数。定义1.13：设（, F, P）为概率空间，=()=(1(), 2(), n()是定义在上的n维向量空间Rn中取值的向量函数，如果对于任意x=(x1,x2,xn)Rn, F，则称=()为n维随机变量或n维随机向量；称F(x)= F(x1,x2,xn) =为=(1(), 2(), n()的联合分布函数。1
12、.3 条件概率和条件数学期望以事件为条件的条件概率：，其中以事件为条件的条件数学期望：，其中设为示性函数，则：条件概率可以处理为条件数学期望。定义1.14 （以-代数为条件的条件数学期望）：设X是（, F, P）上的随机变量，G是F的子-代数，随机变量称为是关于-代数G的条件数学期望，如果1）是G可测的随机变量；2）对任意，。（是随机变量，而为确定实数，是事件为条件的数学期望的推广）讨论：i. 设， 定义 对任意, =则满足1）和2）。 ii. 如果G=F，则X本身满足1）和2）两条，如果G为F的真子集，则X不满足第1）条。 iii. 定义了由的可加函数，称为广义测度（不必满足非负性，否则为测
13、度，再加上规范性则为概率测度）。由Radon-Nikdym定理可保证满足1）和2）两条的随机变量的存在性和在概率为1的意义下的唯一性。 例：，定义定义1.15（以随机变量为条件的条件数学期望）：设X、Y都是（, F, P）上的随机变量，称为Y以X为条件的条件数学期望。定义1.16（以随机变量束为条件的条件数学期望）:设T为有限或可列集，记为随机变量束产生的-代数，称为X在下的条件数学期望。设上述的T为有限集，记T=(1,2,n)，则存在n维Borel实函数f(z1,z2,zn)使得 ，称f(z1,z2,zn)为X在 条件下的条件数学期望。1.4 随机过程定义1.17：设（, F, P）为概率空
14、间，T是给定的参数集，若对每个有一个随机变量X(t, )与之对应，则称随机变量簇是（, F, P）上的随机过程，T称为参数，通常表示时间。X(t, )简记为X(t)。例1.1 生物群体的增长问题。在描述群体的发展和演变过程中，以Xt表示在时刻t群体的个数，则对每一个t， Xt是一个随机变量。假设从t=0开始每隔24小时对群体的个数观测一次，则Xt, t=0,1,2,是随机过程。 一般地，用表示随机变量X在t1时刻取x1,tn时刻取xn的联合概率密度。由联合概率密度可以定义条件概率： 表示固定时，随机变量X具有的联合概率密度。定义1.18：设是随机过程，如果对任意，EX(t)存在，则称函数（其中）为的均值函数。若对任意，存在，则称为二阶矩过程。并称（其中）为的协方差函数；（其
