Kombinatorna optimizacija i metaheuristike
Studijski program: Poslovna analitika, MEN i organizacija, SI i RN
Nastavnik: Milan J. Stanojević, Mirjana M. Čangalović (Bisera Š. Andrić Gušavac)
Status predmeta: izborni
Broj ESPB: 6
Cilj predmeta
Upoznavanje studenata sa nekim od problema i modela kombinatorne optimizacije, kao i sa savremenim metaheurističkim metodologijama za njihovo rešavanje.
Ishod predmeta
Studenti se osposobljavaju za samostalno modeliranje i rešavanje realnih kombinatornih problema primenom savremenih metaheurističkih metodologija uz pomoć odgovajućih računarskih softvera.
Sadržaj predmeta
Teorijska nastava: Računska složenost problema i algoritama. Celobrojno programiranje. Metoda grananja i ograničavanja. Metoda odsecajućih ravni. Optimalni putevi i stabla u grafu: problem najkraćeg puta, problem minimalnog razapinjućeg stabla. Protoci u mreži – problem maksimalnog protoka. Problem trgovačkog putnika. Heuristički pristup rešavanju optimizacionih problema. Pojam heuristike. Osnovni principi metaheurističkih metodologija. Pojam okoline. Princip lokalnog pretraživanja. Osnovne metaheurističke metodologije: simulirano kaljenje, tabu pretraživanje, metoda promenljiih okolina, genetski algoritmi. Primeri primene metaheuristika na rešavanje nekih problema kombinatorne optimizacije: problema ranca, trgovačkog putnika, kao i nekih realnih problema raspoređivanja.
Praktična nastava: Primena postojećih softverskih paketa (CONCORD, GENOCOP) za heurističko rešavanje problema kombinatorne optimizacije.
Literatura
1. Cvetković D., Čangalović M., Dugošija Đ., Kovačević Vujčić V., Simić S., Vuleta J., Kombinatorna ptimizacija, matematička teorija i algoritmi, DOPIS, Beograd, 1996.
2. Cook W.J., at al, Combinatorial optimization, John Wiley&Sons, Inc., 1998.
3. Gendreau M., Jean-Yves P. (Ed.), Handbook of Heuristics, Springer, 2010.
4. Günther Z., Roland B., Michael B., Metaheuristic Search Concepts, Springer, 2010.
5. Vujošević M., Metode optimizacije u inženjerskom menadžmentu, AINS,FON, Beograd, 2012
Metode izvođenja nastave: Mentorski rad i/ili klasičan način uz primenu računara.
| Predispitne obaveze | poena | Završni ispit | poena |
|---|---|---|---|
| aktivnost u toku nastave | 30 | usmeni ispit | 70 |