数学建模-动态规划(美赛运用)

动态规划模型的要素是对问题解决的抽象，其可分为：

阶段。指对问题进行解决的自然划分。例如：在最短线路问题中，每进行走一步的决策就是一个阶段。
状态。指一个阶段开始时的自然状况。例如：在最短线路问题中，每进行走一步后，对所走的点进行标注。
决策。当一个阶段的状态确定后，作出选择从而演变到下一阶段的某个状态的选择手段称为决策，在优控制问题中也称为控制。
策略。由决策组成的序列称为策略。由第k到第j阶段的策略可记作

下面以我在建模美赛中的题目实列来阐述：

背景

美国和加拿大的五大湖是世界上最大的淡水湖群。这五个湖泊和相连的水道构成了一个巨大的

流域，其中包含了这两个国家的许多大城市，气候和当地的天气条件各不相同。

湖区的水有多种用途 ( 捕鱼、娱乐、发电、饮用、航运、动物和鱼类栖息地、建筑、灌溉等 ) 。因

此，各种各样的利益相关者都对流入和流出湖泊的水的管理感兴趣。特别是，如果从湖泊排出

或蒸发的水太少，那么可能会发生洪水，沿岸的家庭和企业受到影响 ; 如果排水过多，那么大型

船只就无法通过水路运送补给，支持当地经济。主要问题是调节水位，使所有利益相关者都能

受益。

每个湖泊的水位是由进出湖泊的水量决定的。这些水位是温度、风、潮汐、降水、蒸发、测深

( 湖底形状 ) 、河流流量和径流、水库政策、季节周期和长期气候变化等复杂相互作用的结果。在

五大湖系统的水流中有两种主要的控制机制 : 苏河水闸补偿工程。玛丽 ( 三个水力发电厂，五个航

行船闸和一个在激流顶端的闸门大坝 ) 和康沃尔的摩西 - 桑德斯大坝，如附录所示。

虽然这两座控制水坝、许多渠道和运河以及流域水库可能是由人类控制的，但降雨、蒸发、侵

蚀、冰塞和其他水流现象的速率是人类无法控制的。地方政府的政策可能会产生与预期不同的

影响，流域的季节和环境变化也可能会产生不同的影响。这些变化反过来又会影响该地区的生

态系统，从而影响湖泊内外动植物的健康以及生活在水盆中的居民。尽管五大湖似乎有一个规

律的年度模式，但水位从正常水平的 2 到 3 英尺的变化会极大地影响一些利益相关者。

这种动态的网络流量问题是“邪恶的”——由于相互依赖、复杂的要求和固有的不确定性，解

决起来异常具有挑战性。对于湖泊的问题，我们有不断变化的动态和利益相关者的利益冲突。

有关附加信息，请参阅问题 D 附录

国际联合委员会(IJC)请求贵公司国际网络控制建模师(icm)提供支持，协助管理和建模直接影响

五大湖水网水位的控制机制(附录中所示的两座水坝-补偿工程和摩西-桑德斯大坝)。你的 ICM

主管已经让你的团队领导开发模型和实施模型的管理计划。你的导师指出，有几个考虑因素可

能有助于实现这一目标，首先是为五大湖建立一个网络模型，并将从苏必利尔湖到大西洋的河

流连接起来。你的导师提到的其他一些可选的考虑因素或问题是:

•考虑到各个利益相关者的愿望(每个利益相关者的成本和收益可能不同)，确定五大湖区在一

年中任何时候的最佳水位。

•根据五大湖的流入和流出数据，建立算法以维持五大湖的最佳水位。

•了解您的控制算法对两个控制坝的流出的敏感性。考虑到 2017 年的数据，对于各利益相

关者来说，你的新控制方法是否会使当年的实际记录水位令人满意或更好?

•你们的算法对环境条件(例如，降水、冬季积雪、冰塞)的变化有多敏感?

•将您的广泛分析集中在影响安大略湖的利益相关者和因素上，因为最近对该湖的水位管

理有更多的关注。

在第二问中需要找到算法来维持最佳水位，这本身就是动态规划问题。

前面第一问得到了五大湖的最佳水位，第二问的核心是波动情况下，近可能地使得五大湖的最佳水位波动尽可能小。

采用之前构建的网络流模型来模拟五大湖及其连接河流的水位和流量:节点定义:将每个湖泊和与其直接相连的河流定义为网络中的一个节点。边定义:根据水流方向，定义从一个节点到另一个节点的边。

流量和水位数据准备:使用提供的平均水位和流量数据来设定节点属性和边的容量运用网络流算法来模拟水流动态，并应用目标优化方法寻找维持最佳水位的策略。不过我们只考虑河流影响因素，其它外部因素不考虑在内。

一、算法实现：

制定算法：遗传算法（GA）：使用遗传算法等启发式算法求解优化问题，找到维持最优水位的控制策略。通过湖泊的流入和流出数据来维持五大湖的最佳水位。

解释：

遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。

步骤如下：

在动态流模型中如果当前水位低于目标水位，减少流出量；反之增加流出量。不同的是遗传算法在本基础上加上往年同月或同季节中的河流量变化值作为参考，在该动态网络流模型中的再次进行相应的河流流量调整从而得到最后相对更加准确的结果。

采用简单遗传算法：

SGA=(C,E,P_0, M,D, H,S,T）

C 表示个体的编码方案

E 表示个体适应度评价函数

P_0 表示初始种群

M 表示种群

D表示选择算子

H表示交叉算子

S表示变异算子

T 表示遗传算法终止条件

遗传算法使用以下遗传算子：

从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体。个体被选中的概率跟适应度值有关，个体适应度值越高，被选中的概率越大，根据该思想，建立河流流量概率相关值：

fi为本遗传值，叠加之后为累次遗传。

在此之后，再进行指数尺度变换：

得到每个湖的在不同遗传系中的适配分部数据的热力图：

再通过动态网络流模型得到湖泊之间连接的河流流量的调整值：

圣玛丽河：2178.23

圣克莱尔河：5739.34

底特律河：5991.12

尼亚加拉河：6023.77