Бакалавриат
2020/2021
Исследование операций
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Когда читается:
3-й курс, 1-3 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Бацына Екатерина Константиновна
Язык:
русский
Кредиты:
6
Контактные часы:
100
Программа дисциплины
Аннотация
Дисциплина "Исследование операций" является одной из базовых фундаментальных дисциплин направления подготовки бакалавров "Прикладная математика и информатика". Изучаются критерии оптимальности в задачах выпуклой оптимизации и основные задачи и алгоритмы линейного программирования
Цель освоения дисциплины
- Уметь строить и анализировать математические модели практических оптимизационных и теоретико игровых задач
Планируемые результаты обучения
- Знать основные определения и теоремы выпуклой оптимизации
- Строит математические модели задач линейного программирования, знает их алгоритмы решения
- Знает алгоритмы решения транспортных задач
- Строит Парето-оптимальные решения
- Знает алгоритмы сетевой оптимизации
- Решает целочисленные задачи линейного программирования
- Решает матричные игры в чистых и смешанных стратегиях
Содержание учебной дисциплины
- Выпуклая оптимизацияЭлементы выпуклого анализа. Выпуклые множества. Крайние точки множества. Выпуклые функции. Критерии выпуклости и строгой выпуклости дифференцируемых и дважды дифференцируемых функций. Оптимальные точки выпуклых функций и их свойства. Принцип Лагранжа в задачах с ограничениями типа равенств и неравенств. Принцип Лагранжа в задачах выпуклого программирования. Условие Слейтера. Седловая точка функции Лагранжа. Теорема Куна-Таккера в форме седловой точки. Теорема Куна-Таккера в дифференциальной форме. Теорема Куна-Таккера в задаче выпуклого программирования с линейными ограничениями.
- Линейная оптимизацияКаноническая форма задачи линейного программирования. Базисные и небазисные переменные. Допустимые базисные точки. Симплекс-алгоритм. Экспоненциальная сложность алгоритма. Двойственность. Основная теорема двойственности как следствие условий Куна-Таккера. Принцип дополняющей нежесткости. Анализ чувствительности структуры решения к возмущению параметров задачи. Задача оптимального плана производства. Теневые цены.
- Транспортные моделиСбалансированная и несбалансированная транспортная модель. Транспортная задача с промежуточными пунктами. Задача, двойственная к транспортной задаче. Алгоритм потенциалов. Задача о назначениях. Венгерский метод.
- Сетевые моделиОсновные определения. Алгоритм нахождения минимального остова. Алгоритм нахождения кратчайшего пути. Алгоритм нахождения максимального потока. Поток наименьшей стоимости. Методы сетевого анализа (CPM, PERT, COST).
- Целочисленное линейное программированиеПроблемы дискретной оптимизации. Метод перебора. Метод ветвей и границ. Метод отсекающих плоскостей (Гомори). Задача о рюкзаке. Задача коммивояжера. Особенности двоичной оптимизации.
- Многокритериальная оптимизацияМодель Марковица формирования оптимального инвестиционного портфеля. Постановка задачи многокритериальной оптимизации. Доминируемые и недоминируемые альтернативы. Фронт Парето и множество Парето. Методы построения множества Парето: метод идеальной точки, метод свертки, метод приоритетов, метод уступок
- Основные понятия теории игрЭлементы игры. Стратегии игрока. Рандомизированный выбор и смешанные стратегии. Доминируемые и доминирующие стратегии. Равновесие по Нэшу. Существование равновесия по Нэшу в смешанных стратегиях.
Элементы контроля
- КонтрольнаяСтудент может выбрать, будет ли он сдавать экзамен или оценка за экзамен будет выставлена по промежуточной аттестации (накопленной оценке по проведенным элементам контроля). В случае выбора экзамена, он проводится в письменной форме. При невозможности офлайн проведения, экзамен проводится на платформе Zoom (https://zoom.us). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Zoom. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи до 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
- Контрольные
- КонтрольнаяСтудент может выбрать, будет ли он сдавать экзамен или оценка за экзамен будет выставлена по промежуточной аттестации (накопленной оценке по проведенным элементам контроля). В случае выбора экзамена, он проводится в письменной форме. При невозможности офлайн проведения, экзамен проводится на платформе Zoom (https://zoom.us). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Zoom. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи до 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
- Контрольные
- Работа на семинарских занятиях
- Работа на семинарских занятиях
Промежуточная аттестация
- Промежуточная аттестация (1 модуль)0.5 * Контрольная + 0.25 * Контрольные + 0.25 * Работа на семинарских занятиях
- Промежуточная аттестация (3 модуль)0.25 * Контрольная + 0.125 * Контрольные + 0.5 * Промежуточная аттестация (1 модуль) + 0.125 * Работа на семинарских занятиях
Список литературы
Рекомендуемая основная литература
- Карманов, В. Г. Математическое программирование [Электронный ресурс] : Учебное пособие / В. Г. Карманов. - 6-е изд., испр. - М. : ФИЗМАТЛИТ, 2008. - 264 с. - ISBN 978-5-9221-0983-3.
- Колемаев, В. А. Математические методы и модели исследования операций [Электронный ресурс] : учебник для студентов вузов, обучающихся по специальности 080116 «Математические методы в экономике» и другим экономическим специальностям / В. А. Колемаев; под ред. В. А. Колемаева. - М. : ЮНИТИ-ДАНА, 2012. - 592 с. - ISBN 978-5-238-01325-1.
- Математические методы и модели исследования операций / Шапкин А.С., Шапкин В.А. - М.:Дашков и К, 2016. - 400 с.: ISBN 978-5-394-02610-2
Рекомендуемая дополнительная литература
- Введение в исследование операций, пер. с англ. и ред. к.физ.-мат.н. А. А. Минько, 7-е изд., 912 с., Таха, Х. А., 2005