动态规划(2).ppt

1、7-2动态规划应用示例7-6一家著名的快餐店计划在一个城市设立五个分店，该城市分为三个区，分别用1、2和3表示。由于各地区的地理位置、交通状况和居民构成的差异，将对各分公司的经营状况产生直接影响。经过市场调查和咨询，经营者制定了下表。该表显示了在每个地区设立不同数量的分支机构时的利润估计，并且通过确定在每个地区设立的分支机构的数量来使总利润最大化。解决方案：每个领域都有三个阶段。状态：Sk是在K阶段开始时可供分配的商店数量。决策：dk是分配给K区的商店数量。状态转移方程：Sk 1=Sk-dk效益：rk(dk)是分配给K和dk区商店的利润。fk(Sk)是当第k阶段的初始状态为Sk时，从第k阶段到

2、最后阶段的最大利润。当fk(sk)=max rk(dk)fk 1(sk 1)dk(sk)k=1，2，3f4 (S4)=0、k=3时，其计算如下：当k=2时，其计算如下：d*3=0 S2-D2最大总利润=22。D1 *=3，S2=S1-D1 *=5-3=2，D2 *=2s3=S2-D2 *=2-2=0，D3 *=0。建立动态规划模型的要点是：分析问题的意义，识别问题的多阶段，并按时间或空间顺序适当划分满足递归关系的几个阶段。建立动态规划模型的要点：正确选择状态变量要具备两个必要的特征：(1)可知性：可以直接或间接地确定过去演化过程中各阶段状态变量的值。(2)能准确描述过程的演化，不满足后效。建立

3、动态规划模型的要点：根据状态变量和决策变量的含义，正确编写状态转移方程或转移规则。根据问题的含义，定义了指数函数、最优指数函数和一段收益的含义，即阶段指数。正确列出了最优指标函数的递推关系和边界条件(即微分方程基本方程)。例7-7(投资问题)现有资金500万元，可用于投资三个项目。投资金额为整数(百万元)，其中2#项目投资不超过300万元，1#和3#项目投资不超过400万元，3#项目投资不低于100万元。每个项目投资5年后，预计收入如下表所示。询问如何获得最大的投资。解决方案：这个投资问题可以分为三个阶段。在k阶段，确定k #的投资金额，使Sk投资1#、2#.(k -1)#项目。Xk对k项目的

4、投资。Rk (Xk)投资k#项目Xk的收入。fk(Sk)在k #(k 1)#.N#通过使用剩余资金Sk。，状态转移方程为：Sk 1=Sk- Xk为了获得最大效益，必须用500万元进行投资。因此，当第四阶段存在时，S4=0是必要的，所以递推方程是fk(sk)=maxrk(xk)fk 1(sk 1)dk(sk)k=3，2，1f4 (S4投资至少100万元)f3(1)=4，f3(2)=8，f3(3)=11，f3(4)=15，当k=2，(2#投资少于300万元)F2 (1)=R2 (0) F3 (1)=0 4f2 (2当k (2#投资不超过300万元)F2 (3)=最高R2(2)F3(1)R2(1)F

5、3(2)R2(0)F3(3)=最高104，58，011=14，F2 (4)=最高R2(3)F3(1)R2(2)F3(2)R2(1)F3(3)R2(0)F3(4)=最高124，108，511，015=18，当k=2时，(2#投资不超过，当k=1时，3#至少应投资100万元)F1(5)=Max R1(0)F2(5)R1(1)F2(4)R1(2)F2(3)R1(3)F2(2)R1(4)F2(1)=Max 0 21，3 18，6 14 10 9，最优投资方案：方案1: x * 1=0，X*2=2，X * 3=3方案二：x * 1=1，X*2=2，X*3=2，最高收入为2100万元。一维“背包”问题示例

6、7-8:有一辆卡车，最大货运量为10吨，用于装载三种货物。每种货物的单位重量和相应的单位价值如下。总价值应该如何最大化？解决方法：如果第一类货物装载的件数是xi(i=1，2，3)，则问题可以表示为：Max Z=4x15x26x3 1x14x25x3 10，这是一个整数(i=1，2，3)。方法1:因为决策变量是一个整数，所以它可以通过列表方法来求解。当k=1时，f1(s)=max 4x1 03x1 s x1为整数或f1(s)=max 4x1=4 s/3 0 x1 s/3 x1为整数，计算结果如下：当k=2时，f2(s)=max 5x2 f1(s-4x2) 0 x2 s/4 x2为整数。当k=3，

7、f3(10)=最大6x3 f2(10-5x3) 0 x3 2 x3是一个整数=最大6x3f2 (10-5x3) x3*=0 0，1，2=最大f2(10)，6f2 (5)，12f2 (0)=最大13，65，120方法2:问题的最终要求是f3(10)。F3 (10)=最大4x1 5x2 6x3 3x1 4x2 5x3 10 Xi是整数1=1，2，3=最大4x1 5x2 6x3 3x1 4x2 10-5x3 Xi是整数1=1，2，3=最大6x3最大4x1 5x2 10-5x3 0 3x1 4x2 10-5x3 x3 0是整数xi 0是整数1=1，2=最大6x3 F2 (10-5x3) x3=0，1，

8、2=最大0f2 (10 f2(5)和f2(0)必须在f3(10)=max 4x15x23x14x210x1，x2 0 integer=max 4x 1 5x 2 3x 1 10-4x 2 x1，x2 0 integer，max 5x 2 max 4x 110-4x 203 x110-4x 2 x20 integer x1 0 integer=max 5x 2 f1(10-4x 2 x2=0，1，2=maxf1 (10)，5f1 (6)，10f1 (2)之前计算，同样如此。 F2(5)=最大4x1 5x2 3x1 4x2 5 x1，x2 0 integer=最大5x2 f1(5-4x2) x2=

9、0，1=maxf1 (5)，5f1 (1)，F2 (0)=max4x15x23x14x20x1，X2 0 integer=最大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)=最大4x1=4s/3 0 x1 s/3 x1是整数f1(10)=12(x1=3)，f1(6)=8(x1=2)，f1(5)=4(x1=1)，f1(2)=0 (x1=0因此F2 (10)=maxf1 (10)，5f1 (6)，10f1 (2)=max12，5 8，10 0=1

10、3 (x1=2，x2=1) F2 (5)=maxf1 (5)，5f1 (1)=max4，50 X2=1) f2(0)=f1(0)=0 (x1=0，x2=0)，最后F3 (10)=maxf2 (10)，6f2 (5)，12f2 (0)=max13，65， 120=13 (x1=2)用最大容量为10立方米的某型卡车装载甲、乙两种货物，每件货物重量分别为3吨和4吨，体积分别为1立方米和5立方米，取值分别为2和3，以获得合理装载的最大效益。解决方法：如果A和B装载的货物数量为xi(i=1，2)，则问题可以表示为：最大Z=2x13x23x14x212x15x210整数(i=1，2)，F2 (12，10)

11、=最大2x13x14x212x15x210整数(I=)2=最大2x 13 x2x3x 12-4x 2x 110-5x 2x 10整数(i=1，2)，最大3x2f1 (12-4x2， 6f1 (4，5) 0) f1 (12，10)=max2x1=max2x1 3x1 12x1=0，1，2，3，4x1 10x10 integer=8 (x1*=4)，同样，f1 (8，5)=4 (x1 *=2) f1 (4，0)=0 3f1 (8，5)，6f1 (4，0)=max8，34，60=8 (x1 *=4x2 *=0)。 因此，最好的方案是包装4件甲货而不包装乙货，最大值为8件。例7-10:一家公司有10万

12、元资金，可以投资项目一(i=1，2，3)。如果投资金额为xi，其收入为g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32。如何分配投资金额使总收益最大化？解决方案：建立该问题的数学模型，并找到xi，这样，根据变量的数量，最大Z=4x19X22x32 S.T. X1X2X310X1，X2，X30可视为一个三阶段决策问题。让状态变量sk表示可以分配给第kth阶段第三个项目的资金量。决策变量xk:决定kth项目的投资金额。有：s1=10，s2=s1-x1，s3=s2-x2，即状态转移方程为：sk 1=sk-xk，这样最佳指标函数fk(sk)代表kth阶段，当初始状态为sk时，获得从k

13、th到第3个项目的最大收益，f1(s1)是总收益。Fk (sk)=maxgk (xk) fk1 (sk1) xk k=3，2，1f4 (S4)=0，当k=3时，f3(s3)=最大2x32 0 x3 s3当x3*=s3时，最大值为2s32，即F3 (S3)=最大2x32 F2 (S2)=最大9X2F3 (S3)0x2S2=最大9X22S320x2S2=最大9X22 (S2-X2) 20x2S2，让h2(s2，x2)=0 s2终点：F2 (0)=2s22f2 (S2)=9s2f2 (0) F2 (S2)当s2 9/2时，x2*=0当s2 9/2时，f2 (0) F2 (S2)当x2 *=S2且k=1 F1(s1)=最大4x1 f2(s2) 0 x1 s1当f2(s2)=9 s2时，f1 (10)=最大4x19s1-9x10x110=最大9s1-5x10x110=9s1