第九讲 动态规划

湖州师范学院商学院12020年2月26日运筹学（operationalresearch,OR）第九讲动态规划商学院电子商务系湖州师范学院商学院22020年2月26日v2v3v4v7v5v9v6v8v1028512131071013112865885405847最短路径问题下图表示从起点v1到终点v10之间各点的距离。求v1到v10的最短路径。v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min{2+5,8+8,6+4}=7湖州师范学院商学院32020年2月26日动态规划问题具有以下基本特征1.问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。2.每一阶段都有相应的“状态”与之对应。3.每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。4.每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“不变嵌入”。第九讲动态规划湖州师范学院商学院42020年2月26日5.状态具有无后效性当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C290第九讲动态规划湖州师范学院商学院52020年2月26日动态规划基本原理是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。动态规划求解可分为三个步骤：分解、求解与合并。第九讲动态规划湖州师范学院商学院62020年2月26日（1）阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数k可以是确定数、不定数或无限数动态规划理论基本概念（3）决策（Decision）xk：从某一状态向下一状态过度时所做的选择。决策变量记为xk，xk是所在状态sk的函数。在状态sk下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。（2）状态（State）：描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为sk。各阶段所有状态组成的集合称为状态集。第九讲动态规划湖州师范学院商学院72020年2月26日(4)策略(Strategy)：从第1阶段开始到最后阶段全过程的决策构成的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。（5）状态转移方程(Statetransformationfunction)：某一状态以及该状态下的决策，与下一状态之间的函数关系，记为sk+1=T(sk,xk)（6）指标函数或收益函数(Returnfunction)：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。第九讲动态规划湖州师范学院商学院82020年2月26日k阶段指标函数从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。过程指标函数最优指标函数从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。)},({)(,,)(nkknksDdkkPsVsfoptkkk（Opt＝optimization表示“max”或“min”第九讲动态规划湖州师范学院商学院92020年2月26日动态规划要求过程指标满足递推关系，即1111(,,,,)[(,),(,,,)]kkkknkkkkkknVsxxxVvsxVsxx连和形式：1111(,,,,)(,(,,,)(,KKkkknkkkKkknnjjjnjkVVsxxxvsxVsxxvsxV＋）＋）最优指标函数是nksfxsvOptsfkkkkksDxkkkkk,,2,1)},(},({)(11)(第九讲动态规划湖州师范学院商学院102020年2月26日动态规划数学模型上式、边界条件及状态转移方程构成。如连和形式的数学模型：连乘形式(vj≠0)：1111(,,,,)(,)(,,,)(,)KKkkknkkkKkknnjjjnjkVVsxxxvsxVsxxvsxV＋=最优指标函数是nksfdsvOptsfkkkkksDxkkkkk,,2,1)},(},({)(11)(),(0)(,,2,1)},(},({)(111)(kkknnkkkkksDxkkxsTssfnksfxsvOptsfkkk第九讲动态规划湖州师范学院商学院112020年2月26日对于可加性指标函数，上式可以写为nksfxsvsfkkkkksDdkkoptkkk,,2,1)}(},({)(11)(上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为：nksfxsvsfkkkkksDxkkoptkkk,,2,1)}(},({)(11)(上式称为动态规划最优指标的递推方程，是动态规划的基本方程。边界条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的边界条件，即确定最后一个状态n下最优指标fn(sn)的值。第九讲动态规划湖州师范学院商学院122020年2月26日用逆序法列表求解例题k=n=5时，f5(v10)＝0)}(),({min)(55444)(44444sfxsvsfsDxk=4，递推方程为s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策x4*v7v7v10v1055+0=5*5v7v10v8v8v10v1088+0＝8*8v8→v10v9v9v10v1044+0=4*4v9v10第九讲动态规划湖州师范学院商学院132020年2月26日)}(),({min)(44333)(33333sfxsvsfsDxk=3，递推方程为：s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策x3*v5v5v7v5v8v5v9v7v8v92862+5=7*8+8=166+4=107v5v7v6v6v7v6v8v6v9v7v8v9125812+5=175+8=138+4=12*12v6v9第九讲动态规划湖州师范学院商学院142020年2月26日k=2，递推方程为：s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策x2*v2v2v5v2v6v5v6101310+7=17*13+12=2517v2v5v3v3v5v3v6v5v67107+7=14*10+12=2214v3v5v4v4v5v4v6v5v6131113+7=20*11+12=2320v4v5)}(),({min)(33222)(22222sfxsvsfsDx第九讲动态规划湖州师范学院商学院152020年2月26日k=1，递推方程为)}(),({min)(22111)(11111sfxsvsfsDxs1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策x1*v1v1v2v1v3v1v4v2v3v42852+17=19*8+14=225+20=2519v1v2最优值是上表中f1(s1)的值，从v1到v10的最短路长为19。最短路线反向追踪，查看最后一列最优决策，得到最短路径为：v1v2v5v7v10第九讲动态规划湖州师范学院商学院162020年2月26日例：公司拟将某种设备5台，分配给甲、乙、丙三个工厂，各工厂利润与设备数量之间的关系如表所示，问这5台设备如何分配使三个工厂的总利润为最大？第九讲动态规划6107245310000丙乙甲工厂设备台数34591213111111111212湖州师范学院商学院172020年2月26日阶段k：每决定一个工厂的设备数作为一个阶段，k=1,2,3,4。k=4为虚设的阶段状态变量sk：给第k个工厂时拥有的设备数决策变量xk：分配给第k个工厂的设备数决策允许集合：0≤xk≤sk状态转移方程：sk+1=sk－xk阶段指标：vk(sk，xk)见上表中的数据递推方程：11()max(,)()kkkkkkkfxvsxfs边界条件：f4(s4)=0数学模型为11144()max(,)()},3,2,1()00,2,4,6,8,1,2,3kkkkkkkkkkkfxvsxfskssxfxxk第九讲动态规划湖州师范学院商学院182020年2月26日k=4，终端条件f4(s4)=0。k=3，0≤x3≤s3，s4=s3－x3u3s3v3(s3,u3)f*3(s3)u*3012345000014412662311113412124512125湖州师范学院商学院192020年2月26日k=2，0≤x2≤s2，s3=s2－x2u2s2v2(s2,u2)+f*3(s3)f*2(s2)u*201234500+00010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161,250+125+1210+1111+611+4111+0212湖州师范学院商学院202020年2月26日k=1，0≤x1≤s1，s2=s1－x1由此可知最优解有两个，分别为:s1=5,x1*=0,s2=s1－x1=5,x2*=2,s3=s2－x2*=3,x3=3,s4=s3－x3=0；s1=5,x1*=2,s2=s1－x1=3,x2*=2,s3=s2－x2*=1,x3=1,s4=s3－x3=0；分配方案是，工厂甲为0台，工厂乙为2台，工厂丙为3台；或者工厂甲为2台，工厂乙为2台，工厂丙为1台。最大效益都是21万元第九讲动态规划u1s1v1(s1,u1)+f*2(s2)f*1(s1)u*101234550+213+167+149+1012+513+0210，2湖州师范学院商学院212020年2月26日例：某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为x,产量为g=10x，设备年完好率为a=0.75；在低负荷下投入生产的设备数量为y，产量为h=8y，年完好率为b=0.9。假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。阶段k：运行年份（k=1,2,3,4,5,6），k=1表示第一年初，k=6表示第五年末（即第六年初）；状态变量sk：第k年初完好的机器数（k=1,2,3,4,5,6），也是第k－1年末完好的机器数，其中s6表示第五年末（即第六年初）的完好机器数，s1＝100。决策变量xk：第k年初投入高负荷运行的机器数；状态转移方程：sk+1=0.75xk+0.9(sk－xk)第九讲动态规划湖州师范学院商学院222020年2月26日决策允许集合：Dk(sk)={xk|0xksk}阶段指标：vk(sk，xk)=10xk+8(sk－xk)终端条件：f6(s6)=0递推方程：