f第七章动态规划选编.ppt

;定理： 如果A到F的最短路程是: ABCDEF 那么C到F的最短路程一定是: CDEF (Bellman最优化原理）;第六章 动态规划（1）;动态规划应用之一：最优路径问题：类似P201例题： 某工厂从国外进口一部精密设备，由机器制造厂到出口港有三个港口可供选择，而进口港又有三个港口可供选择，进口后可以经两个城市到达目的地，其运输成本 如图所示，求运费最低的路线;A;A;动态规划的基本概念： 1. 阶段：把问题分为互相联系有一定次序的阶段(上例，四个阶段) 状态：每个阶段开始所处自然状况或客观条件，不可控制（第1阶段状态：A，第2阶段状态：B1，B2，B3） 无后效性（马尔科夫性） 3. 决策：某个阶段的某个状态决定下一个阶段的状态（从A出发，三种不同决策： B1，B2，B3 ） 4. 策略：按顺序排列的决策组成的集合（序列） 5. 状态转移方程：确定???一个状态转到另一个状态的过程 指标函数和最优值函数：衡量过程优劣的数量指标 阅读：P196-P198 基本概念;动态规划最优性原理与最优性定理： 动态规划与静态规划的关系： ; 1.资源分配问题 引例：某种原料总数为a分配给n种产品，分配数量Xi用于生产第i种产品，效益为gi(xi);动态规划顺序解法： 第一步：划分阶段 第二步：选择状态变量 第三步：确定决策变量 第四步：写状态转移方程 第五步： 指标函数;第六章 动态规划（1）;第六章 动态规划（1）;第六章 动态规划（1）;背包问题：类似P236 例7： 用动态规划解下列问题： Max Z= 8 X1 +7X2 S.T. 2X1 +X2 ≤ 8 5X1 +2X2 ≤ 15 X1 , X2 为非负整数 ;;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]}} ;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）;第六章 动态规划（3）;第六章 动态规划（3）;第六章 动态规划（3）;动态规划在经济管理中应用： 动态规划应用之一：最优路径问题（已讲） 动态规划应用之二：资源分配问题（已讲） 动态规划应用之三：生产计划调度问题（？） 动态规划应用之四：库存问题，采购问题（？） 动态规划应用之五：设备更新问题（？） 动态规划应用之六： 生产过程最优控制问题（？） 动态规划应用之七： ……….; ;第六章 动态规划（2）;第六章 动态规划（2）;;第六章 动态规划（2）;第六章 动态规划（2）;第六章 动态规划（2）;第六章 动态规划（3）;第六章 动态规划（2）;P 219 例2 动态规划应用举例 动态规划求解 机器负荷分配问题 ;动态规划建模 1 划分阶段：年度 2 状态变量： SK为K 年度完好的机器数 3 决策变量： UK为K 年度分配高负荷生产的机器数， SK － UK为K 年度 低负荷生产的机器数 4 状态转移方程： SK＋1 ＝0.7 UK +