动态规划法解工期优化问题.pdf

《动态规划法解工期优化问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、科技广场2006.3动态规划法解工期优化问题OptimizationofDurationbyDynamicProgramming刘莉LiuLi（华东交通大学土木建筑学院,南昌330013）(SchoolofCivilEngineering&Architecture,EastChinaJiaotongUniversity,Nanchang330013)摘要:分析现有网络计划的工期优化问题针对其计算量大的问题，利用动态规划原理对原有的方法进行改进，建立了工期优化的动态规划的数学模型。利用动态规划的递推公式，以达到简化计算的目的。文中以一个例子

2、说明动态规划法的应用关键词:网络计划;工期优化;动态规划中图分类号：C931文献标识码：A文章编号：1671-4792-(2006)3-0078-02当编制的施工网络计划计算工期大于合同工期时，在人2.3合为一段力、材料、设备等资源有充足保证的前提下，通过压缩关键3数学模型线路中工作的持续时间，以满足工期的要求。在施工措施上，选择压缩时间后对质量影响不大、有充足备用资源、且缩短目标函数:总成本　Min.C=工作持续工作时间而增加费用最少的关键工作，并通过增加式中:V—第K阶段的成本指标函数k资源数量，增加工作班次，改进施工工艺等途经缩短关

3、键工最优化指标函数为:作的时间。式中:—第K阶段的最优指标函数在优化方法上，一般最常用的是图上计算的方法，即根y—第K阶段的状态变量，如下算例，其取值范围0～3。据网络计划的关键路线和关键工作，在网络图的关键线路上kx—第K阶段的决策变量，如下算例，其取值范围0～3。一天天的压缩活动时间，直至计算工期达到合同工期为至。k状态转移方程:y=y+x该方法的优点是计算简单,缺点是在优化过程中可能出现某kk-1k边际条件:y=0些非关键工作转变为关键工作，造成增加费用过大。而且计0算量大、优化速度慢。而利用动态规划法进行工期优化便于4算例分析克服

4、上述缺点。将如下工程项目进行工期优化，其各工作参数见表一。1利用动态规划法进行工期优化的前提工作之间的关系见图一。该工程计划工期为19天1.1应有一个施工网络计划图表一工作参数表1.2求出网络计划的关键线路及各非关键工作的自由时差1.3已知网络计划中各工作的正常工作时间和加快工作的赶工时间1.4求出各工作的压缩极限和压缩界限。所谓压缩极限就是工作正常工作时间和赶工时间之差。压缩界限就是使有关非关键工作转变为关键工作时的关键工作时间压缩量。2采用动态法的阶段划分原则2.1按关键工作分段2.2与同一关键工作相关，可能转变为关键工作的非关4.1

5、对计算例分析，关键线路为①→②→③→⑤→⑥　键工作分段即关键工作是B、C、E、H。工期为22天。78第四阶段K＝4：决策与成本状况表动态规划法解工期优化问题图一工作关系图参数：（正常工作时间、赶工工作时间、直接费变动率）4.2将工作B、C之和持续时间压缩超过两天，A工作将成为关键工作，应对A、B、C同时进行压缩，但有不同的方注:图中括号表示为非关键工作经过压缩转变为关键工案，可用动态法确定。作4.3将工作C、E之和持续时间压缩超过两天，D工作将由上述计算可知，为压缩工期3天可采用如下压缩方案：成为关键工作。工作C压缩2天，工作E、D各压缩

6、一天。共增加费有210元。解法:首先按其关键线路将网络分为4个阶段进行计5结论算：在施工网络工期优化时，随着关键工作活动时间的缩第一阶段：K＝1　状态转移方程:y=y+x短，一些非关键路线上的工作会转变为关键工作，必须同时101令y=0，则y=x，而第一阶段对应的关键工序为B，所缩短其活动时间，而利用动态规划法能很好地考虑这些费用011增加带来的影响。从而获得最优的工期调整方案。以x的取值是0或1，，为简1参考文献明起见用表格表示:[1]钱颂迪．运筹学［Ｍ］．北京：清华大学出版社,1995.第一阶段K=1时：决策与成本状况表[2]中国统筹

7、研究会．工程网络计划技术［Ｍ］．北京：地震出版社,1995.[3]王口爽．应用动态规划［Ｍ］．北京：国防工业出版社,1997.第二阶段K=2时：决策与成本状况表作者简介刘莉（1987—），女，河南信阳人，讲师。第三阶段K＝3：决策与成本状况表79