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

22/09/2017

USMENI ISPITI-oktobarski rok
23.09.2017. 9:00 h (sala 105)
24.09.2017. 9:00 h (sala 103)
25.09.2017. 8:00 h (amfiteatar B103)
Raspored polaganja usmenog ispita za 25.09.2017. (azbučno)
A-M 8:00 h; N-R 9:00 h; S-Š 10:00 h

07/09/2017

VAŽNO OBAVEŠTENJE
Promena termina usmenog ispita u oktobarskom ispitnom roku. Nove termine kao i prijavni formular možete videti ovde. Prijava je OBAVEZNA. Rok za prijavljivanje je 21.9.2017 do 20h.

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.

08/06/2017

Ostvareni broj poena na aktivnosti u toku semestra možete videti ovde.
Uvid u poene će biti organizovan u petak, 9. juna od 12-13h u kancelariji 309a.

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.