Optimization Methods

2021/2022

Academic Year

RUS

Instruction in Russian

5

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Elective course

When:

3 year, 3, 4 module

Instructors

Ignatov, Andrei

Коновалов Евгений Владиславович

Maminov, Artem

Posypkin, Mikhail

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

Аннотация

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

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

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

• Chong, E. K. P., & Żak, S. H. (2013). An Introduction to Optimization (Vol. Fourth edition). Hoboken, New Jersey: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=814819
• Введение в оптимизацию, Поляк, Б. Т., 2014
• Нелинейное программирование : теория и алгоритмы, Базара, М., 1982

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

• Пантелеев А.В., Летова Т.А. - Методы оптимизации в примерах и задачах - Издательство "Лань" - 2015 - 512с. - ISBN: 978-5-8114-1887-9 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/67460

Авторы

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