运筹学讲义第8章.ppt

《运筹学讲义第8章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第八章动态规划DynamicProgramming动态规划（DP）是运筹学的一个分支，解决多阶段决策问题的一种方法。1951年美国数学家贝尔曼（R.Bellman）等提出“最优化原理”，创建动态规划学科。主要应用于工程技术、经济、工业生产、最优控制等问题。动态规划方法对解决离散性优化问题更为有效。2010/031--第8章动态规划--8.1多阶段决策问题例1：某工厂根据合同要求在未来半年中需提供货物数量如表中所示，表中数字为月底交货数量。该厂的生产能力为每月400件，其仓库的存货能力为3百件。已知每百件货物的生产费用为10千元，在进行生产的月份

2、，工厂要支出固定费用4千元，仓库保管费用为每百件货物每月1千元，假定开始及6月底交货后均无存货，试问每个月应该生产多少件产品，才能既满足交货任务又使总费用最小？月份交货数量（百件）1234561253212010/032--第8章动态规划--生产生产生产库存库存库存库存费用费用费用1月2月6月可看成6个阶段的决策：2010/033--第8章动态规划--AB1B3C1C2C3D1D2EB225375632451514633334例2：由A至E需经B、C、D，问如何行走，路程最短？2010/034--第8章动态规划--例3：公司承担一种新产品试制任

3、务，合同要求三个月内交出一台合格的样品，否则将负担1500元的赔偿费。试制时投产一台成功的概率为1/3，投产一批的准备费用为250元，每台试制费用为100元。若投产一批后全部不合格，可再投产一批试制，但每投产一批需要一个月的周期。问每批应该投产多少台，可使总的费用（包括可能发生的赔偿费用）期望值最小？2010/035--第8章动态规划--第1月第2月第3月试制试制试制合格否?合格否?合格否?YYYSTOPSTOPSTOPNN赔偿费N2010/036--第8章动态规划--多阶段决策问题的特点：①决策过程可划分为若干个互相联系的阶段；②在每一阶段分

4、别对应着一组可以选取的决策；③当每个阶段决策选定以后，活动过程也随之确定。许多多阶段决策问题表现出明显的时序性，故体现出“动态”的特点，所以是动态规划研究的主要对象。某些静态问题，当采用动态规划的方法求解时，也会使问题的处理变得简单。2010/037--第8章动态规划--8.2动态规划的基本概念和数学模型一、动态规划的基本概念（1）阶段（stage）：指一个活动过程需要做出决策的步数。k——阶段变量。（2）状态（state）：某阶段初始状况。既是本阶段决策的出发点，又是上一阶段决策产生的结果。是动态规划中各阶段信息的传递点和结合点。Xk——第

5、k阶段状态变量。特征：①反映研究对象的演变特征；②包含到达这个状态前的足够信息，并具有无后效性；或称决策的相互独立性；③状态变量具有可知性，当决策确定后，到达的状态是可以测知的。描述状态所必须使用的变量数，称动态规划的维数。2010/038--第8章动态规划--（3）决策（decision）：指在某阶段从给定的状态出发，决策者从面临的若干种不同的方案中所做出的选择。决策变量uk(xk)∈Dk(xk)——允许决策集合，uk(xk)取值范围。要点：①决策变量是对活动过程控制的手段；②决策变量取值可以是连续型的，也可以是离散型的；③允许决策集合相当

6、于可行域。（4）策略（policy）与子策略（subpolicy）：各阶段决策组成的序列总体称为策略；从某一阶段开始到过程最终的决策序列称为子策略。n阶段策略可记为{u1(x1),u2(x2),…,un(xn)}，子策略可记为{uk(xk),uk+1(xk+1),…,un(xn)}。（5）状态转移律：状态参数变化的规律。从第k阶段的某一状态值xk出发，当决策变量uk的取值确定之后，下一阶段的状态值xk+1按某种规律T(xk,uk)确定。第k+1阶段状态是第k阶段状态xk和变量uk的函数xk+1=T(xk,uk)，又称状态转移方程。2010/03

7、9--第8章动态规划--说明：①当xk,uk确定后，xk+1取值唯一确定，则为确定性多阶段决策问题；②当xk,uk确定后，xk+1取值为具有某种概率分布的随机变量，则称为随机性多阶段决策问题。（6）指标函数：决策所产生的效益的度量函数。分如下的几类：①vk(xk,uk)——阶段指标函数。②Vk,n(xk,uk,xk+1,uk+1,…,xn,un)——过程指标函数。③f(xk)=optVk,n——最优指标函数，只与xk有关。Opt——optimize，可以是max，或者min。说明：为便于计算，指标函数应具有递推性。（7）边界条件：对过程最终状态

8、时的效益值表示。即当k=n+1时，f（xn+1）=？上述基本概念可用下述图示某性表示：2010/0310--第8章动态规划--状态xkxk+1xk+2