Úloha o batohu

• Název práce v češtině: Úloha o batohu
• Název v anglickém jazyce: A knapsack problem
• Klíčová slova: celočíselné programování, optimální řešení, úloha batohu
• Klíčová slova anglicky: integer programming, optimal solution, A knapsack problem
• Akademický rok vypsání: 2017/2018
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra pravděpodobnosti a matematické statistiky (32-KPMS)
• Vedoucí / školitel: doc. RNDr. Ing. Miloš Kopa, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.10.2017
• Datum zadání: 05.10.2017
• Datum potvrzení stud. oddělením: 15.12.2017
• Datum a čas obhajoby: 27.06.2018 08:00
• Datum odevzdání elektronické podoby: 17.05.2018
• Datum odevzdání tištěné podoby: 18.05.2018
• Datum proběhlé obhajoby: 27.06.2018
• Oponenti: doc. RNDr. Petr Lachout, CSc.

Zásady pro vypracování

Student(ka) se seznámí s úlohami celočíselného programování. Zaměří se na různé formulace úlohy o batohu. Souhrně popíše algoritmy na řešení těchto úloh. Na praktické ukázce demonstruje výhody i nevýhody těchto algoritmů.

Seznam odborné literatury

[1] CH. H. Papadimitriou, K. Steiglitz: Combinatorial optimization : algorithms and complexity, Dover Publications, Mineola New York, 1998.
[2] L. A. Wolsey: Integer programming, John Wiley & Sons, New York, 1998.
[3] W. J. Cook et al.: Combinatorial optimization, John Wiley & Sons, New York, 1998.
[4] R. von Randow: Integer programming and related areas, Berlin, Springer - Verlag, 1985.
[5] Balas, E., Zemel, E.: Solving large zero-one knapsack problems, Operation Research, (1980) 28, pp. 1130-1154