例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
动态规划例1求解下列整数规划的最优解
