Исследование операций

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс обязательный

Когда читается:

3-й курс, 1-3 модуль

Преподаватель

Бацына Екатерина Константиновна

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• Уметь строить и анализировать математические модели практических оптимизационных и теоретико игровых задач

Планируемые результаты обучения

• Знать основные определения и теоремы выпуклой оптимизации
• Строит математические модели задач линейного программирования, знает их алгоритмы решения
• Знает алгоритмы решения транспортных задач
• Строит Парето-оптимальные решения
• Знает алгоритмы сетевой оптимизации
• Решает целочисленные задачи линейного программирования
• Решает матричные игры в чистых и смешанных стратегиях

Содержание учебной дисциплины

• Выпуклая оптимизация
  Элементы выпуклого анализа. Выпуклые множества. Крайние точки множества. Выпуклые функции. Критерии выпуклости и строгой выпуклости дифференцируемых и дважды дифференцируемых функций. Оптимальные точки выпуклых функций и их свойства. Принцип Лагранжа в задачах с ограничениями типа равенств и неравенств. Принцип Лагранжа в задачах выпуклого программирования. Условие Слейтера. Седловая точка функции Лагранжа. Теорема Куна-Таккера в форме седловой точки. Теорема Куна-Таккера в дифференциальной форме. Теорема Куна-Таккера в задаче выпуклого программирования с линейными ограничениями.
• Линейная оптимизация
  Каноническая форма задачи линейного программирования. Базисные и небазисные переменные. Допустимые базисные точки. Симплекс-алгоритм. Экспоненциальная сложность алгоритма. Двойственность. Основная теорема двойственности как следствие условий Куна-Таккера. Принцип дополняющей нежесткости. Анализ чувствительности структуры решения к возмущению параметров задачи. Задача оптимального плана производства. Теневые цены.
• Транспортные модели
  Сбалансированная и несбалансированная транспортная модель. Транспортная задача с промежуточными пунктами. Задача, двойственная к транспортной задаче. Алгоритм потенциалов. Задача о назначениях. Венгерский метод.
• Сетевые модели
  Основные определения. Алгоритм нахождения минимального остова. Алгоритм нахождения кратчайшего пути. Алгоритм нахождения максимального потока. Поток наименьшей стоимости. Методы сетевого анализа (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