Research and Implementation of Hungarian Method Based on the Structure Index Reduction for DAE Systems
Research and Implementation of Hungarian Method Based on the Structure Index Reduction for DAE Systems
复制标题
DOI：
10.1260/1748-3018.8.2.219
复制
发表时间：
2014-06
影响因子：
0.9
通讯作者：
Yan Zeng;Xuesong Wu;Jianwen Cao
中科院分区：
文献类型：
--
作者：
Yan Zeng;Xuesong Wu;Jianwen Cao
匈牙利法是解决分配问题的经典方法。它还可以广泛应用于其他问题，例如匹配问题。本文基于组合松弛理论，研究了结构指数约简法在求解高指数微分方程中的应用。组合松弛理论将复杂的数学问题转化为二分图的匹配问题。在此理论的基础上，本文提出了匈牙利法的主要思想，并提出了匈牙利法的三种实现方案。最后，通过运行一组实验来比较三种实现的时间性能。
Hungarian method is a classical method for solving assignment problems. It also can be widely used in other problems, such as matching problem. This paper researches its application on using structural index reduction method to solve high-index DAEs, based on the combinatorial relaxation theory. Combinatorial relaxation theory converts the complex mathematical problem to the matching problem of bipartite graph. Based on this theory this paper presents the main idea of Hungarian method and puts up three implementations for Hungarian method. At last, it compares the time performance of the three implementations by running a set of experiments.