运筹学第八章_动态规划(新)a管理精品资料.ppt

作业：P215 8.1 8.2 第八章 动态规划 第一节 多阶段决策问题 动态规划是用来求解多阶段决策问题的。,多阶段决策问题：可将问题分为若干个相互联系的阶段，在每一阶段分别对应着若干个可以选择的决策，当每个阶段的决策选定之后，也就确定了问题的一个决策过程。将各阶段的决策综合起来，就构成了一个决策序列，称为问题的一个策略。 显然，决策不同，过程的策略也不同。对应于每一个策略，都有一个确定的效果（值）。一般情况下，策略不同，效果也不同。 多阶段决策的目的就是在所有可采取的策略中选取一个最优策略，使在一定条件下取得最优的效果。,例三：将一个数c（ c0）分为n个部分c1,c2,cn 之和 ，且ci0（i=1，2，n）, 问如何分割使其乘积 最大？,第二节 最优化原理与动态规划数学模型 2.1 基本思想 将多阶段问题转化为单阶段问题，按着目标要求和递推关系求出最优结果。 （用逆序解法解例1）,例1 最短路线问题。 设有一个旅行者从图8-1中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图中所示，问该旅行者应选择哪一条路线，使从A到达E的总路程为最短。,f5(E)=0,f4(D1)=3,f4(D2)=4,f3(C1)=4,f3(C2)=7,f3(C3)=6,f2(B1)=11,f2(B2)=7,f2(B3)=8,f1(A)=11,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态 A，（ A，B3）, B3 ,（B3，C2），C2,（C2，D2）, D2，（D2，E）, E 从A到E的最短路径为11，路线为AB3C2 D2 E 。,2.2 动态规划的基本概念 阶段： 问题需要做出决策的步数。阶段用k表示。通常， k=1，2，n。 （逆序编号与顺序编号）。,2. 状态：系统某阶段的出发位置或特征、状况。 通常一个阶段包含有若干个（设r个）状态。每一阶段所有状态的集合称为状态变量集合。用Sk= ski i=1,2,r表示。 第k阶段的状态变量Sk应包含该阶段之前决策过程的全部信息，做到从该阶段后做出的决策只与该状态有关，与这之前的状态和决策相互独立。（无后效性） 状态可以是一个数或一组数，也可能不是数；可以使离散的，也可以是连续的；可以是确定的，也可以是随机的。（维数障碍）,3. 决策： 当某阶段的状态给定以后，从该状态演变到下一阶段某种状态的选择。 决策变量xk(sk)表示第k阶段状态为sk时对方案的选择。显然，它是状态的函数。 决策变量的取值要受到一定的限制（约束条件），用Dk(sk)表示k阶段状态为sk时的决策变量允许取值范围，称为允许决策集合，因而有 xk(sk) Dk(sk) 。,4. 策略和子策略： 策略：动态规划问题各阶段决策组成的序列总体。 子策略：从某一阶段开始到过程最终的决策序列称为问题的子过程策略。 使问题达到最优效果的策略称为最优策略。,f5(E)=0,f4(D1)=3,f4(D2)=4,f3(C1)=4,f3(C2)=7,f3(C3)=6,f2(B1)=11,f2(B2)=7,f2(B3)=8,f1(A)=11,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态 A，（ A，B3）, B3 ,（B3，C2），C2,（C2，D2）, D2，（D2，E）, E 从A到E的最短路径为11，路线为AB3C2 D2 E 。,5. 状态转移方程： 从sk的某一状态（值）出发，当决策变量xk(sk)的取值决定后，下一阶段状态变量sk+1 （的取值）也就随之确定。这种从上一阶段的某一状态（值）到下一阶段某一状态（值）的转移规律称为状态转移率，也称状态转移方程。记为：,6. 指标函数： （1）阶段指标函数：对应某一阶段状态和从该状态出发的一个决策的某种效益的度量。用 v k= (sk，xk）表示。,（2）过程指标函数Vk,n ： 从状态sk（k=1，2，n）出发至过程最终，当采取某种子策略时，按预定标准得到的效益值。它既与sk有关，也与sk以后所选取的策略有关。记作：,（3）最优指标函数：指对某一确定状态sk选取最优策略后得到的指标函数值。记作： f k(sk） =optVk,n optmax或min。,上述基本概念在多阶段决策过程中的关系见图8-2。,2-3 最优化原理与动态规划的数学模型 最优化原理: (R.Bellman) 作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。即：最优策略的子策略都是最优的。,动态规划的基本方程（逆序）：（递推关系式）,2-4 顺序解法 状态转移率：,2-5 动态规划模型的分类 1.确定性，随机性 2.离散性，连续性 3.阶段数固定定期决策过程；阶段数不固定或无限不定期或无期决策过程 注意事项： 1.阶段 2.状态变量 3.决策变量 4.状态转移率 5.过程指标函数,用动态规划解决实际问题的基本过程是： 1.正确划分阶段，选择阶段变量k； 2.对每个阶段，正确选择状态变量sk， 选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性； 3.对每个阶段，正确选择决策变量xk ； 4.列出相邻阶段的状态转移方程: sk+1= Tk(sk, xk (sk) )； 5.列出按阶段可分的准则函数V1,n ； 6.写出递推方程和边界条件，建立基本方程； 7.按照基本方程递推求解。 以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。,第三节 离散确定性动态规划模型的求解 一、一维资源分配问题 假定有一种资源，其数量为a，现须将它分配给n个使用者，而使总收益最大。若分配给第i个使用者的数量为xi(i=1,2,n)，且由此产生的收益(或损失）为gi(xi)(gi(xi)是xi的单调递增(或递减)函数)，则该问题的数学模型为：,例4 某一警卫部门共有9支巡逻队，负责3个要害部位A、B、C的警卫巡逻。对每个部位可分别派出24支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见表8-1。问该警卫部门应往各部位分别派多少支巡逻队，使总的预期损失为最小。,逆序解法： 阶段k：要害部位（k=1，2，3） 。 状态变量sk：每个阶段初拥有的可派遣的巡逻队数（s1=a=9） 。 决策变量xk：对每个部位派遣的巡逻队数 。 Dk(sk) = xk(sk) 2 xk(sk) 4 （k=1,2,3）。,s1 s2 s3 s4,状态转移方程： sk+1= sk xk (k=1,2,3) 指标函数（递推方程） fk(sk) ： s1 s2 s3 s4,X3* =2,作业：P218 8.15 二、设备负荷问题,例：某种机器可在高低两种不同的负荷下运转，高负荷运转时，年损坏率为30%，每台机器的年收益为8万元；低负荷运转时，年损坏率为10%，每台机器的年收益为5万元。若第一年初有1000台设备，问每年如何安排生产，可使得5年内的总收益最大。,第四节 离散随机性动态规划模型的求解,作业：P216 8.4,N第k+1个阶段可能的状态数； pi（i=1,2,.N）给定状态sk和决策xk的情况下，下一个可能到达状态的概率； ci（或vi ）（i=1,2,.N）从k阶段状态sk转移到k+1阶段状态为i时的指标函数值。 基本方程：,作业：P216 8.8 第五节 一般问题的动态规划解法 一、用动态规划求解非线性规划问题,0R22,0，2)