Комбинаторное моделирование и исследование операций

1.       

Название дисциплины

Комбинаторное  моделирование и исследование операций

2.       

Курс обучения

специальность

3, специальность Математика и информационные технологии

3.       

Семестр обучения

5

4.       

Количество кредитов

2

5.       

Ф.И.О. лектора

Бузулуцкая Анна Николаевна

6.       

Цели изучения дисциплины

Изучение основных методов решения экстремальных задач теории графов и задач линейного программирования.  Повышение уровня профессиональной компетенции в решении проблем оптимизации. Дальнейшее формирование у студентов навыков абстрактного математического мышления и умения применять его в конкретных задачах, повышение их математической культуры.

В результате изучения студент должен уметь:

уметь:

применять  теорию графов для решения практических задач;

составлять  сетевые модели;

пользоваться методами динамического программирования

7.       

Пререквизиты

Математический анализ

Алгебра и теория чисел

Методы оптимизации

8.       

Содержание дисциплины

История возникновения экстремальных задач теории графов. ЗЗадача о построении остовного дерева минимального веса. Алгоритм Прима, его корректность. Алгоритм Краскала и его корректность. Ориентированные графы. Алгоритмы Дийкстры и Флойда.

Задача о нахождении кратчайшего пути между двумя заданными вершинами. Алгоритм Дийкстры. Задача о поиске всех кратчайших путей в графе. Алгоритм Флойда. Нахождение циклов отрицательной длины. Сети, потоки, разрезы. Теорема Форда–Фалкерсона (критерий максимальности потока). Задача о нахождении допустимого потока максимальной мощности. Алгоритм Форда–Фалкерсона. Задача о построении потока минимальной стоимости. Алгоритм Басакера–Гоуэна для построения потока минимальной стоимости среди потоков заданной мощности. Задача коммивояжера. Алгоритм Литтла. Гамильтоновы циклы. Метод ветвей и границ. Календарное планирование. Постановка задачи, основные этапы решения. Построение сетевой модели, ранжирование, нахождение критических путей. Построение календарного графика работ и распределения трудовых ресурсов. Оптимизация календарного графика.

Динамическое программирование: основные понятия и алгоритмы. Решение задачи коммивояжера методами динамического программирования. Задача о распределении ресурсов.

9.       

Рекомендуемая литература

1. Бахтин В.И., Ковален ок А.П., Лебедев А.В., Лысенко Ю.В. Исследование операций. – Минск, БГУ, 2003

2. Майника Э. Алгоритмы оптимизации на сетях и графах. 1977.

3. Басакер P., Саати Т. Конечные графы и сети.  1974.

10.   

Методы преподавания

Лекции, практические занятия, УИРС

11.   

Язык обучения

Русский

12.   

Условия (требования), текущий контроль

контрольные работы.

13.   

Форма аттестации

Зачет