当前位置:首页 >> 数学 >>

动态规划及其在资源分配中的应用


动态规划及其在资源分配中的应用
摘要:在概述动态规划原理的基础上,提出了动态规划的数学模型建模的主要步骤,将动态规划思 想运用到求解资源分配中,并通过一个实际应用例子具体说明动态规划如何解决资源分配问题。 关键词:动态规划,资源分配

动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。大约产生 于 20 世纪 50 年代。1951 年美国数学家贝尔曼(R..Bellman)等人,根据一类多阶段决策问题的特 点,把多阶段决策问题变换为一系列相互联系的单阶段问题,然后逐个加以解决。与此同时,他提 出了解决这类问题的“最优性原理” ,研究了许多实际问题,从而创建了解决最优化问题的一种新 的方法——动态规划。 动态规划的方法,在工程技术、企业管理、工农业生产及军事部门中都有广泛的应用,并且 获得了显著的效果。在企业管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产 调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等,所以它 是现代企业管理中的一种重要的决策方法。 许多问题用动态规划的方法去处理, 常比线性规划或非 线性规划更有成效。特别对于离散性的问题,由于解析数学无法施展其术,而动态规划的方法就成 为非常有用的工具。应指出,动态规划是求解某类问题的一种方法,是考查问题的一种途径,而不 是一种特殊算法(如线性规划是一种算法) 。因而,它不像线性规划那样有一个标准的数学表达式 和明确定义的一组规则,而必须对具体问题进行具体分析处理。

1、动态规划原理概述
动态规划最优化原理可以这样阐述: 一个最优化策略不论过去状态和决策如何, 对前面的决策 所形成的状态而言,余下的诸决策必须构成最优策略,即其子策略总是最优的。任何思想方法都有 一定的局限性,动态规划也有其适用的条件。如果某阶段的状态给定后,则在这阶段以后过程的发 展不受这阶段以前各段状态的影响, 这个性质称为无后效性, 适用动态规划的问题必须满足这个性 质; 其次还须满足上述最优化原理。 动态规划基本思想一是正确地写出基本的递推关系式和恰当的 边界条件;二是在多阶段决策过程中,动态规划方法是既把当前一段和后来各阶段分开,又把当前 效益和未来效益结合起来考虑的一种多阶段决策的最优化方法。 每阶段决策和选取是从全局来考虑 的,与该段的最优选择的答案一般是不同的;三是在求整个问题的最优策略时,由于初始状态是已 知的, 而每阶段的决策又都是该阶段状态的函数, 因而最优策略所经过的各阶段状态便可逐次变换 得到,从而确定最优路线。简言之,动态规划的基本思想就是把全局的问题化为局部的问题,为了 全局最优必须局部最优。

2、动态规划建模主要步骤
用动态规划求解实际问题,首先要建立动态规划模型,需进行以下的基本步骤: 第一步:正确划分阶段,确定阶段变量。将多阶段决策问题的实际过程,恰当地划分为若干个 相互独立又相互联系的部分, 每一个部分为一个阶段, 划分出的每一个阶段通常就是需要做出一个 决策的子问题。阶段通常是按决策进行的时间或空间上的先后顺序划分的,阶段变量用k表示。 第二步:确定状态,正确选择状态变量。在多阶段决策过程中,状态是描述研究问题过程的状 况,表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态,用一个或一组变量 来描述,状态变量必须满足两个条件:一是能描述过程的演变;二是满足无后效性。用Sk表示第k 个阶段的状态变量。 第三步:正确选择决策变量及允许的决策集合。决策的实质是关于状态的选择,是决策者从给 定阶段状态出发对下一阶段状态作出的选择, 而在实际问题中, 决策变量的取值往往限制在某一范 围内,此范围称之为允许决策集合。决策变量用Uk表示;允许的决策集合是决策变量的取值范围用 Dk(sk)表示。 第四步:写出状态转移方程。状态转移方程的一般形式为Sk+1=Tk(sk,uk),这里的函数关系T 因问题的不同而不同,如果给定第k个阶段的状态变sk,则该阶段的决策变量uk一经确定,第k+1 阶段的状态变量sk+1的值也就可以确定。 第五步:列出指标函数。根据题意写出指标函数,指标函数常用 Vk,n表示.即 Vk,n=Vk,n(sk,uk,sk+1,??,sn+1),k=1,2,??,n. 它应满足以下三个性质: i它是定义在全过程及所有后部子过程上的数量函数; ii具有可分离性,且满足递推关系,即 Vk,n=Q(sk,uk,Vk+1,n); iii函数 Q(sk,uk,Vk+1,n)关于变量Vk+1,n 要严格单调。 第六步:写出动态规划函数基本方程,用fk(sn+1)表示k---n阶段的最优策略函数: fn+1(xn+1)=0 fk(sk)=opt{vk+fk+1},k=n,n-1,??,1.

3、如何解决资源分配问题
所谓分配问题,就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、 食品等等) ,恰当地分配给若干个使用者,而使目标函数为最优。 设有某种原料,总数量为 a,用于生产 n 种产品。若分配数量 xi 用于生产第 i 种产品,其收 益为 gi(xi)。问应如何分配,才能使生产 n 种产品的总收入最大?

此问题可写成静态规划问题: max z=g1(x1)+g2(x2)+??+gn(xn) x1+x2+??+xn=a xi》0 ,i=1,2,3??n 当 gi(xi)都是线性函数时,它是一个线性规划问题;当 gi(xi)是非线性函数时,它是一个非 线性规划问题。但当 n 比较大时,具体求解是比较麻烦的。然而,由于这类问题的特殊结构,可以 将它看成一个多阶段决策问题,并利用动态规划的递推关系来求解。 在应用动态规划方法处理这类“静态规划”问题时,通常以把资源分配给一个或几个使用者的 过程作为一个阶段,把问题中的变量 xi 选为决策变量,将累计的量或随递推过程变化的量选为状 态变量。 设状态变量 sk 表示分配用于生产第k种产品至第n种产品的原料数量。 决策变量 uk 表示分配给生产第k种产品的原料数,即 uk=xk 状态转移方程: sk+1=sk-uk=sk-xk 允许决策集合: Dk(sk)=﹛uk|0《uk=xk《sk﹜ 令最优值函数 fk(sk)表示以数量为 sk 的原料分配给第k种产品至第n种产品所得到的最大 总收入。因而可写出动态规划的逆推关系式为: fk(sk)=maxgk(xk)+fk+1(sk-xk) ,k=n-1,??1. fn(sn)=maxgn(xn) 利用这个递推关系式进行逐段计算,最后求得 f1(a)即为所求问题的最大总收入。

4、应用举例
一家著名的农产品生冷鲜肉店计划在某城市建立5个分店, 这个城市分成三个区, 分别用1, 2, 3表示。由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异,将对各分店的经营状 况产生直接的影响。经营者通过市场调查及咨询后,建立了下表。 该表表明了各个区建立不同数目的分店时的利润估计,确定各区建店数目使总利润最大(单位 万元)。



区 店数 0 1 2 1 0 3 7 2 0 5 10 3 0 4 7 店数 3 4 5 1 12 14 15

区 2 14 16 16 3 9 10 11

解:阶段,三个区,共三个阶段。 状态:Sk为第k阶段开始时,可供分配的店数。 决策:Dk为分配给区k的店数。 状态转移方程:Sk+1=Sk—Dk 效益:Rk(Dk)为分配给区k,Dk个店时的利润。 (Sk)为当第k阶段初始状态为Sk时,从第k阶段到最后阶段所得最大利润。 Fk(Sk)=Max Rk(Dk)+ +Fk+Fk(Sk+1) F4(S4)=0 k=3时,计算如下: ______________________________________________________ S3 0 1 2 F3(S3) 0 4 7 D3 0 1 2 S3 3 4 5 F3(S3) 9 10 11 D3 3 4 5

k=2时,计算如下: __________________________________________________________________________ D2 S2 0 1 2 3 4 5 0 0 4 7 9 10 11 1 -5 9 12 14 15 R2(D2)+F3(S3) 2 --10 14 17 19 3 ---14 18 21 4 ----16 20 5 -----16 F2(S2) 0 5 10 14 18 21 D2 0 1 2 23 3 3

k=1时,计算如下:

_______________________________________________________________________ D1 S1 5 0 21 1 21 R1(D1)+F2(S2) 2 21 3 22 4 19 5 15 F1(S1) 22 D1 3

所以最优解:k=1时,D*1=3,D*2=2,D*3=0 即在区1建3个分店,在区2建2个分店,而不在区3建立分店。最大总利润=22万元。


赞助商链接
相关文章:
动态规划应用举例
关键词:动态规划;应用; 正一、 资源分配问题 所谓分配问题, 就是将数量一定...当 x 在[0, s1 ]上连续地变化时,若 g ( x ) h( x ) 是线性...
动态规划(应用)
广泛的应用, 产及军事及其它部们都有广泛的应用,并且获得了显著效果。动态规划可用于解决最优 路径问题、资源分配问题、生产计划库存问题、投资分配问题、装载...
动态规划(应用)
广泛的应用, 产及军事及其它部们都有广泛的应用,并且获得了显著效果。动态规划可用于解决最优 路径问题、资源分配问题、生产计划库存问题、投资分配问题、装载...
动态规划_求解资源分配_实验报告
(2) 分析实验中要求求解的问题,根据动态规划的思想,得出优化方程; (3) 从...分析算法的时间和空间复杂度,并由此解释释相应的实验结果; 问题描述:资源分配...
动态规划讲解大全(含例题及答案)
例 如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划...对选手运用动态规划知识的要求也越来越高,已经不再停留于简单的递推 和建模上...
动态规划方法的应用研究
文章例举了动态规划在最短路线、资源分配、设备更新、排序、装载等方面的应用。...但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态...
动态规划习题
在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问 题...介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用...
动态规划算法原理与应用
动态规划算法原理 及其应用研究 系姓 别: x 名: x x x x x x x 指导...在经济管理方面,动态规划可以用来解决最优路径 问题、资源分配问题、生产调度问题...
动态规划
在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问 题...介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用...
动态规划习题详解
产及军事及其它部们都有广泛的应用,并且获得了显著效果.动态规划可用于解决最优 路径问题,资源分配问题,生产计划库存问题,投资分配问题,装载问题, 路径问题,...
更多相关标签: