- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2014-9-4
x (1) 1
* 2
8
管理运筹学课程组 ftp://211.71.69.239
s2 2
f 2 (2) max {g 2 ( x2 ) f 3 ( s3 )}
0 x2 s 2 * x2 (2) 2
3
例1 工业部拟将5台某种设备分配给所属的甲、乙、丙 三个工厂，各工厂若获得这种设备，可以为公司 提供的盈利如表。 问：这五台设备如何分配给各工厂，才能使 公司得到的盈利最大。 解：将问题按工厂分为三 个阶段，甲、乙、丙分别 编号为1，2，3。
工厂 盈利 设备台数 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12
0 x2 s 2 * x2 (0) 0 f 2 (1) max { g 2 ( x2 ) f 3 ( s3 )}
0 x2 s 2
s
2
1
g 2 (0) f 3 (1) 0 4 max max 5 x2 0,1 g 2 (1) f 3 (0) x2 0,15 0
动态规划应用举例 资源分配问题 生产与存贮问题 设备更新问题
2014-9-4
管理运筹学课程组 ftp://211.71.69.239
1
6.3Байду номын сангаас
资源分配问题
将数量一定的一种或若干种资源，恰当地分配 给若干个使用者，使目标函数为最优。 6.3.1一维离散资源分配问题 设有某种原料，总数量为 a ，用于生产 n 种产品。 若分配数量xi用于生产第i 种产品，其收益为gi(xi) 问应如何分配，才能使生产 n 种产品的总收入最大？ MAX =g1(x1)+ g2(x2)+‥ ‥+ gn(xn) s.t. x1+x2+…+ xn=a xi≥0 i=1,2, …,n
4
逆推法﹗
2014-9-4
管理运筹学课程组 ftp://211.71.69.239
sk+1=sk-uk=sk-xk k=3时，0s35， 0x3s3 f3(s3)=max﹝g3﹙x3﹚﹞
可分配的机器数量 0≤x3≤s3
工厂 盈利 设备台数 0 1 2 3 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12
2014-9-4 管理运筹学课程组 ftp://211.71.69.239 2
•uk:分配给生产第k种产品的原料数量，即uk=xk；
•sk:分配给用于生产第k种至第n种产品的原料数量；
•状态转移方程： sk+1=sk-uk=sk-xk
•决策集合：Dk(sk)={uk|0uk=xksk} •最优值函数fk(sk):数量为sk的原料分配给第k种产品 至第n种产品所得到的最大总收益，动态规划的递推 关系为：
f k (sk ) max {g k ( xk ) f k 1 (sk xk )} 0 xk sk f n (sn ) max g n ( xn ) xn sn
2014-9-4
k n 1,,1
管理运筹学课程组 ftp://211.71.69.239
2014-9-4 管理运筹学课程组 ftp://211.71.69.239 5
工 厂 盈利 设备台数 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12
s
3
2
s 3
3
2014-9-4
g3 (0) f 3 (2) max{g3 ( x3 ) f 4 (s4 )} max g3 (1) 6 0 x3 s3 x3 0,1, 2 g3 (2) * x3 (2) 2 g (0)
f4(s4)=0 分配的机器数量
S =?
S3=0,
f3(0)=max｛ g3﹙x3﹚+ f4(s4) ｝ = g3﹙0﹚ =0
0≤x3≤s3
x3 *(0) =0
S3=1,
f3(1)=max｛ g3﹙x3﹚+ f4(s4) ｝ =max
0≤x3≤s3
g3(0) x3=0,1 g3(1)
=4
x3 *(1) =1
工厂 盈利 设备台数 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12
s 4
3
s 5
3
2014-9-4
g3 (0) g3 (1) f 3 (4) max{g3 ( x3 ) f 4 ( s4 )} max g3 (2) 12 0 x3 s3 x3 0,1, 2,3, 4 g3 (3) g3 (4) * x3 (4) 4 g3 (0) g3 (1) g3 (2) f 3 (5) max{g3 ( x3 ) f 4 (s4 )} max g (3) 12 0 x3 s3 x3 0,1, 2,3, 4,5 3 g (4) 3 g3 (5) * x3 (5) 5 管理运筹学课程组 ftp://211.71.69.239 7
3
g3 (1) f 3 (3) max{g3 ( x3 ) f 4 (s4 )} max 11 0 x3 s3 x3 0,1, 2,3 g 3 (2) g (3) 3 * x3 (3) 3
管理运筹学课程组 ftp://211.71.69.239 6
s3
x3 0 1 2 3 4 5 0 0 1 4
g3(x3) 2 3 6 11
4
5
f3(s3) 0 4 6 11 12 12
x*3 0 1 2 3 4 5
12 12
当阶段k=2时， s3=s2-x2， 0s25， 0x2s2，有
s2 0
f 2 (0) max {g 2 ( x2 ) f 3 ( s3 )} g 2 (0) 0
