Kavdratický přiřazovací problém a jeho řešení
| Název práce: | Kavdratický přiřazovací problém a jeho řešení |
|---|---|
| Autor(ka) práce: | Nováčková, Monika |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Jablonský, Josef |
| Oponenti práce: | Fábry, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | 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ší. |
| Klíčová slova: | Gilmore-Lawlerovi dolní meze; kvadratický přiřazovací problém; metoda větví a mezí; kombinatorická optimalizace |
| Název práce: | The quadratic assignment problem and its solution |
|---|---|
| Autor(ka) práce: | Nováčková, Monika |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Jablonský, Josef |
| Oponenti práce: | Fábry, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | quadratic assignment problem; Gilmore-Lawler bound; branch and bound algorithm; combinatorial optimization |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Typ studijního programu: | Bakalářský studijní program |
| Přidělovaná hodnost: | Bc. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 4. 11. 2009 |
|---|---|
| Datum podání práce: | 15. 5. 2010 |
| Datum obhajoby: | 7. 9. 2010 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/22677/podrobnosti |