第三章-工程项目资源计划与优化(1014)电子教案.docx

第三章 工程项目资源计划与优化任何项目的实施都需要有各种资源的投入，如人力资源、原材料、设备、资金等。资源计划与均衡是以进度计划为依据，对项目中的各项工作所需的资源进行估计并进行均衡及分配的过程。第一节 概述项目资源应分成两部分，一是项目本身所需要的材料与设备；二是项目实施中的人力，设施、设备及能源等。资源计划要决定每一项工作所使用的资源种类与数量，另外，资源的供应量是有限的，因此，资源计划还涉及约束条件下的分配与均衡。资源计划确定下来后，结合资源的使用价格，就可以估计资源费用和编制费用计划，因此，资源计划是费用计划与控制的基础。一、资源计划的依据1.工作分解结构WBS利用WBS进行资源计划时，工作划分得越细、越具体，所需资源种类和数量越容易估计。工作分解自上而下逐级展开，各类资源需要量可以自下而上逐级累加，于是便得到了整个项目各类资源需要量情况。2.项目工作进度计划项目工作进度计划是项目计划中最主要的计划，是其他项目计划（如质量计划、资金使用计划）的基础。资源计划必须服务于工作进度计划，什么时候需要何种资源及需要多少是围绕工作进度计划而确定的。3.历史信息历史信息记录了先前类似工作使用资源的情况，在新项目中，分配给某项工作的资源类型和数量可以参考同类工程的经验数据。4.工作范围说明工作范围说明详细说明了项目工作的要求、内容、工作量的大小等信息，工作量的大小及时间上的要求，决定了该项工作所需资源数量。5.资源供应情况什么资源是可能获得的及供应量大小是项目资源计划所必须掌握的。资源需求计划与资源供应水平必须相适应，假如资源获取很困难甚至无法取得，就必须重新选择资源类型，从而需要修改原来的资源需求计划。6.组织策略在资源计划的过程中还必须考虑人事组织、所提供设备的租赁和购买策略。例如，工程项目中劳务人员是用外包工还是本企业职工，设备是租赁还是购买等，都对资源计划产生影响。二、资源计划的方法1.专家调查法在缺乏客观资料和数据的情况下，常常采用专家调查法估计资源类型和数量，制定资源计划。这种方法能充分发挥专家个人的知识、经验和特长方面的优势。其优点是简单易行，专家不受外界干扰，没有心理压力，可最大限度的发挥个人的知识潜力。缺点是计划结果容易受专家个人经验及主观因素的影响，难免带片面性。2.头脑风暴法在确定资源的类型、数量以及如何分配资源时，也可采用头脑风暴法。头脑风暴法的本质是激发群体成员无限制的自由联想和讨论，其目的在于产生新观念或新设想。具体来说就是团队的全体成员在作出最后的决策前，自发地提出尽可能多的主张和想法。头脑风暴法更注重出主意的数量，而不是质量。这样做的目的是要团队想出尽可能多的主意，鼓励成员有新奇或突破常规的主意。应用头脑风暴法时，要遵循两个主要的规则：不进行讨论；没有判断性评论。实践证明，头脑风暴法在帮助团队获得解决问题最佳可能方案时，是很有效的。3.数学模型为了使编制的资源计划具有科学性、可行性，在资源计划的编制过程中，往往借助于某些数学模型，如资源分配模型和资源均衡模型等，这些模型将在下面的章节中予以详细介绍。三、资源计划的类型1.劳动力需要量计划劳动力需要量计划，主要是作为安排劳动力、衡量劳动力消耗指标、安排生活福利设施的依据。其编制方法是根据施工方案、施工进度和施工预算，依次确定专业工种、进场时间、劳动量和工人数，然后汇集成表格形式，作为现场劳动力调配的依据。劳动力需要量计划的编制步骤为：（1）根据工程量汇总表中分别列出的各个单位工程的主要实物工程量，查预算定额或有关资料，得到各个单位工程主要工种的劳动量；（2）根据施工进度计划表的各单位工程中各工种的持续时间，得到某单位工程在某段时间里的平均劳动力数；（3）按同样方法计算出各个建筑物各主要工种在各个时期的平均工人数；（4）将施工进度计划表纵坐标方向上同工种的人数叠加在一起并连成一条曲线，即为某工种的劳动力动态曲线图；（5）其他工种也用同样方法绘成曲线图；（6）根据劳动力曲线图列出主要工种劳动力需要量计划表，其表格形式如表3-1所示。表3-1 劳动力需要量计划表序号工种名称劳动量（工日）月份12345672.主要材料需要量计划主要材料需要量计划，主要是作为备料、供料和确定仓库、堆场面积及组织运输的依据。其编制方法是根据施工预算工料分析和施工进度计划，依次确定材料名称、规格、数量和进场时间，并汇集成表格，其表格形式如表3-2所示。主要材料需求量计划的编制步骤为：（1）根据工程量汇总表所列各建筑物的工程量，查定额或有关资料，可得出各单位工程所需的建筑材料的需要量；（2）根据施工进度计划表，大致算出某些建筑材料在某一时间内的需要量，编制出建筑材料的需要量计划表。表3-2 材料需要量计划表序号材料名称规格需要量供应时间备注单位数量某些分项工程是由多种材料组成的，应按各种材料分类计算，如混凝土工程应计算出水泥、砂石、外加剂和水的数量，列入表格。3.构件和半成品需要量计划建筑结构构件、配件和其他加工半成品的需要量计划主要用于落实加工订货单位，按照所需规格、数量、时间组织加工、运输，确定仓库或堆场面积等。其编制步骤与编制材料需要量计划相同，其表格形式如表3-3所示。表3-3 构件和半成品需要量计划表序号品名规格需要量使用部位供应时间备注单位数量4.施工机械需要量计划施工机械需要量计划主要用于确定施工机具的类型、数量、进场时间，落实施工机具来源，组织其进出场。其编制方法为：将单位工程施工进度表中的每一个施工过程，每天所需要的机械类型、数量按施工工期进行汇总，即得施工机械需要量计划，其表格形式如表3-4所示。表3-4 施工机械需要量计划表序号机械名称型号需要量货源使用时间备注单位数量在安排施工机械进场时间时，应考虑某些机械需要铺设轨道、拼装和架设的时间，如塔式起重机、桅杆式起重机等需要现场拼装和架设。四、资源计划的工具1.资源矩阵资源矩阵用以说明完成项目中的各项工作需要用到的各种资源的情况。表3-5给出了资源矩阵的一个例子。在表3-5中，左边的列给出了项目中的各项工作（任务），上面的行给出了项目中所用到的资源的名称，行列交叉处的元素代表各项工作所需要各种资源的数量。表3-5 资源矩阵 资 源工（台） 时任 务工长高级工中级工初级工1m3挖掘机8m3铲运机人工挖一般土方（三类土，100m3）1.783.5人工铺筑砂石垫层（100m3）10.2497.4挖掘机挖土方（三类土，100m3）4.30.99挖运机铲运土（三类土，100m3）2.522.资源数据表资源数据表用以说明各种资源在项目周期内各时间段上需要的类型和数量。表3-6是资源数据表的一个例子。在表3-6中，第1周，需要电焊工2人、电工1人；第2周，需要电焊工2人、木工1人、电工1人。依此类推，可知项目周期内各时间段上所需资源种类及数量。表3-6 资源数据表 时间 人数资源时 间123456789101112131415电焊工22钢筋工3333砌筑工2222222木工111111电工111111113.资源甘特图资源甘特图用以反映各种资源在项目周期内各时间段上分配给了哪些工作。表3-7是资源甘特图的一个例子。某分部分项工程要用到两类资源：砌筑工和混凝土工。砌筑工要完成的任务包括砌半砖隔墙、砖外墙和砌女儿墙，其在每一项任务上的工作时间用表格右边的短横线表示。例如，砌筑工要在第12-13天砌筑女儿墙。表3-7 资源甘特图资源名称时间（天）12345678910111213砌筑工 M5混合砂浆砌半砖隔墙 M5混合砂浆砌砖外墙 M5混合砂浆砌女儿墙混凝土工 混凝土构造柱 混凝土圈梁 混凝土有梁板4.资源负荷图资源负荷图以图形的方式展示了项目周期内的各时间段上所需要的资源的数量，可以按不同种类的资源画出不同的资源负荷图。图3-1是人力资源负荷图的一个例子。图3-1 人力资源负荷图5.资源累计图在资源负荷图的基础上，按时间累计出项目周期内的各个阶段所需要的资源的数量，绘制而成的曲线就是资源累积图。图3-2是材料需要量累计图的一个例子。图3-2 材料需要量累计图五、资源计划的结果资源计划的结果是一份资源需求计划文件，其应对项目所需各种资源的类型、数量及在时间上的安排加以详细描述，并以图表的形式予以反映。资源的需求安排一般应分解到具体的工作上，即要确定每一项工作需要什么类型资源、需要多少、啥时候需要等。资源计划的结果如下：（1）资源的需求计划；（2）各种资源需求及需求计划的描述；（3）具体工作的资源需求安排。第二节 资源需求量的计算为了便于研究项目的资源需求和工作进度安排之间的关系，假定项目实施中只使用一种资源（劳动力），并且假设每项工作的资源使用率保持不变，于是，劳动力在该工作上的总劳动时数等于每天需要的劳动力与工作持续时间的乘积。如果资源的使用率发生变化，就应该分别确定每一时间区段的资源需要状况。一、最早时间下的资源需求量下面以一个例子来说明当项目中所有工作都按最早时间安排时，其对应的资源需求量应该如何计算。例3-1某分部工程包括7项工作，工作的持续时间及相互之间的逻辑关系见图3-3所示，每项工作每天需要的劳动时数及总劳动时数见表3-8所示。试绘制最早时间资源需求量负荷图及累计曲线。图3-3 项目网络图表3-8 工作所需资源数量序号工作名称持续时间每天需要的劳动时数总劳动时数1A58402B34123C83244D72145E75356F49367G5735解1.计算工作最早时间，并绘制甘特图工作最早开始时间和最早完成时间的计算方法参见第二章相关内容，计算结果见表3-9所示。据此绘制最早时间甘特图，如图3-4所示。2.根据工作最早时间安排，计算项目的资源需求量根据图3-4的工作进度安排，统计项目的每天资源需求量（劳动时数），见表3-10所示。3.绘制相应的资源负荷图根据表3-10所示数据，绘制相应的资源负荷图，见图3-5所示。4. 绘制相应的资源累计曲线根据表3-10所示数据，将劳动时数按时间（天）逐步累计，然后绘制出相应的资源累计曲线，见图3-6所示。表3-9 工作时间参数表工作名称最早开始时间最早完成时间最迟开始时间最迟完成时间A0505B0336C513513D512613E07613F13171317G17221722图3-4 最早时间甘特图表3-10 最早时间下的资源需要量图3-5 最早时间资源负荷图图3-6 最早时间资源累计曲线二、最迟时间下的资源需求量1.计算工作最迟时间，并绘制甘特图工作最迟开始时间和最迟完成时间的计算方法参见第二章相关内容，计算结果见表3-9所示。据此绘制最迟时间甘特图，如图3-7所示。图3-7 最迟时间甘特图2.根据工作最迟时间安排，计算项目的资源需求量根据图3-7的工作进度安排，统计项目的每天资源需求量（劳动时数），见表3-11所示。表3-11 最迟时间下的资源需要量3.绘制相应的资源负荷图根据表3-11所示数据，绘制相应的资源负荷图，见图3-8所示。图3-8 最迟时间资源负荷图4. 绘制相应的资源累计曲线根据表3-11所示数据，将劳动时数按时间（天）逐步累计，然后绘制出相应的资源累计曲线，见图3-9所示。图3-9 最迟时间资源累计曲线第三节 资源优化资源是指为完成一项计划任务所需投入的人力、材料、机械设备和资金等。完成一个项目所需要的资源量基本上是不变的，不可能通过资源优化将其减少。资源优化的目的是通过改变工作的开始时间和完成时间，使资源按照时间的分布符合优化目标。在通常情况下，网络计划的资源优化分为两种，即“资源有限，工期最短”的优化和“工期固定，资源均衡”的优化。前者是通过调整计划安排，在满足资源限制条件下，使工期的延长值达到最少的过程；而后者是通过调整计划安排，在工期保持不变的条件下，使资源需用量尽可能均衡的过程。在优化过程中，不能改变网络计划中各项工作之间的逻辑关系；不能改变网络计划中各项工作的持续时间；除规定可中断的工作外，一般不允许中断工作，应保持其连续性。一、“资源有限，工期最短”的优化“资源有限，工期最短”的优化本质上是为了解决资源需求和供应的冲突问题，当资源的需求量超过了资源的供应量时，项目管理者就要思考如何解决这一矛盾。办法之一是增加资源的供给量，可通过购买、租赁等手段提高资源的最大供应量。办法之二是通过调整项目中工作的开工时间和完工时间，来降低对资源的需求量，在不增加任何额外资源的情况下，解决资源冲突矛盾。“资源有限，工期最短”优化主要是针对后者。1.优化步骤（1）按照各项工作的最早开始时间安排进度计划，并计算项目每天的资源需要量。（2）从计划开始日期起，逐个检查每天的资源需要量是否超过资源限量。如果在整个工期内资源需要量均能满足资源限量的要求，则此方案即为可行方案，否则必须进行优化。（3）分析超过资源限量的时段（资源需要量相同的时间区段）。如果在该时段内有几项并行工作，则采取将一项工作安排在与之平行的另一项工作之后进行的方法，以降低该时段的资源需要量，其结果是项目的总工期有可能变长了。如图3-10所示，在时间段t1，t2内资源出现冲突，即资源需要量大于资源供应量。观察发现，在这一时间段内，工作i和工作j在并行实施。为减少这一时段的资源需要量，拟将工作j安排在工作i完成之后立即开始，如图中黑粗线所示。这一安排上的改变对总工期的影响可用下述公式表示： （3-1）当然，还可将工作i安排在工作j之后实施来减少这一时段的资源需要量。此时，对总工期的影响为： （3-2）“资源有限，工期最短”优化就是在上述两种方案中寻找对总工期影响最小的方案。如果在冲突时段有多项并行工作，要使最小，就必须选择LS最大的一项工作安排在EF最小的另外一项工作的后面，如此安排可使其对总工期的影响最小。（4）对调整后的网络计划重新计算每天的资源需用量。（5）重复上述第2个步骤到第4个步骤，直至网络计划整个工期范围内每天的资源需要量均满足资源限量为止。012345678910111213141516EFi将工作j安排在工作i完成之后立即开始工作iEF LSjLFj工作j资源冲突时段t1t2LS图3-10 并行关系变成先后关系后对总工期的影响2.优化示例例3-2已知某工程双代号网络计划如图3-11所示，图中箭线上方数字为工作的资源强度，箭线下方数字为工作的持续时间（以天为单位）。假定资源限量Ra=12，试对其进行“资源有限，工期最短”的优化。图3-11 初始网络计划解（1）计算网络计划每天的资源需用量，如图3-11图形下方数字所示。（2）从计划开始日期起，经检查发现时段3，4存在资源冲突，即资源需要量超过资源限量，故应首先调整该时段工作安排。（3）在时段3，4有工作1-3和工作2-4两项工作并行作业，它们的最早完成时间和最迟开始时间如下所示：工作1-3： EF1-3=4，LS1-3=3工作2-4： EF2-4=6，LS2-4=3其中EF最小的是工作1-3，LS最大的是工作2-4，所以应将工作2-4安排在工作1-3之后。计划调整结果如图3-12所示。（4）重新计算每天的资源需要量，如图3-12所示。从图中可知，在时段7，9存在资源冲突，故应调整该时段工作安排。图3-12 第一次调整后的网络计划（5）在时段7，9有工作3-6、工作4-5和工作4-6三项工作并行作业，它们的最早完成时间和最迟开始时间如下所示：工作3-6： EF3-6=9， LS3-6=8工作4-5： EF4-5=10， LS4-5=7工作4-6： EF4-6=11， LS4-6=9其中EF最小的是工作3-6，LS最大的是工作4-6，所以应将工作4-6安排在工作3-6之后。计划调整结果如图3-13所示。图3-13 第二次调整后的网络计划（6）重新计算每天的资源需用量，如图3-13所示。由于此时整个工期范围内每天的资源需要量均未超过资源限量，故图3-13所示方案即为最优方案，其最短工期为13。二、“工期固定，资源均衡”的优化“工期固定，资源均衡”的优化，是指在工期不变的情况下，使资源的分布能够尽量达到均衡，即在整个工期范围内每天的资源需要量不出现过多的高峰和低谷，力求每天的资源需要量接近平均值，这样不仅有利于工程建设的组织与管理，而且还可以降低工程费用。“工期固定，资源均衡”的优化方法有多种，如方差值最小法、极差值最小法、削高峰法、遗传算法等，这里仅介绍方差值最小法和遗传算法。（一）方差值最小法1.方差值最小法的原理已知某工程网络计划如图3-14所示，项目总工期为T，每天的资源需要量用R1，R2，RT表示。图3-14 网络计划及资源需要量表达资源需求不均衡的指标可用其方差来表示，方差越大，说明资源需要量越不均衡，其计算公式为： （3-3） （3-4）上述公式中，：第t天的资源需要量；：平均资源需要量。将式（3-3）展开，可简化为： （3-5）因为优化时要保证总工期不变，所以上述公式中的T和为常数。据此，方差的大小仅与的值有关，当的值变小时，也就意味着方差变小了，即资源需要量变得更加均衡了。令从网络计划中任意挑选一项工作k，假设工作k从第i天开始，到第j天完成，工作k的资源需要量为，见图3-14所示。若将工作k右移一天，即工作k从第i+1天开始，到第j+1天完成，从图中可以看出，如此调整后，只有第i天和第j+1天的资源需要量发生了变化，其他时间的资源需量未发生改变。记调整后的资源需用量的平方和为，则调整前后两者的差值为：如果为负值，则说明工作k右移一天能使资源需要量的平方和减少，从而使资源需用量更加均衡。因此，工作k能够右移一天的判别式是： （3-6）由于不可能为负值，故判别式（3-6）可以简化为： （3-7）判别式（3-7）表明，当工作k完成时间之后下一天所对应的资源需用量与工作k的资源需要量之和不超过工作k开始时间所对应的资源需用量时，将工作k右移一天能使资源需要量更加均衡。这时，就应将工作k右移一天。如此判别右移，直至工作k不能右移或工作k的总时差用完为止。2.优化步骤（1）按照各项工作的最早开始时间安排进度计划，并计算网络计划中每天的资源需用量。（2）从网络计划的终点节点开始，按工作完成节点编号值从大到小的顺序依次进行调 整。当某一节点同时作为多项工作的完成节点时，应先调整开始时间较迟的工作。在调整工作时，一项工作能够右移的条件是：1）工作具有足够的机动时间，在不影响工期的前提下能够右移；2）工作满足判别式（3-7）。只有同时满足以上两个条件，才能调整该工作，将其右移至相应位置。（3）当所有工作均按上述顺序自右向左调整了一次之后，为使资源需用量更加均衡，可再按上述顺序自右向左进行多次调整，直至所有工作不能右移为止。3.优化示例例3-3已知某工程双代号网络计划如图3-15所示，图中箭线上方数字为工作的资源强度，箭线下方数字为工作的持续时间（以天为单位）。试对其进行“工期固定，资源均衡”的优化。解（1）计算网络计划每天的资源需用量，放在时标网络图的下方，如图3-15所示。图3-15 初始网络计划及资源需要量由于总工期为14，故资源需用量的平均值为：Rm（214+219+20+8+412+9+35）14=1161411.86（2）第一次调整1）以终点节点为完成节点的工作有三项，即工作3-6、工作5-6和工作4-6。其中工作5-6为关键工作，由于工期固定而不能调整，只能考虑工作3-6和工作4-6。由于工作4-6的开始时间晚于工作3-6的开始时间，应先调整工作4-6。由于R11+r4-69+312，R7=12，二者相等，故工作4-6可右移一天，改为第7天开始；由于R12+r4-65+38，小于R8=12，故工作4-6可再右移一天，改为第8天开始；由于R13+r4-65+38，小于R912，故工作4-6可再右移一天，改为第9天开始；由于R14+r4-65+38，小于R1012，故工作4-6可再右移一天，改为第10天开始。至此，工作4-6的总时差已全部用完，不能再右移。工作4-6调整后的网络计划及资源需求量如图3-16所示。工作4-6调整后，就应对工作3-6进行调整。由于R12+r3-68+412，小于R520，故工作3-6可右移一天，改为第5天开始；由于R13+r3-68+412，大于R68，故工作3-6不能右移一天；由于R14+r3-68+412，大于R79，故工作3-6也不能右移一天。由于工作3-6的总时差只有3天，故该工作此时只能右移一天，改为第5天开始。工作3-6调整后的网络计划及资源需求量如图3-17所示。图3-16 工作4-6调整后的网络计划及资源需要量图3-17 工作3-6调整后的网络计划及资源需要量2）以节点为完成节点的工作有两项，即工作2-5和工作4-5。其中工作4-5为关键工作，不能移动，故只能调整工作2-5。由于R6+r2-58+715，小于R319，故工作2-5可右移一天，改为第3天开始；由于R7+r2-59+716，小于R419，故工作2-5可再右移一天，改为第4天开始；由于R8+r2-59+716，R516，二者相等，故工作2-5可再右移一天，改为第5天开始；由于R9+r2-59+716，大于R68，故工作2-5不可右移一天。此时，工作2-5虽然还有总时差，但不能满足判别式（3-7），故工作2-5不能再右移。至此，工作2-5只能右移3天，改为第5天开始。工作2-5调整后的网络计划及资源需求量如图3-18所示。图3-18 工作2-5调整后的网络计划及资源需要量3）以节点为完成节点的工作有两项，即工作1-4和工作2-4。其中工作2-4为关键工作，不能移动，故只能考虑调整工作1-4。在图3-18中，R6+r1-415+520，大于R114，不满足判别式（3-7），故工作l-4不可右移。4）以节点为完成节点的工作只有工作1-3，在图3-18中，由于R5+r1-39+312，小于R114，故工作1-3可右移一天。工作1-3调整后的网络计划及资源需要量如图3-19所示。5）以节点为完成节点的工作只有工作1-2，由于该工作为关键工作，故不能移动。至此，第一次调整结束。图3-19 工作1-3调整后的网络计划及资源需要量（3）第二次调整从图3-19可知，在以终点节点为完成节点的工作中，只有工作3-6有机动时间，有可能右移。由于R13+r3-68+412，小于R615，故工作3-6可右移一天，改为第6天开始；由于R14+r3-68+412，小于R716，故工作3-6可再右移一天，改为第7天开始。至此，工作3-6的总时差已全部用完，不能再右移。工作3-6调整后的网络计划及资源需要量如图3-20所示。图3-20 优化后的网络计划及资源需要量从图3-20可知，此时所有工作右移或左移均不能使资源需用量更加均衡。因此，图3-20所示网络计划即为最优方案。（4）比较优化前后的方差值1）根据图3-20，优化方案的方差值由公式（3-5）得：2=1141122+142+1228+162+922-11.862=2.772）根据图3-15，初始方案的方差值为：2=1141422+1922+202+82+1224+92+523-11.862=24.343）方差降低率为：24.34-2.7724.34100%=88.62%（二）遗传算法*遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。1.求函数最大值的数学模型及解法对于一个求函数最大值的优化问题（求函数最小值也类同），一般可描述为下述数学规划模型： max f(x) （3-8） s.t. XR （3-9） RU （3-10）式中，X=(x1,x2,xn)T为决策变量，f(X)为目标函数，式（3-9）、（3-10）为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解x称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。在上述最优化问题中，目标函数和约束条件的种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也是不现实的，因而求出其近似最优解或满意解是人们的主要着眼点之一。总的来说，求最优解或近似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。（l）枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。（2）启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。（3）搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到一种较好的平衡。随着问题种类的增多，以及问题规模的扩大，要寻求到一种能以有限的代价来解决上述最优化问题的通用方法仍是一个难题。而遗传算法却为解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。2.遗传算法简介遗传算法中，将n维决策向量X=(x1,x2,xn)T用n个记号Ci(i=1,2,n) 所组成的符号串C来表示，即：C=C1C2C3Cn。把每一个Ci看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。最简单的基因是由0和1这两个整数组成的二进制符号串，比如，C1=1101。假如决策向量是3维的，每一个基因是长度为4的二进制符号串，则X可表示为长度为12的二进制符号串，例如：X=010100010000。这种编码所形成的排列形式C1C2C3Cn称为个体的基因型，与它对应的x1,x2,xn称为个体的表现型。将个体的表现型带入公式（3-8）就可求出目标函数的值。通常个体的表现型和其基因型是一一对应的。对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。对于求最大值问题，可直接将目标函数作为个体的适应度。遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程。第t代群体记做P(t)，经过一代遗传和进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记做P(t+1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的，与此相对应，遗传算法中最优解的搜索过程也模仿生物的这种进化过程，使用所谓的遗传算子作用于群体P(t)中，从而得到新一代群体P(t+1)。遗传算子有三种类型：（1）选择算子选择算子的作用是根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。（2）交叉算子交叉算子的作用就是将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率交换它们之间的部分染色体。（3）变异运算变异运算的作用就是将群体P(t)中的每一个个体，以一定的概率改变某一个或某一些基因的值。遗传算法的一般流程如图3-21所示。产生初始种群计算适应度是否满足优化准则最佳个体结束选择交叉变异开始YesNo图3-21 遗传算法流程图3.多资源均衡优化模型假如某一项目包含N项活动，需要K种资源（如材料、设备等）。第i项活动的持续时间用表示，其单位时间内所需第k种资源数量记为。项目总工期记为T，第t时刻项目所需第k种资源数量记为。资源均衡优化过程中要保证：（1）不能改变活动之间的逻辑关系；（2）任何一项活动必须保持连续施工，不能有停顿；（3）项目的总工期保持不变。多资源均衡优化的目标是寻找各项活动的计划开工时间，使得在项目总工期内各种资源需要量的标准偏差线性加权之和达到最小。其优化模型可用公式（3-11）表示。 s.t. （3-11）公式（3-11）中，和分别代表活动i和j的计划开工时间；和分别代表活动i的最早开始时间和最迟开始时间；代表活动i的紧后活动，Pred（i）代表活动i的紧前活动；为选定的一组权系数，满足 ；表示第k种资源需要量的标准偏差，可按下列公式计算。 （3-12）公式（3-12）中，代表第k种资源需要量的平均值，其值按公式（3-13）进行计算。 （3-13）4.遗传算法实现资源均衡优化遗传算法的编码形式对算法的搜索能力和种群多样性等性能有着重要影响。考虑到资源均衡优化目标函数以及约束条件的复杂性，一般采用浮点数编码方法。以活动的计划开工时间作为决策变量，个体的编码长度等于其决策变量的个数，个体的每个基因值用区间ES,LS内的一个浮点数来表示。个体的适应度采用一足够大的整数减去目标函数值，将资源均衡问题转化为极大化问题。（1）选择运算采用轮盘赌选择法来选择遗传个体。其基本思想是：各个个体被选中的概率与其适应度大小成正比。具体过程为：1）先计算出群体中所有个体的适应度总和；2）计算每个个体的相对适应度大小，它等于个体适应度与适应度总和的比值，此即为该个体被遗传到下一代的概率；3）使用模拟赌盘操作（即0到1的随机数）来确定各个个体被选中的次数。（2）交叉运算采用单点交叉算子。其基本思路是：对每一对相互配对的个体，随机选择交叉点，依设定的交叉概率，在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。（3）变异运算采用均匀变异算子。均匀变异操作是指用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。利用Matlab提供的遗传算法工具箱，并结合具体问题编制相应的适应度函数、选择函数、交叉函数和变异函数的运行代码，运行主程序后即可得到优化结果。5.优化示例某网络计划如图3-22所示，箭线上方的数字表示活动所需资源数量（假设项目中所有活动使用两种资源），箭线下方数字表示活动的持续时间（时间单位为天），假定两种资源的权重分别为0.7和0.3。表3-12列出了各项作业的开始时间、结束时间和总时差。图3-22 活动所需资源数量表3-12 各项作业的开始时间、结束时间和总时差作业持续时间ESEFLSLFTFA505050B1