Методы анализа и оптимизации в дискретных задачах

2020/2021

Учебный год

RUS

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

4

Кредиты

Кто читает:

Департамент прикладной математики

Статус:

Курс по выбору

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

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

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

Славнов Сергей Андреевич

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

Аннотация

Целями дисциплины является ознакомление студентов с основными методами анализа и оптимизации в дискретных задачах. Обсуждается понятия сложности и приближенной разрешимости. В качестве модельного примера рассматривается базовая задача "об укладке рюкзака". Рассматриваются различные приложения.

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

• Целями освоения дисциплины «Методы анализа и оптимизации в дискретных задачах» являются ознакомление студентов с основными методами и алгоритмами решения задач оптимизации в дискретных системах.

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

• Знать теоретические основы и основные алгоритмы дискретной оптимизации, в том числе – в моделях, используемых при проектировании и анализе функционирования вычислительных систем.
• Уметь давать математическую постановку прикладных задач дискретной оптимизации, выбирать адекватный метод их решения, определять его параметры, использовать стандартные программы для решения задач дискретной оптимизации.
• Иметь навыки практической программной реализации известных алгоритмов решения задач дискретной оптимизации.

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

• Эффективно решаемые задачи дискретной оптимизации
  1. Задача о минимальном остовном дереве. Матроиды и жадные алгоритмы. 2. Задача о максимальном паросочетании. Задача о поиске минимального пути. 3. Потоки и сети. Теорема о максимальном потоке и минимальном разрезе. Задача о максимальном потоке.
• Задача линейного программирования и двойственность
  Задача линейного программирования. Геометрия множества допустимых решений. Двойственность. Условия дополняющей нежесткости.
• Венгерский алгоритм и прямо-двойственные алгоритмы
  1. Задача о взвешенном паросочетании и венгерский алгоритм. 2. Прямо-двойственные алгоритмы.
• Симплекс-алгоритм
• Целочисленное линейное программирование: подходы к решению задач.
  1. Вполне унимодулярные матрицы.. Непрерывная релаксация. Отсекающие плоскости. 2. Приближенные алгоритмы. Задача о минимальном покрытии. Задача коммивояжера — алгоритм Кристофидеса.
• Метод ветвей и границ
  Схема метода ветвей и границ. Метод ветвей и границ в задаче о рюкзаке. Метод ветвей и границ в задаче коммивояжера.

Элементы контроля

• Экзамен/зачет
• Контрольная работа
• Домашние задания
• Работа на семинарских занятиях
• Экзамен/зачет
• Контрольная работа
• Домашние задания
• Работа на семинарских занятиях

Промежуточная аттестация

• Промежуточная аттестация (3 модуль)
  0.5 * Контрольная работа + 0.5 * Экзамен/зачет

Список литературы

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

• Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач: Учебное пособие / Струченков В.И. - М.:СОЛОН-Пр., 2016. - 192 с.: ISBN 978-5-91359-181-4
• Лунгу К.Н. - Линейное программирование. Руководство к решению задач - Издательство "Физматлит" - 2009 - 132с. - ISBN: 978-5-9221-1029-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2253

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

• Линейное программирование. Транспортная задача: Учебное пособие / Литвин Д.Б., Мелешко С.В., Мамаев И.И. - Ставрополь:Сервисшкола, 2017. - 84 с.: ISBN - Режим доступа: http://znanium.com/catalog/product/976430