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

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


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

动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。大约产生 于 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万元。


赞助商链接
相关文章:
资源分配问题
1.模型构建动态规划的应用范围非常广泛。本文主要研究企业资源分配的问题,企业中...适应外部环境的变化 ,使得企业的资源不能充分的利用,从而造成资源浪费 利益...
动态规划实验报告
规划资源分配问题的每一个步骤都要做细致深入的分析,了解每一步的 具体算法; 四、缺点不足 这个程序只能计算简单的特定原料数、厂家数的资源与动态规划资源分配...
动态规划二维分配问题-MATLAB
动态规划二维分配问题-MATLAB_数学_自然科学_专业资料。动态规划二维分配问题-MATLAB 动态规划原理及应用姓名 评分 实验报告 课程名称: 实验名称: 专业: 动态规划 二...
基于MATLAB的水资源优化分配问题动态规划解法
3.3 MATLAB 编程计算 运用 MATLAB 语言编程,程序如下: 4 结语 本文介绍了动态规划的基本解法,针对水资源分配问题进行了动态规划 方法分析。针对具体问题用 ...
9-《运筹学》-第九章
9-《运筹学》-第九章 - 第九章 第九章 动态规划应用举例 §1 资源分配问题背包问题 1. 一维分配问题 问题:一种数量为 a 的资源,分配给 n 个用户。若...
更多相关标签: