Студијски програм: ИСиТ, OM, I ниво- основне академске студије

Наставници: Мирјана Чангаловић, Вера Вујчић, Ненад Младеновић

Број ЕСПБ: 5

Услов: положени Операциона истраживања 1 и 2

Циљ предмета

Упознавање студената са основним проблемима, моделима и методама комбинаторне оптимизације

Исход предмета

Студенти се оспособљавају за самостално моделирање и решавање реалних комбинаторних проблема уз примену одговарајућих рачунарских софтвера

Садржај предмета

Теоријска настава: 1. Рачунска сложеност проблема и алгоритама. Класе P и NP. 2. Хеуристичко решавање проблема. Специјалне и опште хеуристике. 3. Целобројно програмирање. Целобројни полиедри. 4. Методе гранања и ограничавања. Методе одсецање. 5. Методе гранања и одсецања. Имплицитна енумерација. 6. Екстремни путеви у графовима. 7. Проблем минималног разапињућег стабла у графу. 8. Проблем налажења максималног протока у мрежи. 9. Проблем одређивања протока са минималном ценом. 10. Проблем оптималног спаривања у бипартитном и произвољном графу. 11. Проблем оптималног спаривања у тежинском графу. 12. Хамилтонови путеви у графу . Проблем трговачког путника и његове релаксације. 13. Хеуристике за решавање проблема трговачког путника. 14. Проблем оптималног бојења графа и неке његове примене.15. Хеуристике за оптимално бојење графа

Практична настава: Примена софтверских пакета BARON, CPLEX и CONCORD на решавање целобројних модела проблема комбинаторне оптимизације који се изучавају у оквиру теоријске наставе.

Литература

Основна литература:

1. Цветковић Д., Чангаловић М., Дугошија Ђ., Ковачевић-Вујчић В., Симић С., Вулета Ј., Комбинаторна оптимизација, Математичка теорија и алгоритми, ДОПИС, Београд, 1996.

Допунска литература:

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

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

 

Методе извођења наставе: менторски рад

Оцена знања (максимални број поена 100)
Предиспитне обавезе	поена	Завршни испит	поена
Активност у току предавања	30	Писмени испит	50*
Семинар(и)	70*	Усмени испит	50
* значи алтернативни начин полагања.