生产计划_动态规划讲座

4动态规划 4 1多阶段决策问题与动态规划4 2动态规划的基本概念4 3动态规划的步骤4 4动态规划的应用1求解静态规划问题2资源分配问题3不确定性采购问题4排序问题 例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产 在高负荷下进行生产时 产品的年产量g和投入生产的机器数量u的关系为g g u 这时机器的年完好率为a 0 a 1 在低负荷下生产时 产品的年产量h和投入生产的机器数量v的关系为h h v 这时机器的年完好率为b a b 1 假定开始生产时完好的机器数量为s1 要求制定一个五年计划 在每年开始时决定机器在两种不同负荷下生产的数量 使五年内产品的总产量最高 4 1多阶段决策问题与动态规划 多阶段决策问题和我们前面遇到的决策问题不同 它是和时间有关的 与时间有关的活动过程称为动态过程 其优化方法称为动态规划 而与时间无关的活动过程称为静态过程 相应的的优化方法称为静态规划 1 阶段 stage 把所研究的决策问题 按先后顺序划分为若干相互联系的决策步骤 以便按一定的次序进行求解 描述阶段的变量称阶段变量 常用k表示 2 状态 state 状态表示每个阶段开始时所处的自然状况或客观条件 它描述了影响决策的因素随决策进程的变化情况 它既是前面阶段所作决策的结果 又是本阶段作出决策的出发点和依据 描述状态的变量称为状态变量 第k阶段的状态变量常用sk表示 通常 在第一阶段状态变量s1是确定的 称初始状态 3 决策 decision 决策表示在某一阶段处于某种状态时 决策者在若干种方案中作出的选择决定 描述决策的变量称决策变量 第k阶段的决策变量常用uk表示 决策变量的取值会受到状态变量的制约 被限制在某一范围之内 4 2动态规划的基本概念 一 4 策略 policy 把从第一阶段开始到最后阶段终止的整个决策过程 称为问题的全过程 而把从第k阶段开始到最后阶段终止的决策过程 或称为k子过程 在全过程上 各阶段的决策按顺序排列组成的决策序列p1 n u1 u2 un 称为全过程策略 简称策略 而在k子过程上的决策序列pk n uk uk 1 un 称为k子过程策略 也简称子策略 5 状态转移方程若第k阶段的状态变量值为sk 当决策变量uk的取值决定后 下一阶段状态变量sk 1的值也就完全确定 即sk 1的值对应于sk和uk的值 这种对应关系记为sk 1 Tk sk uk 称为状态转移方程 状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律 4 2动态规划的基本概念 二 6 指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数 阶段指标函数是对某一阶段的状态和决策产生的效益值的度量 用vk sk uk 表示 过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值 记为Vk n Vk n sk uk sk 1 uk 1 sn un 动态规划所要求的过程指标函数应具有可分离性 即可表达为它所包含的各阶段指标函数的函数形式 常见的两种过程指标函数形式是 各阶段指标函数的和Vk n vj sj uj 各阶段指标函数的积Vk n vj sj uj 把过程指标函数Vk n对k子过程策略pk n求最优 得到一个关于状态sk的函数 称为最优值函数 记为fk sk 即fk sk optVk n sk uk sn un uk un式中的 opt optimization 可根据具体问题而取min或max 7 基本方程通常动态规划问题的最优值函数满足递推关系式 设过程指标函数为各阶段指标函数的和的形式 即Vk n vj sj uj 则有fk sk opt vk sk uk fk 1 sk 1 uk Dk sk k n n 1 1 递推方程fn 1 sn 1 0边界条件递推方程和边界条件一起称为动态规划的基本方程 可根据边界条件 从k n开始 由后向前逆推 逐步求得各阶段的最优决策和相应的最优值 最后求出f1 s1 时 就得到整个问题的最优解 此问题的基本方程为fk sk Min dk uk fk 1 sk 1 uk Dk sk k 6 5 4 3 2 1f7 s7 0 4 3动态规划的步骤 一 当k 6时 按基本方程由后向前继续递推有 当k 5时 当k 4时 当k 3时 当k 2时 当k 1时 由此可以看出 A到G的最短路长为18 路径为 A B1 C2 D1 E2 F2 G 现在把动态规划法的步骤归纳如下 1 将所研究问题的过程划分为n个恰当的阶段 k 1 2 n 2 正确地选择状态变量Sk 并确定初始状态S1的值 3 确定决策变量uk以及各阶段的允许决策集Dk Sk 4 给出状态转移方程 5 给出满足要求的过程指标函数Vk n及相应的最优值函数 6 写出递推方程和边界条件 建立基本方程 7 按照基本方程递推求解 以上步骤是动态规划法处理问题的基本步骤 其中的前六步是建立动态规划模型的步骤 4 3动态规划的步骤 二 例 机器负荷问题某种机器可以在高低两种不同的负荷下进行生产 在高负荷下进行生产时 产品的年产量g和投入生产的机器数量u的关系为g 8u 这时机器的年完好率为a 0 7 在低负荷下生产时 产品的年产量h和投入生产的机器数量v的关系为h 5v 这时机器的年完好率为b 0 9 假定开始生产时完好的机器数量为s1 要求制定一个五年计划 在每年开始时决定机器在两种不同负荷下生产的数量 使五年内产品的总产量最高 1 按年数划分为5个阶段 k 1 2 3 4 5 2 取第k年初完好的机器数sk为状态变量 s1 1000 3 取第k年投入高负荷的机器数xk为决策变量 0 xk sk 4 状态转移方程为sk 1 0 7xk 0 9 sk xk 0 9sk 0 2xk 5 指标函数为Vk 5 8xj 5 sj xj 5sj 3xj 6 基本方程为fk sk max 5sj 3xj fk 1 sk 1 k 5 4 3 2 10 xk skf6 s6 0 解 当k 5时 f5 s5 max 5s5 3x5 f6 s6 max 5s5 3x5 8s5 x5 s5 0 x5 s50 x5 s5 当k 4时 f4 s4 max 5s4 3x4 8s5 max 5s4 3x4 8 0 9s4 0 2x4 0 x4 s40 x4 s4 max 12 2s4 1 4x4 13 6s4 x4 s4 0 x4 s4 当k 3时 f3 s3 max 5s3 3x3 13 6s4 max 5s3 3x3 13 6 0 9s3 0 2x3 0 x3 s30 x3 s3 max 17 24s3 0 28x3 17 5s3 x3 s3 0 x3 s3 当k 2时 f2 s2 max 5s2 3x2 17 52s3 max 5s2 3x2 17 52 0 9s2 0 2x2 0 x2 s20 x2 s2 max 20 77s2 0 504x2 20 7s4 x2 0 0 x2 s2 当k 1时 f1 s1 23 7s1 x1 0 f1 1000 23700 s1 1000 x1 0 s2 900 x2 0 s3 810 x3 810 s4 576 x4 576 s5 397 x5 397 某些静态规划问题可用动态规划法来求解 例用动态规划法求解maxz x12 x22 x3x1 x2 x3 cxi 0i 1 2 3 4 4动态规划的应用 一 1求解静态规划问题 资源分配问题可描述如下 设有某种原料 总数量为a 分配给n个使用者 已知第i个使用者得到数量xi的资源 可创造的收益为gi xi 问应如何分配该资源 才能使总收益最大 4 4动态规划的应用 二 用动态规划法处理这种问题时 通常把给一个使用者分配资源的过程看成一个阶段 按n个使用者分成先后n个决策阶段 即先给第1个使用者分配资源 为第一阶段 再给第2个使用者分配 为第2阶段 依此类推 最后给第n个使用者分配 为第n阶段 2资源分配问题 例某工业部门根据国家计划安排 拟将五台某种高效率的机器分配给所属的甲 乙 丙三个工厂 各工厂得到不同数量的机器可获得的收益如下表 问应如何分配机器 才能使各厂的总效益最大 某单位准备在以后的n个时期内采购一批物资 各时期的价格不是确定的 而是按照某种已知的概率分布取值 试制定采购策略 确定在哪一时期以什么价格采购 能使采购价的数学期望值最低 这类问题也适合用动态规划法进行处理 下面通过实例加以说明 例7某厂生产上需要在近五周内采购一批原料 而估计在未来五周的价格有波动 其浮动价格和概率策得如下表 试确定该厂应在哪一周以什么价格购入 能使其采购价的数学期望值最小 并求出期望值 4 4动态规划的应用 三 3不确定性采购问题 设有n个工件需要在机床A B上加工 每个工件都必须先经过A而后B 两道加工工序 以ai bi分别表示工件i 1 i n 在A B上的加工时间 问应如何在两机床上安排各工件的加工顺序 使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止 所用的加工总时间最少 加工工件在机床A上有加工顺序问题 在机床B上也有加工顺序问题 可以证明 最优加工顺序在两台机床上可同时实现 因此 最优排序方案可以只在机床A B上加工顺序相同的排序中寻找 即使如此 所有可能的方案仍有n 个 这是一个不小的数 用穷举法是不现实的 4 4动态规划的应用 四 4排序问题 用动态规划法可以推出 工件i应该排在工件j之前的条件为min ai bj min aj bi 根据这个条件 构造下列排序方法 a1a2 an1 建立工时矩阵M b1b2 bn2 在工时矩阵M中找出最小元素 若不止一个可任选其一 若它在上行 则相应的工件排在最前位置 若它在下行 则相