Original title: Kavdratický přiřazovací problém a jeho řešení
Translated title: The quadratic assignment problem and its solution
Authors: Nováčková, Monika ; Jablonský, Josef (advisor) ; Fábry, Jan (referee)
Document type: Bachelor's theses
Year: 2009
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
Kvadratický přiřazovací problém je jednou z nejsložitějších úloh kombinatorické optimalizace. Jedná se o velmi rozsáhlou rozhodovací úlohu třídy NP-complete. Poprvé tento problém představili v roce 1957 Koopmans a Beckman. Od té doby byly zkoumány různé metody řešení tohoto problému. Jedná se o nejrůznější exaktní ale i heuristické algoritmy. V této práci je podrobněji popsán jeden z exaktních algoritmů tzv. metoda větví a mezí (branch and bound algorithm) založená na Gilmore Lawlerově způsobu výpočtu dolních mezí. Dále jsou zde popsány některé aplikační oblasti kvadratického přiřazovacího problému. Jedná se například o úlohu, jak nejlépe rozmístit jednotlivé kliniky a zařízení v areálu nemocnice tak, aby pacienti celkově během svého pobytu v nemocnici museli překonat, co nejmenší vzdálenost mezi jednotlivými klinikami, nebo jak uspořádat jednotlivé komponenty v počítači na desce motherboard tak, aby celkový součin množství signálů a vzdálenosti, kterou musí data překonat, byl co nejmenší. The QAP (quadratic assignment problem) is one of the most involved combinatorial optimization problems. This formidable decision problem is included in the complexity class called NP-complete. The QAP has been first time introduced by Koopmans and Beckman in year 1957. Since then the various methods for solving this problem have been investigated. The studied methods include both: exact algorithms and heuristic methods. Some of them will be shortly described in this paper. One of them, the branch and bound algorithm based on Gilmore Lawler bounds will be analyzed in detail. View applications of this problem will be also discussed. Described applications include the problem of localization of the departments or clinics in a hospital in order to minimize the total traveling distance among clinics by patients. Another described example of application of this problem is the task how to place the components on a computer motherboard optimally.
Keywords: branch and bound algorithm; combinatorial optimization; Gilmore-Lawler bound; quadratic assignment problem; Gilmore-Lawlerovi dolní meze; kombinatorická optimalizace; kvadratický přiřazovací problém; metoda větví a mezí

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/24781

Permalink: http://www.nusl.cz/ntk/nusl-76589


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Bachelor's theses