《1 引言》
1 引言
我国加入WTO后, 国内的建筑市场竞争白热化, 建筑行业整体进入微利时代。为使企业获得较好的经济效益, 必须实行科学管理。网络计划技术是行之有效的科学管理方法
网络计划优化的传统方法, 如梯度法, 不能保证搜索到全局最优点, 而实际的网络计划优化问题通常含有多变量多约束, 甚至有的目标函数和约束条件表现为高度非线性、不可微及非凸, 确定性算法对此显得无能为力。一种进化算法即差异演化
《2 网络计划多目标优化模型》
2 网络计划多目标优化模型
《2.1净收益最大的工期-费用数学模型》
2.1净收益最大的工期-费用数学模型
决策者对进度计划做出安排时最关心的是投资的回报。对于承包商来说, 当收入与项目实现时间相关时, 使所有活动都以可能的最短时间完成, 可以因提前完工而获得奖励。但如果压缩活动所增加的费用大于这一额外的收益, 会得不偿失。必须在两极间进行权衡, 合理压缩工期, 间接费用的节约和提前竣工所得的奖励与同时提高的直接费用相抵后, 得到额外收益最大时的最佳工期。据此, 提出净收益最大化的工期-费用优化模型:
《图1》
式中P (j) = {i|活动i是活动j的紧前工作}, T=max{tbi+ti|i=1, 2, …, n}, IN为项目的净收益, t = (t1, t2, …, tn) 为活动的实际持续时间向量, T为实际工期, T+为正常工期, σ为提前竣工单位时间的奖金, Cind为单位时间所需间接费, F为固定利润 (T+, σ, Cind, F是已知常数) , Ci为活动i的单位时间压缩费用即费率, ti为活动i的实际持续时间即模型的决策变量, tbi为活动i的最早开始时间, n为网络所有的活动数目, i为活动编号, TUi为活动i的正常持续时间, TLi为活动i的极限持续时间。
假定:a. 整个项目正常直接费用总额一定;b.单位时间内间接费用不随时间t变化;c. 压缩费用是工期的分段线性凸函数, 但各工序持续时间相对工期来说非常短, 假定为线性关系
《2.2网络计划质量-时间优化的数学模型》
2.2网络计划质量-时间优化的数学模型
工程质量由施工过程中的工序质量决定, 对任何一道工序, 不同的完成时间形成不同程度的工序质量, 工作时间的压缩会影响质量。基于此, 在施工前对每一施工工序建立质量-时间模型, 人为地选择工程质量相对好的网络计划方案。
假定工序在正常持续时间TUi下完成的质量水平为1, 即工作的完成满足规范的要求 (在规范所规定的范围内, 且偏差很小甚至为零)
根据规范规定的质量水平, 有经验的工程管理人员估计出在临界时间完成情况下的相对质量水平值。由于各工序对该工程有不同的重要性, 工程质量是各工序质量考虑到权重后的均值。为了简便起见, 假设工程总质量的指标是各工序完成质量的总平均值。设网络共有n项活动, 网络计划的工序质量-时间模型为
《图3》
其中a=q′i-bTLi, b= (1-q′i) / (TUi-TLi) , 分别为工序i的时间-质量曲线的截距和斜率, q′i为工序i极限持续时间下的工序相对质量, Q为工程的相对质量值。
《2.3工期-净收益-质量多目标优化模型的建立》
2.3工期-净收益-质量多目标优化模型的建立
根据决策者对各目标的偏好, 预先确定各目标的权系数, 并采用线性加权的方法建立工期-净收益-质量多目标优化模型
《图4》
为对各子目标函数统一量纲, 不受目标值大小影响, 引入了I′N (净收益单目标的最大值) 。
《3 网络计划多目标优化模型求解策略》
3 网络计划多目标优化模型求解策略
《3.1约束条件的处理》
3.1约束条件的处理
DE算法适用于求解最小值优化问题, 故需将式 (3) 转化为
《图5》
差异演化算法不宜直接处理有约束的规划问题, 通常需用罚函数将式 (3) 转换为无约束的优化问题, 其评价函数为
《图6》
式中f (t) 为原目标函数, α为惩罚因子, α的取值对差异演化算法收敛性有较大的影响, 取值过大将造成惩罚过量, 增加早熟倾向;取值过小又可能造成惩罚过轻, 使约束条件得不到满足。为此, 采用动态罚因子
《3.2差异演化算法的基本原理》
3.2差异演化算法的基本原理
差异演化算法是在可行域内随机产生初始种群, 进化过程中使具有更好适应值的个体获得较大的生存概率, 通过演化算子操作在搜索空间中迭代以获得最优解。差异演化算法求解网络计划多目标优化模型的操作步骤如下:
令ts (g) 是第g代的第s个染色体, 则
《图7》
其中n是染色体的长度, Np为群体规模, gmax是最大的进化代数。
Step 1 产生初始种群。在可行域中随机产生Np个染色体, 由于工程时间以日为单位, 则
《图8》
其中TUsi, TLsi分别是第i个变量的上界和下界, R1si 是[0, 1]区间的随机小数。
Step 2 变异操作。从群体中随机选择3个染色体tr1, tr2, tr3且 (s≠r1≠r2≠r3) , 则
《图9》
|tr2i (g) -tr3i (g) |为绝对差异化向量, η为缩放因子。
Step 3 交叉操作。交叉操作是为了增加群体的多样性, 具体操作如下:
《图10》
其中RC为交叉概率, RC∈[0, 1], R (s) 在[1, n]之间的随机整数, 这种交叉策略可确保ts (g+1) 至少有一分量由ths (g+1) 的相应分量贡献。
Step4 选择操作。为了决定ts (g) 是否成为下一代的成员, 向量tvs (g+1) 和目标向量ts (g) 对评价函数进行比较:
《图11》
《4 工程实例分析》
4 工程实例分析
《4.1工程实例》
4.1工程实例
某网络进度计划如图2所示, 已知资料见表1, 包含工程在正常时间及极限时间下完成各工序的费用和质量相对值。提前完工奖励500元/d, 间接费为500元/d。
由表1可得各工序的最大压缩时间tmax、费率Ci和压缩工序质量qi的数学模型, 见表2。
用差异演化算法对净收益最大和质量最优的多目标进行优化求解, 2个子目标权值由决策者按需要确定, 净收益和质量的权值分别为0.6和0.4。
《4.2工序间的逻辑关系处理》
4.2工序间的逻辑关系处理
工序间的逻辑关系约束采用关系矩阵r来处理。r是描述网络中工序间前后逻辑约束关系的矩阵。根据工序间的前后逻辑关系, 把网络中每个活动与所有活动的关系写成一行, 作为r的行, 关系矩阵的行数和列数均等于活动的个数, 即
《图15》
rij是第i行第j列的元素, 表示i工序与j工序之间的关系:0表示i工序是j工序的紧前工序, -1表示两工序没有直接关系, 1表示i工序是j工序的紧后工序。不论网络计划如何调整, 其关系矩阵是固定不变的, 不会出现违反逻辑关系的解。
对工期约束T≤T+用罚函数法处理。对工序持续时间的约束TLi≤ti≤TUi, 按3.2节处理。
《4.3基于DE算法的网络计划多目标优化》
4.3基于DE算法的网络计划多目标优化
用DE算法对网络计划多目标进行优化, 最大进化代数gmax=2 000, 群体规模均取50, 交叉概率RC均取0.3, DE算法缩放因子η= 0.5。用遗传算法 (GA) 和模拟退火 (SA) 的优化结果进行比较, 结果见表3。
从表3可看出, DE算法的优化结果较其他两种方法优越, 它所对应的各工序持续时间为{6, 23, 15, 12, 22, 26, 17, 14}。
《5 结论》
5 结论
对净收益最大的工期-费用以及质量-时间详细分析之后, 建立起工期-净收益-质量多目标优化模型, 并设计差异演化算法对该多目标模型进行求解。结果表明, 用DE算法提高了施工企业的经济效益, 比其他算法也具有较大的优越性。该方法对于施工网络计划优化有一定的应用价值。
京公网安备 11010502051620号
