文档介绍：线性规划(第一、二、三章)回顾
线性规划问题 LP
建模、图解法、标准型、解、单纯形法
对偶规划问题 DP
性质与定理、
影子价格、
灵敏度分析
整数规划问题 IP
不同类型问题建模、
分支定界法、
0-1整数规划求解
互为对偶
松弛问题
第四章动态规划Dynamic Programming
运筹学Operations Research
动态规划基本概念与方法
动态规划应用举例
动态规划是一项最优化技术,而不是一种算法;具体问题具体分析处理。
1951年,美国数学家Bellman提出解决多阶段决策问题的“最优性原理”,创建了动态规划(1957年出版)。
动态规划是一种将实际问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的方法策略。
一般来说,只要原问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解,就可以考虑用动态规划解决。
动态规划基本概念与方法
一、多阶段决策问题与动态规划方法
[例1] 时间阶段——生产负荷问题
某种机器可以在高、低两种负荷下进行生产。高负荷年产量8,;低负荷年产量5,。现有完好机器1000台,需制定一个5年计划,以决定每年安排多少台机器投入高、低负荷生产,使5年的总产量最大。
不同时间阶段的决策问题:
(1)工厂生产过程:由于市场需求随着时间而变化,为了取得最佳经济效益,要在生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。
(2)设备更新问题:设备刚买来时故障少,经济效益高,转让处理价值也高;随着使用年限的增加,故障多,经济效益差,处理价值也越低。如果卖去旧的买新的,,使总的经济效益最好。
[例2] 空间阶段——最短路问题
如图为一线路网络,现要从A点铺设一条管道到E点,图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路,使总距离最短。
多阶段决策问题的特点:
(1)多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。因此,问题的求解就比较复杂、困难。
(2)适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。
无后效性:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。即“未来与过去无关”,当前的状态是此前历史的一个完整总结。
注意无后效性一般是针对问题的分析方式的,不是描述一个问题的。
(3)类型:离散确定型、离散随机型、连续确定型、连续随机型。
(1)全枚举法或穷举法
从A到E的路程可分为4个阶段,共有16条可能的路线,
分别算出各条路线的距离,最后进行比较,可知最优路线是A →B2→ C1 → D1 →E ,最短距离是19。
当节点很多时,计算量庞大,且包含许多重复计算。
(2)局部最优路径法
从A出发,并不顾及全线是否最短,只是选择当前最短途径,“逢近便走”,这样所取决策必是:
A →B3→ C3 → D1 →E ,全程长度是25。
显然,该方法错误地以为局部最优会得到整体最优,结果常是错误的。