第五节 一般数学规划模型的动态规划解法

,2010,年,5,月,管理工程学院,运筹学,*,第五节 一般数学模型的动态规划解法,了解一般数学模型的动态规划解法,1,动态规划的一般性,动态规划的一局限性,2,例,6,：,用动态规划的逆序法求解下列非线性规划问题,解：,将变量,x,1,、,x,2,、,x,3,的取值分为三个阶段,k,=1,2,3,，,x,i,分别为第,i,个阶段的决策变量。,3,(1),状态变量设为,s,k,，有,s,1,=12,，,s,2,=,s,1,-,x,1,，,s,3,=,s,2,-3,x,2,，,s,4,=,s,3,-2,x,3,。,(2),各决策变量的允许值为：,0,x,1,s,1,，,0,x,2,s,2,/3,，,0,x,3,s,3,/2,。,解：,将变量,x,1,、,x,2,、,x,3,的取值分为三个阶段,k,=1,2,3,，,x,i,分别为第,i,个阶段的决策变量。,4,(3),数学模型为,当,k,=3,时,5,当,k,=2,时,6,当,k,=1,时,由,s,1,=12,，,x,1,*=4,知,s,2,=8,，,x,2*=4/3,，得,s,3,=4,，,x,3*=2,。,7,例,7,：,用动态规划方法求解线性规划问题：,8,解：,先将这个问题化为动态规划的模型。,(1),把确定,x,1,、,x,2,的值看作分两个阶段的决策，用,k,表示阶段数。状态变量为,k,阶段初各约束条件右端项的剩余值，分别用,R,1,k,、,R,2,k,、,R,3,k,来表示，它为下阶段决策变量提供依据。,(2),状态转移为：,:,9,(3),指标函数为：,V,k,2,=,c,k,x,k,+,V,k,+1,2,，,c,k,为,x,k,在目标函数中的系数。,(4),动态规划的递推方程可表为：,(5),边际条件,f,3,(,R,13,R,23,R,33,)=0,。,10,当,k,=2,时，,则,(,取到上限,),11,当,k,=1,时，,12,因为,所以,13,由此,即本例的最优解为,14,