例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；当s3?5,6,7,8,9时，x3可取0或1；当s3?10时，x3可取0，1，2，由此确定f3?s3?.现将有关数据列入表4.1中
表4.1中.
fs3012345x36x3?f4(s4)000000012f3(s3)000006*x30000016678910
当k?2时，有
0000066666
12
66661211112
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?。现将有关数据列入表4.2中.
表4.2 fx200+00+00+00+00+00+60+60+60+60+60+125x2?f3(s2?4x2)12s2012345678910当k?1时,有
f3(s3)00005666101112*x300001000210s30123056705105+05+05+05+05+05+65+610+010+010+0f1?s1??maxs?1?0≤x1≤???3????4x?f?s???122?1?0≤x1≤???3???maxs?4x?f?s121?3x1??,而s1?10,故x1只能取0,1,2,3,由此确定f1?s1?。现将有关数据列入表4.3中。表 4.3fs110按
x100+12计
算
顺
4x1?f2?s1?3x1?14+6序
反
28+5推
312+0，
由
f1?s1?13表
*x124.3可
知
s24,当
x1??2时,f1(s1)取得最大值13.又由s2?4查表4.2得x2??1,及
s3?0,再由表4.1查得x3?0.因此,最优解为?? x?3?2,x3?1,x3?0,最优解maxZ?13.例5 用动态规划方法解下列非线性规划问题
2maxz?x1?x2?x3?x1?x2?x3?c??xi?0i?1,2,3解： 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。
按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3设状态变量为s1，s2，s3，s4并记s1≤c取问题中的变量x1，x2，x3为决策变量状态转移方程为：s3=x3允许决策集合为：x3=s3
各阶段指标函数为：v1（x1）=x1
s3+x2=s20≤x2≤s2
v2（x2）=x22
s2+x1=s1≤c
0≤x1≤s1
v3（x3）=x3，各指标函
数以乘积方式结合，最优指标函数fk（sk）表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：
max[vk(xk)?fk?1(sk?1)]??fk(sk)?xk?Dk(sk)???f4(s4)?1k?3,2,,1用逆序解法由后向前依次求解：k=3时，
f3(s3)?max[v3(x3)?f4(s4)]?max(x3)?s3x3?D3(s3)x3?s3x3*=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?0dx2解得：x2?2s23x2=0（舍）
d2h2?2s2?6x22dx2所以x2?d2h22??2s2?02dx2x2?s232s2是极大值点。32243f2(s2)?(s2)2(s2?s2)?s23327*x2?2s23k=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)327dh1412?(s1?x1)3?x1(s1?x1)2(?1)?0dx12727解得：x1?1s14x1=s1（舍）
d2h11212242422?(s?x)(?1)?(s?x)?x(s?x)?(s1?x1)(2x1?s1)1111111227272727dx1d2h192??s1?0127dx12x1?s14所以x1?1s1是极大值点。414114f1(s1)?s1?(s1?s1)3?s142746414s1)64f1(s1)?14c64*x1?1s14由于s1未知，所以对s1再求极值，
0?s1?cmaxf1(s1)?max(0?s1?c显然s1=c时，f1（s1）取得最大值反向追踪得各阶段最优决策及最优值：
1114s1?cf1(s1)?c44643214313**s2?s1?x1?cx2?s2?cf2(s2)?s2?c4322716111**s3?s2?x2?cx3?s3?cf3(s3)?s3?c44411114***?c,x2?c,x3?c,z*?c所以最优解为：x142464s1=c*x1?例6 用动态规划方法解下列非线性规划问题
3maxz?x12?x2?x3?x1?x2?x3?6??xj?0j?1,2,3解： 按变量个数将原问题分为三个阶段，阶段变量k=1，2，3；
选择xk为决策变量；
状态变量sk表示第k阶段至第3阶段决策变量之和；
取小区间长度Δ=1，小区间数目m=6/1=6，状态变量sk的取值点为：
?sk?0,1,2,3,4,5,6??s1?6k?2状态转移方程：sk+1=sk－xk；
允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝k=1，2，3xk，sk均在分割点上取值；阶段指标函数分别为：g1（x1）=x12
动态规划的基本方程为：
[gk(xk)?fk?1(sk?1)]??fk(sk)?0max?xk?sk???f4(s4)?1k?3,2,1g2（x2）=x2g3（x3）=x33，
最优指标函数fk（sk）表示从第k阶段状态sk出发到第3阶段所得到的最大值，
k=3时，
33f3(s3)?max(x3)?s3x3?s3s3及x3取值点较多，计算结果以表格形式给出，见表6.1-6.3所示。
表6.1 计算结果
fs30123456x3f3(s3)0018276412521612345601827641252160123456x3*x3表6.2 计算结果fs2x2 f3(s2－x2)f2(s2)0123456x2*x2
动态规划例1 求解下列整数规划的最优解
