数学建模案例分析--最优化方法建模6动态规划模型举例.doc
文本预览下载声明
§6 动态规划模型举例
以上讨论的优化问题属于静态的,即不必考虑时间的变化,建立的模型——线性规划、非线性规划、整数规划等,都属于静态规划。多阶段决策属于动态优化问题,即在每个阶段(通常以时间或空间为标志)根据过程的演变情况确定一个决策,使全过程的某个指标达到最优。例如:
(1)化工生产过程中包含一系列的过程设备,如反应器、蒸馏塔、吸收器等,前一设备的输出为后一设备的输入。因此,应该如何控制生产过程中各个设备的输入和输出,使总产量最大。
(2)发射一枚导弹去击中运动的目标,由于目标的行动是不断改变的,因此应当如何根据目标运动的情况,不断地决定导弹飞行的方向和速度,使之最快地命中目标。
(3)汽车刚买来时故障少、耗油低,出车时间长,处理价值和经济效益高。随着使用时间的增加则变得故障多,油耗高,维修费用增加,经济效益差。使用时间俞长,处理价值也俞低。另外,每次更新都要付出更新费用。因此,应当如何决定它每年的使用时间,使总的效益最佳。
动态规划模型是解决这类问题的有力工具,下面介绍相关的基本概念及其数学描述。
(1)阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段,描述阶段的变量称为阶段变量,记为 SKIPIF 1 0 。
(2)状态 状态表示每个阶段开始时所处的自然状况或客观条件,它描述了研究过程的状况。各阶段的状态通常用状态变量描述。常用 SKIPIF 1 0 表示第 SKIPIF 1 0 阶段的状态变量。 SKIPIF 1 0 个阶段的决策过程有 SKIPIF 1 0 个状态。用动态规划方法解决多阶段决策问题时,要求整个过程具有无后效性。即:如果某阶段的状态给定,则此阶段以后过程的发展不受以前状态的影响,未来状态只依赖于当前状态。
(3)决策 某一阶段的状态确定后,可以作出各种选择从而演变到下一阶段某一状态,这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用 SKIPIF 1 0 表示第 SKIPIF 1 0 阶段处于状态 SKIPIF 1 0 时的决策变量,它是 SKIPIF 1 0 的函数,用 SKIPIF 1 0 表示 SKIPIF 1 0 的允许决策集合。
(4)策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第 SKIPIF 1 0 阶段的状态 SKIPIF 1 0 开始到终止状态的后部子过程的策略记为 SKIPIF 1 0 。在实际问题中,可供选择的策略有一定范围,称为允许策略集合。其中达到最优效果的策略称为最优策略。
(5)状态转移方程 如果第 SKIPIF 1 0 个阶段状态变量为 SKIPIF 1 0 ,作出的决策为 SKIPIF 1 0 ,那么第 SKIPIF 1 0 阶段的状态变量 SKIPIF 1 0 也被完全确定。用状态转移方程表示这种演变规律,写作 SKIPIF 1 0 SKIPIF 1 0 , SKIPIF 1 0
(6)最优值函数 指标函数是系统执行某一策略所产生结果的数量表示,是用来衡量策略优劣的数量指标,它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。
下面的方程在动态规划逆序求解中起着本质的作用。
SKIPIF 1 0
称此为动态规划逆序求解的基本方程(贝尔曼方程)。
可以把建立动态规划模型归纳成以下几个步骤:
(1)将问题恰当地划分为若干个阶段;
(2)正确选择状态变量,使它既能描述过程的演变,又满足无后效性;
(3)规定决策变量,确定每个阶段的允许决策集合;
(4)写出状态转移方程;
(5)确定各阶段各种决策的阶段指标,列出计算各阶段最优后部策略指标的基本方程。
下面结合具体例子阐述建立动态规划模型的思路。
例13 生产计划问题。公司要对某产品制定周的生产计划,产品每周的需求量、生产和贮存费用、生产能力的限制、初始库存量等都是已知的,试在满足需求的条件下,确定每周的生产量,使周的总费用最少。
决策变量是第 SKIPIF 1 0 周的生产量,记作 SKIPIF 1 0 。已知下列数据及函数关系:第 SKIPIF 1 0 周的需求量 SKIPIF 1 0 :第 SKIPIF 1 0 周产量为 SKIPIF 1 0 时的生产费为 SKIPIF 1 0 ;第 SKIPIF 1 0 周初贮存量为时这
显示全部