Modifikované úlohy čínského listonoše - experimenty

Název práce: Modifikované úlohy čínského listonoše - experimenty
Autor(ka) práce: Jelínek, Tomáš
Typ práce: Diplomová práce
Vedoucí práce: Fábry, Jan
Oponenti práce: Pelikán, Jan
Jazyk práce: Česky
Abstrakt:
Diplomová práce popisuje modifikované úlohy čínského listonoše. Úlohy jsou řešeny pomocí (smíšeného) celočíselného lineárního programování. Modifikované úlohy i použitá metoda řešení (celočíselné programování) patří minimálně do NP složitých úloh. Práce analyzuje, porovnává a odhaduje výpočetní složitost jednotlivých modelů. Z této analýzy je vyvozena použitelnost (tj. řešitelnost v rozumnén čase) modelů pro řešení reálných úloh. Modely se primárně zaměřují na úlohy z městského prostředí, lze je tak aplikovat na problémy jako je optimalizace svozu komunálního odpadu nebo údržby silnic. Pro potřeby práce je naprogramován generátor grafů a zadání úloh.
Klíčová slova: výpočetní složitost; celočíselné lineární programování; úloha čínského listonoše
Název práce: Modified Chinese Postman Problems - Experiments
Autor(ka) práce: Jelínek, Tomáš
Typ práce: Diploma thesis
Vedoucí práce: Fábry, Jan
Oponenti práce: Pelikán, Jan
Jazyk práce: Česky
Abstrakt:
This master's thesis describes modified Chinese Postman Problems. These Problems are solved by (mixed) integer linear programming. The modified problems and also used approach (integer programming) belong at least to the NP complexity class. The thesis analyzes, compares and estimates computational complexity of each model. Based on this analysis, usability of described models for solving real-life problems is deduced. The models are focused on problems in urban environment. Therefore, it is possible to apply these models on problems like optimization of a waste collection or road maintenance. Graph and problem generator is programmed for purposes of this thesis.
Klíčová slova: Chinese postman problem; computational complexity; mixed integer programming

Informace o studiu

Studijní program / obor: Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum
Typ studijního programu: Magisterský studijní program
Přidělovaná hodnost: Ing.
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: 5. 10. 2010
Datum podání práce: 5. 5. 2011
Datum obhajoby: 6. 2. 2013
Identifikátor v systému InSIS: https://insis.vse.cz/zp/27771/podrobnosti

Soubory ke stažení

    Poslední aktualizace: