动态规划在经济管理中的应用文献综述.doc

文献综述 动态规划在经济管理中的应用 前言部分 动态规划是解决多阶段决策过程最优化问题的一种数学规划方法这类问题的特点是，它涉及的活动过程可以划分为若干个互相联系的阶段，在每个阶段都需要做出决策，且前一阶段的决策影响后一阶段的决策，从而影响整个过程的活动方式。各个阶段所采取的决策，构成一个决策序列，称为策略。由于每个阶段可供采取的决策通常有多个可以选择，因而也就可以构成多个策略。按不同策略进行活动的经济效果往往不一样，因此，要按给定的评价指标衡量，哪一个策略的效果好，以求得最优策略。 动态规划在经济、工程技术、工业生产及军事等许多领域都有着重要的应用。动态规划的处理方法是用一种称为“最优化原则”的思想方法导出一个函数方程，然后求解。[1] 线性规划研究目标函数和约束条件都特别简单的优化（极值）问题。[2]与线性规划相比，动态规划没有一个标准的数学模型。然而，动态规划是一类很普遍的问题解决方法，需要建立特定的方程以适应各种情况。因而，对动态规划问题总体结构要求一定程度上的独创性和洞察力，以识别何时以及如何通过动态规划的方法解决问题，这些能力可以通过大范围的动态规划应用和对其普遍特性的研究形成。[3] 二、主题部分 2.1 动态规划概述 动态规划是 2.2动态规划在经济管理中的应用 2.2.1多阶段决策过程的最优化[7] 多阶段决策过程，是一类特殊的活动过程，它可以按时间顺序分解成若干相互联系的阶段，每个阶段称为“时段”。在每个时段都需要做出决策，全部过程的决策是一个决策序故多阶段决策问题属贯决策问题。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各阶段决策间有机地联系着，所以本阶段决策的执行将影响到下一段的决策，以至于影响总体效果，故决策者在短阶段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全面来讲是最优的决策。 使用动态规划方法解决多阶段决策问题，首先耍将实际问题写成动态规化模型，具体包括以下思想： (一)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。 (二)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (三)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法， 因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。动态规划的基本方程是递推逐段求解的根据，一般的动态规划基本方程可以表为： 式中可根据求解问题取或，为状态、决策 时对应的第阶段的指标函数值。 2.2.2动态规划建模 (1)将实际问题的过程划分成恰当阶段，确定阶段变量 根据多阶段决策问题的实际过程，将其划分为若干个相互独立又相互联系的部分，每一个部分为一个阶段，划分出的每一个阶段通常就是需要做出一个决策的子问题目。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用表示。 (2)确定状态，正确选择状态变量 在多阶段决策过程中，状态是描述每个阶段所必须的信息，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态，用一个或一组变量来描述，状态变量必须既能描述过程的演变，又要满足无后效性。用表示第个阶段的状态变量。 (3)确定决策变量及允许的决策集合 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。决策变量用表示；允许的决策集合是决策变量的取值范围用表示。 (4)写出状态转移方程 状态转移方程，这里的函数关系因问题的不同而不同，如果给定第个阶段的状态变量，则该阶段的决策变量一经确定，第阶段的状态变量的值也就可以确定。 (5)列出指标函数 指标函数的关系，并要求具有可分离性及递推性； (6)写出动态规划函数基本方程，用表示阶段的最优策略函数： [8] 2.2.3 动态规划在经济管理中的应用[9] 1、背包问题 1)一维背包问题 (1)问题 有一个人带一个背包上山，其可携带物品重量的限度为公斤。设有种物品可供他选择装入背包中，这中物品编号为1，2，，。已知第种物品每件重量为公斤，在上山过程中的作用(价值)是携带数量的函数。问此人应如何选择携带物品(各几件)，使所有作用（总价值)最大。这就是著名的背包问题，类似的问题有工厂里的下料问题，运输中的货物装载问题，人造卫星内的物品装载问题等等。 (2)模型及其解法 设为第种物品的装入件数，则问题的数学模型为： 它是一个整数规划问题。如果只取0或1，又称为0—1背包问题。下面用动态规划的方法来求解，可写出动态规划的顺序递推关系式为： 然后，逐步计算出最优值函数及相应的决策函数，最后