整数规划的动态规划法 最优化原理 例:最短路问题求各点到T的最短路 “全过程的最优策略具有这样的性质:不管该最优 策略上某状态以前的状态和决策如何,对该状态而 言,余下的诸决策必定构成最优子策略.”即:最优策 略的任一后部子策略都是最优的 这只是最优性定理的一个推论,即最优策略的必 要条件 L()=min(cn+L()节点到节点r的最短路长 最优子结构〔 Optimal Substructure) An optimal solution to the problem contains within it L(T)=0 递推计算 optimal solutions to subproblems. 建立动态规划模型的基本过程 动态规划基本方程 逆序递推41 1)正确划分阶段,选择阶段变量k (2)对每个阶段,正确选择状态变量x选择状态变 x世xx 量时应当注意两点:一是要能够正确描述受控过程的 演变特性,二是要满足无后效性 f(x1)f2(x2) f(x1) fa(r,) (3)对每个阶段,正确选择决策变量k f(x)表示第k阶段初始状态为x时 (4)列出相邻阶段的状态转移方程:xk+=T(x,uA) k后部子过程阶段kk+1,,n)的最优准则函数 (5)列出按阶段可分的准则函数vm J(x2=mirv(e, 4)+H(xe+) Lm(xn)=0(边界条件)x41=7(x2L4) 假设问题的目标是极小化 (学学奖 (学学 应用动态规划方法的几个例子 少共有M个工厂,可以把问题分解为N个阶段: 资源分配问题:某公司现有M台设备准备分配给该公 司所属的N家工厂.当分配台u设备给工厂A时,工厂k 当阶段kN时,把手中设备分配给工厂N; 利用这些设备为公司创造的利润(假设非负)为gA(u) 当阶段k=N-1时,把手中设备分配给工厂N1; 如何分配设备资源,使得公司总利润最大? 依次类推; 当阶段k=1时,把手中设备分配给工厂 max:=∑8(4) 状态变量x-第阶段初分配者手中拥有的设备台数 由题意可知x=M,xN=0 决策变量a:第A阶段分配给工厂k的设备台数0≤叫≤x ∈z 状态转移方程 可能是非线性整数规划,甚至gA(u4)没有显式表达式 阶段的准则函数为"(x1,41)=8(a4)5 整数规划的动态规划法 例：最短路问题 求各点到T的最短路 5 6 7 7 4 9 6 8 6 5 8 3 3 6 C1 B1 C2 B2 A1 A2 A3 T S 6 ( ) 节点i到节点T 的最短路长 ( ) 0 ( ) min ( ) ( , ) = = + ∈ L T L i c L j ij i j A 递推计算 “全过程的最优策略具有这样的性质：不管该最优 策略上某状态以前的状态和决策如何，对该状态而 言，余下的诸决策必定构成最优子策略. ”即：最优策 略的任一后部子策略都是最优的. 这只是最优性定理的一个推论，即最优策略的必 要条件. 最优化原理 最优子结构（Optimal Substructure）: An optimal solution to the problem contains within it optimal solutions to subproblems. （1） 正确划分阶段，选择阶段变量k. （2） 对每个阶段，正确选择状态变量xk. 选择状态变 量时应当注意两点：一是要能够正确描述受控过程的 演变特性，二是要满足无后效性. （3） 对每个阶段，正确选择决策变量uk . （4） 列出相邻阶段的状态转移方程： xk+1= Tk(xk, uk). （5） 列出按阶段可分的准则函数V1,n . 假设问题的目标是极小化 建立动态规划模型的基本过程 逆序递推 k=1 k=2 k k=n 1 x 2 x 3 x k+1 x n+1 x k x n x ( ) 1 1 f x 1 u 2 u k u n u ( ) 2 2 f x ( ) k k f x ( ) n n f x ⎩ ⎨ ⎧ = = + + + + + ∈ ( ) 0 (边界条件） ( ) min[ ( , ) ( )] 1 1 1 1 n n k k k k k u U k k f x f x v x u f x k k ( , ) k 1 k k uk x =T x + fk(xk)表示第 k 阶段初始状态为xk时， k后部子过程(阶段k,k+1,…,n)的最优准则函数 动态规划基本方程 资源分配问题： 某公司现有M台设备准备分配给该公 司所属的N家工厂. 当分配台uk设备给工厂k时，工厂k 利用这些设备为公司创造的利润（假设非负）为gk(uk). 如何分配设备资源，使得公司总利润最大？ 可能是非线性整数规划, 甚至gk(uk)没有显式表达式 应用动态规划方法的几个例子 + = = ∈ = = ∑ ∑ u Z st u M z g u k k N k k N k k 1 1 . . max ( ) ( ) k k g u k u 工厂k 设备数 1 2 3 0 1 2 3 4 0 4 6 7 7 0 2 5 6 8 0 3 5 7 8 状态变量xk - 第k阶段初分配者手中拥有的设备台数. 由题意可知 x0 = M， xN+1 = 0 阶段的准则函数为 共有N个工厂，可以把问题分解为N个阶段： 当阶段k=N时，把手中设备分配给工厂N； 当阶段k=N-1时，把手中设备分配给工厂N-1； 依次类推； 当阶段k=1时，把手中设备分配给工厂1. 决策变量uk：第k阶段分配给工厂k的设备台数 k k 0 ≤ u ≤ x 状态转移方程 k k u k x +1 = x − ( , ) ( ) k k uk gk uk v x =