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