例1 求解下列整数规划的最优解:
maxZ?4x1?5x2?6x3
? ?3x1?4x2?5x3≤10s..t???xj≥0?j?1,2,3?,xj为整数.解 (1)建立动态规划模型:
阶段变量:将给每一个变量xj赋值看成一个阶段,划分为3个阶段,且阶段变量k=1,2,3. 设状态变量sk表示从第k阶段到第3阶段约束右端最大值,则sj?10. 设决策变量xk表示第k阶段赋给变量xk的值(k?1,2,3). 状态转移方程:s2?s1?3x1,s3?s2?4x2.
阶段指标:u1(s1,x1)?4x1,u2(s2,x2)?5x2,u3(s3,x3)?6x3. 基本方程;
?fk(sk)?max?uk?sk,xk??fk?1?sk?1???sk???k?3,2,1?0≤x3≤?? ??ak????f(s)?0.?44其中a1?3,a2?4,a3?5. (1) 用逆序法求解: 当k?3时,
f3?s3??max?6x3?f4?s4???maxss?3?0≤x3???5????3?0≤x3≤???5????6x3?,
而s3??0,1,2,3,4,5,6,7,8,9,10?.?x?表示不超过x的最大整数。因此,当s3?0,1,2,3,4时,
x3?0;x3可取0或1;x3可取0,当s3?5,6,7,8,9时,当s3?10时,1,2,由此确定f3?s3?.现将有关数据列入表中
表中. f0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 s3 x3 6x3?f4(s4) 1 6 6 2 f3(s3) 0 0 0 0 0 6 6 *x3 0 0 0 0 0 1 1
7 8 9 10 当k?2时,有
0 0 0 0 6 6 6 6 12 6 6 6 12 1 1 1 2 f2?s2??maxs?2?0≤x2≤????4???5x2?f3?s3???maxs?2?0≤x2≤????4???5x2?f3?s2?4x2??,
而s2??0,1,2,3,4,5,6,7,8,9,10?。所以当s2?0,1,2,3时,x2?0;当s2?4,5,6,7时,
x2?0或1;当s2?8,9,10时x2?0,1,2。由此确定f2?s2?。现将有关数据列入表中.
表 f 5x2?f3(s2?4x2) x2 0 0+0 0+0 0+0 0+0 0+0 0+6 0+6 0+6 0+6 0+6 0+12 5+0 5+0 5+0 5+0 5+0 5+6 5+6 1 2 10+0 10+0 10+0 s2 0 1 2 3 4 5 6 7 8 9 10 f3(s3) 0 0 0 0 5 6 6 6 10 11 12 *x3 s3 0 1 2 3 0 5 6 7 0 5 10 0 0 0 0 1 0 0 0 2 1 0 当k?1时,有
f1?s1??maxs?1?0≤x1≤???3????4x?f?s???122?1?0≤x1≤???3???maxs?4x?f?s?3x??,
1211而s1?10,故x1只能取0,1,2,3,由此确定f1?s1?。现将有关数据列入表中。 表 f x1 s1 10 0 0+12 算顺4x1?f2?s1?3x1? 1 4+6 序反2 8+5 推3 12+0 ,由f1?s1? 13 表可x1* 2 知,s2 4 当及
按计x1??2时,f1(s1)取得最大值13.又由s2?4查表4.2得x2??1,
s3?0,再由表4.1查得x3?0.因此,最优解为 x?2,x?1,x?0,最优解maxZ?13.?3?3?3
例5 用动态规划方法解下列非线性规划问题
2max z?x1?x2?x3?x1?x2?x3?c ??xi?0 i?1,2,3解: 解决这一类静态规划问题,需要人为地赋予时间概念,从而将该问题转化为多阶段决策过程。
按问题的变量个数划分阶段,把它看作一个三阶段决策问题,k=1,2,3 设状态变量为s1,s2,s3,s4并记s1≤c 取问题中的变量x1,x2,x3为决策变量 状态转移方程为: s3=x3 允许决策集合为: x3=s3
s3+x2=s2 0≤x2≤s2
s2+x1=s1≤c
0≤x1≤s1
v3(x3)=x3,各指标函
各阶段指标函数为:v1(x1)=x1 v2(x2)=x22
数以乘积方式结合,最优指标函数fk(sk)表示从第k阶段初始状态sk出发到第3阶段所得到的最大值,则动态规划基本方程为:
max[vk(xk)?fk?1(sk?1)] k?3,2,,1??fk(sk)?xk?Dk(sk) ???f4(s4)?1用逆序解法由后向前依次求解: k=3时,
f3(s3)?max[v3(x3)?f4(s4)]?max(x3)?s3
x3?D3(s3)x3?s3 x3*=s3
k=2时,
22f2(s2)?max[v2(x2)?f3(s3)]?max(x2?s3)?max[x2?(s2?x2)]
x2?D2(s2)0?x2?s20?x2?s2令h2(s2,x2)=x22(s2-x2) 用经典解析法求极值点:
dh22?2x2s2?3x2?0 dx2
解得:x2?2s2 3x2=0(舍)
d2h2?2s2?6x2 2dx2所以x2?
d2h22??2s2?0 2dx2x2?s23
2s2是极大值点。 32243f2(s2)?(s2)2(s2?s2)?s2
3327
*x2?2s2 3
k=1时,
f1(s1)?max[v1(x1)?f2(s2)]?max(x1?x1?D1(s1)0?x1?s1434s2)?max[x1?(s1?x1)3]
0?x1?s12727令h1(s1,x1)?x1?4(s1?x1)3 27dh1412?(s1?x1)3?x1(s1?x1)2(?1)?0 dx12727解得:x1?1s1 4x1=s1(舍)
d2h11212242422?(s?x)(?1)?(s?x)?x(s?x)?(s1?x1)(2x1?s1)1111111227272727dx1
d2h192??s1?0 127dx12x1?s141s1是极大值点。 414114f1(s1)?s1?(s1?s1)3?s1
42746414s1) 64 所以x1?
*x1?1s1 4由于s1未知,所以对s1再求极值,
0?s1?cmaxf1(s1)?max(0?s1?c显然s1=c时,f1(s1)取得最大值
f1(s1)?14c 6414c 644313f2(s2)?s2?c
27161f3(s3)?s3?c
4反向追踪得各阶段最优决策及最优值:
11s1?c 44321**s2?s1?x1?c x2?s2?c
43211**s3?s2?x2?c x3?s3?c
44111***所以最优解为:x1?c,x2?c,x3?c,z*424s1=c
*x1?
?f1(s1)?14c 64例6 用动态规划方法解下列非线性规划问题
3max z?x12?x2?x3?x1?x2?x3?6 ??xj?0 j?1,2,3解: 按变量个数将原问题分为三个阶段,阶段变量k=1,2,3;
选择xk为决策变量;
状态变量sk表示第k阶段至第3阶段决策变量之和;
取小区间长度Δ=1,小区间数目m=6/1=6,状态变量sk的取值点为:
k?2?sk?0,1,2,3,4,5,6 ??s1?6状态转移方程:sk+1=sk-xk;
允许决策集合:Dk(sk)={xk|0≤xk≤sk} k=1,2,3
xk,sk均在分割点上取值;
阶段指标函数分别为:g1(x1)=x12
g2(x2)=x2
g3(x3)=x33,
最优指标函数fk(sk)表示从第k阶段状态sk出发到第3阶段所得到的最大值,动态规划的基本方程为:
[gk(xk)?fk?1(sk?1)] k?3,2,1??fk(sk)?0max?xk?sk ???f4(s4)?1k=3时,
33 f3(s3)?max(x3)?s3x3?s3s3及x3取值点较多,计算结果以表格形式给出,见表所示。
表 计算结果
f s3 0 1 2 3 4 5 6 x3 f3(s3) 0 0 1 1 2 8 3 27 4 64 5 125 6 216 0 1 8 27 64 125 216 0 1 2 3 4 5 6 x3* x3
表 计算结果 f s2 x2 f3(s2-x2) f2(s2) 0 1 2 3 4 5 6 x2* x2