智能优化-动态规划概要

4动态规划4.1多阶段决策问题与动态规划4.2动态规划的基本概念4.3动态规划的步骤4.4动态规划的应用1求解静态规划问题2资源分配问题3背包问题4库存问题4.1多阶段决策问题与动态规划例1最短路问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643求A~G的最短路径？例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产．在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝g(u),这时机器的年完好率为a（0a1)．在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝h(v),这时机器的年完好率为b（ab1）．假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。以上两个问题都可以划分为先后多个决策阶段。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示：状态状态状态3状态n．．．１２ｎ决策1决策2决策n状态n+112多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。最优性原理作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策序列必然构成最优子序列。这种过去的状态和决策对于今后的决策所形成的状态没有影响，也称为无后效性或者马尔可夫性。(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。(2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。4.2动态规划的基本概念（一）(4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n＝{u1,u2,……,un}称为全过程策略，简称策略；而在k子过程上的决策序列pk,n＝{uk,uk+1,……,un}称为k子过程策略，简称子策略。(5)状态转移方程若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1＝Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。(6)指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为Vk,n＝Vk,n(sk,uk,sk+1,uk+1,……,sn,un)动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是：①各阶段指标函数的和Vk,n＝∑vj(sj,uj)；②各阶段指标函数的积Vk,n＝∏vj(sj,uj)。把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称为最优值函数，记为fk(sk)。即fk(sk)＝optVk,n(sk,uk,……,sn,un)uk,…,un式中的“opt”（optimization）根据具体问题而取min或max。(7)基本方程通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,n＝∑vj(sj,uj)，则有fk(sk)＝opt{vk(sk,uk)+fk+1(sk+1)}uk∈Dk(sk)(k＝n,n-1,…,1)递推方程fn+1(sn+1)＝0边界条件递推方程和边界条件一起称为动态规划的基本方程。可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。例最短路问题AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643此问题的基本方程为fk(sk)＝Min{dk(uk)+fk+1(sk+1)}uk∈Dk(sk)k＝6,5,4,3,2,1f7(s7)＝04.3动态规划的步骤（一）当k=6时s6u6D(u6)+f7(s7)F6(s6)F1F1G4+0=4*4F2F2G3+0=3*3按基本方程由后向前继续递推有:当k=5时当k=4时s4u4d(u4)+f5(s5)f4(s4)D1D1E1D1E22+7=92+5=7*7D2D2E2D2E31+5=6*2+9=116D3D3E2D3E33+5=8*3+9=128s5u5d(u5)+f6(s6)f5(s5)E1E1F1E1F23+4=7*5+3=87E2E2F1E2F25+4=92+3=5*5E3E3F1E3F26+4=106+3=9*9当k=3时s3u3d(u3)+f4(s4)f3(s3)C1C1D1C1D26+7=13*8+6=1413C2C2D1C2D23+7=10*5+6=1110C3C3D2C3D33+6=9*3+8=119C4C4D2C4D38+6=144+8=12*12当k=2时当k=1时s2u2d(u2)+f3(s3)f2(s2)B1B1C1B1C2B1C31+13=143+10=13*6+9=1513B2B2C2B2C3B2C48+9=177+9=16*6+12=1816s1u1d(u1)+f2(s2)f1(s1)AAB1AB25+13=18*3+16=1918由此可以看出，A到G的最短路长为18，路径为：A→B1→C2→D1→E2→F2→G现在把动态规划法的步骤归纳如下：(1)将所研究问题的过程划分为n个恰当的阶段，k＝1,2,…,n；(2)正确地选择状态变量Sk，并确定初始状态S1的值；(3)确定决策变量uk以及各阶段的允许决策集Dk(Sk)；(4)给出状态转移方程；(5)给出满足要求的过程指标函数Vk,n及相应的最优值函数；(6)写出递推方程和边界条件，建立基本方程；(7)按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。4.3动态规划的步骤（二）例2：机器负荷问题某种机器可以在高低两种不同的负荷下进行生产．在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝8u,这时机器的年完好率为a=0.7．在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝5v,这时机器的年完好率为b=0.9．假定开始生产时完好的机器数量为s1＝1000，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。(1)按年数划分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数sk为状态变量,s1=1000(3)取第k年投入高负荷的机器数xk为决策变量,0≤xk≤sk(4)状态转移方程为sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指标函数为Vk,5=∑[8xj+5(sj-xj)]=∑(5sj+3xj)(6)基本方程为fk(sk)＝max{5sk+3xk+fk+1(sk+1)}k=5,4,3,2,10≤xk≤skf6(s6)＝0解:当k=5时f5(s5)＝max{5s5+3x5+f6(s6)}=max{5s5+3x5}=8s5(x5*=s5)0≤x5≤s50≤x5≤s5当k=4时f4(s4)＝max{5s4+3x4+8s5}=max{5s4+3x4+8(0.9s4-0.2x4)}0≤x4≤s40≤x4≤s4=max{12.2s4+1.4x4}=13.6s4(x4*=s4)0≤x4≤s4当k=3时f3(s3)＝max{5s3+3x3+13.6s4}=max{5s3+3x3+13.6(0.9s3-0.2x3)}0≤x3≤s30≤x3≤s3=max{17.24s3+0.28x3}=17.5s3(x3*=s3)0≤x3≤s3当k=2时f2(s2)=max{5s2+3x2+17.52s3}=max{5s2+3x2+17.52(0.9s2-0.2x2)}0≤x2≤s20≤x2≤s2=max{20.77s2-0.504x2}=20.7s4(x2*=0)0≤x2≤s2当k=1时f1(s1)=23.7s1(x1*=0)f1(1000)=23700s1=1000,x1*=0s2=900,x2*=0s3=810,x3*=810s4=576,x4*=576s5=397,x5*=397某些静态规划问题可用动态规划法来求解。例用动态规划法求解maxz=x1.x22.x3x1+x2+x3=cxi≥0i=1,2,34.4动态规划的应用(一)1求解静态规划问题该题在课本p145页例3解:把问题看成一个三阶段决策问题，对应关系状态变量:s1,s2,s3,s4;sk表示从第k阶段到最后一个阶段可以分配的资源，s1=c。决策变量：x1,x2,x3,x3;s.t.0=xk=sk;允许决策集:Dk(sk)={xk|0=xk=sk}状态转移方程:sk+1=sk-xk价值函数：Vk,第k阶段决策变量xk确定后对于目标函数的贡献：V1=x1;V2=x22;V3=x3基本方程:0)()}(),({max)(411)(kkkkkksDxkksfsfxsVsfkkk222222232222222222222222202222033220223*33333274)(32,02|)(0,32032),(max)]([max))((max)(;)(max)(2222222222ssfsxsdxhdxsxxsxdxdhxxhxsxsfxsfsxsxsfsxsxsxsxsx为极大值点舍去当k=3时，同样因此按照计算的顺序反推算得64/)(,4/64/)(,4/),(max])(274[max)]([max)(411*141111*1111031110221011111111csfcxssfsxxshxsxsfxsfsxsxsx微分求驻点得64)(max;4;2,44/)(,4/,4/2/4/316/)(,2/3/2,4/34/41*3*2*133*3*2233222*2*112ccfzcxcxcxcsfcxcccxsscsfcsxcccxss因此得到最优解资源分配问题例5.6:有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。1.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0≤dk≤xk5.状态转移方程：xk+1=xk-dk6.阶段指标：vk(xk,dk)见表中所示；7.递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}8.终端条件：f4(x4)=0k=4，f4(x4)=0k=3，0≤d3≤x3，x4=x3-d3k=2，0≤d