数学建模8-动态规划和目标规划

数学建模数学建模 8 动态规划和目标规划动态规划和目标规划 一 一 动态规划动态规划 1 动态规划是求解决策过程最优化的数学方法 主要用于求解以时间划分阶段的动态过程 的优化问题 但是一些与时间无关的静态规划 如线性规划 非线性规划 只要人为地 引进时间因素 把它视为多阶段决策过程 也可以用动态规划方法方便地求解 2 基本概念 基本方程 1 阶段 2 状态 3 决策 4 策略 5 状态转移方程 6 指标函数和最优值函数 7 最优策略和最优轨线 8 递归方程 3 计算方法和逆序解法 此处较为抽象 理解较为困难 建议结合例子去看 此处较为抽象 理解较为困难 建议结合例子去看 4 动态规划与静态规划的关系 一些静态规划只需要引入阶段变量 状态 决策等就可以 用动态规划方法求解 详见书中例 4 5 若干典型问题的动态规划模型 1 最短路线问题 2 生产计划问题 状态定义为每阶段开始时的储存量 xk 决策为每个阶段的产量 记每 个阶段的需求量 已知量 为 dk 则状态转移方程为 3 资源分配问题 详见例 5 状态转移方程 最优值函数 自有终端条件 4 具体应用实例 详见例 6 例 7 二 二 目标规划目标规划 1 实际问题中 衡量方案优劣要考虑多个目标 有主要的 有主要的 也有次要的 有最 大值的 也有最小值的 有定量的 也有定性的 有相互补充的 也有相互对立的 这 时可用目标规划解决 其求解思路有加权系数法 优先等级法 有效解法等 2 基本概念 1 正负偏差变量 2 绝对 刚性 约束和目标约束 3 优先因子 优先等级 与权系数 凡要求第一位达到的目标赋予优先因子P1 次位赋 予P2 以此类推 4 目标规划的目标函数 5 一般数学模型 3 求解目标规划的解法 1 序贯式算法序贯式算法 用 LINGO 软件求解 有编程模板可以使用 下面以书中例 3 说明 具体 还可以参考书中例 6 例 8 model sets level 1 3 p z goal variable 1 2 x h con num 1 1 b s con num 1 4 g dplus dminus h con h con num variable a s con s con num variable c obj level s con num 1 1 2 2 3 3 3 4 wplus wminus endsets data ctr goal 0 b 12 g 1500 0 16 15 a 2 2 c 200 300 2 1 4 0 0 5 wplus 0 1 3 1 wminus 1 1 3 0 enddata min sum level p z p ctr 1 for level i i ne ctr p i 0 for level i z i sum obj i j wplus i j dplus j wminus i j dminus j for h con num i sum variable j a i j x j b i for s con num i sum variable j c i j x j dminus i dplus i g i for level i i lt size level bnd 0 z i goal i end 2 多目标规划的多目标规划的 MATLAB 解法解法 以书中例 5 详细说明如下 a 1 1 0 0 0 0 1 1 3 0 2 0 0 3 0 2 b 30 30 120 48 c1 100 90 80 70 c2 0 3 0 2 x1 g1 linprog c1 a b zeros 4 1 求第一个目标函数的目标值 x2 g2 linprog c2 a b zeros 4 1 求第二个目