深圳大学管理学院：《运筹学》课程教学资源（案例PPT）服装公司

通籌学一态舰划 复合糸统工作可靠性问题 姓名:佘俊 学号:20070150212

运筹学—动态规划 复合系统工作可靠性问题 姓名：佘俊 学号：20070150212

内容 ≯动态规划的基本概念和基本原理 A6yx>动态规划模型的建立和求解 ≯动态规划在经济管理中的应用 复合系统工作可靠性问题

内容 ➢动态规划的基本概念和基本原理 ➢动态规划模型的建立和求解 ➢动态规划在经济管理中的应用 ➢复合系统工作可靠性问题

动态规划基本原理 最优化原理 “一个过程的最优策略具有这样的性质:即 3无论初始状态及初始决策如何,对于先前决策 所形成的状态而言,其以后的决策应构成最优 策略”。 B A

动态规划基本原理 最优化原理 “一个过程的最优策略具有这样的性质：即 无论初始状态及初始决策如何，对于先前决策 所形成的状态而言，其以后的决策应构成最优 策略” 。 A M B

内容 ≥动态规划的基本概念和基本原理 动态规划模型的建立和求解 ≯动态规划在经济管理中的应用 复合系统工作可靠性问题

内容

动态规划模型的建立 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步,在确 定多阶段特性后,按时间或空间先后顺序,将过程划分为若干 相互联系的阶段。对于静态问题要人为地赋予“时间”概念, 以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性,而且各 阶段状态变量的取值能够确定。一般地,状态变量的选择是从 过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量,同时要给出决 策变量的取值范围,即确定允许决策集合

1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确 定多阶段特性后，按时间或空间先后顺序，将过程划分为若干 相互联系的阶段。对于静态问题要人为地赋予“时间”概念， 以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性，而且各 阶段状态变量的取值能够确定。一般地，状态变量的选择是从 过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量，同时要给出决 策变量的取值范围，即确定允许决策集合。 动态规划模型的建立

4、确定状态转移方程 根据k阶段状态变量和决策变量,写出k1阶段状态变量,状态 转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数,建立动态规划基本方 程 阶段指标函数是指第k阶段的收益,最优指标函数是指从第k 阶段状态出发到第n阶段未所获得收益的最优值,最后写出动态 规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于动态规划模 型与线性规划模型不同,动态规划模型没有统-的模式,建模时必 须根据具体问题具体分析,只有通过不断实践总结,才能较好掌握 建模方法与技巧

4、确定状态转移方程 根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态 转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方 程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态 规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于动态规划模 型与线性规划模型不同，动态规划模型没有统一的模式，建模时必 须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握 建模方法与技巧

动态规划的求解 >离散变量的分段穷举法國 连续变量的解法國 逆序解法 顺序解法 ≯连续变量的离散化解法國 高维问题的降维法

动态规划的求解 ➢离散变量的分段穷举法 ➢连续变量的解法 ➢逆序解法 ➢顺序解法 ➢连续变量的离散化解法 ➢高维问题的降维法

A 134 D

A B 1 B 2 C 1 C 2 C 3 D 24 33 3 3 2 1 1 1 4

k f (sk)=opt( vk(Sk,uk)f(sk+d) n+1(n+1 k+1 2 k f(Skd=optv (skil,un) X(sk) f(s)=1

1 2  k s1 u1 s2 u2 s3 sk uk sk+1 1 2  k s1 u1 s2 u2 s3 sk uk sk+1 ( ) { ( , ) ( )} 1 k k 1 k k 1 k u k k f s opt v s u f s k + = + + − ( ) 0 f 0 s1 = ( ) { ( , ) ( )} = k k k + k+1 k+1 u k k f s opt v s u f s k f n+1 (sn+1 ) = 0 × × 1 1

fK(sk)= max [gk(xr)+fk+1(sk+1] 0≤uk≤Sk k=1,2, n+15n+1 )=0 Sk= Sk+1 k Sk=0,△,2△,…m△