动态规划应用举例.docx

动态规划应用举例南京航空航天高校运筹学课程论文题目：动态规划应用举例学号：姓名：完成日期:2013«5«16摘要动态规划是解决最优限制的一种重要方法之一，算法的优点有：(1)易于确定全局最优解：(2)能得到一族解，有利于分析结果：(3)能利用阅历，提高求解的效率。动态规划方法虽然存在很多不足之处，但随着计算机的日益普及，动态规划的应用越来越广泛，它能够奇妙地解决科学技术和实际生活中的很多实例。本文列举了一些典型例题，介绍了如何用动态规划去求解，不足之处是这些问题大多数都是确定型的，而对于连续型、随机型问题接触较少。关键词：动态规划：应用；正文一、资源安排问题所谓安排问题，就是将数量肯定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地安排给若干个运用者，而使目标函数为最优。设有某种原料，总数量为a,用于生产n种产品。若安排数量ix用于生产第i种产品，其收益为()iigx,问应如何安排，才能使生产n产品的总收入最大？此问题可写成静态规划问题：112212max()()()0,1,2,i,nn11izgxgXgxxxxaxn=+=+=当()iigx都是线性函数时，它是一个线性规划问题；当()iigX是非线性函数时，它是一个非线性规划问题。但当n比较大时，详细求解是比较麻烦的。由于这类问题的特别结构，可以将它看成一个多阶段决策问题，并利用动态规划的递推关系来求解。在应用动态规划方法处理这类静态规划问题时，通常以把资源安排给一个或几个运用者的过程作为一个阶段，把问题中的变量ix为决策变量，将累计的量或随递推过程改变的量选为状态变量。设状态变量ks表示安排用于生产第k种产品至第n种产品的原料数量。决策变量ku表示安排给生产第k种产品的原料数，即ku=kx状态转移方程：Ikkkkkssusx+=允许决策集合：)()OkkkkkkDsuuxs=令最优值函数()kkfS表示以数量为ks的原料安排给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为：10()maxkx()O,1,1()maxnx=()RnkkkkkkksnnnnsfSgxfsxknfsgx+=+=利用这个递推关系式进行逐段计算，最终求得K)fa即为所求问题的最大总收入。例1某工业部门依据国家支配的支配，拟将某种高效率的设备五台，安排给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家供应的盈利如表9-1所示。表9-1工厂盈利/万元备设台数甲乙丙0123450379121305.