分配问题

Rainer+Burkard

自19世纪20年代起，在研究匹配问题中产生的组合数学思想提出以来，出现了很多关于分配问题的研究成果，使得我们可以不使用计算机就可以轻松地解决现实问题。匈牙利算法与其他一些整数线性规划中的基础性研究成果，催生了一个新的研究领域，即组合优化。在过去的50多年中，数百名研究人员对分配问题、线性变化和二次分配问题的研究，促进了组合优化的发展。本书将介绍分配问题中已有的研究成果，讨论理论细节、算法思想与大量分配问题的实际发展，以期使读者对于分配问题有一个较为清晰的理解。

全书由10章组成：1.引言。分配问题的概念及其数学表达，给出了线性分配问题、二次分配问题与多指数分配问题的总体概况，提出了针对分配问题的研究路线；2.理论基础。详细阐释了分配问题中的理论基础知识，包括全匹配的合并定律及其存在性与分配多面体，如分配多面体的双随机矩阵的多面体，即伯克霍夫多面体；3.二分匹配算法。本章介绍了在基数匹配中占据重要地位的二分匹配，给出了用于寻找最大基数匹配的标记法与HopcroftKarp算法及其改进方法的思想，介绍了凸二分图匹配算法及其应用，讨论了最大匹配与矩阵算法和二分随机图中的最优匹配问题，并介绍了最大匹配问题的应用实施过程；4.线性总和分配问题：串行算法。提出了在线性编程与组合优化中最著名的问题，即线性求和分配问题，详细介绍了其研究背景及成果，主要讨论了几种线性总和分配问题中的串行算法及其性能分析，简要介绍了在该分配问题中的并行算法；5.线性求和分配问题的进一步研究成果；6.其他类型的线性分配问题。主要介绍了应用瓶颈对象函数的分配问题，提出了代数分配问题、k项求和分配问题、平衡分配问题、字典瓶颈分配问题和逆向分配问题；7.二次分配问题：表述与约束。介绍了二次分配问题的表述，给出了几种公式化方法与二分对象函数公式进行了线性化表示，讨论了GilmoreLawler约束及还原方法、特征值约束和半定规划编程约束及凸二次规划编程约束；8.二次分配问题：算法。介绍了基于Bender分解、分支约束与分支切割的精确算法，及几种启发式算法，给出了计算机代码，提出了一些简单和困难的特殊案例；9.其他类型的二次分配问题；10.多指数分配问题。介绍了经典的三指数分配问题模型：轴向模型与平面模型，提出了当前研究的多指数分配问题。

本书中提供了以练习形式给出的算例，便于读者自学与深入理解算法内涵，并在相应的网页上提供的小程序供读者进行测试与学习，使读者从概念到实际发展方面对分配问题有一个综合的认识。

本书适合从事离散数学、信息论、编码理论和计算机科学等专业的高年级硕士研究生或博士研究生阅读和参考，亦可作为对分配问题、组合优化研究感兴趣的其他专业研究人员和教授的参考书。

张进兴，硕士研究生

（中国科学院空间科学与应用研究中心）endprint