运筹学资料6动态规划2.ppt

《运筹学资料6动态规划2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7-2动态规划应用举例例7-6一家著名的快餐店计划在某城市建立5个分店，这个城市分成三个区，分别用1，2，3表示。由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异，将对各分店的经营状况产生直接的影响。经营者通过市场调查及咨询后，建立了下表。该表表明了各个区建立不同数目的分店时的利润估计，确定各区建店数目使总利润最大。解：阶段：每个区，共三个阶段。状态：Sk为第k阶段开始时，可供分配的店数。决策：dk为分配给区k的店数。状态转移方程：Sk+1=Sk-dk效益：rk(dk)为分配给区k,dk个店时的利

2、润。fk(Sk)为当第k阶段初始状态为Sk时，从第k阶段到最后阶段所得最大利润。fk(Sk)=Maxrk(dk)+fk+1(Sk+1)dk(Sk)k=1，2，3f4(S4)=0k=3时，计算如下：k=2时，计算如下：S3=S2-d2k=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*=2s3=s2-d2*=2-2=0,d3*=0建立动态规划模型的要点：分析题意，识别问题的

3、多阶段性，按时间或空间的先后顺序适当地划分满足递推关系的若干阶段，对非时序的静态问题要人为地赋予“时段”的概念。建立动态规划模型的要点：正确地选择状态变量，使其具备两个必要特征：建立动态规划模型的要点：正确地选择状态变量，使其具备两个必要特征：（1）可知性：即过去演变过程的各阶段状态变量的取值，能直接或间接地确定。建立动态规划模型的要点：正确地选择状态变量，使其具备两个必要特征：（1）可知性：即过去演变过程的各阶段状态变量的取值，能直接或间接地确定。（2）能够确切地描述过程的演变且满足无后效性。建立动态规划

4、模型的要点：根据状态变量与决策变量的含义，正确写出状态转移方程或转移规则。建立动态规划模型的要点：根据状态变量与决策变量的含义，正确写出状态转移方程或转移规则。根据题意明确指标函数，最优指标函数以及一段效益即阶段指标的含义。并正确列出最优指标函数的递推关系及边界条件（即DP基本方程）。例7-7（投资问题）现有资金5百万元，可对三个项目进行投资，投资额均为整数（单位为百万元），其中2#项目的投资不得超过3百万元，1#和3#项目的投资均不得超过4百万元，3#项目至少要投资1百万元，每个项目投资5年后，预计可获得

5、收益由下表给出，问如何投资可望获得最大收益。解：这个投资问题可以分成三个阶段，在第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

6、+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）=M

7、axr2(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)

8、+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吨的卡车，用于装载三种货物，每种货物的单位重量及相应单位价值如下，应如何装载可使总价值最大？解：设第i种货物装载的件数为xi(i=1,2,3)则问题可表