数模动态规划.ppt

第7章动态规划?动态规划(Dynamic Programming)是最优化的一个分支。(贝尔曼)等人根据一类多阶段决策问题的特性,提出了解决这类问题的“最优性原理”,并研究了许多实际问题,从而建立了最优化的一个分支——动态规划。动态规划?动态规划把比较复杂的问题划分成若干阶段,通过逐段求解,最终求得全局最优解。特别对于离散性问题,由于解析数学无法运用,动态规划就成为非常有效的工具。然而动态规划目前还存在以下弱点:1)动态规划没有一个统一的算法,它必须针对各种问题的性质,利用最优性原理得出函数方程后,再结合其它数学技巧来求解,而没有一种统一的处理方法,从而我们称动态规划是一种方法。2)当变数的个数(维数)太大时,这类问题虽可以用动态规划来描述,但由于计算机存贮容量和计算机速度的限制在无法解决,此即所谓“维数障碍”。动态规划?动态规划根据多阶段决策过程的时间参量是离散的还是连续的和其决策过程的演变是确定性的还是随机的,可以分为离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。§1多阶段决策问题及实例?所谓多阶段决策问题,是指一类活动过程,它可以分为互相联系的若干个阶段,在每一阶段都需要作出决策,从而使整个过程达到最优的活动效果。因此,各个阶段决策的选取常依赖于当前面临的状态,又影响下一个阶段的决策,从而影响整个过程的活动路线,这种把一个问题看成一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,也称序贯决策过程。多阶段决策问题及实例?各个阶段的决策确定以后就构成一个决策序列,称为一个策略。由于每一个阶段可供选择的决策不止一个,因而对应于整个活动过程就有许多策略选择采用,从中选出一个效果最好的为最优策略。在多阶段决策问题中,既然引入了阶段的概念,也就与时间密不可分,决策过程从一个状态到另一个状态,随着时间的变化在变化,也就有了“动态”的含义。有一些问题表面上处来与时间无关,只要人为地引入“时间”因素,也可以变为下个多阶段决策问题,用动态规划方法来处理。多阶段决策问题及实例?例1 最短路线问题AB1B2C1C2C3C4D1E1F1GD2D3E2E3F25313687668353384221233355266434375976813**********多阶段决策问题及实例?例2 多阶段资源分配问题?某工厂生产A, B和C三种产品,都要使用某种原材料,原材料共有4吨。将不同数量的这种原料分配给各种产品时产生收益如下表(单位:万元),试确定使总收益最大的分配法。?原料分配量产品种类?(吨)A B C?0 0 0 0?1 10 6 8?2 17 17 11?3 20 18 --§2动态规划的基本概念?一、最短路线问题的解?首先讨论最短路线问题的求解方法?[解法一]枚举法?48条不同路线?48×6=288步加法?47次路线长度的比较?最短路长为18最短路线问题的解?[解法二]共有6个阶段?记f1(A) ——A到G的最短距离?则?f1(A)依赖于f2(B1), f2(B2),?………?而f6(F1)=4, f6(F2)=3?故由后向前写出相应公式的形式。?解法二称为逆推解法(逆序解法)最短路线问题的解?上面的做法极其简单,从中我们可以处到这样一个规律,即最短路线必须且只能由最短子路线组成,在求A到G的最短路线时,附带求得了从所有中间顶点到G的最短路,它们是作为整个问题的子问题出现的,并且被嵌入较大问题之中,这常常是动态规划方法的一个特点。