3.1多阶段决策问题在线视频

同学们好

本节课主要讲授多阶段决策问题

在生活中

我们常常会面临最短路径选择的一类问题

比如要完成一趟从起点城市a

至终点城市d的旅途

其中呢

需要历经两次旅途中转

在已知各城市之间行程距离的条件下

如图所示

应该怎么样选择一条行程距离最短路径

第二类问题是竞争性的水资源量

如何分配的问题

有限水资源量在不同的供水用户中分配时

往往将产生不同的经济

社会和环境效益

那么怎么样去分配水量

才能使得总效益达到最大

再比如在水库调度管理过程中

面临调度计划编制问题

在每年年初需要制定一年内水库

在各个月的蓄放水调度计划

已知各月水库预报来水量级

设定年初

年末水库蓄量状态

如何寻求总调度效益最优的调度计划

与以往课程中所讲的优化问题不同的是

上述三个问题均具有如下几个方面的特点

第一个特点是决策过程具有显著的阶段性

比如最短路问题需要经历两次中转

每次中转都需要选择目标站点的位置

空间上具有阶段性

资源分配问题需要确定各用户的水量分配方案

水量的供给有先后次序和阶段性

在水库调度问题中

需要确定每个月的放水方式

时程上具有阶段性

第二个特点是

每个阶段的决策具有前后关联性

既依赖于当前面临的状态

又影响到以后的发展

比如问题一中

目标站点的选择取决于当前阶段的出发点

同时又影响到后续阶段的选择

问题二中

分配给某一用户的水量既受到剩余

可分配水量的影响

同时又将影响后续未分配用户的水量额度

而问题三中

当前月份的放水方式受月初蓄水量多少的影响

又影响到后续月份的可用水量大小

第三个特点是

决策的最终目标是

要选择整个过程中效果最好的方案

所以

对于这一类可划分为前后之间具有一定关联性的

多个阶段的不断决策过程问题

即统称为多阶段决策问题

也叫作序贯决策问题

这类问题的解通常具有如下的最优性特征

即最优方案中的子方案依然为子问题的最优方案

比如我们以最短路问题为例

假设我们已知最短的路径为a到b2到c3到d

也就是第一阶段从a出发

应该选择b2作为中转站

第二阶段从b2出发

选择c3中转

最后由c3到达d

按照最优性特征

b2出发经c3到d的路径依然是b2为起点

以d为终点的所有路径中的最短路

这个特性可以通过反证法进行证明

假设b2到d的其他路径中存在一条

比B2经c3至D更短的路径

比如说b2到c1到d的路径

那么这样一来的话就是整个全程的

最短路应该是a到b2到c1到d

而不是现在的这条线路

所以一旦确认了所有阶段的最优策略

那么该策略中的任意子策略

即对应该子问题的最优解

依据这一特性

就可以通过逐步推求子问题的最优解

来寻求全过程的最优解

比如最短路问题

依据该特性

便可以通过逐一标号的方式进行逐阶段递推求解

比如到D的最短路径

最后一次中转

必然经过c1或者c2或者c3中的某一站点

只需要分别知道到这三个站点

已经走过了多少的距离

然后从这三个站点出发

到d还剩下多少距离要走

把所有可行方案对应的距离进行比选

就可以找到最短路径

按照这个办法

我们来演示一下标号法的求解方式

比如

最后一个阶段

如果从c1出发

那么还剩3个单位的距离到d

我们把剩余的距离3和选择的

站点d标记在对应的中转站点上

那么类似的

c2的剩余距离是5

c3的剩余距离是4

他们都对应以d为终点

来到第二个阶段

求从b1出发到d最短的剩余距离是多少

从b1中转到d只有三种选择方案

如果从c1中转

那么剩余的距离是b1到c1的3个单位

加上c1的剩余3个单位为6

从c2中转

剩余距离是4+5等于9

从c3中转结果是5+4等于9

所以在所有方案中

由b1到d最短的剩余距离是6

把对应的剩余距离6

以及选择的中转站c1进行标记

也就是从b1出发

最短需要经过6个单位的距离才能到d

类似的

如果从b2出发的话

到d的最短距离为7个单位

最后来到第一阶段

由,A到b1的距离为5

所以选择b1路径进行中转的话

对应a到d的总距离为5+6等于11

如果选择b2中转的话

对应的a到d的累积距离为3+7等于10

所以整个全程最短的距离为10

应该选择b2中转

最后确定最短的路径需

要从a点开始逐阶段回溯

把标记的中转站号逐一相连即最短路

为a到b2到c3到d

标号法虽然简单

但是他没有办法构建统一的

程序模块去解决复杂的多阶段决策问题

下一讲

我们将介绍怎样运用动态规划法

建立解决这一类问题的通用模型

同学们

同学们

本次课到此结束

谢谢大家

再见