动态规划应用举例 - 图文(7)

2。2 不确定性的采购问题

在实际问题中，还会遇到某些多阶段决策过程，其状态转移不是完全确定的，出现了随机性因素，状态转移是按照某种已知概率分布取值的。

具有这种性质的多阶段决策过程称为随机性决策过程。

用动态规划方法也可处理这类随机性问题，又称为随机性动态规划。

例6 采购问题。某厂生产上需要在近五周内必须采购一批原料，而估计在未来五周内价格有波动，其浮动价格和概率已测得如表9-8所示。试求在哪一周以什么价格购入，使其采购价格的数学期望值最小，并求出期望值。

表9-8

单价 500 600 700 概率 0。3 0。3 0。4 解 价格是一个随机变量，按某种已知的概率分布取值。用动态规划方法处理，按采购期限5周分为5个阶段，将每周的价格看作该阶段的状态。设

yk——状态变量，表示第k周的实际价格。

xk——决策变量，xk =1时表示第k周决定采购；xk=0时表示第k周决定等待。 ykE——第k周决定等待，而在以后采取最优决策时采购价格的期望值。

fk(yk)——第k周实际价格为yk时，从第k周至第5周采取最优决策所得的最小期望值。

因而可写出逆序递推关系式为

fk(yk)?min?yk,ykE?, yk?skf5(yk)?y5, y5?s5其中 sk??500,600,700?, k?1,2,3,4,5由ykE和fk(yk)的定义可知：

(9?13)(9?14)

(9?15)

ykE?Efk?1(yk?1)?0.3fk?1(500)?0.3fk?1(600)?0.4fk?1(700)并且得出最优决策为：

(9?16)

??1(采购) 当fk(yk)?ykxk????0(等待) 当fk(yk)?ykE从最后一周开始，逐步向前递推计算，具体计算过程如下。

(9?17)

k=5时，因f5(y5)?y5,y5?s5，故有f5(500)?500,f5(600)?600,f5(700)?700 即在第五周时，若所需的原料尚未买入，则无论市场价格如何，都必须采购，不能再等。

k=4时，由(9-16)式可知

y4E?0.3f5(500)?0.3f5(600)?0.4f5(700)?0.3?500?0.3?600?0.4?700?610

于是，由(9-13)式得

f4(y4)?min?y4,y4E??min?y4,610?y4?s4y4?s4?500 若 y4?500???600 若 y4?600?610 若 y?7004?由(9-17)式，第4周最优决策为

?1(采购) 若 y4?500 或 600x4??

0(等待) 若 y?700?4同理求得

f3(y3)?min?y3,y3E??min?y3,574?y3?s3y3?s3 ?500 若 y3?500???574 若 y3?600 或 700所以 x3???1 若 y3?500?0 若 y3?600 或 700y2?s2y2?s2

f2(y2)?min?y2,y2E??min?y2,551.8? ?500 若 y2?500???551.8 若 y2?600 或 700所以 x2???1 若 y2?500?0 若 y2?600 或 700y1?s1y1?s1

f1(y1)?min?y1,y1E??min?y1,536.26? ?500 若 y1?500???536.26 若 y1?600 或 700所以 x1???1 若 y1?500?0 若 y1?600 或 700

由上可知，最优采购策略为：在第一、二、三周时，若价格为500就采购，否则应该等待；在第四周时，价格为500或600应采购，否则就等待；在第五周时，无论什么价格都要采购。

依照上述最优策略进行采购时，价格(单价)的数学期望值为

23333???500?0.3?1?0.7?0.7?0.7?0.7?0.4?600?0.30.7?0.4?0.7?????700?0.42?0.73

?500?0.80106?600?0.14406?700?0.05488?525.382?525且 0.8010?6

0.14?4060.?0 5

三、 背 包 问 题

有一个人带一个背包上山，其可携带物品重量的限度为a公斤。设有n种物品可供他选择装入背包中，这n种物品编号为1，2，…，n。已知第i种物品每件重量为wi公斤，在上山过程中的作用(价值)是携带数量xi的函数ci(xi)。问此人应如何选择携带物品(各几件)，使所起作用(总价值)最大。这就是著名的背包问题。类似的问题有工厂里的下料问题，运输中的货物装载问题，人造卫星内的物品装载问题等等。

设xi为第i种物品的装入件数，则问题的数学模型为

max f??ci(xi)i?1n ?nwx?a??ii?i?1?x?0 且为整数 (i?1,2,?,n)?i它是一个整数规划问题。如果xi只取0或1，又称为0—1背包问题。下面用动态规划方法来求解。

设按可装入物品的n种类划分为n个阶段。

状态变量w表示用于装第1种物品至第k种物品的总重量。

??w?xw 决策变量xk表示装入第k种物品的件数。则状态转移方程为wkk??w????允许决策集合为Dk(w)??xk0?xk????

??wk????最优值函数fk(w)是当总重量不超过w公斤，背包中可以装入第1种到第k种物品的最大使用价值。即

fk(w)?max?wixi?wk?c(x)

iii?1kxi?0且为整数(i?1,2,?,k)i?1因而可写出动态规划的顺序递推关系为：

f1(w)?fk(w)?x1?0,1,?,?w/w1?x1?0,1,?,?w/wk?max?c1(x1)max?ck(xk)?fk-1(w?wkxk)? 2?k?n

然后，逐步计算出f1(w),f2(w),?,fn(w)，及相应的决策函数x1(w),x2(w),?,xn(w)，最后得出的fn(a)就是所求的最大价值，其相应的最优策略由反推运算即可得出。

例7 max f?4x1?5x2?6x3

?3x1?4x2?5x3?10 ?x?0且为整数，i?1,2,3?i

解 用动态规划方法来解，此问题变为求f3(10)。

f3(10)?3x1?4x2?5x3?10xi?0,整数，i?1,2,3max?4x1?5x2?6x3??3x1?4x2?10?5x3xi?0,整数，i?1,2,3max?4x1?5x2?(6x3)??????max?6x3?max?4x1?5x2???max?6x3?f2(10?5x3)? 10?5x3?03x1?4x2?10?5x3x3?0,1,2?x3?0,整数?x?0,x?0,整数?12??max?0?f2(10),6?f2(5),12?f2(0)?由此看到，要计算f3(10)，必须先计算出f2(10),f0(5),f2(0)

f2(10)?3x1?4x2?10x1?0,x2?0,整数max?4x1?5x2??3x1?10?4x2x1?0,x2?0,整数max?4x1?(5x2)??????max?5x2?max(4x1)??max?5x2?f1(10?4x2)?10?4x2?03x1?10?4x2x2?0,1,2?x2?0,整数?x?0,整数?1??max?f1(10),5?f1(6),10?f1(2)?f2(5)?f2(0)?3x1?4x2?5x1?0,x2?0,整数

max?4x1?5x2??max?5x2?x?0,12f1(5?4x2)??max?f1(5),5?f1(1)?f1(0?4x2)??f1(0)3x1?4x2?0x1?0,x2?0,整数max?4x1?5x2??max?5x2?x?02为了要计算出f2(10),f2(5),f2(0)，必须先计算出f1(10),f1(6),f1(5),f1(2),f1(1),f1(0)，一般地有

f1(w)?max(4x1)?4?(不超过w/3的最大整数)?4??w/3?

3x1?wx1?0,整数相应的最优决策为x1=［w/3］，于是得到

f1(10)?4?3?12 (x1?3);f1(6)?4?2?8 (x1?2)f1(5)?4?1?4 (x1?1);f1(2)?4?0?0 (x1?0) f1(1)?4?0?0 (x1?0);f1(0)?4?0?0 (x1?0)从而

f2(10)?max?f1(10),5?f1(6),10?f2(0)??max?12,5?8,10?0??13 (x1?2,x2?1)f2(5)?max?f1(5),5?f1(1)??max?4,5?0??5 (x1?0,x2?1)f2(0)?f1(0)?0 (x1?0,x2?0)故最后得到

f3(10)?max?f2(10),6?f2(5),12?f2(0)??max?13,6?5,12?0??13 (x1?2,x2?1, x3?0)所以，最优装入方案为x1?2,x2?1,x3?0，最大使用价值为13。

***

如果再增加对背包体积的限制为b，并假设第i种物品每件的体积为vi立方米，问应如何装使得总价值最大。这就是“二维背包问题”，它的数学模型为

nmax f??ci(xi)i?1?n??wixi?a?i?1 n???vixi?b?i?1?xi?0, …… 此处隐藏：2789字，全部文档内容请下载后查看。喜欢就下载吧 ……