1. |
Название дисциплины |
Комбинаторное моделирование и исследование операций |
2. |
Курс обучения специальность |
3, специальность Математика и информационные технологии |
3. |
Семестр обучения |
5 |
4. |
Количество кредитов
|
2 |
5. |
Ф.И.О. лектора |
Бузулуцкая Анна Николаевна |
6. |
Цели изучения дисциплины |
Изучение основных методов решения экстремальных задач теории графов и задач линейного программирования. Повышение уровня профессиональной компетенции в решении проблем оптимизации. Дальнейшее формирование у студентов навыков абстрактного математического мышления и умения применять его в конкретных задачах, повышение их математической культуры. В результате изучения студент должен уметь: уметь: применять теорию графов для решения практических задач; составлять сетевые модели; пользоваться методами динамического программирования |
7. |
Пререквизиты |
Математический анализ Алгебра и теория чисел Методы оптимизации |
8. |
Содержание дисциплины |
История возникновения экстремальных задач теории графов. ЗЗадача о построении остовного дерева минимального веса. Алгоритм Прима, его корректность. Алгоритм Краскала и его корректность. Ориентированные графы. Алгоритмы Дийкстры и Флойда. Задача о нахождении кратчайшего пути между двумя заданными вершинами. Алгоритм Дийкстры. Задача о поиске всех кратчайших путей в графе. Алгоритм Флойда. Нахождение циклов отрицательной длины. Сети, потоки, разрезы. Теорема Форда–Фалкерсона (критерий максимальности потока). Задача о нахождении допустимого потока максимальной мощности. Алгоритм Форда–Фалкерсона. Задача о построении потока минимальной стоимости. Алгоритм Басакера–Гоуэна для построения потока минимальной стоимости среди потоков заданной мощности. Задача коммивояжера. Алгоритм Литтла. Гамильтоновы циклы. Метод ветвей и границ. Календарное планирование. Постановка задачи, основные этапы решения. Построение сетевой модели, ранжирование, нахождение критических путей. Построение календарного графика работ и распределения трудовых ресурсов. Оптимизация календарного графика. Динамическое программирование: основные понятия и алгоритмы. Решение задачи коммивояжера методами динамического программирования. Задача о распределении ресурсов. |
9. |
Рекомендуемая литература |
1. Бахтин В.И., Ковален ок А.П., Лебедев А.В., Лысенко Ю.В. Исследование операций. – Минск, БГУ, 2003 2. Майника Э. Алгоритмы оптимизации на сетях и графах. 1977. 3. Басакер P., Саати Т. Конечные графы и сети. 1974. |
10. |
Методы преподавания |
Лекции, практические занятия, УИРС |
11. |
Язык обучения |
Русский |
12. |
Условия (требования), текущий контроль |
контрольные работы. |
13. |
Форма аттестации |
Зачет |