运筹学第05章.ppt

《运筹学第05章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第五章动态规划2本章内容多阶段决策问题动态规划的基本概念和基本原理动态规划问题实例3引例1某运输公司拟将一大型设备从下列交通网络的A点运输到F点，试用动态规划求从A到F的最短路径。4引例2某企业生产某种产品，每月月初按订货单发货，生产的产品随时入库，仓库最多能够储存产品90千件。在1至6月其生产成本和产品订单的需求数量情况如下表：已知上一年底库存量为40千件，要求6月底库存量仍能够保持40千件。问：如何安排这6个月的生产量，使既能满足各月的定单需求，同时生产成本最低。月份(k)成本与需求123456生产成本(ck)/（万元／千件）2

2、.12.82.32.72.02.5需求量(rk)/千件356350326744多阶段决策过程特点:状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+1第一节多阶段决策问题第二节动态规划的基本概念和基本原理一、动态规划的基本概念1.阶段和阶段变量动态规划求解，需把问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。用以描述阶段的变量叫做阶段变量，一般以k表示阶段变量．阶段数等于多段决策过程从开始到结束所需作出决策的数目。

3、动态规划的基本概念2.状态、状态变量和可能状态集描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。8动态规划的基本概念——状态状态变量需能够描述问题的过程，并满足无后效性。无后效性（又称马尔柯夫性）指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策决定，与系统以前经历的状态和决策无关。动态规划的基本概念—状态每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记为sk，终止状态记为sk

4、+1。通常定义阶段的状态即指其初始状态。9动态规划的基本概念—状态一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定。10113.决策、决策变量和允许决策集合决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。动态规划的基本概念动态规划的基本概念—决策用以描述决策变化的量称之决策变量。决策变量的值可以用数，向量、

5、其他量，也可以是状态变量的函数。记uk=uk(sk)，表示于阶段k状态为sk时的决策变量。12动态规划的基本概念—决策决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示,uk(sk)∈Uk(sk)允许决策集合实际是决策的约束条件。13144.策略和允许策略集合策略(Policy)也叫决策序列．策略有全过程策略和k部子策略之分，全过程策略是指由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,n{u1,u2,…,un}。动态规划的基本概念动态规划的基本概念—策略从k阶段到

6、第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,n{uk,uk+1,…,un}，显然当k=1时的k部子策略就是全过程策略。15动态规划的基本概念—策略在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n，从允许策略集中，找出具有最优效果的策略称为最优策略。16175.状态转移方程系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1。动态规划

7、的基本概念动态规划的基本概念—状态转移方程对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2,…,sk-1及其决策u1(s1),u2(s2)，…，uk-1(sk-1)无关。18动态规划的基本概念—状态转移方程系统状态的这种转移，用数学公式描述即有：通常称上式为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。1920动态规划的基本概念6.指标函数用来衡量策略或子策略或决策的效果的

8、某种数量指标，称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同的问题，指标函数可以是费用、成本、产值、利润、产量、耗量、距离、时间、效用等。动态规划的基本概念—指标函数阶段指标函数（阶段效应）用g