图论在工程项目优化中的应_...
- 格式：pdf
- 大小：602.28 KB
- 文档页数：4
第26卷第3-4期建 井 技 术V ol 26 N o 3-4 2005年 8月M I NE CON ST RU CT ION T ECH NO L OGYA ug 2005收稿日期:2005 04 11图论在工程项目优化中的应用吕宁华1,郭庆军2,何 晖2(1西安建筑科技大学管理学院,陕西西安,710055;2西安工业学院建筑工程系,陕西西安,710032)摘 要:图论在解决运筹学、网络理论、控制论等领域问题中显示出很大的优越性,现已广泛应用于运输工程、计算机辅助设计等领域。
在工程项目优化中,特别是大中型工程项目的优化,利用图论有关方法及计算机技术比用传统手工方法具有明显的优越性,有助于加快计算机辅助工程资源管理进程。
关键词:图论;工程项目;优化;网络图;关键线路中图分类号:T U 12 文献标识码:B 文章编号:1002 6029(2005)03-4 0060 04 工程项目的优化,是在满足既定约束条件下,按照一定目标,通过不断改进资源方案,寻求满意结果的过程。
过去资源优化是以正常工期为前提,逐次压缩关键线路上工作的持续时间(不低于极限时间),且每次压缩时均选择直接费用变化率最小者;一般只能在小型工程中应用,且很少有人考虑间接费用的变化。
对于大型工程项目,资源优化较复杂。
图论可将各种复杂的工程规划设计和进程安排用 图 来描述,然后用数学方法求得最优结果。
图论中所研究的 图 ,是由若干个点(称作顶点,Vertex )和若干条连接两顶点的线段(称作边,Edge)组成[1]。
通常顶点可用来表示事物,边用来表示这些事物之间的关系。
与工程上的平面图、地形图不同,图论中的 图 是用来表示事物之间的联系,顶点的位置、边的长短是无关紧要的,仅是解决许多工程问题的一种理想数学模型,便于计算机辅助分析计算。
我们引入图论中割集的概念,利用割集在有向图中的定义,提出了工程项目优化算法;且在原工程网络图改变时,只需将描述文件进行修改即可,应用起来快速简便。
图论在解决运筹学、网络理论、控制论等领域问题中显示出很大的优越性,现已广泛应用于运输工程、计算机辅助设计等领域。
1 基本概念(1)工程网络图[2]网络图指由箭线和节点组成的有向连通图。
完整线路指网络中包括始节点和末节点的线路。
关键线路指网络图中持续时间最长的线路。
正常工期指子项目在正常作业条件下完工的时间。
极限工期指子项目工期缩短到一定程度时,即使增加费用,工期也不能缩短。
直接费用变化率指减少或增加单位时间引起的该工程直接费用(人、材、机)增加或减少值。
间接费用变化率指减少或增加单位时间引起的该工程间接费用(管理费等)减少或增加值。
最优工期指父项目最低工程成本所对应的工程总工期。
(2)图论[2]网络图的生成树是网络图中的连通子图,包含所有节点,但任意两个节点间只有1条路径。
树枝是某棵生成树的边,连枝是除了树枝外的边。
第3-4期吕宁华等:图论在工程项目优化中的应用图1为某工程双代号施工网络图,箭线上字母表示子项目名称,括号内数字为直接费用变化率(单位:元);箭线下括号外数字为正常工期,括号内数字为极限工期。
关键线路为A -D -E 。
可选A ,B,C,E 为1个生成树的所有树枝;边D,F为连枝。
图1 某工程施工网络图工程成本由直接费与间接费组成。
直接费由人工费、材料费和施工机械使用费组成。
施工方案不同,直接费不相同;施工方案一定,如工期不同,直接费也不同。
间接费一般随工期的增加而增加。
考虑工程总成本时,还应考虑拖期要受到惩罚,提前竣工会得到奖励,提前投产会得到收益等因素。
工期与成本关系曲线如图2所示。
图2 工期与成本关系曲线割集是1个或多个边的集合。
割集的条件[3]是:对于1张有向连通图,若将其1个割集中所有边删去,则该图就被分成两个连通子图;若只删去该割集中的1个真子集,则有向图仍为1个连通图。
也就是说,割集S 是使连通图G 失去连通性的最小边集合。
有向图的关联(以行表示点,以列表示边)a ij =0, 边与点无关1, 边从点出发-1,边指向点有向图的割集矩阵(以行表示割集,以列表示边)q ij =0, 割集中不包含该边 1, 割集中包含该边,且边的方向与预定参考方向相同-1,割集中包含该边,且边的方向与预定参考方向相反基本割集矩阵是由某一棵树所对应的全部割集组成的矩阵。
图3中两条曲线即对应该项目的两个割集。
预定参考方向为包含始节点的节点集指向包含末节点的节点集,列的顺序为按子项目名正序排列,则S 1=(1,1,0,0,0,0),S 2=(0,0,1,0,1,0)。
图3 网络图的割集示意2 问题分析已知条件:网络图已确定,每个子项目允许正常工期D n 、极限工期D c 、直接费用变化率K 。
输入:间接费用变化率 。
输出:最优工期T 优、工程成本降低值C 降。
工序如何调整,才能使工程项目费用最少。
如果网络图关键线路只有1条,则压缩关键线路上直接费用变化率最小的工序作业时间,且工程总费用降低(直接费用变化小于间接费用变化);如果多于1条,可将网络图中的始、末节点分割在两侧的割集上,找1个直接费用最少的割集(正方向从始节点所在61建 井 技 术 2005年第26卷点集指向末节点所在点集,正方向的边对应的工序都缩减1个单位时间,负方向则延长1个单位时间),该割集所含元素直接费用变化小于间接费用变化。
3 工程项目优化算法关键线路子图为仅由该图所有关键线路组成的图。
设定间接费用变化率为 ,正常工期为T 。
定义 T =0,C 降=0,Opt{ T , C }为1个空数组。
如项目优化流程图(图4)所示:第1步:如果关键线路只有1条,转第2步;否则转第3步。
第2步:定义关键线路长度与次长线路差为 T 1。
在关键线路上找出直接费用变化率最小的工作I (关键线路上所有有调整余地的边的直接费用变化率按升序排列,自左向右在调整余地范围内调整),把所选边名I 和调整的时间 T i ( T i =D nI -D cI )记录在数组Opt 中,则 T =min{ T 1, T i }。
如果 C =K I - >0,转输出;否则T =T - T ,C 降=C 降+ C 。
如果仍有1条关键线路,则重复第2步;如果关键线路多于1条,则转第3步。
第3步:找出网络图关键线路子图,算出将该网络图分为分别包括始、末节点的割集矩阵,并分别计算割集对应的直接费用变化,将直接费用变化最小且在调整范围之内的边名I 和调整时间记入Opt 中。
若I 为1个子项目,则 T i =D n I -D cI ;若多于1个,设为J 个,则 T i =min{D(1)nI-D(1)cI,D(2)n I-D(2)cI, ,D (J )nI -D (J )cI }。
关键线路长度与次长线路差图4 项目优化流程62第3-4期 吕宁华等:图论在工程项目优化中的应用为 T1, T=m in{ T1, T i}。
如果 C= K I- >0,转输出;否则T=T- T,C降=C降+ C。
对于新网络图,重复第3步。
输出:最优工期T优,工程成本降低值C降,各子项目调整时间。
割集矩阵在现代信息传输中有重要用途,可用于开关网络优化设计和网络中的状态变量方程。
割集矩阵求法[2]如下:设关键线路子图节点数为m,边条数为r,且n=m-1,则关键线路子图的关联矩阵为m r。
设I=0。
第1步:删除关联矩阵任意一行,变为n r矩阵,记为A。
第2步:取出该矩阵中任意n列,组成n n的行列式B,求其值。
如果|B|>0,则求C=B-1,且I=I+1。
计算Q=C A,记为Q I。
如果矩阵中任意n列已罗列完,则转第3步;否则重复第2步。
第3步:对所有Q I的行进行比较,如果Q I的p行(Q ip)与Q J的q行(Q jq)满足Q ip= Q jq,则认为Q I和Q J为同一个割集。
对所有的Q I进行运算,求出所有割集的合集。
删去原割集矩阵中将始、末节点分在一侧的割集所对应的行组成的矩阵为割集矩阵。
将割集向量中值为1的边缩短1d对应的直接费用求和,记为D;将割集向量中值为-1的边增加1d对应的直接费用变化求和,记为E;则割集对应的费用为D-E。
4 案 例[4]某公路工程项目各单位工程施工控制天数及费用见附表。
附表 某公路工程项目各单位工程施工工期及费用工作代号工作名称紧前工作正常工期/d极限工期/d直接费用变化率/元A拆迁旧物、清理现场 30249000 B临时附属工程 28265000 C地下管线A,B25022018000 D涵洞和排水建筑物B1009015000 E路基工程C,D30028020000 F路面工程E40036023000 G桥梁工程B36034024000 H沿线设施F,G908010000 I整修H15134000输入:对于父项目,间接费用变化率 = 2万元/d,T=1085d。
输出:最优工期T优=1019d,工程降低成本C降=22 6万元。
拆迁旧物、清理现场工作压缩4d,临时附属工程压缩2d,地下管线压缩30d,路基工程压缩20d,沿线设施压缩10d,整修工作压缩2d。
以上过程可采用C语言编程。
5 结 论我们运用数学上的图论对项目优化进行了研究,并给出了算法。
可以看出,图论是工程项目管理的有效工具,它可使计算简便、快速、准确,特别适用于复杂的工程网络图处理。
结合CAD/CAM在工程中应用,图论必将显示强大的生命力。
[参考文献][1]王树禾 图论[M] 北京:科学出版社,2004[2]陈薇薇,王忠民 基于图论的工程成本工期平衡算法[J] 计算机工程与应用,2003,(18)[3]马 军,解建仓,刘瑞雪,等 工程施工中运输网络优化方案[J] 数学的实践与认识,2003,(8)[4]高一凡,王选仓 图论在工程进度管理中的应用[J]西安公路交通大学学报,2001,(1)63。
