文档介绍：9 动态规划应用举例
例9-1 一家著名的快餐店计划在某城市建立5个分店,这个城市分成三个区,分别用1,2,3表示。由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异,将对各分店的经营状况产生直接的影响。经营者通过市场调查及咨询后,建立了下表。
该表表明了各个区建立不同数目的分店时的利润估计,确定各区建店数目使总利润最大。
解:
阶段:每个区,共三个阶段。
状态:Sk为第k阶段开始时,可供分配的店数。
决策:dk为分配给区k的店数。
状态转移方程:Sk+1=Sk-dk
效益:rk(dk)为分配给区k,dk个店时的利润。
fk(Sk)为当第k阶段初始状态为Sk时,从第k阶段到最后阶段所得最大利润。
fk(Sk)=Max rk(dk) + fk+1(Sk+1)
dk (Sk)
k=1,2,3
f4(S4)= 0
k=3 时, 计算如下:
k=2 时, 计算如下:
S3=S2-d2
k=1 时, 计算如下:
最优解:d*1 =3, d*2 =2,d*3 =0
即:在区1建3个分店,在区2建2个分店,而不在区3建立分店。最大总利润=22。
d1*=3,s2=s1- d1*=5-3=2, d2*=2
s3=s2- d2*=2-2=0, d3*=0
建立动态规划模型的要点:
分析题意,识别问题的多阶段性,按时间或空间的先后顺序适当地划分满足递推关系的若干阶段,对非时序的静态问题要人为地赋予“时段”的概念。