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
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. | |||