匈牙利算法在输电线路项目分段招标中的应用研究.doc

匈牙利算法在输电线路项目分段招标中的应用研究 张祥ZHANGXiang；杨莉菲YANGLi-fei （国家电网中国电力技术装备有限公司，北京100052） 摘要：分段招标法输电线路项目、石油和天然气管道项目、铁路和公路项目具有广泛的应用。本文以某跨国输电线路项目招标为例，介绍以匈牙利算法为基础的分段招标法在大型项目招标中的应用，并在典型问题的基础上，对解决几种实际应用中遇到的特殊问题进行讨论。本文可为大型项目分段招标提供一定的理论和实践参考。 关键词：分段招标；匈牙利算法；输电线路项目 ：U723.3：A：1006-4311（xx）23-0145-02 作者简介：张祥（1983-），男，广西南宁人，经济师，博士，研究方向为工程项目管理。 0引言 分段招标法在输电线路项目、石油和天然气管道项目、铁路和公路项目应用较广。此类项目投资较大且项目具有一定的复杂性，业主需确保项目分段实施过程的工期和质量满足项目本身要求，同时项目总投资最小，即各标段投标价格总和最小。 在分段招标时，假设N个投标人中标N个标段，每个投标人只能中标一个标段，则该问题可以转化为典型的指派问题。对于N个投标人N个标段，解决指派问题的最直接的方法是穷举法，但是该方法需要进行N的阶乘次比较，当N较大时，需要比较的次数呈几何倍数增长，基本不能适应实际计算应用需要。匈牙利算法的提出为解决此类问题提供了一个较为简单快速的方法。本文介绍匈牙利算法的基本步骤，以某跨国输电线路项目招标为例介绍该方法在解决典型问题中的应用，并在典型问题的基础上，对解决几种特殊问题进行讨论。 1问题的数学模型描述和匈牙利算法过程 1.1问题描述 假设N个投标人分配N个标段，一个投标人只能分配一个标段，即一个标段只能分配给一个投标人，每个投标人在所有标段都有报价，需要解决的问题为如何分配标段，保证项目的投标价总和最小。 1.2匈牙利算法过程 该方法应用于在给定的nn价格矩阵寻找最佳分配结果。实施步骤如下： 步骤1：第一行中减去最小的数形成新的矩阵； 步骤2：第一列中减去最小的数形成新的矩阵； 步骤3：利用最少的水平线或垂直线覆盖所有的0； 步骤4：判定是否最优： 如果水平线和垂直线的总数是n，算法结束，即得到最优分配矩阵； 如果水平线和垂直线的总数小于n，表明还未达到最优分配结果，进入到步骤5； 步骤5：判断没有被覆盖的最小值，没有被覆盖的每行减去最小值，被覆盖的每列加上最小值，跳转到步骤3。 2应用案例 某跨国联网输电线路项目分5个标段进行招标，每个公司只能中标一个标段。共有21家公司参与该项目投标，均对5个标段进行报价。截标后经技术评标和商务评标，A、B、C、D、E五家公司进入最终短名单，各公司在各标段报价如下（单位为万美元）： 根据上述步骤，应用匈牙利算法对该矩阵进行计算最终达到以下最优结果： 即得到的评标结果为，A公司中标第4标段，中标价为2535万美元；B公司中标第5标段，中标价为2878万美元；C公司中标第1标段，中标价为2639万美元；D公司中标第3标段，中标价为2626万美元；E公司中标第2标段，中标价为3034万美元。投标价总和13712万美元，为最优组合。 3匈牙利算法应用过程中几种特殊情况的讨论 3.1某个投标人可以中标两个以上标段 上节案例中，假设业主评标委员会认定，E公司由于实力较强，可以中标两个标段。因此，在经技术评标和商务评标后，只有A、C、D、E四家公司进入短名单。E公司由于被允许中两个标段，故在价格矩阵中出现两次。经计算，最终可得最优投标价总和13895万美元。其中，E公司中标第1标段和第2标段，分别为2873万美元和3034万美元。 3.2某个投标人只在某些标段报价 上节案例中，业主评标委员会认定A、B、C、D、E五家公司进入最终短名单。但B公司未对第5标段进行报价，C公司未在第1标段和第2标段报价。此时，只需要在矩阵上未报价的区域填写一个比每列最大的数还大的数。经计算，最终可得最优投标价总和13787万美元。填写一个比每列最大的数还大的数的目的，是为了保证第5标段无论如何也不会被指派给B公司，第1标段和第2标段无论如何也不会被指派给C公司。 3.3超过N家公司符合投标要求 上节案例中，业主评标委员会认定A、B、C、D、E和F六家公司进入最终短名单。假设F在五个标段的报价分别为2789、3333、2765、2709、2987美元。此时，该价格矩阵是一个矩阵，为了应用匈牙利算法，在矩阵右侧加上一列0，可得一个矩阵。经计算，E公司未能中标，最终可得最优投标价总和13622万美元。 4结语 本文介绍以匈牙利算法在大型项目分段招标中的应用，并对解决几种实际应用中遇到的特殊问题进行讨论。该方法具有很强的实用性，可以应对某个投标人可以中标两个以上标段、某个投标人只在某些标段报价、超过N家公司符合投标要求等实际特殊情况。本文可为大型项目分段招标提供一定的理论和实践参考。 需要强调的是，业主使用分段招标的目的是为了项目能够以最低的成本顺利实施。例如在输电线路项目招标时，由于各标段同时开工建设，可以确保项目整体以最低的成本实施并在规定工期完工。但是，过分强调以匈牙利算法为基础的项目总体最低价中标的局限性在于，并不能保证投标人的履约能力达到业主要求。例如部分公司为了中标恶意报出低价，这对以完成项目整体为目标的输电线路项目、石油和天然气管道项目、铁路和公路项目等造成极大的项目整体风险。业主评标委员会在评价过程中，除了考察价格因素外，还需要对投标人的财务状况、以往完工业绩、在执行项目履约情况等情况进行严格考查，对投标人的项目履约能力进行定量评价，结合总体最低价中标规则，才能选择出能够完成项目的最佳投标人。 参考文献： 1KuhnHW.TheHungarianmethodfortheassignmentproblemJ.Navalresearchlogisticsquarterly,1955，2（1-2）：83-97. 2张新辉.任务数多于人数的指派问题J.运筹与管理，1997，6（3）：20-25. 3白国仲，毛经