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

17/11/2017

Detaljan raspored polaganja prvog pismenog kolokvijuma iz OI1 možete videti ovde.

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.