第6章 动态规划应用.ppt

动态规划应用
资源分配问题
将数量一定的一种或若干种资源(原材料、资金、设备、劳动力、食品等)分配给若干使用者,使目标函数最优
某原料总数量 a,生产 n 种产品,分配数量 xi 生产第 i种产品,收益为 gi ( xi )。如何分配,才能使总收入最大?
将资源分阶段地分配给各个使用者,xk 为决策变量,累计的量或随过程变化的量为状态变量
sk ——分配用于生产 k 至 n 种产品的原料数
xk ——分配给第 k 种产品的原料数
状态转移方程—— sk+1 = sk-xk
允许决策集合——
fk(sk) ——数量 sk 的原料分配给 k 至 n 种产品所得的最大总收入
例某工业部门将五台设备分配给三个工厂,各工厂利用设备生产所获利润为

如何分配,使得利润最大?
工厂
设备台数
甲
乙
丙
0
0
0
0
1
3
5
4
2
7
10
6
3
9
11
11
4
12
11
12
5
13
11
12
该例子决策变量取离散值,销售的分配、投资分配、货物分配问题都是这类分配问题。这种只将资源合理分配不考虑回收的问题,称为资源平行分配问题。
考虑资源回收利用的问题,决策变量取连续值,称为资源连续分配问题。
数量s1的资源,生产A和B。生产情况如下表,如何安排生产使得总收入最大?
投入A的数量
投入B的数量
收入
回收的资源
第一年
u1
s1-u1
g(u1)+h(s1-u1)
s2=au1+b(s1-u1)
第二年
u2
s1-u2
g(u2)+h(s2-u2)
s3=au2+b(s2-u2)
第三年
u3
s3-u3
g(u3)+h(s3-u3)
s4=au3+b(s3-u3)
…
…
…
…
…
此问题写出静态规划模型
投入A的数量
投入B的数量
收入
回收的资源
第一年
u1
s1-u1
g(u1)+h(s1-u1)
s2=au1+b(s1-u1)
第二年
u2
s1-u2
g(u2)+h(s2-u2)
s3=au2+b(s2-u2)
第三年
u3
s3-u3
g(u3)+h(s3-u3)
s4=au3+b(s3-u3)
…
…
…
…
…
sk ——第 k 阶段(第 k 年)可投入的资源量
uk ——第 k 阶段(第 k 年)投入A的资源量,
则 sk-uk 为投入B的资源量,0≤uk ≤ sk
状态转移方程—— sk+1=auk+b(sk-uk)
最优值函数 fk(sk) 表示资源量 sk ,从第 k 阶段至第n 阶段采取最优分配方案所得最大总收入
动态规划的递推关系式为
例机器负荷问题某机器在高负荷下生产的产量函数为g=8u1,其中 u1 为投入生产的机器数量,完好率为a=;在低负荷下生产的产量函数为h=5y,其中y为投入生产的机器数量,完好率为b=。若开始生产时完好的机器数量1000台,如何安排高低负荷下的生产,使得五年的总产量最大?
固定资金分配问题
设有 n 个生产行业,都需要某两种资源。对于第k 个生产行业,如果用第1种 xk 和第2种资源 yk 进行生产,可获得利润为 rk(xk,yk)。若第一种资源的单价为 a,第2种资源的单价为 b,现有资金Z。问应购买两种资源各多少单位,分配到 n 个生产行业,使总利润最大?
zk ——用于第 k 行业的资金
sk ——用于第 k 至 n 行业的资金