运筹学-第3版-课件-动态规划例题

1、,.用动态规划方法求整数规划模型，而非线性规划模型的最优解。,例求解下列整数规划的最优解：,解（）建立动态规划模型：,划分为个阶段，且阶段变量,设状态变量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

2、=5,6,7,8,9时，x3可取0或1；当s3=10时，x3可取0,1,2，由此确定f3(s3)。,现将有关数据列入表4.1中。,续表,其中,由此确定f2(s2)。现将有关数据列入表中。,当k=1时，有,其中，,而s1=10，故x1只能取0,1,2,3,由此确定f1(s1)。现将有关数据列入表中。,按计算顺序反推，由表可知，当x1*=2时，f1(s1)取得最大值13。又由s2=4查前面的表可得x2*=1及s3=0 ，再者，x3*=0。因此，最优解为,x1*=2, x2*=1, x3*=0，最优值maxZ=13。,8.2 一维资源分配问题,例2 某科研项目由三个小组用不同方法独立进行研究，它们失

3、败的概率分别为0.40，0.60和0.80。为了减少三个小组都失败的可能性，现决定暂派两名高级科学家参加这一科研项目。把这两人分配到各组后，各小组仍失败的概率如下表所示，问应如何分派这两名高级科学家以使三个小组都失败的概率最小？,解（）建立动态规划模型 按小组数将问题划分为个阶段，阶段变量k=1,2,3。 状态变量sk表示第k阶段初可用于分配的科学家数，s1=2。,因而基本方程采用乘积形式，即,当k=3时，,因为s4=s3-x3=0，所以x3=s3（即尚未分配给第和第小组的全部分配给第小组）。计算结果如表所示：,（）采用逆序法求解：,当k=2时，,0.32,由上表知，x1*=1，f1(s1)=

4、0.060，由s2=1查前面的表知，x2*=0；由s3=1查表得x3*=0。,注：此问题还有一种更简捷的解法，将它化为最短路模型，即将各阶段状态作为结点，各小组失败的概率为弧线上的数据，见下图。然后在图上用逆序法计算，计算结果标于图上的方框内。,因此，所有一维资源分配（离散型）均可化为最短路问题来求解，在图上用逆序算法求解较简便。,.二维资源分配问题,例3设现有两种原料，数量各为单位，现要将这两种原料分配用于生产种产品。如果第一种原料以数量xj单位，第二种原料以数量yj单位用于生产第j种产品（j=1,2,3），所得的收入gj(xj,yj)如下表所示，问应如何分配这两种原料于种产品的生产，使总收入最大？,解（）建立动态规划模型,阶段变量：将两种原料分配用于生产每一种产品看成一个阶段，则可将问题划分为个阶段，即k=1,2,3。 状态变量(sk,uk), sk表示第k阶段初至第阶段可用于分配的第一种原料数量，uk表示第k阶段初至第阶段可用于分配的第二种原料数量。 决策变量(xk,yk), xk, yk分别表示第k阶段分配第k种产品用的第一种，第二种原料的数量，xk, yk取整数。 状态转移方程： sk+1=sk-xk uk+1=uk-yk,阶