动态规划的应用.ppt

贪梦算法 第九章 动态规划的应用 §1 资源分配问题 例1：某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。 问：这五台设备如何分配给各个工厂，才能使国家的盈利最大？ 工厂 台 数 盈利 甲 乙 丙 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12 静态规划模型 动态规划求解 s3 max P3(x3) F3 (s3) X3* x3 0 1 2 3 4 5 0 0 0 0 1 4 4 1 2 6 6 2 3 11 11 3 4 12 12 4 5 12 12 5 K=3时计算结果： s2 max [P2(x2)+f2(s2-x2)] F2 (s2) x2* x2 0 1 2 3 4 5 0 0 0 0 1 0+4 5+0 5 1 2 0+6 5+4 10+0 10 2 3 0+11 5+6 10+4 11+0 14 2 4 0+12 5+11 10+6 11+4 11+0 16 1、2 5 0+12 5+12 10+11 11+6 11+4 11+0 21 2 K=2时计算结果： 不利用动态规划，怎么处理？ Lingo代码： sets: ts/1..6/:a; gc/1..3/; links(ts,gc):c,x; endsets data: a=0 1 2 3 4 5; c=0 0 0 3 5 4 7 10 6 9 11 11 12 11 12 13 11 12; enddata max=@sum(links(i,j):c(i,j)*x(i,j)); @for(gc(j):@sum(ts(i):x(i,j)) =1); @sum(links(i,j):a(i)*x(i,j))=5; @for(links(i,j):@bin(x(i,j))); Global optimal solution found at iteration: 0 Objective value: 21.00000 Variable Value Reduced Cost X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 0.000000 0.000000 X( 2, 1) 0.000000 -3.000000 X( 2, 2) 0.000000 -5.000000 X( 2, 3) 0.000000 -4.000000 X( 3, 1) 0.000000 -7.000000 X( 3, 2) 1.000000 -10.00000 X( 3, 3) 0.000000 -6.000000 X( 4, 1) 0.000000 -9.000000 X( 4, 2) 0.000000 -11.00000 X( 4, 3) 1.000000 -11.00000 X( 5, 1) 0.000000 -12.00000 X( 5, 2) 0.000000 -11.00000