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

动态规划及其在资源分配中的应用 摘要：在概述动态规划原理的基础上，提出了动态规划的数学模型建模的主要步骤，将动态规划思想运用到求解资源分配中，并通过一个实际应用例子具体说明动态规划如何解决资源分配问题。关键词：动态规划，资源分配 动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。大约产生于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)=optvk+fk+1,k=n,n-1,，1.3、如何解决资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料、资金、机器设备、劳力、食品等等），恰当地分配给若干个使用者，而使目标函数为最优。设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)。问应如何分配，才能使生产n种产品的总收入最大？此问题可写成静态规划问题： ax z=g1(x1)+g2(x2)+gn(xn) x1+x2+xn=a xi0 ,i=1,2,3n当gi(xi)都是线性函数时，它是一个线性规划问题；当gi(xi)是非线性函数时，它是一个非线性规划问题。但当n比较大时，具体求解是比较麻烦的。然而，由于这类问题的特殊结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。在应用动态规划方法处理这类“静态规划”问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段，把问题中的变量xi选为决策变量，将累计的量或随递推过程变化的量选为状态变量。设状态变量sk表示分配用于生产第种产品至第种产品的原料数量。决策变量uk表示分配给生产第种产品的原料数，即ukxk状态转移方程：sk1skukskxk允许决策集合：Dk（sk）uk|0ukxksk令最优值函数fk（sk）表示以数量为sk的原料分配给第种产品至第种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为：fk（sk）maxgk（xk）fk+1（skxk），n-1，1.fn（sn）maxgn（xn）利用这个递推关系式进行逐段计算，最后求得f1(a)即为所求问题的最大总收入。4、应用举例 一家著名的农产品生冷鲜肉店计划在某城市建立5个分店，这个城市分成三个区，分别用1，2，3表示。由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异，将对各分店的经营状况产生直接的影响。经营者通过市场调查及咨询后，建立了下表。该表表明了各个区建立不同数目的分店时的利润估计，确定各区建店数目使总利润最大(单位万元)。 表 区 区店数 1 2 3 店数 1 2 3 0 0 0 0 3 12 14 91 3 5 4 4 14 16 102 7 10 7 5 15 16 11 解：阶段，三个区，共三个阶段。状态：Sk为第k阶段开始时，可供分配的店数。决策：Dk为分配给区k的店数。状态转移方程：Sk+1=SkDk效益：Rk(Dk)为分配给区k，Dk个店时的利润。(Sk)为当第k阶段初始状态为Sk时，从第k阶段到最后阶段所得最大利润。Fk(Sk)=Max Rk(Dk)+ +Fk+Fk(Sk+1)F4(S4)=0k=3时，计算如下：_S3 F3(S3) D3 S3 F3(S3) D3 0 0 0 3 9 31 4 1 4 10 42 7 2 5 11 5 k=2时，计算如下：_ D2 R2(D2)+F3(S3)S2 0 1 2 3 4 5 F2(S2) D2 0 0 - - - - - 0 01 4 5 - - - - 5 12 7 9 10 - - - 10 23 9 12 14 14 - - 14 234 10 14 17 18 16 - 18 35