《运筹学》教学课件 动态规划例题.ppt

　　８.１　用动态规划方法求整数规划模型，而非线性规划模型的最优解。 例１　求解以下整数规划的最优解： 解　〔１〕建立动态规划模型： 阶段变量：将给每一个变量 赋值看成一个阶段， 划分为３个阶段，且阶段变量 设状态变量sk表示从第k阶段到第3阶段约束右端最大值，那么s1=10。 设决策变量xk表示第k阶段赋给变量xk的值(k=1,2,3)。 状态转移方程：s2=s1-3x1, s3=s2-4x2。 阶段指标：v1(s1,x1)=4x1, v2(s2,x2)=5x2, v3(s3,x3)=6x3 根本方程： 其中，a1=3,a2=4,a3=5。 〔2〕用逆序法求解： 当k=3时， ,[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中。 0 0 ? ? 0 0 1 0 ? ? 0 0 2 0 ? ? 0 0 3 0 ? ? 0 0 4 0 ? ? 0 0 5 0 6 ? 6 1 ? x3 s3 6x3+f4(s4) f3(s3) x3* 0 1 2 续表 ? 6 0 6 ? 6 1 7 0 6 ? 6 1 8 0 6 ? 6 1 9 0 6 ? 6 1 10 0 6 12 12 2 ? ? 当k=2时,有 f2(s2)=max{5x2+f3(s3)}=max{5x2+f3(s2-4x2)} 其中 所以当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)。现将有关数据列入表中。 s2 x2 5x2+f3(s2-4x2) f2(s2) x2* s3 0 1 2 0 0+0 ? ? 0 0 0 1 0+0 ? ? 0 0 1 2 0+0 ? ? 0 0 2 3 0+0 ? ? 0 0 3 4 0+0 5+0 ? 5 1 0 5 0+6 5+0 ? 6 0 5 6 0+6 5+0 ? 6 0 6 7 0+6 5+0 ? 6 0 7 8 0+6 5+0 10+0 10 2 0 9 0+6 5+6 10+0 11 1 5 10 0+12 5+6 10+0 12 0 10 当k=1时，有 其中， 而s1=10，故x1只能取0,1,2,3,由此确定f1(s1)。现将有关数据列入表中。 ? x1 s1 4x1+f2(s1-3x1) f1(s1) x1* s2 0 1 2 3 10 0+12 4+6 8+5 12+0 13 2 4 按计算顺序反推，由表可知，当x1*=2时，f1(s1)取得最大值13。又由s2=4查前面的表可得x2*=1及s3=0 ，再者，x3*=0。因此，最优解为 x1*=2, x2*=1, x3*=0，最优值maxZ=13。 8.2 一维资源分配问题 　 例2 某科研工程由三个小组用不同方法独立进行研究，它们失败的概率分别为0.40，0.60和0.80。为了减少三个小组都失败的可能性，现决定暂派两名高级科学家参加这一科研工程。把这两人分配到各组后，各小组仍失败的概率如下表所示，问应如何分派这两名高级科学家以使三个小组都失败的概率最小？ 高级科学家的人数 小 组 1 2 3 0 0.40 0.60 0.80 1 0.20 0.40 0.50 2 0.15 0.20 0.30 ? 解　〔１〕建立动态规划模型 按小组数将问题划分为３个阶段，阶段变量k=1,2,3。 状态变量sk表示第k阶段初可用于分配的科学家数，s1=2。 } 阶段指标vk(sk,xk)表示第k 个小组失败的概率。 过程指标函数Vk.n= 。 决策变量xk表示第k阶段分配给第k个小组的高级科学家人数。 状态转移方程：sk+1=sk-xk。 允许决策集合：Dk(sk)={xk 因而根本方程采用乘积形式，即 当k=3时， 　　因为s4=s3-x3=0，所以x3=s3〔即尚未分配给第１和第２小组的全局部配给第３小组〕。计算结果如表所示： s3 x3* f3(s3) 0 0 0.80 1 1 0.50 2 2 0.