Kombinatorna optimizacija

Studijski program: ISiT, OM, I nivo- osnovne akademske studije

Nastavnici: Mirjana Čangalović, Vera Vujčić, Nenad Mladenović

Broj ESPB: 5

Uslov: položeni Operaciona istraživanja 1 i 2

Cilj predmeta

Upoznavanje studenata sa osnovnim problemima, modelima i metodama kombinatorne optimizacije

Ishod predmeta

Studenti se osposobljavaju za samostalno modeliranje i rešavanje realnih kombinatornih problema uz primenu odgovarajućih računarskih softvera

Sadržaj predmeta

Teorijska nastava: 1. Računska složenost problema i algoritama. Klase P i NP. 2. Heurističko rešavanje problema. Specijalne i opšte heuristike. 3. Celobrojno programiranje. Celobrojni poliedri. 4. Metode grananja i ograničavanja. Metode odsecanje. 5. Metode grananja i odsecanja. Implicitna enumeracija. 6. Ekstremni putevi u grafovima. 7. Problem minimalnog razapinjućeg stabla u grafu. 8. Problem nalaženja maksimalnog protoka u mreži. 9. Problem određivanja protoka sa minimalnom cenom. 10. Problem optimalnog sparivanja u bipartitnom i proizvoljnom grafu. 11. Problem optimalnog sparivanja u težinskom grafu. 12. Hamiltonovi putevi u grafu . Problem trgovačkog putnika i njegove relaksacije. 13. Heuristike za rešavanje problema trgovačkog putnika. 14. Problem optimalnog bojenja grafa i neke njegove primene.15. Heuristike za optimalno bojenje grafa

Praktična nastava: Primena softverskih paketa BARON, CPLEX i CONCORD na rešavanje celobrojnih modela problema kombinatorne optimizacije koji se izučavaju u okviru teorijske nastave.

Literatura

Osnovna literatura:

1. Cvetković D., Čangalović M., Dugošija Đ., Kovačević-Vujčić V., Simić S., Vuleta J., Kombinatorna optimizacija, Matematička teorija i algoritmi, DOPIS, Beograd, 1996.
Dopunska literatura:

1. Cook W.J. at al., Combinatorial optimization, John Wiley&Sons,Inc., 1998.

2. Schrijver A., Combinatorial Optimization, Vol. A,B,C, Springer, 2003.

 

Metode izvođenja nastave: mentorski rad

Ocena znanja (maksimalni broj poena 100)
Predispitne obaveze poena Završni ispit poena
Aktivnost u toku predavanja 30 Pismeni ispit 50*
Seminar(i) 70* Usmeni ispit 50
* znači alternativni način polaganja.

Novosti

26/04/2018

Rezultate prvog pismenog kolokvijuma iz OI2 možete videti ovde. Uvid u radove će biti organizovan u četvrtak, 03.05.2018 od 12:00 do 13:00 časova u kabinetu 309a.

18/04/2018

Studentski tim FON-a Andrijana Bačević, Nemanja Vilimonović, Igor Dabić, Jakov Petrović i Darko Damnjanović su osvojili četvrto mesto u finalu svetskog takmičenja INFORMS OR & Analytics Student Team Competition. Mentori tima su: prof. dr Dragana Makajić-Nikolić, prof. dr Marija Kuzmanović i prof. dr Gordana Savić i Dušan Džamić. U finalu su učestvovali 8 od 28 timova iz celog sveta koji su uspeli da ispune kriterijume takmičenja i predlože rešenje problema koji je zadala kompanija Principal®, a odnosi se na optimizaciju portfolija nad podacima velikih dimenzija. Prezentacija rešenja je održana u okviru prestižne konferencije Conference on Business Analytics and Operations Research u Baltimoru, Merilend, SAD, od 15. do 17. aprila 2018. godine.

01/02/2018

Obaveštavamo studente da je na strani materijal za nastavu iz OI1 postavljena skripta za pitanje Metoda grananja i ograničavanja.

13/06/2017

Za pismeni ispit iz OI2 dolaze 4. zadatka iz sledećih oblasti: mrežno planiranje, matrične igre, upravljanje zalihama, dinamičko programiranje i redovi čekanja.

01/06/2015

Primere zadataka sa drugog kolokvijuma iz OI2 od nekoliko prošlih generacija možete preuzeti ovde. Za pismeni kolokvijum dolaze zadaci iz sledećih oblasti: matrične igre, upravljanje zalihama i redovi čekanja.

10/04/2015

Primer zadataka iz MP i DP za 1. kolokvijum iz OI2 možete preuzeti ovde.

Master studije

Prezentaciju smera poslovna analitika možete pogledati na ovoj adresi www.pa.fon.bg.ac.rs.