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

Бакалавриат 2020/2021

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Прикладная математика)

Направление: 01.03.04. Прикладная математика

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

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 3-й курс, 3 модуль

Формат изучения: без онлайн-курса

Преподаватели: Славнов Сергей Андреевич

Язык: русский

Кредиты: 4

Контактные часы: 40

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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