运筹学动态规划新a管理资料.pptx
多阶段决策问题：可将问题分为若干个相互联系的阶段，在每一阶段分别对应着若干个可以选择的决策，当每个阶段的决策选定之后，也就确定了问题的一个决策过程。将各阶段的决策综合起来，就构成了一个决策序列，称为问题的一个策略。显然，决策不同，过程的策略也不同。对应于每一个策略，都有一个确定的效果（值）。一般情况下，策略不同，效果也不同。多阶段决策的目的就是在所有可采取的策略中选取一个最优策略，使在一定条件下取得最优的效果。第1页/共85页第2页/共85页第3页/共85页例三：将一个数c（c0）分为n个部分c1,c2,cn 之和 ，且ci0（i=1，2，n）,问如何分割使其乘积 最大？第4页/共85页第二节 最优化原理与动态规划数学模型2.1 基本思想 将多阶段问题转化为单阶段问题，按着目标要求和递推关系求出最优结果。（用逆序解法解例1）第5页/共85页 例1 最短路线问题。设有一个旅行者从图8-1中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图中所示，问该旅行者应选择哪一条路线，使从A到达E的总路程为最短。第6页/共85页25375632455114633334C1C3D1AB1B3B2D2EC2第7页/共85页25375632455114633334C1C3D1AB1B3B2D2EC2f5(E)=0f4(D1)=3f4(D2)=4f3(C1)=4f3(C2)=7f3(C3)=6f2(B1)=11f2(B2)=7f2(B3)=8f1(A)=11状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态 A，（A，B3）,B3,（B3，C2），C2,（C2，D2）,D2，（D2，E）,E从A到E的最短路径为11，路线为AB3C2 D2 E。第8页/共85页第9页/共85页第10页/共85页第11页/共85页第12页/共85页2.2 动态规划的基本概念 阶段：问题需要做出决策的步数。阶段用k表示。通常，k=1，2，n。（逆序编号与顺序编号）。第13页/共85页2.状态：系统某阶段的出发位置或特征、状况。通常一个阶段包含有若干个（设r个）状态。每一阶段所有状态的集合称为状态变量集合。用Sk=ski i=1,2,r表示。第k阶段的状态变量Sk应包含该阶段之前决策过程的全部信息，做到从该阶段后做出的决策只与该状态有关，与这之前的状态和决策相互独立。（无后效性）状态可以是一个数或一组数，也可能不是数；可以使离散的，也可以是连续的；可以是确定的，也可以是随机的。（维数障碍）第14页/共85页3.决策：当某阶段的状态给定以后，从该状态演变到下一阶段某种状态的选择。决策变量xk(sk)表示第k阶段状态为sk时对方案的选择。显然，它是状态的函数。决策变量的取值要受到一定的限制（约束条件），用Dk(sk)表示k阶段状态为sk时的决策变量允许取值范围，称为允许决策集合，因而有 xk(sk)Dk(sk)。第15页/共85页4.策略和子策略：策略：动态规划问题各阶段决策组成的序列总体。子策略：从某一阶段开始到过程最终的决策序列称为问题的子过程策略。使问题达到最优效果的策略称为最优策略。第16页/共85页25375632455114633334C1C3D1AB1B3B2D2EC2f5(E)=0f4(D1)=3f4(D2)=4f3(C1)=4f3(C2)=7f3(C3)=6f2(B1)=11f2(B2)=7f2(B3)=8f1(A)=11状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态 A，（A，B3）,B3,（B3，C2），C2,（C2，D2）,D2，（D2，E）,E从A到E的最短路径为11，路线为AB3C2 D2 E。第17页/共85页5.状态转移方程：从sk的某一状态（值）出发，当决策变量xk(sk)的取值决定后，下一阶段状态变量sk+1（的取值）也就随之确定。这种从上一阶段的某一状态（值）到下一阶段某一状态（值）的转移规律称为状态转移率，也称状态转移方程。记为：第18页/共85页6.指标函数：（1）阶段指标函数：对应某一阶段状态和从该状态出发的一个决策的某种效益的度量。用 v k=(sk，xk）表示。第19页/共85页（2）过程指标函数Vk,n：从状态sk（k=1，2，n）出发至过程最终，当采取某种子策略时，按预定标准得到的效益值。它既与sk有关，也与sk以后所选取的策略有关。记作：第20页/共85页（3）最优指标函数：指对某一确定状态sk选取最优策略后得到的指标函数值。记作：f k(sk）=optVk,noptmax或min。第21页/共85页 上述基本概念在多阶段决策过程中的关系见图8-2。第22页/共85页2-3 最优化原理与动态规划的数学模型最优化原理:(R.Bellman)作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。即：最优策略的子策略都是最优的。第23页/共85页动态规划的基本方程（逆序）：（递推关系式）第24页/共85页第25页/共85页2-4 顺序解法状态转移率：第26页/共85页第27页/共85页2-5 动态规划模型的分类1.确定性，随机性2.离散性，连续性3.阶段数固定定期决策过程；阶段数不固定或无限不定期或无期决策过程注意事项：1.阶段2.状态变量3.决策变量4.状态转移率5.过程指标函数第28页/共85页用动态规划解决实际问题的基本过程是：1.正确划分阶段，选择阶段变量k；2.对每个阶段，正确选择状态变量sk，选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性；3.对每个阶段，正确选择决策变量xk；4.列出相邻阶段的状态转移方程:sk+1=Tk(sk,xk(sk)；5.列出按阶段可分的准则函数V1,n；6.写出递推方程和边界条件，建立基本方程；7.按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。第29页/共85页第三节 离散确定性动态规划模型的求解一、一维资源分配问题 假定有一种资源，其数量为a a，现须将它分配给n n个使用者，而使总收益最大。若分配给第i i个使用者的数量为x xi i(i=1,2,n)(i=1,2,n)，且由此产生的收益(或损失）为g gi i(x(xi i)(g)(gi i(x(xi i)是x xi i的单调递增(或递减)函数)，则该问题的数学模型为：第30页/共85页第31页/共85页 例4 某一警卫部门共有9支巡逻队，负责3个要害部位A、B、C的警卫巡逻。对每个部位可分别派出24支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见表8-1。问该警卫部门应往各部位分别派多少支巡逻队，使总的预期损失为最小。第32页/共85页(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 第33页/共85页状态转移方程：sk+1=sk xk (k=1,2,3)指标函数（递推方程）fk(sk)：s1 s2 s3 s4第34页/共85页第35页/共85页第36页/共85页X3*=2第37页/共85页第38页/共85页第39页/共85页第40页/共85页作业：P218 8.15二、设备负荷问题第41页/共85页第42页/共85页例：某种机器可在高低两种不同的负荷下运转，高负荷运转时，年损坏率为30%，每台机器的年收益为8万元；低负荷运转时，年损坏率为10%，每台机器的年收益为5万元。若第一年初有1000台设备，问每年如何安排生产，可使得5年内的总收益最大。第43页/共85页第44页/共85页第45页/共85页第46页/共85页第47页/共85页第48页/共85页第四节 离散随机性动态规划模型的求解作业：P216 8.4第49页/共85页N第k+1个阶段可能的状态数；pi（i=1,2,.N）给定状态sk和决策xk的情况下，下一个可能到达状态的概率；ci（或vi）（i=1,2,.N）从k阶段状态sk转移到k+1阶段状态为i时的指标函数值。基本方程：第50页/共85页第51页/共85页第52页/共85页第53页/共85页第54页/共85页作业：P216 8.8第五节 一般问题的动态规划解法一、用动态规划求解非线性规划问题第55页/共85页第56页/共85页0R220，2)内一阶导数大于零，故为增函数。第57页/共85页第58页/共85页第59页/共85页第60页/共85页第61页/共85页第62页/共85页第63页/共85页作业：P217 8.9(a)选作二、用动态规划求解线性规划问题补例：第64页/共85页R11=4,R21=12,R31=18R13=R12-0R23=R22-2X2R33=R32-2X2第65页/共85页第66页/共85页第67页/共85页三、背包问题第68页/共85页作业：P215 8.3第69页/共85页第70页/共85页离散第71页/共85页第72页/共85页第73页/共85页第74页/共85页四、生产计划问题第75页/共85页第76页/共85页第77页/共85页0 x44=d第78页/共85页第79页/共85页第80页/共85页第81页/共85页第82页/共85页五、二维资源分配问题第83页/共85页第84页/共85页感谢您的观看！第85页/共85页
