资源描述：
《第04章动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第四帝动态规划§1引言1」动态规划的发展及研究内容动态规划（dynamicprogramming）是运筹学的一个分支，是求解决策过程（decisionprocess）最优化的数学方法。20世纪50年代初R.E.Bellman等人在研究多阶段决策过程（multistepdecisionprocess）的优化问题吋，提出了著名的最优性原理（principleofoptimality）,把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法一动态规划。1957年出版了他的名著《DynamicProgrammingL这是该领域的第一木著作。动态规划问世以来，在经济管理、生
2、产调度、工程技术和最优控制等方面得到了广泛的应用。例如最範路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是-•种特殊算法（如线性规划是-•种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具休问题进行具体分析处理。因此，在学习时，除了要对基木概念和
3、方法正确理解外，丿应以丰富的想象力去建立模型，用创造性的技巧去求解。例1最短路线问题图1是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A到G距离最知［（或费用最省）的路线。例2生产计划问题工厂牛产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2,3,2,4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，口然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为（）.5（千元）。还规定年初和年末这种
4、产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。1.2决策过程的分类根据过程的时间变量是离散的还是连续的，分为离散时间决策过程(discrctc-timcdccisionprocess)和连续时间决策过程(continuous-timedecisionprocess)；根据过程的演变是确定的还是随机的，分为确定性决策过程(deterministicdecisionprocess)和随机性决策过程(stochasticdecisionprocess),中应用最广的是确定性多阶段决策过程。§2基木概念、基木方程和计算方法2」动态规划的基本概念和基
5、本方程一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。2.1.1阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征來划分阶段，以便按阶段的次序解优化问题。阶段变量一般用kl,2,L,n表示。在例1中由A出发为k1,由B(i1,2)出发为k2,依此下去从F(i1,2)出发为k6,共n6个阶段。在例2中按照第一、二、三、四季度分为k1,2,3,4,共四个阶段。2.1.2状态状态(state)表示每个阶段开始时过程所处的口然状况。它应能描述过程的特征并且无示效性，即当某阶段的状态变量给定时，这个阶段以示过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直
6、接或间接可以观测的。描述状态的变量称状态变量(statevariable)o变虽:允许取值的范围称允许状态集合(setofadmissiblestates)0用kxk表示第阶段的状态变量，它可以是一个数或一个向量。用X表示第k阶段的允许状态集合。在例1X可取B,B,或将B定义为k212•1i(i1,2)，则x21或2,而X2{1,2}on个阶段的决策过程有n+1个状态变量，xn+1表示xn演变的结果。在例1中x7収G,或定义为1,即x71o根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便冇时又将离散变虽视为连续的。状态变量简称为状态。
7、2.1.3决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision),在最优控制问题屮也称为控制(control)o描述决策的变量称决策变虽(decisionvariable),变量允许取值的范围称允许决策集合(setofadmissibledecisions)。用u(x)表示笫k阶段处于状态x时的决策变量，它是X的两数,用U(X)农示XC,C或C9kkk1123可
