动态规划例1求解下列整数规划的最优解-第4篇.docx
5页
动态规划例1求解下列整数规划的最优解- 例1 求解下列整数规划的最优解：()123123max 45634510..01,2,3,j j Z x x x x x x s t x j x =++++???=??≤≥为整数.解 （1）建立动态规划模型：阶段变量：将给每一个变量j x 赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3.设状态变量k s 表示从第k 阶段到第3阶段约束右端最大值，则10.j s =设决策变量k x 表示第k 阶段赋给变量k x 的值(1,2,3)k =. 状态转移方程：2113223,4.s s x s s x =-=-阶段指标：111122223333(,)4,(,)5,(,)6.u s x x u s x x u s x x === 基本方程；()(){}()3113,2,1044()max ,()0.s k k k k k k k k k k x a f s u s x f s f s ++??=???????=+???=?≤≤ 其中1233,4, 5.a a a === （1） 用逆序法求解：当3k =时，()(){}{}33333443330055max 6max 6,ssx x f s x f s x ????????????????=+=≤≤≤而{}[]30,1,2,3,4,5,6,7,8,9,10.s x ∈表示不超过x 的最大整数。
因此，当30,1,2,3,4s =时，30x =；当35,6,7,8,9s =时，3x 可取0或1；当310s =时，3x 可取0，1，2，由此确定()33.f s 现将有关数据列入表中下载文档原格式(Word原格式，共16页)付费下载例1 求解下列整数规划的最优解：()123123max 45634510..01,2,3,j j Z x x x x x x s t x j x =++++???=??≤≥为整数.解 （1）建立动态规划模型：阶段变量：将给每一个变量j x 赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3.设状态变量k s 表示从第k 阶段到第3阶段约束右端最大值，则10.j s =设决策变量k x 表示第k 阶段赋给变量k x 的值(1,2,3)k =. 状态转移方程：2113223,4.s s x s s x =-=-阶段指标：111122223333(,)4,(,)5,(,)6.u s x x u s x x u s x x === 基本方程；()(){}()3113,2,1044()max ,()0.s k k k k k k k k k k x a f s u s x f s f s ++??=???????=+???=?≤≤ 其中1233,4, 5.a a a === （1） 用逆序法求解：当3k =时，()(){}{}33333443330055max 6max 6,ssx x f s x f s x ????????????????=+=≤≤≤而{}[]30,1,2,3,4,5,6,7,8,9,10.s x ∈表示不超过x 的最大整数。
因此，当30,1,2,3,4s =时，30x =；当35,6,7,8,9s =时，3x 可取0或1；当310s =时，3x 可取0，1，2，由此确定()33.f s 现将有关数据列入表中下载文档原格式(Word原格式，共16页)付费下载 -全文完-。
