基于匈牙利算法的城市商业网点最优布设问题研究

郑少妹

摘 要：本文依据城市商业网点规划理论，结合实例，基于匈牙利算法并利用WinQSB2.0软件对城市商业网点最优选择问题进行仿真模拟计算。本文的研究为解决城市商业网点选址问题提供了一种全新的科学计算方法，具有较为重要的理论和应用价值。

关键词：匈牙利算法；商业网点；模拟仿真；最优选择

一、引 言

从可持续发展的视角确定城市商业网点的规模与数量、空间分布和业态结构，满足消费者需求，培育城市综合竞争力，最终实现城市商贸经济可持续发展目标。不同商业网点布局和组合决定了该区域商贸业的繁荣程度与可持续发展能力。基于城市商贸特色及内涵，运用匈牙利算法和WinQSB2.0软件对城市商业网点最优选择问题进行仿真模拟计算。本文的研究为解决城市商业网点选址问题提供了一种新的科学计算方法，具有重要的理论和应用价值。

二、城市商业网点规划理论概述

为充分体现“以人为本”理念，通过信息化，规模化发展，利用现代网络技术对传统行业加以改造，大幅度提升商业服务效率和质量，改善商业生态环境，促进商贸流通体系的发展。城市商业网点的空间布设，要求制定出符合城市发展的商业网点规划，其城市商业网点规划的主要理论基础有：

（一）区位理论。 （1）市场竞争区位理论。市场竞争区位理论于1935年由瑞典经济学家帕兰德提出。他从市场的角度来探讨区位的形成与变化，发现人口的分布变化与新产品、新技术的引进都可以打破原有的市场平衡，从而改变市场与产业的分布状况。（2）贸易边界理论。贸易边界理论认为，任何商业企业的竞争力主要取决于销售量，取决于市场区域的大小与消费者的数量。两个企业的贸易边界由双方的价格和成本之比决定，成本或价格相同，贸易边界在两个企业的中央；成本或价格不同，市场边界则偏向成本或价格高的一方。（3）中心地理论。中心地理论认为，向周边区域居住的消费者所供应物品和劳务的场所称为中心点，而消费者到中心点购买商品或服务的成本会随离中心点的距离增大而增加。当距离大到一定的程度，消费者就会转而向其他距离较近的中心点去购买，这个最大距离称之为市场边界。（4）市场区位理论。市场区位理认为，市场完全是经济力量内部作用的结果。因产品价格随距离的增大而增加，而消费者的购买规模与数量却随价格的增加而减少，直至到0。市场区位理论，使得土地的使用更高效与合理。

（二）商圈理论。商圈，指店铺以其所在地点为中心，沿着相应的方向和距离扩展，即那些优先选择到本店来消费的顾客分布的区域范围。一个商业企业的服务空间范围具有一定限度，才使得在该商业企业周边存在一个以其为中心的区域，该中心区域在零售学中，就被称之为商圈。科学预测未来商圈范围的变化，对商业网点布设规划工作有着重要的作用。

（三）集聚效益理论。俗语：店多成市。通过商店集聚、客流集聚以及各种经济活动的集聚，从而产生集聚经济效益。在商业网点规划方面，集聚经济效益其具体表现为：服务或商店设施的集聚；人流与客流的集聚可以产生市场规模效应；集聚可以促进商店的专业化分工而提高经营效率；集聚可以提供更加广泛全面的辅助设施以及公共服务设施的完善；集聚也可激发有才能的企业家集聚等，从而产生吸引与辐射效应等。当然，集聚形态与地理位置的不同组合，则会形成不同的城市商业布局形态。

（四）级差地租理论。级差地租理论的基本要点：按城市土地级差地租的级别，商业布局分为城市中心区、社区和街区等若干等级。任何一个商业中心的核心区，总会被那些足以显示该商业中心最高等级的职能部门所占领。级差地租理论是通过商业房屋与市场土地的供需关系，即房租价格或土地价格的信号，推动商业布局的合理调整。

（五）提升生活价值与和谐理论。随着社会进步与经济发展，现代商业规划应包括城市功能、城市文化、城市历史和城市建筑风格等方面的内在和谐性。消费者不仅满足于物品的消费，而更多是关注对生活价值的体验，因此，就要求商业规划应满足多方面的和谐，如服务功能与多元化需求的和谐；消费者偏好与商业企业经营特色的和谐；等级体系与城市商业网络的和谐；地区文化与个性化建筑的和谐等，从而给消费者提供更加优质的综合服务。

三、匈牙利算法概述

（一） “指派问题”的数学模型：指派问题（assignment prob

lem）标准形式是：有个人和项工作，已知第个人做第项工作的费用为cij，i，j=1，2，…，n（cij可表示为成本、时间等），要求人与工作之间是一一对应的指派关系，使完成项工作总费用最少。

约束条件（1）表示每项工作必有且只有一个人去完成，约束条件（2）表示每个人必须完成且只须完成一项工作。

指派问题的可行解可用矩阵表示：

解矩阵的每行每列元素中都有且只有一个1，以满足约束条件。指派问题有个可行解。

从上述数学模型可知，指派问题是0-1整数规划的特殊情况，也是运输问题的特例，当然更是一个整数规划问题，因此指派问题可以用分枝定界法、表上作业法和隐枚举法求解。然而我们根据指派问题数学模型特点，寻找更加简便的计算方法，从而有效地减少计算量。1955年库恩（W.W.Kuhn）利用匈牙利数学家康尼格（D.k？nig）的关于矩阵中独立零元素的定理，提出了求解指派问题的匈牙利算法（Hungary algorithm）。

（二）匈牙利算法（Hungary algorithm）设计如下： （1）先对各行元素分别减去本行的最小元素，然后对各列也如此。此时，

中各行和各列都已出现元素，且没有负数。（2）确定

中的独立元素。（3）此时，需要确定能覆盖所有元素的最少直线数目的直线集合。可按下面步骤进行： ① 对没有○0的行打“√”； ② 在已打“√”的行中，对所在列打“√”； ③ 在已打“√”的列中；对○0所在行打“√”； ④ 重复②和③，直到再也不能找到可以打“√”的行或列为止； ⑤ 对没有打“√”的行画一横线，对打“√”的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。（4）在未被直线覆盖的元素中找出一个最小元素，对未被覆盖元素所在行中各元素都减去这一最小元素，这样势必会出现元素，但同时却又使已被直线覆盖的元素中出现负数，为了消除这些负数，只要对划了线的列的各元素都加上这一最小元素即可。 （5）返回步骤（2）确定中的独立元素，故可确定指派问题的最优指派方案。

四、算法应用与模拟仿真

本文将采用WinQSB2.0专用软件基于匈牙利算法对城市商业网点最优选择问题进行仿真模拟。

通过一系列评估，家具超市不能置于第三个网点，而计算机超市不能置于第四个网点，不同类别的商品投资到各商业网点的年利润（万元）预测值如下表1。该商业集团在该城市如何对商业网点做出最优选择才能使其年利润最大。

求解与模拟仿真步骤如下：

（1）输入数据。在选择数据输入格式时，选择Spreadsheet

Matrix Form则以电子表格形式输入价值系数矩阵，并点击菜单栏Edit→Node Names对目标和配置进行重命名如下图1所示：

2）选择Solve the Problem（只求出最优解）。如下图2所示：

（3）点击菜单栏Results→Graphic Solution，以网络图的形式显示结果。如下图3所示：

（4）最优决策方案。从求解结果可得，最优选择方案为：计算机超市设在地点1、服装超市设在地点2、食品超市设在地点3、电器超市设在地点4， 最大年利润为1350.00万元。

结束语：本文利用城市商业网点规划理论，通过实例，基于匈牙利算法并结合WinQSB2.0软件对城市商业网点最优选择的问题进行仿真模拟计算。为城市商业网点的布设问题提供了一种新的科学计算方法。然而，需要阐明的是，基于城市商业网点的布设问题的复杂性、不确定性以及人们认识能力的局限性。所以，城市商业网点布设问题的研究是一项复杂的系统工程，无论在理论上还是在方法技术等方面仍然需要展开系统的深入思考。

参考文献：

[1]刘星原.城市商业网点规划布局的若干问题探讨[J].北京工商大学学报，2007（04）：6-10

[2]李萍.城市商业网点规划理论框架的构建[J].现代商贸工业，2007（08）：39-40