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

Komentari studenata

Program sam odabrala jer sam želela da od najboljih naučim kako da teorijsko znanje primenim u praksi. Prilikom odabira presudilo je to što se na predavanjima koriste softveri koje koriste mnoge ko…

Novosti

01/12/2014

Literatura za učenje ispita Poslovna analitika možete preuzeti ovde.