张绪林
重庆交通大学
摘要：动态规划是针对最优化的问题的一种求解方法，其求得的解根据不同的条件而有所不同。因此，动态规划模型不同的条件和不同的问题上，可能有不同的解决方法。由于动态规划模型具有复杂性和多样性，所以求解动态规划模型不能依靠一种万能的方法。本文将利用动态规划对施工机群进行模型建立。
关键词：动态规划；求解；模型
在实际工程项目中，整个项目可以看做是由多个阶段组合而成的，而且各阶段之间相互有影响，在求解过程中，先对子问题进行求解，最终通过组合子问题的解来求解原问题，这就是建立动态规划模型的过程。由于不同的子问题相互之间会有影响，所以动态规划主要应用于子问题叠加的情况。这样就只需要对每个子问题求解一次即可，然后记录所求的结果，可以有效的避免不必要的工作。
1 动态规划模型中的子问题
子问题通常情况下可以反应整个问题的情况，所以在建立一个动态规划模型时应该考虑所涉及的子问题及子问题之间的关系[1]。
如图1所示的带权值的平面网络图是根据泡沫沥青冷再生施工项目中的平面流程图所绘制。各个节点表示可选的设备方案，在整个机群施工过程中所包含有搅拌、运输、摊铺和压实四个工序，涉及的机械设备有泡沫沥青搅拌站、自卸汽车、泡沫沥青摊铺机、钢轮压路机和轮胎压路机。在网络图中，每个节点代表可供选择的设备，权值表示操作人员水平以及同种设备的工作参数的不同而导致的差异。
.png)
图1 带权值的平面网络图
根据上面的平面网络图，可以将整个问题划分为五个相互影响的子问题。自左向右沿着有向图的方向，如果给定泡沫沥青搅拌站的效率，那么必然可以求解出所需自卸汽车的数量。在整个问题中，对于所有的子问题，只有前面的子问题都求解出来之后才能求解本身。
2 机群配置中的动态规划原理
虽然在上面已经建立了动态规划的模型，但是动态规划在机群配置中的优势并没有体现。因此，接下来我会具体阐述在机群配置中应用动态规划模型求解最优方案必须具有的两个要素，即子问题重叠和最优子结构。
2.1 动态规划模型中的重叠子问题
由带权值的平面网络图可以看出，在自卸汽车数量的配置上出现重复，这就会造成子问题重叠。在解决这类重叠子问题时，一般情况是将每个子问题都求解一遍，然后记录这些解，当再次遇到相同子问题时，直接用所求得的解。
在施工过程中可以将自卸汽车作为研究对象，自卸汽车从搅拌机处运料至摊铺机处卸料之后返回搅拌机处的整个过程是一个循环。随着施工的进行，搅拌站与施工地点距离发生改变，所以整个循环中的子问题也会相应发生改变。由于动态运距的改变，重叠子问题的情况只会出现在某一个循环之内。
2.2 动态规划模型中的最优子结构
在构建动态规划模型来优化机群配置的过程中，第一步就是刻画最优的结构。如果某个子问题的最优解在整个问题的最优解里面，就可以认为这个问题具有最优子问题结构[2]。在使用动态规划来优化机群配置的过程中，本文将会用子问题的最优解来构造原问题的最优解，因此，在求解子问题时尽量保证每个子问题达到最优解。
在动态规划模型中，通常是从子问题到原问题的方式使用最优子结构[3]。也即是，首先求得子问题的最优解，然后由子问题的最优解求出原问题的最优解。
下面证明加权集群配置网络图具有最优子结构的性质。在此过程中以自卸汽车的数量作为参考对象，假设搅拌站的工作效率为,摊铺机的工作效率为。要满足搅拌站的需求所需要的自卸汽车数量设为，要满足摊铺机的需求所需要的的自卸汽车数量设为。此时取与中的最大值作为自卸汽车的数量，那么必有一个满足最优子结构。
3 建立动态规划模型
把一个施工循环看做一个整体，这个循环是由5个相互关联的子问题组成的，这5个子问题也就是5个阶段。由于自卸汽车联系着整个施工循环，因此将其作为阶段变量，用表示。每个阶段都有自己的施工状态，这些状态受到自然因素和客观因素的影响，包括气候条件，设备故障等因素，但是不受人们的主观意志的影响，也称为不可控因素。在整个施工循环中，自卸汽车是从搅拌站出发，到达施工点处卸料后返回搅拌站处。
在建立动态规划模型的过程中必须规定，每个阶段的自卸汽车一旦确定就不能随意更改。由以上章节所述，自卸汽车的数量受搅拌站的工作效率和摊铺机的工作效率影响。因此，在施工中就应该尽量保证搅拌站和摊铺机的工作效率不发生改变。这样一旦确定了前一个阶段之后，那么后一个阶段就会被确定，不会对后一个阶段产生第二次影响。换句话说，每个阶段的自卸汽车数量确定之后，那么最后选择所需自卸汽车数量最多的那个阶段的自卸汽车数量作为整个施工循环的自卸汽车数量。从搅拌站开始，一旦其工作效率确定，那么自卸汽车数量就会确定，不能受认为主观意志影响，这个性质就被称为无后效性。
在确定阶段变量之后就必须可以建立状态转移方程了，给定第个阶段的状态变量之后，由于阶段变量是固定不变的,所以第个阶段的状态变量就完全确定了。也就是说第个阶段的状态变量受第个阶段的状态变量和阶段变量共同影响，可以建立与的对应关系，用 。这就是从阶段到阶段的状态转移方程。在状态转移方程确定之后，动态规划的模型就已经建立完成了。
4 总结
本文主要研究了机群施工过程中动态规划模型的建立，提出了一种新的研究手段，将连续的施工过程分成多个子过程。此外，动态规划为施工机群的配置提供了合理的理论解释，在实际施工过程中也可以根据动态规划的模型对机群作进一步优化。
参考文献
[1] 刘人境,何正文,樊耘.动态规划的一类解法及其应用[J].系统管理学报,2008(05):581-585.
[2] 何思瑶,沈樾,辛琰钰.动态规划算法求最优解问题[J].电声技术,2019,43(03):42-44.
[3] 林志红.求动态规划最优解的一种简便新方法——图解法[J].数学理论与应用,2005(01):125-128.