Основные разделы курса

Введение

В дисциплине "Методы оптимизации" изучаются методы решения оптимизационных задач (или задач нахождения экстремумов). В общем виде такую задачу можно сформулировать следующим образом: имеется некоторое множество M и заданный на этом множестве функционал F. Требуется найти максимально (минимально) возможное значение этого функционала на множестве M, а также - элемент x* множества M, при котором функционал F достигает своего экстремального значения.

Поскольку на практике выбор оптимального варианта почти всегда весьма актуален, не удивительно, что задача в такой постановке имеет большое количество конкретных примеров.

Цели курса "Методы оптимизации":

-провести классификацию оптимизационных задач, сопровожденную широким спектром классических примеров и постановок задач;

-показать основные приемы и подходы к решению экстремальных задач.

Основное внимание уделяется теоретическим аспектам, в некоторых разделах исследуются особенности практической реализации приводимых алгоритмов.

Курс опирается на изученную в рамках "Математического анализа" теорию безусловного и условного экстремумов для функций нескольких действительных переменных, разделы функционального анализа и дифференциальных уравнений.

Основные разделы курса

1. Линейное программирование. Основная задача ЛП состоит в отыскании экстремума линейной функции нескольких действительных переменных на множестве, заданном линейными равенствами и неравенствами. Такая задача может возникнуть при планировании производственной деятельности. Теоретически задачу можно изучать средствами математического анализа. Несложными рассуждениями можно установить, что решение такой задачи следует искать в угловых точках множества допустимых векторов. Поскольку чаще всего число таких точек конечно, можно считать, что задача решена. Однако в практических приложениях важно уметь получать конкретный ответ, поэтому необходимо довести алгоритм решения до конкретной реализации. Такой реализацией в данном случае является алгорим симплекс-метода. Классическая транспортная задача об оптимизации перевозок является частным случаем задачи ЛП, которая показывает, что знание особенностей таких задач (теория двойственности) позволяет на основе симплекс-метода разрабатывать эффективные специализированные алгоритмы для более узких классов задач.

2. Дискретная оптимизация. Выбор макс-го числа из конечного множества никогда в теоретических рассуждениях не считается задачей, поскольку решается очень простым способом за конечное число шагов. Однако на практике с увеличением числа шагов возникает проблема времени работы алгоритма, которая ставит проблему не только конечности, но и эффек-и алгоритмов. Алг-мы дискретной оптимизации, такие как метод вариаций, метод ветвей и границ, динамическое программирование, показывают, каким образом можно избежать полного перебора всех вариантов, сохраняя уверенность в оптимальности выбранного элемента. Класс-ие задачи: оптимизация очереди, задача о рюкзаке, задача коммивояжера, целочисленное линейное прогр-ние, распределение ресурсов, кратчайшие пути и потоки на сетях, задача обработки деталей на двух станках, управление запасами.

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

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

5. Вариационное исчисление. Общая теория нелинейного прог-ния позволяет получить для классических задач вариационного исчисления (в их числе задача о брахистохроне, изопериметричекая задача, задача о кратчайшем расстоянии и т.д.) необх условия экстремума. В разделе эти условия изучаются методами мат. анализа и диф. уравнений. Док-ся классические теоремы, дающие критерии для нахождения решения указанных задач.

6. Оптимальное управление. В разделе оптимального управления рас-ся задача оптимального терминального управления на примере задачи оптимального быстродействия, приводятся условия, позволяющие найти ее решение. Приводятся приложения теории оптимального управления в экономике.

Поиск по сайту: