动态规划,生产计划.docx

动态规划,生产计划第四章动态规划 1引言动态规划的发展及研究内容动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。(multistepdecisionprocess)的优化问题时,提出了著名的最优性原理,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《DynamicProgramming》,这是该领域的第一本著作。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划,只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。例1最短路线问题下面是一个线路网,连线上的数字表示两点之间的距离。试寻求一条由A到G距离最短的路线。例2生产计划问题工厂生产某种产品,每单位的成本为1,每次开工的固定成本为3,工厂每季度的最大生产能力为6。经调查,市场对该产品的需求量第一、二、三、四季度分别为2,3,2,4。如果工厂在第一、二季度将全年的需求都生产出来,自然可以降低成本,但是对于第三、四季度才能上市的产品需付存储费,每季每千件的存储费为。还规定年初和年末这种产品均无库存。试制定一个生产计划,即安排每个季度的产量,使一年的总费用最少。决策过程的分类根据过程的时间变量是离散的还是连续的,分为离散时间决策过程和连续时间决策过程;根据过程的演变是确定的还是随机的,分为确定性决策过程和随-40- 机性决策过程,其中应用最广的是确定性多阶段决策过程。 2基本概念、基本方程和计算方法动态规划的基本概念和基本方程一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段,以便按阶段的次序解优化问题。阶段变量一般用k?1,2,?,n表示。在例1中由A出发为k?1,由Bi(i?1,2)出发为k?2,依此下去从Fi(i?1,2)出发为k?6,共n?6个阶段。在例2中按照第一、二、三、四季度分为k?1,2,3,4,共四个阶段。状态状态表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性,即当某阶段的状态变量给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用xk表示第k阶段的状态变量,它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在例1中x2可取B1,B2,或将Bi定义为i(i?1,2),则x2?1或2,而X2?{1,2}。在例1中x7取xn?1表示xn演变的结果。n个阶段的决策过程有n?1个状态变量, G,或定义为1,即x7?1。根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化;为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。决策当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策,在最优控制问题中也称为控制。描述决策的变量称决策变量,变量允许取值的范围称允许决策集合。用uk(xk)表示第k阶段处于状态xk时的决策变量,它是xk的函数,用Uk(xk)表示xk的允许决策集合。在例1中u2(B1)可取C1,C2或C3,可记作u2(1)?1,2,3,而U2(1)?{1,2,3}。决策变量简称决策。策略决策组成的序列称为策略。由初始状态x1开始的全过程的策略记作p1n(x1),即 p1n(x1)?{u1(x1),u2(x2),?,un(xn)}. 由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pkn(xk),即 pkn(xk)?{uk(xk),?,un(xn)},k?1,2,?,n?1. 类似地,由第k到第j阶段的子过程的策略记作 pkj(xk)?{uk(xk),?,uj(xj)}. 可供选择的策略有一定的范围,称为允许策略集合(setofadmissiblepolicies),用-41- P1n(x1),Pkn(xk),Pkj(xk)表示。状