[理学]动态规划的应用.ppt

第九章 动态规划的应用 §1 资源分配问题 例1：某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。 问：这五台设备如何分配给各个工厂，才能使国家的盈利最大？ 静态规划模型 动态规划求解 不利用动态规划，怎么处理？ 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))); 例2 机器负荷分配问题 某种机器可以在高低两种不同负荷下进行生产，设机器在高负荷下生产的产量为g=8u1，其中u1为投入生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。 假定开始生产时完好的机器数量s1=1000台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。 静态规划模型： Lingo代码 max=8*x1+5*(s1-x1)+8*x2+5*(s2-x2)+8*x3+5*(s3-x3)+8*x4+5*(s4-x4)+8*x5+5*(s5-x5); s2=0.7*x1+0.9*(s1-x1); s3=0.7*x2+0.9*(s2-x2); s4=0.7*x3+0.9*(s3-x3); s5=0.7*x4+0.9*(s4-x4); s6=0.7*x5+0.9*(s5-x5); s1=1000; x1=s1; x2=s2; x3=s3; x4=s4; x5=s5; 动态规划 §2 生产与存储问题 例3：某工厂要对一种产品制定今后四个时期的生产计划，根据估计在今后四个时期内，市场对于该产品的需求量如下表所示： 假定该厂生产每批产品的固定成本为3（千元），若不生产就为0；每单位产品成本为1（千元）；每个时期生产能力所允许的最大生产批量为6单位；每个时期末未售出的产品每单位存储费用为0.5（千元）。还假设在第一个时期的初始库存量为0，第四个时期的库存量也为0.试问该厂应如何安排各个时期的生产与库存，才能满足市场需要的条件下，使总成本最小。 静态规划模型 动态规划 Lingo代码 min=3*y1+x1+0.5*v1+3*y2+x2+0.5*v2+3*y3+x3+0.5*v3+3*y4+x4+0.5*v4; M=10000; d1=2; d2=3; d3=2; d4=4; x1=y1*M; x2=y2*M; x3=y3*M; x4=y4*M; v0=0; v4=0; v1=x1-d1; v2=(x1-d1)+(x2-d2); v3=(x1-d1)+(x2-d2)+(x3-d3); v4=(x1-d1)+(x2-d2)+(x3-d3)+(x4-d4); v2=0; v3=0; v4=0; x1=6; x2=6; x3=6; x4=6; @gin(x1); @gin(x2); @gin(x3); @gin(x4); @bin(y1); @bin(y2); @bin(y3); @bin(y4); §3 背包问题 Lingo代码 max=10*x1+20*x2+30*x3+32*x4+40*x5+45*x6+50*x7+60*x8; x1+10*x2+20*x3+22*x4+30*x5+40*x6+45*x7+55*x8=110; @bin(x1); @bin(x2); @bin(x3); @bin(x4); @bin(x5); @bin(x6); @bin(x7); @bin(x8); 贪梦算法 * * 12 11 12 4 11 11 9 3 6 10 7 2 12 11 13 5 4 5 3 1 0 0 0 0 丙 乙 甲 工厂 台 数 盈利 Global optimal solution found at iteration: 0 Objective value: 21.00000 Variable