• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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
Список литературы

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

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

  • 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

Авторы

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