Методы оптимизации

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

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

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

Кто читает: Департамент больших данных и информационного поиска

Где читается: Санкт-Петербургская школа физико-математических и компьютерных наук

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Игнатов Андрей Дмитриевич, Коновалов Евгений Владиславович, Маминов Артем Дмитриевич, Посыпкин Михаил Анатольевич

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

Кредиты: 5

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

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

Аннотация

Методы оптимизации применяются в широком спектре областей: планирование производственных процессов, логистика, инженерное проектирование, телекоммуникации, облачные технологии, биоинформатика, нанотехнологии и др. При существенно разнообразии применений, алгоритмы оптимизации построены на хорошо разработанной теории и канонических численных методах решения оптимизационных задач. Курс “Методы оптимизации” ставит своей задачей ознакомление слушателя с современной теорией и методами оптимизации. Особенностью курса является широкий охват тем. В теоретической части курса рассматриваются различные задачи непрерывной и дискретной оптимизации с одним и несколькими критериями и ограничениями различного типа, изучаются локальные методы и методы глобальной оптимизации. На семинарах студентам предлагаются задачи, которые требуется решить с использованием языка программирования Python и специализированных пакетов. После освоения курса студент будет иметь представление о различных постановках задач оптимизации и основных методах их решения.

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

Знать формы записи задачи линейного программирования. Знать основные определения, понятия прямой и двойственной задачи. Владеть симплекс методом и его вариантами.
Знать отличия в постановке задач глобальной и локальной оптимизации. Владеть основными методами решения задач глобальной оптимизации.
Знать общую постановку задачи комбинаторной оптимизации. Владеть основными методами решения задач ЦЛП.
Знать постановку задачи о ранце с одним и несколькими ограничениями. Знать методы ветвей и границ, жадные алгоритмы, методы динамического программирования.
Знать постановку задачи об оптимальной упаковке контейнеров, жадные алгоритмы, точные алгоритмы решения.
Знать постановку задачи многокритериальной оптимизации, понятия оптимальности по Парето и Слейтеру, условия оптимальности. Владеть основными методами решения задач многокритериальной оптимизации.

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

Знать основные термины, обозначения, понятия, постановку задач оптимизации.
Владеть основными методами решения задач безусловной оптимизации.
Владеть основными методами решения задач непрерывной условной оптимизации.
Знать общую постановку задачи математического программирования. Знать необходимые и достаточные условия экстремума.
Знать определение двойственной задачи, теоремы двойственности.
Знать понятие условного экстремума при функциональных ограничениях, функцию Лагранжа, теорему Куна-Таккера.
Уметь составлять двойственную задачу к задаче математического программирования.

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

Введение в оптимизацию, основные термины, обозначения, понятия. Постановка задачи оптимизации, примеры из практики.
Задачи математического программирования. Безусловный экстремум и экстремум при простых и ограничениях. Необходимые и достаточные условия экстремума.
Основные методы решения задач безусловной оптимизации.
Условный экстремум при функциональных ограничениях. Функция Лагранжа, теорема Куна-Таккера.
Двойственность в оптимизации. Теоремы двойственности, примеры применения.
Основные методы решения задач непрерывной условной оптимизации.
Линейное программирование. Основные определения, понятия, прямая и двойственная задача.
Симплекс метод и его варианты.
Непрерывная глобальная оптимизация. Эвристические методы. Липшицевы методы.
Интервальные методы глобальной оптимизации.
Задачи комбинаторной оптимизации. Общая постановка, основные классы задач. Основные методы решения задач ЦЛП.
Задача о ранце с одним и несколькими ограничениями. Методы ветвей и границ, жадные алгоритмы, динамическое программирование.
Задача об оптимальной упаковке контейнеров, жадные алгоритмы, точные алгоритмы решения. Приложения.
Многокритериальная оптимизация, эффективное решение, множество оптимальных решений по Парето и Слейтеру. Условия оптимальности.
Основные методы решения задач многокритериальной оптимизации.

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

Домашнее задание 1
Реализация методов оптимизации нулевого порядка на языке Python. Предлагается написать программы, реализующие заданные алгоритмы.
Домашнее задание 2
Реализация методов оптимизации первого и второго порядка на языке Python. Предлагается написать программы, реализующие заданные алгоритмы.
Домашнее задание 3
Реализация методов оптимизации, основанных на техниках линейного программирования (ЛП) и интервальном анализе функций. Предлагается написать программы, реализующие заданные алгоритмы.
Контрольная работа 1
Поиск точек экстремума в задачах безусловной и условной минимизации аналитическими методами
Контрольная работа 2
Аналитическое решение задач комбинаторной и многокритериальной оптимизации
Экзамен

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

2021/2022 учебный год 4 модуль
0.1 * Домашнее задание 1 + 0.1 * Домашнее задание 2 + 0.1 * Контрольная работа 2 + 0.1 * Контрольная работа 1 + 0.5 * Экзамен + 0.1 * Домашнее задание 3

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

Авторы

Посыпкин Михаил Анатольевич

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