《运筹学》课程教学资源（PPT课件讲稿）第四章 动态规划（4.2）动态规划的基本概念和模型

一、经典运输问题 二、运输问题线性规划的一般形式

age: 2 线性规划经典问题 生产计划问题 某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙 、丁四种产品。每件产品在生产中需要占用的设备机时 数,每件产品可以获得的利润以及三种设备可利用的时 数如下表所示:

多目标决策问题 实际问题决策经常面临的问题: 方案优劣并不以单一准则为目标,而是以多重准则为目标 约束条件并不完全符合严格的刚性条件,具有一定的弹性 可能的弹性约束 最好等于 最好不大于 最好不小于

一、动态规划算法的基本思想 二、矩阵连乘问题 三、最长公共子序列 四、最大子段和 五、0-1背包问题 六、最优二叉搜索树

动态规划是一类多阶段决策过程的最优化方法。 基本方法是：按阶段把一个大问题化成一系列相互有联系的子问题，建立相应的递推公式，解一系列的子问题，最后求得整个问题的最优解

一、多阶段决策问题 1. 时间阶段的例子（机器负荷问题） 某厂有1000台机器，现需作一个五年计划， 以决定每年安排多少台机器投入高负荷生产（产 量大但损耗也大）可使五年的总产量最大

动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化 的一种非常有效的方法

第四章动态规划 4.1一般方法 1.多阶段决策问题 多阶段决策过程:问题的活动过程分为若干相互联系的阶段,任一阶段i以后的行为仅依赖于i阶段的过程状态,而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策,这决策过程称为多阶段决策过程(multistep decision process)。最优化问题:问题的每一阶段可能有多种可供选择的决策,必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同,所导致的问题的结果可能不同

一、对最短路问题: