文档详情

《运筹学研究生辅导课件》动态规划例1 求解下列整数规划的最优解.doc

发布:2016-12-31约8.84千字共15页下载文档
文本预览下载声明
例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
显示全部
相似文档