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

张祥 ZHANG Xiang；杨莉菲 YANG Li-fei

（国家电网中国电力技术装备有限公司，北京100052）

摘要：分段招标法输电线路项目、石油和天然气管道项目、铁路和公路项目具有广泛的应用。本文以某跨国输电线路项目招标为例，介绍以匈牙利算法为基础的分段招标法在大型项目招标中的应用，并在典型问题的基础上，对解决几种实际应用中遇到的特殊问题进行讨论。本文可为大型项目分段招标提供一定的理论和实践参考。

教育期刊网 http://www.jyqkw.com
关键词 ：分段招标；匈牙利算法；输电线路项目

中图分类号：U723.3 文献标识码：A 文章编号：1006-4311（2015）23-0145-02

作者简介：张祥（1983-），男，广西南宁人，经济师，博士，研究方向为工程项目管理。

0 引言

分段招标法在输电线路项目、石油和天然气管道项目、铁路和公路项目应用较广。此类项目投资较大且项目具有一定的复杂性，业主需确保项目分段实施过程的工期和质量满足项目本身要求，同时项目总投资最小，即各标段投标价格总和最小。

在分段招标时，假设N个投标人中标N个标段，每个投标人只能中标一个标段，则该问题可以转化为典型的指派问题。对于N个投标人N个标段，解决指派问题的最直接的方法是穷举法，但是该方法需要进行N的阶乘次比较，当N较大时，需要比较的次数呈几何倍数增长，基本不能适应实际计算应用需要。匈牙利算法的提出为解决此类问题提供了一个较为简单快速的方法。本文介绍匈牙利算法的基本步骤，以某跨国输电线路项目招标为例介绍 该方法在解决典型问题中的应用，并在典型问题的基础上，对解决几种特殊问题进行讨论。

1 问题的数学模型描述和匈牙利算法过程

1.1 问题描述

假设N个投标人分配N个标段，一个投标人只能分配一个标段，即一个标段只能分配给一个投标人，每个投标人在所有标段都有报价，需要解决的问题为如何分配标段，保证项目的投标价总和最小。

1.2 匈牙利算法过程

该方法应用于在给定的n×n价格矩阵寻找最佳分配结果。实施步骤如下：

步骤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家公司符合投标要求等实际特殊情况。本文可为大型项目分段招标提供一定的理论和实践参考。

需要强调的是，业主使用分段招标的目的是为了项目能够以最低的成本顺利实施。例如在输电线路项目招标时，由于各标段同时开工建设，可以确保项目整体以最低的成本实施并在规定工期完工。但是，过分强调以匈牙利算法为基础的项目总体最低价中标的局限性在于，并不能保证投标人的履约能力达到业主要求。例如部分公司为了中标恶意报出低价，这对以完成项目整体为目标的输电线路项目、石油和天然气管道项目、铁路和公路项目等造成极大的项目整体风险。业主评标委员会在评价过程中，除了考察价格因素外，还需要对投标人的财务状况、以往完工业绩、在执行项目履约情况等情况进行严格考查，对投标人的项目履约能力进行定量评价，结合总体最低价中标规则，才能选择出能够完成项目的最佳投标人。

教育期刊网 http://www.jyqkw.com
参考文献：

[1]Kuhn H W. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly, 1955，2（1-2）：83-97.

[2]张新辉.任务数多于人数的指派问题[J].运筹与管理，1997， 6（3）：20-25.

[3]白国仲，毛经中.C指派问题[J].系统工程理论与实践，2003，23（3）：107-111.