4.3动态规划的建模与求解.ppt

动态规划的
建模与求解
建摸
1、理论依据
-----最优化原理
最优化原理:
一个过程的最优策略具有这样的性质,即无论初始状态及初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成最优策略
2、动态规划模型的几个要素:
1)阶段数k
2)状态变量sk
3)决策变量uk ( sk )
4)指标函数Vk,n
状态转移方程
5)最优值函数fk(sk)
3、建立动态规划模型的基本要求:
1)所研究的问题必须能够分成几个相互联系的阶段,而且在每一个阶段都具有需要进行决策的问题。
2)在每一阶段都必须有若干个与该阶段相关的状态
一般情况下,状态是所研究系统在该阶段可能处
于的情况或条件
建模时总是从与决策有关的条件中,或是从问题的约束条件中去选择状态变量。
3)具有明确的指标函数,且阶段指标值可以计算
4)能正确列出最优值函数的递推公式和边界条件
(b)能通过现阶段的决策,使当前状态转移
成下一阶段的状态
即能够给出状态转移方程
(c)状态的无后效性
状态的选取必须注意以下几个要点:
(a)在所研究问题的各阶段,都能直接或间
接确定状态变量的取值
例(资源分配问题)
某公司有资金a万元,拟投资于n个项目,已知对第i个项目投资xi万元,收益为
g i (xi),问应如何分配资金可使总收益最大?
解:阶段k=1,2, …,n
状态变量sk
决策变量uk
:第k个项目的投资额
:在第k阶段时可以用于投资
第k到第n个项目的资金数
状态转移方程:
sk+1 = sk -uk
指标函数Vk,n
:第k阶段可分配的资金数为sk时,
第k至第n个项目的最大总收益
边界条件:
k=n,n-1, …,2,1
资源分配问题的动态规划基本方程:
建立递推公式:
:在第k阶段分配的资金数为sk时,
第k至第n个项目的最大总收益
某种机器的工作系统由n个部件串联组成,只要有一个部件失灵,整个系统就不能正常工作。为提高系统工作的可靠性,在每一个部件上均装有主要元件的备用件,并设计了备用元件自动投入装置。显然,备用元件越多,整个系统的可靠性越大,但备用元件增多也会导致系统的成本、重量相应增大。设部件i(i=1,2, …,n)上装有xi个备用元件时,正常工作的概率为pi ( xi )。设装一个i部件的设备元件费用为ci ,重量wi为,要求整个系统所装备用元件的总费用不超过C,总重量不超过W,问如何选择个部件的备用元件数,使整个系统的工作可靠性最大?
例复合系统工作可靠性问题
解:设A---整个系统正常工作,Ai—部件i正常工作
满足:
非线性规划问题
系统由n个部件串联组成,每一个部件上装有备用件,部件i(i=1,2, …,n)上装有xi个备用元件时,正常工作的概率为pi ( xi )。设装一个i部件的设备元件费用为ci ,重量wi为,要求总费用不超过C,总重量不超过W,问如何选择个部件的备用元件数,使整个系统的工作可靠性最大?
例复合系统工作可靠性问题
解: n个部件=n个阶段
决策变量uk =
部件k上所装的备用元件数xk
状态变量:
sk
=第k个到第n个部件可使用的总费用
yk
=第k个到第n个部件容许的总重量
状态转移方程:
指标函数Vk,n