动态规划在经济中的应用论文

1、 动态规划在经济学论文选题中的应用 目录TOC o 1-3 h z u HYPERLINK l _Toc230014395 摘要1 HYPERLINK l _Toc230014398 摘要1 HYPERLINK l _Toc230014399 1. 动态规划相关背景32. HYPERLINK l _Toc230014400 动态规划的相关概念32.1 HYPERLINK l _Toc230014401 基本功能32.2 HYPERLINK l _Toc230014402 基本概念42.3 基本思路 HYPERLINK l _Toc230014403 52.4动态规划模型的分类和方法52.5 H

2、YPERLINK l _Toc230014417 动态规划的优缺点63. 动态规划的优化原理和最优性定理 HYPERLINK l _Toc230014418 83.1 优化原理的概念与证明 HYPERLINK l _Toc230014419 83.2 动态规划的无效原理 HYPERLINK l _Toc230014420 84. HYPERLINK l _Toc230014422 动态规划在工业中的应用94.1 HYPERLINK l _Toc230014422 生产计划问题 94.2 HYPERLINK l _Toc230014422 设备更新问题 1 2五 HYPERLINK l _Toc

3、230014422 、结论 2 0 HYPERLINK l _Toc230014422 参考文献 2 0 HYPERLINK l _Toc230014423 至2 1动态规划摘要：动态规划是运筹学的一个分支，是一种解决多阶段决策过程优化问题的数学方法。所谓“动态”，就是在问题的多阶段决策中，按照一定的顺序，根据每一步选择的不同决策，立即转移状态，最后形成一个决策序列在改变的状态下生成。动态规划是使生成的决策序列在一定条件下达到最优。动态规划方法广泛应用于工程技术、企业管理、工农业生产和军事等部门，取得了显著成效。在企业管理方面，动态规划可用于解决最优路径问题、资源分配问题、生产调度问题、库存问

4、题、装载问题、分拣问题、设备更新问题、生产过程的最优控制问题等。 ，所以它是现代经济管理中的一种重要决策方法。它的应用也越来越受到重视。本文主要利用动态规划的思想，设计一个有效的数学模型，解决生产领域遇到的一些问题，优化资源配置，规划出最优或可行的方案。本文首先讨论了“动态规划”的理论基础。给出了动态规划的基本理论和基本方程。其次，给出并证明了最优性定理。最后以业界最典型的两个问题为例，阐述了动态规划基本原理的应用。关键词：动态规划；最优性原则；经济;计划生产;设备更新CLC 编号： O221.31 相关背景动态规划是一种可以将复杂问题转化为一系列相对简单问题的最优方法，称为DP方法。其基本特

5、征是优化过程中的多阶段性。许多优化问题可以通过动态规划方法来处理，这些方法往往具有其独特的优势。特别是对于离散问题，这些问题往往难以用数学方法处理，动态规划方法成为解决这些问题的非常有用的工具。优化原理最早由美国贝尔曼（Bellman）提出。最优化原则可以表述为：“问题全过程的最优策略有这样一个性质：不管之前的状态和策略，对于之前的决策形成的状态，剩下的所有决策都必须构成最优策略”。利用优化原理，待处理的多阶段决策问题的求解过程可视为一个连续递推的过程，从前到后或从后到前逐级计算。在解决方案中，每个阶段的先前决策和状态仅相当于其对后续子问题的初始条件，一般不影响后续过程的最优策略。因此，一个问

6、题可以按阶段分解为多个相互关联的子问题，每个子问题都是一个比原问题简单得多的优化问题，每个子问题的解只使用它的下一个阶段。子问题的优化结果依次求解，最终得到原问题的最优解1 。在对动态规划的背景有所了解之后，下面简要介绍动态规划的一些基本概念和基本方程、动态规划的基本思想、模型的分类和方法以及动态规划的优缺点。2 动态规划相关概念2.1 基本特点动态规划问题具有以下基本特征：1.整个舞台可以按空间划分，也可以人为按时间划分。动态规划问题的特点是多阶段决策。2.每个阶段都有一个与之对应的“状态”。我们称描述状态的量为“状态变量”。3.每个阶段都面临一个决策，我们选择不同的决策会导致下一个阶段的不

7、同状态，不同的决策会导致这个阶段不同的目标函数值。4.每个子问题的结构与原问题完全相同，每个阶段的最优解可以递归地简化为下一个阶段每个可能状态的最优解。解决动态规划问题的关键是能否构造出这样的递归解。这种递归归约的过程称为“不变嵌入”。为了形式化上述特征，我们提出了以下动态规划的基本概念2 。2.2基本概念1.阶段：给定问题的过程被适当地划分为几个相互关联的顺序环节，称为阶段。描述阶段的变量成为阶段变量，通常用k表示。阶段的划分一般是根据空间和时间的自然特性。2.状态：描述研究过程的状态，也称为不可控因素，即每个阶段开始的自然状态或客观条件。用 表示第 k 个阶段的状态变量。这里提到的状态应该

8、没有后遗症（即马尔可夫性质）。3、决策：决策是过程在一定阶段处于一定状态时可以做出的选择或决定。决策变量可以表示为状态处于第 k 阶段时的决策变量。在实际问题中，决策变量的取值往往被限制在一定范围内，称为允许决策集。常用于表示从第 k 阶段的状态开始的允许策略的集合。是的。4. 策略：策略是按顺序排列的决策集合。由各个段的决策按顺序组成的决策函数序列成为k-word处理策略，简称子策略，即。即当k=1时，这个决策函数序列就变成了整个过程的策略，简称策略，记住。5、状态转移方程：如果第k阶段的状态变量的值给定，如果本阶段的决策变量确定了，那么第k+1阶段的状态变量的值也确定了，即值的值随总和的值

9、而变化。 .用方程表示，它描述了从阶段 k 到阶段 k+1 的状态转移规律。这个方程是某个过程从一种状态到另一种状态的演变。6、指标函数和最优指标函数：指标函数具体包括阶段指标函数和过程指标函数。阶段指标函数是指某个阶段对应的某个收益量和从该阶段开始的阶段决策，用 表示。过程指标函数是指从状态到过程结束，采用某种子策略时，按照预定标准获得的效益值。该值既与的状态值有关，也与后面选择的策略有关，是两者的函数值。最优指标函数是指对某一状态选择最优策略后得到的指标函数值，也是最优子策略对应的收益值。现在我们来了解一下动态规划的灵魂，也就是它的基本思想。2.3 基本思想1.求解动态规划问题的关键是正确

10、写出基本的递推关系和合适的边界条件，也就是说，将前面子问题的优化结果用在每个子问题的求解中，从边界条件和逐步重复。优化是按顺序进行的，最后一个子问题得到的最优解就是整个问题的最优解。2.决策的每个阶段都是从全局角度考虑的，一般不同于每个阶段的最优选择。因此，在决策过程中，动态规划法是一种将当前段和未来段分开，同时考虑当前收益和未来收益的优化方法。3、在寻找整个动态规划问题的最优策略时，由于初始状态已知，并且每个段的决策是段状态的函数，最优策略通过的每个段的最优状态可以是一一转化。 ，从而确定最优策略。在使用动态规划求解问题时，经常会用到不同的模型和方法，下面简单介绍一下。2.4 动态规划模型的

11、分类与方法根据多阶段决策过程的时间变量是连续的还是离散的，将过程分为连续决策过程和离散决策过程。根据决策过程的演化是随机的还是确定性的，可以将过程分为随机决策过程和确定性决策过程。结合起来，有四种决策过程模型：离散确定性、离散随机性、连续确定性和连续随机性。动态规划法：动态规划法可分为逆序求解法和顺序求解法。那么，它们的基本动态规划方程应表示为：假设指标函数为各阶段指标之和的形式，即其中表示第 i 个阶段的索引。他显然满足指标函数的三个性质。所以上式可以写成。当给定初始状态时，确定过程的策略，确定指标函数。因此，指标函数的初始状态和策略的函数可以记为，所以上述递推关系也可以写成它的子策略有一个

12、决策，可以看成是决策和组合的组合。这是如果使用初始状态的后退子过程的所有子策略中的最优子策略。那么最优值函数为和但所以边界条件为。以上就是动态规划逆序求解法的基本方程。根据边界条件，从头到尾，逐步得到各段的最优决策和对应的最优值。整个问题的最优解。动态规划序贯求解法的基本方程：假设阶段序数 k 和状态变量的定义保持不变，而决策变量的定义发生变化，比如 take ，此时的状态转移不是由 go 决定的，而是反过来由 go 决定的，状态转移方程的一般形式是因此，第 k 阶段的允许决策集也应相应改变，记为。指标函数也应该用sum函数代替。因此，动态规划序列求解方法的基本方程可以得到为边界条件在公式中。

13、求解过程，根据边界条件，从头到尾，从前到后，逐步得到每个段的最优决策和对应的最优值，最终得到整个问题的最优解4 .本文主要强调动态规划在经济方面的优势，但不可否认动态规划也有其不足之处。2.5 动态规划的优缺点动态规划法与穷举法相比有两个明显的优势： （1）计算量大大减少（2）计算结果丰富在一定条件下，根据问题的具体性质确定各个阶段的收益后，找到一种优化整个过程总收益的方法，这就是动态规划优化。需要注意的是，阶段的划分是动态规划应用的关键，必须根据问题分析寻求合理的阶段（子问题）划分方法。并且每个子问题都是比原始问题简单得多的优化问题。而且，在每个子问题的解中，都使用其后一个子问题的优化结果，

14、直到最后一个子问题得到的最优解就是原问题的最优解。当然，动态规划方法也有不足之处：到目前为止，还没有一个标准模型可以适用于所有问题。由于实际问题的复杂性和差异性，动态规划模型是不同的。虽然一些静态规划问题理论上可以转化为动态规划模型来解决，但这种转化优势变得非常困难，需要丰富的想象力。和灵活的技能。还有应用限制。在构建静态规划模型时，状态变量必须满足“无后效应”条件，这不仅取决于状态转移规律，还取决于允许的决策集和指标函数的结构，这是一个比较强的条件。在许多实际问题中，将其自然特征作为状态变量往往不能满足这一条件，从而降低了动态规划的通用性。求解数值时还有一个“维度障碍”，在存在的约束下，超出

15、三个维度的动态规划目前一般是不可取的。在为实际问题构建动态规划模型时，必须做到以下五点：（一）根据实际情况将问题处理成适当的阶段；(2) 正确选择变量，使他能够描述过程的演变，并且不满足后遗症；(3) 正确确定每个阶段的决策变量和允许的决策集；(4)正确写出状态转移方程；(5) 正确写出指标函数的关系，应满足以下三个性质：是对整个过程和所有后续子过程定义的量函数；必须是可分的且满足递推关系，即 函数对于变量必须是严格单调的。以上五点是正确编写动态规划基本方程的基本要素，也是构建动态规划模型的基础。下面介绍动态规划的最优性原理及其无效性。3 动态规划的最优性原则和无后遗症3.1 最优性原理的概念

16、和证明动态规划的最优性原则可以简单描述为：作为一个整体的最优策略具有这样一个性质：无论过去的状态和决策是什么，对于前一个决策形成的状态，剩下的决策必然构成最优策略.简而言之，最优策略的子策略总是最优的。最优性原则：设多阶段决策过程，阶段数为n，阶段数为。许可策略是最优策略的充分必要条件。对于任何 k，0kn-1 和有其中它是由给定的初始状态和子策略确定的 k 段状态。当V为收益函数时，opt取最大值；当 V 是损失函数时， opt 取最小值。推论：如果允许的策略是最优策略，那么对于任意k，0kn-1，其子策略必定是以k到n-1为起点的子过程的最优策略（注: k 段状态由和) 确定。上述定理是动

17、态规划的理论基础5 。3.2动态规划的无效原理所谓无后遗症原则，就是指这样一种性质：一旦某个阶段的状态确定了，后续过程的演化就不再受之前的状态和决策的影响。换言之，“未来与过去无关”，当前状态是对前一历史的完整总结，前一历史只能通过当前状态影响过程的未来演变。具体来说，如果把一个问题划分为各个阶段，那么阶段I的状态只能通过状态转移方程从阶段I+1的状态中得到，与其他状态没有关系，尤其是和没有发生的状态. ，这没有后遗症 7 。下面简要列举两个动态规划应用的例子，并简要介绍其在经济中，尤其是在工业中的作用。4. 动态规划在经济特别是工业中的应用4.1 生产计划问题对于生产计划等问题，根据计划时间

18、自然划分阶段，状态定义为每个阶段开始时的入库量，决策是每个阶段的输出，即需求（已知每个阶段的数量）为，则状态转移方程为,设各阶段开工固定成本为a，生产单位数量产品的成本为b，单位数量产品各阶段的仓储成本为c，阶段指标为阶段总和成本和存储成本，即指示函数是sum 。最优值函数是从第 k 个段的状态到过程结束的最小成本，满足允许的决策集由每个阶段的最大生产能力决定。如果设置过程结束时的允许存储容量为，则终止条件为 构成问题的动态规划模型。示例 1：某公司与客户签订合同，在 4 个月内销售一定数量的某种产品。由于各种原因，每月最多生产100台，限产10的倍数。产品可以入库，入库费用为2元/台。生产成

19、本和月销售额见表 1-1。要求是确定一个能够满足合同要求的生产过程，以最大限度地降低生产成本。解决方案：阶段变量代表月份。状态变量表示在 k 开始时可用的产品数量。决策变量表示决定第k个月的生产数量，满足约束状态转换，阶段指标。表 1-1月单位生产成本合同销售170602727038012047660当k=4时（表1-2），由于1-3月最大生产量为300台，合同总销量为250台，4月最大仓储量为50台，即可能值为0, 10, 20 , 30, 40, 50. 解决,是的，有。表 1-20456060103820502030804030234030401600205086010k=3时（表1-3

20、），一、二月最大生产量为200台，销售合同金额为60+70=130，因此3月初最大存储量为70台。渐渐地。 _所以可能的值为 20、30、40、50、60、70 个单位。解决表 1-35060708090100201260012600100301182011880118209040110401110011160110408050102601032010380104401026070609480954096009660972094806070870087608820888089409000870050当k=2时（表1-4），1月份最大生产量为100台，合同销售量为60台，那么2月份最大库存量为1

21、00-60=40，即可能的值为0, 10, 20, 30, 40. 解决并通过，得到。表 1-4506070809010001908019020190201001018380183201826018260100201768017620175601750017500100301698016920168601680016740167401004016280162201616016100160401598015980100当 K=1 时（表 1-5）， , 有表 1-5607080901000232202316023100230402298022980100最低总成本和最优生产安排见表 1-6。表

22、1-6月101006070000700024010070720080728037050120400014041404060604560045604.2 设备更新问题例2：矿山中型自卸车更新问题研究铁矿为矿石开采的特大型露天矿山，年产铁矿石650万吨，总采采量约1.5亿吨。矿石通过汽车和电力机车在线运输，工艺流程如图1所示。从下图可以看出，该矿的矿石和岩石量主要由矿用自卸车运输，电力机车进入作业后只负责矿石的输出。税收和利润任务发挥着重要作用。该矿目前有 65 辆铁矿石自卸车。载重量为20t。其中，B20-203车辆仅有40辆，自来矿以来已经使用了六年多。此外，还有25辆TJ371车辆，自来矿以

23、来已经使用了四年多。根据国务院有关规定，矿用中型自卸车的使用寿命为8至10年。随着使用寿命的增加，B20-203车辆虽然尚未达到规定的使用寿命，但其性能和技术条件日益恶化，运输成本不断增加，综合经济效益逐年下降.此外，随着开采年限的增加，采场工作面不断缩小。这些原因都促使相关部门考虑是否保留或更新这种车。岩石坠场电铲装车矿石入溜场汽车运输溜井配矿机电车运输爆破选矿厂穿孔图1但由于目前我国生产重型自卸车的厂家不多，产量也很少，根据矿山的具体情况和实践经验，只有两个系列能满足矿山所需吨位的产品。该车厂生产的RD系列轿车引进英国技术和某省第二机械厂与美国联合生产的33系列轿车。因此，矿场近几年主要更

24、新换代了这两个系列的车。今年是一个年度循环，从2007年开始，为了最大化汽车的总效益，从2007年到2011年每年年初，无论是买新车（ P：购买）还是保养旧车（ K：保留) ) 问题以做出决定。据了解，B20-203型车到2011年初已经使用了7年，TJ731型车也使用了5年。至2011年的五年内，如果继续使用旧车，所产生的费用或更换新车的费用见表2；如果您在这五年内使用 33-001 车更新，费用如表 3 所示。如果您使用 RD150-1 车更新，费用如表 4 所示。表二（万元）模型B20-203（6 年）TJ731（4年）使用年限789101156789收入（万元）11.51110.510

25、913.61312.712.311.5年使用费6.78.67.59.58.56.17.36.88.88.4更新汽车5658606365625254565858606264675456596062表三（万元）开始年份2007年2008年200920102011使用年限012340123012010年收入252626252425272825262728293030年使用费68108116810.597910910.59.5续订费303436384032343638333537353736表4（万元）开始年份1988年1989199019911992使用年限012340123012010年收入283

26、029272 52 83029272 93028293030年使用费891112138.59.51211.58.5101291010.5 _续订费3 8404244463 9414345404244404241我们开始建模：为了建立汽车更新的数学模型，指定的符号如下：新购车第一周期获得的收入；-第一期已使用 y 年的车辆的收入；-第一个周期使用新车的费用；-在第一个周期中使用已使用 y 年的汽车的使用成本；的第一个周期，该车的更新费用已经使用了y年，该车为当年生产的新车；T现有汽车的使用年限；A转换系数（因为工业利率是1.5%，所以这里A的值是0.9985）；- 在第一个周期开始时，在第一个周

27、期中获得的已使用 y 年的汽车的最优收益；- 在第一个周期开始时，获得的决定（只有两个决定，购买新车（P）或修理旧车（K）。假设第一期初为新车，第一期获得的总收益为：第一期从新车获得的收入减去第一期使用新车的成本，减去第一个期间开始时使用的 y 年。汽车更新的成本，加上在第一个周期开始时使用了1年的汽车所获得的最优收益（乘以转换因子A，换算为在第一个周期开始时获得的最优收益)，即 A ，那么更新的总收益为：P: - - +A同理，假设使用了y 年的车还在第一期使用，第一期获得的总收益为：该车的使用成本，加上该车已使用的最优收益第一期期初y+1年（乘以换算系数A，换算为第一期期初得到的最优收益，

28、即A ，所以留着以后用总收益是： - + A因此，对于在第一个周期中使用了 y 年的汽车，在第一个周期中获得的总收入的基本方程是：规定：计算B20-203车型已经使用了7年，TJ371车型已经使用了5年，它们的使用年限都是8到10年，所以从2007年到2011年的5年，这两款车都需要更新。这里设置为5年。B20-203型车和TJ371型车分别使用了7年和5年。如果将B20-203型车换成B33-001型车，每个周期的最优收益和决策可计算如下：(1) 逆序最优目标函数值集和最优决策集。当时，使用年复一年，它的最佳效益和决策是：所以所以=所以=所以=所以表 5使用年限12341119.517.01

29、6.013.00.5第五个周期，B20-203型车辆更新为B33-001型车辆。不同服务年限的最优收益及其决策如表 5 所示。此时的最优收益和使用寿命决策如下：所以所以=所以=所以表 6使用年限1231036.032.530.01.0第四个周期将B20-203型车辆更新为B33-001型车辆，不同服役年限的最优效益和决策如表6所示。第三和第二周期的最优回报和决策可以类似地计算，如表 7 所示。表 7第三个周期周期 2使用期限12918最优回报52.445.9463.913.3最优决策最后，那个时候所以(2)具体解决方法如下。根据以上计算结果，B20-203车更新为B33-001车，2007年后

30、五年的最优决策可归纳如表8所示。得出B20-203车为2007年初用B33-001车更新，这样2011年获得的总利润最大，最高利润26.8万元，2007年初的更新相比保留每辆增加收入8.72万元车。元。同理，可以计算出其他三种情况。 B20-203型更新为RD150-1型，TJ371型更新为B33-001型，RD150-1型，2007年后五年的最优收益和决策如图所示桌子。如图 9 所示。表 8循环使用期限做决定1721324354表 9RD150-1 替代 B20-203B33-001 替换 TJ371RD150-1 替代 TJ3711磷磷磷2345最优收入（万元）27.832.731.7我们可以得出结论和分析：从上述计算结果（表8和表9）可以看出，如果该矿现有车辆采用技术更新方法，则选择原B20-203型车辆作为RD150-1型车将于2007年初更新。计算周期内获得的最高总收益为27.8万元，比留存单多出15.6万元。原TJ371车使用3