运筹学10动态规划1

《运筹学10动态规划1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划（DynamicProgramming）动态规划是美国数学家Bellman创立的。是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基本方法之一。RBellman50年代执教于普林斯顿和斯坦福大学，后进入兰德（Rand）研究所。1957年发表“DynamicProgramming”一书，标志动态规划的正式诞生。动态系统：包含随时间变化的因素和变量的系统。包含:线性系统、非线性系统。动态系统的特点：系统在某个时刻的状态，往往要依某种形式受过去某些决策的影响，而系统的当前状态和决策又会影响

2、系统过程今后的发展。动态决策问题：将时间作为决策变量之一的决策问题称为动态决策问题。动态决策问题的特点：在动态决策问题中，系统所处的状态和时刻是进行决策的重要因素，即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策，找到不同时刻的的最优决策以及整个过程的最优策略。第一节：动态规划的研究对象和引例多阶段决策问题：是动态决策问题的一种特殊形式。在多阶段决策过程中，系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段，而且在每个阶段都要进行决策。目的是使整个过程的决策达到最优效果。

3、多阶段决策问题的典型例子：1、生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。12n状态决策状态决策状态状态决策在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为h=h(u2)相应的机器年完好率b,0

4、：某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器数量就为a,0

5、段的决策问题用动态规划方法来解决。静态规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决，后面将详细介绍。5、最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266431234561阶段、阶段变量：把所给问题的过程，适当地分为若干个相互联系的阶段，目的是能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶

6、段的划分，一般是按照时间和空间的自然特征划分，原则是便于把问题过程能转化为多阶段决策过程。2状态、状态变量：状态表示每个阶段开始所处的自然状态或客观条件，通常一个阶段有若干个状态。描述过程状态的变量称为状态变量。可用一个数、一组数或一向量来描述，常用sk标记第k阶段的状态。一般来说，状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。第二节：动态规划的基本概念和定义3决策、决策变量：当过程处于某一阶段的某个状态时，可以做出不同的决定（或选择），从而决定下一阶段的状态，这种决定称为决策。在最优控制中

7、也称为控制。描述决策的变量，称为决策变量。它可以用一个数、一组数或一个向量来描述。它是状态变量的函数，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有uk(sk)Dk(sk)。4多阶段决策过程：即可在各个阶段进行决策，控制过程发展的多段过程。多阶段决策过程的发展是通过一系列的状态转移来实现的，一般来说，系统在某一阶段的状态转移不但与系统的当前（或本阶段）状态和决策有关

8、，而且还于系统历史状态和过去的决策有关。其状态转移方程如下（一般形式）图示如下：状态转移方程描述过程由一个状态到另一个状态的演变规律。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。12决策u1决策u2决策uk状态s1状态s2状态sk状态s3k状态sk+1无后效性或马尔可夫性：某阶段状态给定后，则这个阶段以后的过程发展不受这个阶段以前各段状态的影响。换句话说，过