动态规划.

7-2动态规划应用举例例7-6一家著名的快餐店计划在某城市建立5个分店，这个城市分成三个区，分别用1，2，3表示。由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异，将对各分店的经营状况产生直接的影响。经营者通过市场调查及咨询后，建立了下表。该表表明了各个区建立不同数目的分店时的利润估计，确定各区建店数目使总利润最大。区区店数123店数1230000312149135441416102710751516112解：阶段：每个区，共三个阶段。状态：Sk为第k阶段开始时，可供分配的店数。决策：dk为分配给区k的店数。状态转移方程：Sk+1=Sk-dk效益：rk(dk)为分配给区k,dk个店时的利润。fk(Sk)为当第k阶段初始状态为Sk时，从第k阶段到最后阶段所得最大利润。fk(Sk)=Maxrk(dk)+fk+1(Sk+1)dk(Sk)k=1，2，3f4(S4)=0SS33ff33((SS33))dd**33SS33ff33((SS33))dd**3300039314141042725115k=3时，计算如下：区区店数123店数1230000312149135441416102710751516112k=2时，计算如下：RR22((dd22))++ff33((SS33))dd22SS22012345ff22((SS22))dd**2200-----00145----5127910---10239121414--142,3,41014171816-1835111519212016213S3=S2-d2k=1时，计算如下：最优解：d*1=3，d*2=2，d*3=0即：在区1建3个分店，在区2建2个分店，而不在区3建立分店。最大总利润=22。RR11((dd11))++ff22((SS22))dd11SS11012345ff11((SS11))dd**115212121221915223sif1(s1)d1*f2(s2)d2*f3(s3)d3*00000151412102723142,39341831045223213115d1*=3,s2=s1-d1*=5-3=2,d2*=2s3=s2-d2*=2-2=0,d3*=0建立动态规划模型的要点：•分析题意，识别问题的多阶段性，按时间或空间的先后顺序适当地划分满足递推关系的若干阶段，对非时序的静态问题要人为地赋予“时段”的概念。建立动态规划模型的要点：•正确地选择状态变量，使其具备两个必要特征：（1）可知性：即过去演变过程的各阶段状态变量的取值，能直接或间接地确定。（2）能够确切地描述过程的演变且满足无后效性。建立动态规划模型的要点：•根据状态变量与决策变量的含义，正确写出状态转移方程或转移规则。•根据题意明确指标函数，最优指标函数以及一段效益即阶段指标的含义。并正确列出最优指标函数的递推关系及边界条件（即DP基本方程）。例7-7（投资问题）现有资金5百万元，可对三个项目进行投资，投资额均为整数（单位为百万元），其中2#项目的投资不得超过3百万元，1#和3#项目的投资均不得超过4百万元，3#项目至少要投资1百万元，每个项目投资5年后，预计可获得收益由下表给出，问如何投资可望获得最大收益。投资额项目012341#03610122#051012-3#-481115解：这个投资问题可以分成三个阶段，在第k阶段确定k#的投资额令Sk——对1#，2#…...（k-1）#项目投资后剩余的资金额。Xk——对k项目的投资额。rk(Xk)——对k#项目投资Xk的收益.fk(Sk)——应用剩余的资金Sk对k#,(k+1)#…...N#投资可获得的最大收益。状态转移方程为：Sk+1=Sk-Xk为了获得最大收益，必须将5百万元全部用于投资，故假想有第4阶段存在时，必有S4=0，于是得递推方程：fk(Sk)=Maxrk(Xk)+fk+1(Sk+1)dk(Sk)k=3,2,1f4(S4)=0当k=3时，（3#至多投资4百万元，至少投资1百万元）f3(1）=4，f3(2）=8，f3(3）=11，f3(4）=15当k=2时，（2#投资不超过3百万元）f2(1）=r2(0)+f3(1）=0+4f2(2）=Maxr2(1)+f3(1)r2(0)+f3(2）=Max5+4，0+8=9当k=2时，（2#投资不超过3百万元）f2(3）=Maxr2(2)+f3(1)r2(1)+f3(2）r2(0)+f3(3）=Max10+4，5+8，0+11=14f2(4）=Maxr2(3)+f3(1）r2(2)+f3(2)r2(1)+f3(3）r2(0)+f3(4）=Max12+4，10+8，5+11，0+15=18当k=2时，（2#投资不超过3百万元）f2(5）=Maxr2(3)+f3(2）r2(2)+f3(3)r2(1)+f3(4）=Max12+8，10+11，5+15=21注意：3#至多投资4百万元当k=1时，S1=5（最初有5百万元，3#至少投资1百万元）f1(5）=Maxr1(0)+f2(5）r1(1)+f2(4)r1(2)+f2(3）r1(3)+f2(2）r1(4)+f2(1）=Max0+21，3+18，6+1410+9，12+4=21解：应用顺序反推可知，最优投资方案：方案1：X*1=0，X*2=2，X*3=3方案2：X*1=1，X*2=2，X*3=2最大收益均为21百万元。一维“背包”问题例7-8：有一辆最大货运量为10吨的卡车，用于装载三种货物，每种货物的单位重量及相应单位价值如下，应如何装载可使总价值最大？货货物物编编号号ii123单单位位重重量量（（吨吨））345单单位位价价值值CCii456解：设第i种货物装载的件数为xi(i=1,2,3)则问题可表示为：maxZ=4x1+5x2+6x33x1+4x2+5x310xi0且为整数(i=1,2,3)方法一：由于决策变量取整数，所以可以用列表法求解。当k=1时,f1(s)=max{4x1}03x1sx1为整数或f1(s)=max{4x1}=4[s/3]0x1s/3x1为整数计算结果见下表：s012345678910f1(s)0004448881212x1*00011122233当k=2时,f2(s)=max{5x2+f1(s-4x2)}0x2s/4x2为整数计算结果见下表：s012345678910x200000,10,10,10,10,1,20,1,20,1,2c2+f100044,54,58,58,98,9,1012,9,1012,13,10f2(s)00040,5589101213x2*00001101201当k=3时f3(10)=max{6x3+f2(10-5x3)}0x32x3为整数=max{6x3+f2(10-5x3)}x3=0,1,2=max{f2(10),6+f2(5),12+f2(0)}=max{13,6+5,12+0}=13此时x3*=0，可推得全部策略为：x1*=2，x2*=1，x3*=0，最大价值为13。方法二：问题最终要求f3(10)。而f3(10)=max{4x1+5x2+6x3}3x1+4x2+5x310xi为整数I=1,2,3=max{4x1+5x2+6x3}3x1+4x210-5x3xi为整数I=1,2,3=max{6x3+max[4x1+5x2]}10-5x303x1+4x210-5x3x30为整数xi0为整数I=1,2=max{6x3+f2(10-5x3)}x3=0,1,2=max{0+f2(10),6+f2(5),12+f2(0)}由此看到要计算f3(10)须先计算f2(10)，f2(5)，f2(0)而f2(10)=max{4x1+5x2}3x1+4x210x1，x20整数=max{4x1+5x2}3x110-4x2x1，x20整数=max{5x2+max[4x1]}10-4x203x110-4x2x20整数x10整数=max{5x2+f1(10-4x2}x2=0，1，2=max{f1(10),5+f1(6),10+f1(2)}同理，f2(5)=max{4x1+5x2}3x1+4x25x1，x20整数=max{5x2+f1(5-4x2)}x2=0，1=max{f1(5),5+f1(1)}f2(0)=max{4x1+5x2}3x1+4x20x1，x20整数=max{5x2+f1(0-4x2)}x2=0=f1(0)为了计算f2(10）f2(5)f2(0)需要先计算f1(10)f1(6)f1(5)f1(2)f1(1)f1(0)。由于f1(s)=max{4x1}=4[s/3]0x1s/3x1为整数f1(10)=12（x1=3），f1(6)=8（x1=2），f1(5)=4（x1=1），f1(2)=0（x1=0），f1(1)=0（x1=0），f1(0)=0（x1=0）。从而f2(10)=max{f1(10),5+f1(6),10+f1(2)}=max{12，5+8，10+0}=13（x1=2，x2=1）f2(5)=max{f1(5),5+f1(1)}=max{4，5+0}=5（x1=0，x2=1）f2(0)=f1(0)=0（x1=0，x2=0）最后有f3(10)=max{f2(10),6+f2(5),12+f2(0)}=max{13,6+5,12+0}=13（x1=2，x2=1，x3=0）二维“背包”问题例7-9：有一辆最大货运量为12吨，最大容量10立方米的某种类型卡车，用于装载两种货物A、B，每种货物的单件重量分别3吨、4吨，体积为1立方米、5立方米，价值为2、3，求合理装载的最大效益？解：设A、B货物装载的件数为xi(i=1,2)则问题可表示为：maxZ=2x1+3x23x1+4x212x1+5x210xi0整数(i=1,2)并解出f2(12，10)=max{2x1+3x2}3x1+4x212x1+5x210xi0整数(i=1,2)=max{2x1+3x2}3x112-4x2x110-5x2xi0整数(i=1,2)=max{3x2+f1(12-4x2,10-5x2)}12-4x2010-5x20xi0整数(i=2)=max{3x2+f1(12-4x2,10-5x2)}x212/4x210/5xi0整数(i=2)=max{3x2+f1(12-4x2,10-5x2)}x2=0,1,2=max{f1(12,10),3+f1(8,5),6+f1(4,0)}先要计算f1(12,10),f1(8,5),及f1(4,0)f1(12,10)=max{2x1}=max{2x1}3x112x1=0,1,2,3,4x110x10整数=8(x1*=4)同理，f1(8,5)=4(x1*=2)f1(4,0)=0(x1*=0)f2(12，10)=max{f1(12,10),3+f1(8,5),6+f1(4,0)}=max{8，3+4，6+0}=8(x1*=4x2*=0)因此，最优方案为：装A种货物4件，不装B种货物，最大价值为8。连续变量的解法例7-10：某公司有资金10万元，可投资于项目i(i=1,2,3)，若投资额为xi，其收益分别为g1(x1)=4x1，g2(x2)=9x2,g3(x3)=2x32,问如何分配投资额，使总收益最大？解：建立此问题的数学模型求xi使maxZ=4x1+9x2+2x32s.t.x1+x2+x310x1,x2,x30按变量个数分阶段，可看成三段决策问题，设状态变量sk表示：第k阶段可以分配给第k到第3个项目的资金额。决策变量xk：决定投资给第k个项目的资金额。则有：s1=10,s2=s1-x1,s3=s2-x2即状态转移方程为：sk+1=sk-xk令最优指标函数fk(sk)表示第k个阶段，初始状态为sk时，从第k个到第3个项目所获最大收益,f1(s1)即为所求的总收益。fk(sk)=max{gk(xk)+fk+1(sk+1)}xkk=3,2,1f4(s4)=0k=3时，f3(s3)=max{2x32}0x3s3当x3*=