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


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



Содержание курса.

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

Литература

  • Карманов В.Г. Математическое программирование. –М.: Наука, 1986. -288с.

  • Васильев Ф.П. Численные методы решения экстремальных задач М.: Наука,2002. – 552 с.

  • Корнеенко В.П. Методы оптимизации. -М.: ВШ, 2007.- 664с.

  • Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: ВШ, 1980. -304с.

  • Габасов Р., Кириллова Ф.М. Методы оптимизации. -Минск: ВШ, 1980.-280с.

  • Интрилигатор М. Математические методы оптимизации и экономическая теория.- М.: Айрис-пресс, 2002. – 576с.

  • Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и примерах. М.: Наука, 1991.-448с.

  • Заславский Ю.Л. Сборник задач по линейному программированию. М., Наука, 1969, 256с.

  • Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. Минск, ВШ, 1978, -256с.

  • Капустин В.Ф. Практические занятия по курсу математического программирования. Изд. ЛГУ, 1976. –192с.

  • Избранные труды Л.С. Понтрягина (сер. «Выдающиеся ученые МГУ»). М.: МАКС Пресс, 2004.-552с.

  • Основы теории оптимального управления (под ред. В.Ф. Кротова) – М., ВШ, 1990, - 430с.

  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

  • Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир. 1985.

  • Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание. 1987. № 10.

  • Карманов В.Г. Математическое программирование. М.: Наука. 1986.

  • Сухарев А..Г., Тимохов А..В., Федоров В.В. Курс методов оптимизации. М.: Наука. 1985.

  • Мину М. Математическое программирование. М.: Наука. 1990.