4.3动态规划的 建模与求解
4.3.1建摸 1、理论依据--最优化原理 最优化原理: 个过程的最优策略具有这样的性质, 即无论初始状态及初始决策如何,对于 先前决策所形成的状态而言,其以后的 所有决策必构成最优策略
4.3.1 建摸 1、理论依据 -----最优化原理 最优化原理： 一个过程的最优策略具有这样的性质， 即无论初始状态及初始决策如何，对于 先前决策所形成的状态而言，其以后的 所有决策必构成最优策略
2、动态规划模型的几个要素: 阶段数k 2状态变量S 3)决策变量uk(Sk) 状态转移方程S1=T(s,u4) 4)指标函数Vkn 5)最优值函数f(S
2、动态规划模型的几个要素： 1)阶段数k 2)状态变量sk 3)决策变量uk （ sk ） 4)指标函数Vk,n 状态转移方程 ( ) k k uk s T s , +1 = 5)最优值函数fk (sk )
3、建立动态规划模型的基本要求: 1)所研究的问题必须能够分成几个相互联系的 阶段,而且在每一个阶段都具有需要进行决策的 问题 2)在每一阶段都必须有若干个与该阶段相关的状态 建模时总是从与决策有关的条件中,或是从问 题的约束条件中去选择状态变量。 般情况下,状态是所研究系统在该阶段可能处 于的情况或条件
3、建立动态规划模型的基本要求： 1）所研究的问题必须能够分成几个相互联系的 阶段，而且在每一个阶段都具有需要进行决策的 问题。 2）在每一阶段都必须有若干个与该阶段相关的状态 一般情况下，状态是所研究系统在该阶段可能处 于的情况或条件 建模时总是从与决策有关的条件中，或是从问 题的约束条件中去选择状态变量
状态的选取必须注意以下几个要点: (a)在所研究问题的各阶段,都能直接或间 接确定状态变量的取值 (b)能通过现阶段的决策,使当前状态转移 成下一阶段的状态 即能够给出状态转移方程Sk=T(s,u) (c)状态的无后效性 即以第阶段的状态为出发点的后部子过程的 最优策略应与s之前的过程无关 3)具有明确的指标函数,且阶段指标值可以计算 4)能正确列出最优值函数的递推公式和边界条件
3)具有明确的指标函数，且阶段指标值可以计算 4)能正确列出最优值函数的递推公式和边界条件 （b）能通过现阶段的决策，使当前状态转移 成下一阶段的状态 即 能够给出状态转移方程 ( ) k k uk s T s , +1 = （c）状态的无后效性 最优策略应与 之前的过程无关 即以第 阶段的状态 为出发点的后部子过程的 k k s k s 状态的选取必须注意以下几个要点： （a）在所研究问题的各阶段，都能直接或间 接确定状态变量的取值
例(资源分配问题)某公司有资金a万元,拟投资于 n个项目,已知对第个项目投资x万元,收益为 g;(x),问应如何分配资金可使总收益最大? 解:阶段k=1,2,,n 状态变量s:在第k阶段时可以用于投资 第k到第n个项目的资金数 决策变量u:第k个项目的投资额 状态转移方程: k-ukUk={k|0≤k≤Sk} 指标函数Vkn:g,() i=k 最优值函数/(s):第k阶段可分配的资金数为s时 求f(a) 第k至第n个项目的最大总收益
例 （资源分配问题）某公司有资金a万元，拟投资于 n个项目，已知对第i个项目投资xi万元，收益为 g i (xi )，问应如何分配资金可使总收益最大？ 解：阶段k=1,2, …,n 状态变量sk 决策变量uk ：第k个项目的投资额 ：在第k阶段时可以用于投资 第k到第n个项目的资金数 状态转移方程：sk+1 = sk -uk 指标函数Vk,n ( ) = n i k ： gi ui ：第k阶段可分配的资金数为sk时， 第k至第n个项目的最大总收益 { | 0 } k k k k U = u u s ( ) k k 最优值函数f s f (a) 求 1
最优值函数(s):在第k阶段分配的资金数为s时, 第k至第n个项目的最大总收益 建立递推公式: f( sk)=maxi gk(ux) k(Zl 边界条件:fn1(sn)=0 资源分配问题的动态规划基本方程: (s)=max{g(a4)+fA1(s)k=n,n-1…2,1 0≤u1≤s M Sm)=0
f k (sk ) = 边界条件： k=n,n-1, …,2,1 f n+1 (sn+1 ) = 0 资源分配问题的动态规划基本方程： ( ) ( ) ( ) ( ) = = + = − + + + + 0 max , 1, ,2,1 1 1 1 1 0 n n k k k k u s k k f s f s g u f s k n n k k 建立递推公式： ( ) gk uk ( ) + k+1 k+1 f s k k 0u s max ：在第k阶段分配的资金数为sk时， 第k至第n个项目的最大总收益 ( ) k k 最优值函数f s
例复合系统工作可靠性问题 某种机器的工作系统由n个部件串联组成,只要有 个部件失灵,整个系统就不能正常工作。为提 高系统工作的可靠性,在每一个部件上均装有主 要元件的备用件,并设计了备用元件自动投入装 置。显然,备用元件越多,整个系统的可靠性越 大,但备用元件增多也会导致系统的成本、重量 相应增大。设部件j(i=1,2,…,n)上装有x个备用元 件时,正常工作的概率为p;(x1)。设装一个邮部 件的设备元件费用为c,重量w;为,要求整个系 统所装备用元件的总费用不超过C,总重量不超过 W,问如何选择个部件的备用元件数,使整个系 统的工作可靠性最大?
某种机器的工作系统由n个部件串联组成，只要有 一个部件失灵，整个系统就不能正常工作。为提 高系统工作的可靠性，在每一个部件上均装有主 要元件的备用件，并设计了备用元件自动投入装 置。显然，备用元件越多，整个系统的可靠性越 大，但备用元件增多也会导致系统的成本、重量 相应增大。设部件i(i=1,2, …,n)上装有xi个备用元 件时，正常工作的概率为pi （ xi ）。设装一个i部 件的设备元件费用为ci ，重量wi为，要求整个系 统所装备用元件的总费用不超过C，总重量不超过 W，问如何选择个部件的备用元件数，使整个系 统的工作可靠性最大？ 例 复合系统工作可靠性问题
解:设A-整个系统正常工作,A部件i常工作 A=A1A2…An 则P(4)=P(4)P(A2)…P(4)=Ip(x) 数学模型为:求mxP=Ip(x) 满足:∑cx≤C ∑1x1≤W x≥0且为整数 非线性规 划问题
解：设A---整个系统正常工作，Ai—部件i正常工作 满足： c x C n i i i =1 w x W n i i i =1 xi 0且为整数 非线性规 划问题 ( ) ( ) ( ) ( ) 则P A = P A1 P A2 P An , A = A1 A2 An ( ) i i n i p x =1 = ( ) i i n i P p x 1 max = 数学模型为：求 =
例复合系统工作可靠性问题 系统由n个部件串联组成,每一个部件上装有备用件,部 件j(i=1,2,…,n)上装有x个备用元件时,正常工作的概率为 p;(x)。设装一个部件的设备元件费用为c;,重量w;为, 要求总费用不超过C,总重量不超过W,问如何选择个部 件的备用元件数,使整个系统的工作可靠性最大? 解:n个部件=n个阶段 决策变量u=部件k上所装的备用元件数x 状态变量: Sk=第k个到第n个部件可使用的总费用 yk=第k个到第n个部件容许的总重量 状态转移方程:∫S+1=Sk-ck Jk+ =yk- wru 指标函数Vkn=Ip1(u2)
系统由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个部件容许的总重量 状态转移方程： k+ = k − k uk s s c 1 k k wk uk y +1 = y − 指标函数Vk,n ( ) i i n i k p u = =