分配問題

Rainer+Burkard

自19世紀20年代起，在研究匹配問題中產生的組合數學思想提出以來，出現了很多關于分配問題的研究成果，使得我們可以不使用計算機就可以輕松地解決現實問題。匈牙利算法與其他一些整數線性規(guī)劃中的基礎性研究成果，催生了一個新的研究領域，即組合優(yōu)化。在過去的50多年中，數百名研究人員對分配問題、線性變化和二次分配問題的研究，促進了組合優(yōu)化的發(fā)展。本書將介紹分配問題中已有的研究成果，討論理論細節(jié)、算法思想與大量分配問題的實際發(fā)展，以期使讀者對于分配問題有一個較為清晰的理解。

全書由10章組成：1.引言。分配問題的概念及其數學表達，給出了線性分配問題、二次分配問題與多指數分配問題的總體概況，提出了針對分配問題的研究路線；2.理論基礎。詳細闡釋了分配問題中的理論基礎知識，包括全匹配的合并定律及其存在性與分配多面體，如分配多面體的雙隨機矩陣的多面體，即伯克霍夫多面體；3.二分匹配算法。本章介紹了在基數匹配中占據重要地位的二分匹配，給出了用于尋找最大基數匹配的標記法與HopcroftKarp算法及其改進方法的思想，介紹了凸二分圖匹配算法及其應用，討論了最大匹配與矩陣算法和二分隨機圖中的最優(yōu)匹配問題，并介紹了最大匹配問題的應用實施過程；4.線性總和分配問題：串行算法。提出了在線性編程與組合優(yōu)化中最著名的問題，即線性求和分配問題，詳細介紹了其研究背景及成果，主要討論了幾種線性總和分配問題中的串行算法及其性能分析，簡要介紹了在該分配問題中的并行算法；5.線性求和分配問題的進一步研究成果；6.其他類型的線性分配問題。主要介紹了應用瓶頸對象函數的分配問題，提出了代數分配問題、k項求和分配問題、平衡分配問題、字典瓶頸分配問題和逆向分配問題；7.二次分配問題：表述與約束。介紹了二次分配問題的表述，給出了幾種公式化方法與二分對象函數公式進行了線性化表示，討論了GilmoreLawler約束及還原方法、特征值約束和半定規(guī)劃編程約束及凸二次規(guī)劃編程約束；8.二次分配問題：算法。介紹了基于Bender分解、分支約束與分支切割的精確算法，及幾種啟發(fā)式算法，給出了計算機代碼，提出了一些簡單和困難的特殊案例；9.其他類型的二次分配問題；10.多指數分配問題。介紹了經典的三指數分配問題模型：軸向模型與平面模型，提出了當前研究的多指數分配問題。

本書中提供了以練習形式給出的算例，便于讀者自學與深入理解算法內涵，并在相應的網頁上提供的小程序供讀者進行測試與學習，使讀者從概念到實際發(fā)展方面對分配問題有一個綜合的認識。

本書適合從事離散數學、信息論、編碼理論和計算機科學等專業(yè)的高年級碩士研究生或博士研究生閱讀和參考，亦可作為對分配問題、組合優(yōu)化研究感興趣的其他專業(yè)研究人員和教授的參考書。

張進興，碩士研究生

（中國科學院空間科學與應用研究中心）endprint