《运筹学研究生辅导课件》动态规划例1 求解下列整数规划的最优解.doc
文本预览下载声明
例1 求解下列整数规划的最优解:
解 (1)建立动态规划模型:
阶段变量:将给每一个变量赋值看成一个阶段,划分为3个阶段,且阶段变量k=1,2,3.
设状态变量表示从第阶段到第3阶段约束右端最大值,则
设决策变量表示第阶段赋给变量的值.
状态转移方程:
阶段指标:
基本方程;
其中
用逆序法求解:
当时,
而表示不超过的最大整数。因此,当时,;当时,可取0或1;当时,可取0,1,2,由此确定现将有关数据列入表4.1中
表4.1中.
0 1 2 0
1
2
3
4
5
6
7
8
9
10 0
0
0
0
0
0
0
0
0
0
0
6
6
6
6
6
6
12 0
0
0
0
0
6
6
6
6
6
12 0
0
0
0
0
1
1
1
1
1
2 当时,有
而。所以当时,;当时,;当时。由此确定。现将有关数据列入表4.2中.
表4.2
0 1 2 0
1
2
3
4
5
6
7
8
9
10 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
10+0
10+0
10+0 0
0
0
0
5
6
6
6
10
11
12 0
0
0
0
1
0
0
0
2
1
0 0
1
2
3
0
5
6
7
0
5
10 当时,有
而故只能取0,1,2,3,由此确定。现将有关数据列入表4.3中。
表 4.3
0 1 2 3 10 0+12 4+6 8+5 12+0 13 2 4 按计算顺序反推,由表4.3可知,当及
例5 用动态规划方法解下列非线性规划问题
解: 解决这一类静态规划问题,需要人为地赋予时间概念,从而将该问题转化为多阶段决策过程。
按问题的变量个数划分阶段,把它看作一个三阶段决策问题,k=1,2,3
设状态变量为s1,s2,s3,s4并记s1≤c
取问题中的变量x1,x2,x3为决策变量
状态转移方程为: s3=x3 s3+x2=s2 s2+x1=s1≤c
允许决策集合为: x3=s3 0≤x2≤s2 0≤x1≤s1
各阶段指标函数为:v1(x1)=x1 v2(x2)=x22 v3(x3)=x3,各指标函数以乘积方式结合,最优指标函数fk(sk)表示从第k阶段初始状态sk出发到第3阶段所得到的最大值,则动态规划基本方程为:
用逆序解法由后向前依次求解:
k=3时,
x3*=s3
k=2时,
令h2(s2,x2)=x22(s2-x2)
用经典解析法求极值点:
解得: x2=0(舍)
所以是极大值点。
k=1时,
令
解得: x1=s1(舍)
所以是极大值点。
由于s1未知,所以对s1再求极值,
显然s1=c时,f1(s1)取得最大值
反向追踪得各阶段最优决策及最优值:
s1=c
所以最优解为:
例6 用动态规划方法解下列非线性规划问题
解: 按变量个数将原问题分为三个阶段,阶段变量k=1,2,3;
选择xk为决策变量;
状态变量sk表示第k阶段至第3阶段决策变量之和;
取小区间长度Δ=1,小区间数目m=6/1=6,状态变量sk的取值点为:
状态转移方程: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阶段所得到的最大值,动态规划的基本方程为:
k=3时,
s3及x3取值点较多,计算结果以表格形式给出,见表6.1-6.3所示。
表6.1 计算结果
x3 f3(s3) x3* 0 1 2 3 4 5 6 0
1
2
3
4
5
6 0
1
8
27
64
125
216 0
1
8
27
64
125
216 0
1
2
3
4
5
6
表6.2 计算结果
x2 f3(s2-x2) f2(s2) x2* 0 1 2 3 4 5 6 0
1
2
3
4
5
6 0
0
0
0
0
0
0
1×0
1×1
1×8
1×27
1×64
1×125
2×0
2×1
2×8
2×27
2×64
显示全部