第六章动态规到(1) 背包问题:类似P236例7:用动态规划解下列问题: Max ZF8XI 经济意义:X1,X2为物品数量,8,7为单位 S..2X1+X2≤8 物品的价值,2,1为单位物品的体积,8为背 包的最大容积,5,2为单位物品的重量, 5X1+2X2≤15 15为背包的最大承受重量(太重背包带会断) X1,x2为非负整数 运学 熊中描教
运筹学 熊中楷教授 背包问题：类似P236 例7： 用动态规划解下列问题： Max Z= 8 X1 +7X2 S.T. 2X1 +X2 ≤ 8 5X1 +2X2 ≤ 15 X1 , X2 为非负整数 经济意义：X1 , X2为物品数量，8，7为单位 物品的价值，2，1为单位物品的体积，8为背 包的最大容积，5，2为单位物品的重量， 15为背包的最大承受重量（太重背包带会断） 第六章 动态规划（1）
第六章动态规到(1) 类似P207例3用动态规划逆序算法解下列问题(二维背包间题): Max ZF8X+7X2 (最大效益,重量限制,体积限制) S.T.2X1+X2≤8(重量) V1=8,W1=15 5X1+2X2≤15(体积) V,,W2 V2=V12X1(重量) X1,X2为非负整数 w2=W1-5X1(体积) 解:用逆序算法。设 阶段:分成两个阶段,分别对应第1种物体的数量x1,第2种物仆自数量 第1阶段决定背包中第2种物体的数量 V, WI 决策变量:X1,X2为背包中两种物体的数量 状态变量:V1为第1阶段可供分配重量,V1=8 W1为第1阶段可供分配体积,W1=15,V2,W2对应第2阶段 于是,F2(V2,W2)=Max{7X2 0≤X2sV2(重量) 0≤2X2≤W2(体积) 运学 狼中J
运筹学 熊中楷教授 第六章 动态规划（1） 类似P207例3 用动态规划逆序算法解下列问题（二维背包问题）： Max Z= 8 X1 +7X2 （最大效益，重量限制，体积限制） S.T. 2X1 + X2 ≤ 8 (重量) 5X1+2X2 ≤ 15 (体积) X1 , X2 为非负整数 解：用逆序算法。设： 阶段：分成两个阶段，分别对应第1种物体的数量X1，第2种物体的数量X2 第1 阶段决定背包中第2种物体的数量 决策变量：X1，X2 为背包中两种物体的数量 状态变量：V1为第1 阶段 可供分配重量，V1 ＝8 W1 为第1 阶段可供分配体积，W1 ＝15，V2 ，W2 对应第2阶段 于是， F* 2（V2 ，W2 ）= Max {7 X2 } 0≤X2 ≤V2 (重量) 0≤2X2 ≤W2 (体积) x1 x V1 ， W1 2 V2 ， W2 V1 =8 ， W1 = 15 V2 = V1 -2X1 ( 重量) W2 = W1 - 5X1 (体积)
第六章动态规到(1) 为整数 7min I V2l, W2/213 (V是小于等于V的最大整数) F(V1,W1)=Max{8x1+F2(V1-2X1,W1-5X1)} 0≤2X1≤V1(重量) 0≤5X1≤W1(体积) X1为整数 而V1=8,W1=15因此 F'1(8,15)=Max{8x1+7min{8-2x1l,(15-5X1)/2l} 0<2X<8 0≤5X1≤15 X1为整数 由于X1≤min{8/2,(15/5)=3(X1为0,1,2,3,分别代入下式,也可用分析) Ft(V1,W1)=Max{8X1+7min{8-2X1l,I(15-5X1)2B} 运学 狼中J
运筹学 熊中楷教授 X2 为整数 = 7min {[ V2 ], [W2 /2]} ([ V]是小于等于V的最大整数) F* 1（V1 ，W1 ）= Max {8 X1 + F* 2（V1 -2X1，W1 - 5X1）} 0≤2X1 ≤V1 (重量) 0≤5X1 ≤W1 (体积) X1 为整数 而V1 =8，W1=15 因此 F* 1（8 ，15 ）= Max {8 X1 + 7min {[ 8 -2X1 ], [(15 - 5X1 )/2]} 0≤2X1≤8 0≤5X1 ≤15 X1 为整数 由于 X1 ≤ min {[ 8 /2], [(15/5)]=3 (X1 为0，1，2，3，分别代入下式，也可用分析) F* 1（V1 ，W1 ）= Max {8 X1 + 7min {[ 8 -2X1 ], [(15 - 5X1 )/2]}} 第六章 动态规划（1）
第六章动态规到(1) X=0 X 2= min I Val, W2/213 V2=V1-2X1=8,W2=W1-5X1=15 X*,=7 因此,最优解为X*1=0,X*2=7,最优值:Z*=49 运学 熊中描教
运筹学 熊中楷教授 X*1 =0 X*2 = min {[ V2 ], [W2 /2]} V2=V1 - 2X1=8， W2=W1 -5X1 =15 X*2 = 7 因此, 最优解为X*1 =0, X*2 = 7 , 最优值:Z*= 49 第六章 动态规划（1）
第六章动态规到(1) 总结 基本定理:如果A到F的最短路程是 ABCDEF 那么C到F的最短路程一定是CDEF( Bellman最优化原理) 动态规划的基本概念: 1。阶段:把问题分为互相联系有一定次序的阶段 2。状态:每个阶段开始所处自然状况或客观条件,不可控制 3。决策:某个阶段的某个状态决定下一个阶段的状态 4。策略:某个阶段的某个状态所有可能的决策 5。状态转移方程:确定由一个状态转到另一个状态的过程 6。指标函数和最优值函数:衡量过程优劣的数量指标 运学 熊中描教
运筹学 熊中楷教授 第六章 动态规划（1） 基本定理：如果A到F的最短路程是ABCDEF， 那么C到F的最短路程一定是 CDEF (Bellman最优化原理） 总结 动态规划的基本概念： 1。阶段：把问题分为互相联系有一定次序的阶段 2。状态：每个阶段开始所处自然状况或客观条件，不可控制 3。决策：某个阶段的某个状态决定下一个阶段的状态 4。策略：某个阶段的某个状态所有可能的决策 5。状态转移方程：确定由一个状态转到另一个状态的过程 6。指标函数和最优值函数：衡量过程优劣的数量指标