线性规划动态规划.pptVIP

* 6. 动态规划 动态规划建模——引例 动态规划模型基本概念 动态规划模型基本要素 动态规划基本定理 动态规划的示意图 动态规划的应用 引例1： 最短路问题 从上海到伊犁间有一个铁路网,某学生暑假打算到伊犁旅游,出于经济关系只能坐火车,而且要求费用最少。下图标出了各种可能的行车路线,请为这位同学的决策做出指导。 上海 伊犁 A B 4 5 C D E 8 5 5 F H 1 6 7 5 3 G 4 3 6 5 4 5 4 6 求费用最小的方案 穷举法所有路径的费用? ?多阶段决策问题！ 例2 生产计划问题 工厂生产某种产品, 每单位(千件)的成本为1(千元), 每次开工的固定成本为3(千元), 工厂每季度的最大生产能力为6(千件). 经调查, 市场对该产品的需求量第一、二、三、四季度分别为 2, 3, 2, 4(千件). 如果工厂在第一、二季度将全年的需求都生产出来, 自然可以降低成本(少付固定成本费), 但是对于第三、四季度才能上市的产品需付存储费, 每季每千件的存储费为0.5(千元). 还规定年初和年末这种产品均无库存. 试制订一个生产计划, 即安排每个季度的产量, 使一年的总费用(生产成本和存储费)最少. 该规划问题看似一个线性规划或线性整数混合规划问题, 但实际上由于问题的动态特性, 是不容易建立常规的规划问题的(非常复杂)! 但可以分阶段进行决策,即多阶段决策问题. 需要引入新的方法——动态规划方法. 动态规划的基本概念 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。 多阶段决策过程,是指这样的一类特殊的活动过程,问题可以按时间顺序或空间位置分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。 动态规划模型的基本要素 (1) 阶段(Step)——为了表示决策和过程的发展顺序,通常根据决策进行的先后次序、时间顺序或空间特征,将全过程来划分为若干阶段。阶段变量一般用k=1,2,..,n表示。 (2) 状态(State)——表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性,即当某阶段的状态给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关,即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。 在例1中由“上海”出发为第一阶段(k=1),由A、B 出发的为第二阶段(k=2),依此下去可得n=4个阶段。在例2中按照第一、二、三、四季度分为k=1,2,3,4,共4个阶段。 描述状态的变量称状态变量。变量允许取值的范围称允许状态集合。用xk表示第k阶段的状态变量,它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在例1中x2可取A,B,X2={A,B}。n个阶段的决策过程有n+1个状态变量,xn+1表示xn演变的结果,在例1中x5取目的地“伊犁”。 根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。 动态规划模型的基本要素(续) (3)决策(Decision)——当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策(decision),在最优控制问题中也称为控制(control)。 (4) 策略(policy)——决策组成的序列称为策略. 由初始状态x1开始的全过程的策略记作p1,n(x1), 即 p1,n(x1)={u1(x1),u2(x2),...,un(xn)}. 由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pk,n(xk), 即 pk,n(xk)={uk(xk),uk+1(xk+1),..., un(xn)}. 类似地, 由第k到第j阶段的子过程的策略记作 pk,