网络计划的优化——总工期不变,成本最低.docx

网络计划的优化——总工期不变,成本最低
概述
网络计划是工程项目管理中常用的一种管理工具，通过构建项目网络图，确定项目中的关键任务，制定合理的工期安排和进度控制，以及预测项目的最终完成时间。然而，在网络计划的实施过程中，如何控制成本是一个较为棘手的问题，通常需要制定线性规划模型，以及采用最优化算法进行求解。本文将从总工期不变、成本最低的问题出发，介绍网络计划的优化策略，并通过实例分析，探讨如何制定合理的优化方案，降低工程项目的成本，提升工作效率。
一、线性规划模型
在控制项目成本的问题上，线性规划模型是常用的优化方法之一。其基本思想是将网络计划中的各项工作转化为变量，以及各项工作的成本、工期等限制条件转化为线性约束条件，最后将生产成本、生产量等目标函数转化为线性函数进行最小化或最大化求解。
假设一个工程项目需要完成n项任务，每项任务完成所需的时间为Ti，每天的造价为Ci，每项任务均有一定的前置时间要求，由此可以设计如下的线性规划模型：
目标函数：
min∑i=1nCiTi
约束条件：
1.每项任务完成所需时间不得超过规定时间
∑j∈M(i)Tj+Ti≤D,i=1,2,...,n
其中M(i)表示任务i的前置任务集合，D为总工期
2.每项任务必须在其前置任务的完成之后才能开始
Tj+Tj≥Ti,i=1,2,...n,j∈M(i)
3.每项任务的工期必须为正值
Ti≥0,i=1,2,...,n
通过以上线性规划模型，可以确定工程项目中各项任务的最佳时间安排，并以此为基础确定生产成本，确保工程项目的总工期不变，成本最低。
二、最优化算法
线性规划模型虽然能在一定程度上优化工作成本，但是其求解过程需要耗费大量的计算资源，同时在实际生产中，工作任务之间存在不确定性，导致任务的完成时间和工期存在一定的漂移。因此，其优化效果有时难以得到精确的把握。
为了克服模型求解的难题，同时提高优化效果，网络计划的最优化算法应运而生。其中，动态规划、贪心算法、遗传算法、蚁群算法等算法均可应用于网络计划的优化过程。
例如，遗传算法是通过模拟遗传学的进化过程，通过选择、交叉、突变等操作，从而找到最优的解决方案。针对网络计划中的优化问题，遗传算法可以将各项任务的时间安排视为染色体，通过对染色体进行交叉、变异等操作，逐步生成新的个体，并通过选择和淘汰操作，逐渐逼近最优解。
三、实例分析
下面以一座建筑工程为例，对网络计划的优化过程进行实例分析。
建筑工程计划需要完成7项工作，每项工作在完成前需要满足一定的前置条件，并存在一定的成本和时间限制。具体项目流程如下：
如图所示，各项工作之间存在着一定的前置关系，但目标是保证工程总工期不变，成本最低，因此需要针对工程项目制定合理的优化方案。
方案一：线性规划模型
首先，针对上述工程项目，建立如下的线性规划模型：
目标函数：
min∑i=1nCiTi
约束条件：
1.每项任务完成所需时间不得超过规定时间
T1≤4,T2≤2,T3≤2,T4≤3,T5≤3,T6≤2,T7≤4
2.每项任务必须在其前置任务的完成之后才能开始
T2+T3≥T1,T4+T5≥T2,T6≥T4,T7≥T5
3.每项任务的工期必须为正值
Ti≥0,i=1,2,...,n
通过求解以上线性规划方程，可以得出最佳时间安排为T1=4，T2=2，T3=2，T4=3，T5=3，T6=2，T7=4，进而推算出最低成本为42。
方案二：遗传算法
针对上述建筑工程问题，可以采用遗传算法进行求解。以时间安排为染色体，初始种群为随机生成的1~10个合理个体，用该种群作为基础，逐渐生成更优的个体，直到找到最优解。
图2-1遗传算法流程
遗传算法主要有以下几个步骤：
1.确定初始化条件，随机生成初始种群
2.适应性函数的生成
将目标函数中的成本最低转化为适应性函数，将问题转化为求适应性函数最高个体的过程。
3.选择操作
从适应度高的个体中选择种群，以保持基因多样性。
4.交叉操作
对两个亲代染色体进行交叉操作，生成新的个体。
5.变异操作
以一定概率对染色体进行变异，生成新的个体。
6.繁衍新种群
根据上述步骤生成新种群，迭代求解，最终找到最优解。
通过上述方案二，将建筑工程的时间安排转化为染色体，得到如下的遗传操作结果：
遗传代数适应度最高的染色体染色体的最大适应度
1<4,2,2,3,3,2,4>171
2<4,2,2,3,3,2,4>168
3<4,2,2,3,3,2,4>165
4<4,2,1,3,3,2,4>160
5<4,2,1,2,3,2,4>156
6<4,2,1,2,3,1,4>145
7<4,2,1,2,3,1,3>141
8<4,1,1,2,3,1,3>134
9<3,1,1,2,3,1,3>123
10<3,1,1,2,2,1,3>119
通过对适应度