- •1. Введение
- •Основные разделы курса
- •3. Основная задача линейного программирования. Различные формы записи задачи.
- •6. Алгоритм симплекс-метода.
- •1.3. Реализация симплекс-метода в виде симплексных таблиц.
- •8Транспортная задача. Описание и примеры применения метода потенциалов.
- •29.Метод ветвей и границ. Задача о рюкзаке.
- •Задача о рюкзаке
- •30. Метод ветвей и границ. Задача коммивояжера.
- •28. Методы перебора вариантов. Метод вариаций.
- •31.Задачей целочисленного программирования называется задача линейного программирования, в которой имеется дополнительное условие, требующее, чтобы часть переменных принимала только целые значения.
- •35.Общие принципы дискретного динамического программирования. Уравнение Беллмана.
- •36. Задача распределения ресурсов.
- •38. Построение кратчайшего пути на сети.
- •37. Задача оптимального планирования. Обработка деталей на двух станках.
- •10. Выпуклые множества и выпуклые функции.
- •13.Двойственность в задачах выпуклого программирования
- •14. Квадратичное программирование
- •12. Постановка задачи. Теорема Куна – Таккера.
- •16. Геометрическое программирование
- •11. Свойства выпуклых множеств и выпуклых функций
- •19. Общая задача нелинейного программирования.
- •22.Свойства дифференцируемых функций.
- •24. Дифференцируемость оператора Немыцкого.
- •25. Необходимый признак экстремума в задачах без ограничений первого и второго порядков.
- •27 . Правило множителей Лагранжа для гладких нелинейных задач.
- •41. Простейшая вариационная задача (пвз), исследование необходимых условий экстремума первого порядка.
- •45. Вариационная задача с кусочно-гладкими кривыми.
- •46. Исследование необходимых условий экстремума второго порядка. Условия Лежандра и Якоби.
- •42.. Алгоритм Гюйгенса исследования пвз.
- •48.. Поле экстремалей. Достаточные условия сильного экстремума.
- •Задача Больца.
- •6.9. Изопериметрические задачи.
- •51. Принцип максимума Понтрягина.
1. Введение
В дисциплине "Методы оптимизации" изучаются методы решения оптимизационных задач (или задач нахождения экстремумов). В общем виде такую задачу можно сформулировать следующим образом: имеется некоторое множество M и заданный на этом множестве функционал F. Требуется найти максимально (минимально) возможное значение этого функционала на множестве M, а также - элемент x* множества M, при котором функционал F достигает своего экстремального значения.
Поскольку на практике выбор оптимального варианта почти всегда весьма актуален, не удивительно, что задача в такой постановке имеет большое количество конкретных примеров.
Цели курса "Методы оптимизации" :
-провести классификацию оптимизационных задач, сопровожденную широким спектром классических примеров и постановок задач;
-показать основные приемы и подходы к решению экстремальных задач.
Основное внимание уделяется теоретическим аспектам, в некоторых разделах исследуются особенности практической реализации приводимых алгоритмов.
Курс опирается на изученную в рамках "Математического анализа" теорию безусловного и условного экстремумов для функций нескольких действительных переменных, разделы функционального анализа и дифференциальных уравнений.
Основные разделы курса
1. Линейное программирование. Основная задача ЛП состоит в отыскании экстремума линейной функции нескольких действительных переменных на множестве, заданном линейными равенствами и неравенствами. Такая задача может возникнуть при планировании производственной деятельности. Теоретически задачу можно изучать средствами математического анализа. Несложными рассуждениями можно установить, что решение такой задачи следует искать в угловых точках множества допустимых векторов. Поскольку чаще всего число таких точек конечно, можно считать, что задача решена. Однако в практических приложениях важно уметь получать конкретный ответ, поэтому необходимо довести алгоритм решения до конкретной реализации. Такой реализацией в данном случае является алгорим симплекс-метода. Классическая транспортная задача об оптимизации перевозок является частным случаем задачи ЛП, которая показывает, что знание особенностей таких задач (теория двойственности) позволяет на основе симплекс-метода разрабатывать эффективные специализированные алгоритмы для более узких классов задач.
2. Дискретная оптимизация . Выбор макс-го числа из конечного множества никогда в теоретических рассуждениях не считается задачей, поскольку решается очень простым способом за конечное число шагов. Однако на практике с увеличением числа шагов возникает проблема времени работы алгоритма, которая ставит проблему не только конечности, но и эффек-и алгоритмов. Алг-мы дискретной оптимизации, такие как метод вариаций, метод ветвей и границ, динамическое программирование, показывают, каким образом можно избежать полного перебора всех вариантов, сохраняя уверенность в оптимальности выбранного элемента. Класс-ие задачи: оптимизация очереди, задача о рюкзаке, задача коммивояжера, целочисленное линейное прогр-ние, распределение ресурсов, кратчайшие пути и потоки на сетях, задача обработки деталей на двух станках, управление запасами.
3. Выпуклое прогр-ние. При решении задач с бесконечным мн-ом допустимых вариантов одним из основных приемов нахождения решения является использование правила множителей Лагранжа. Теорема Куна-Таккера для задач выпуклого прогр-ния - один из наиболее успешных его вариантов, дающий необходимые и достаточные условия, которые фактически позволяют свести выпуклую задачу с ограничениями-неравенствами к задаче без таких ограничений. Эта теорема может быть записана в виде теоремы о двойственности, эффек-сть которой можно проследить на примере задачи геом программирования.
4. Нелинейное програ-ние. Одним из результатов данного раздела является обоснование понятия гладкой задачи без ограничений. Под гладкостью задачи, как обычно, понимается диф-сть входящих в нее функций. Показывается, что в данном контексте естественно рассматривать фукнции, определенные на аффинных пространствах, поскольку в этом случае, с одной стороны, имеется разработанная теория диф-сти, а с другой - необходимые признаки экстремума имеют привычный вид равенства нулю дифференциала. К тому же для задач с ограничениями-неравенствами и равенствами справедлива теорема о множителях Лагранжа. Классические задачи нелинейного прог-ния без ограничений - простейшая вариационная задача и задача Больца. В этот же раздел можно отнести и соответствующие задачи для функций нескольких переменных. Для изучения раздела желательны знания в области фунана.
5. Вариационное исчисление. Общая теория нелинейного прог-ния позволяет получить для классических задач вариационного исчисления (в их числе задача о брахистохроне, изопериметричекая задача , задача о кратчайшем расстоянии и т.д.) необх условия экстремума. В разделе эти условия изучаются методами мат. анализа и диф. уравнений. Док-ся классические теоремы, дающие критерии для нахождения решения указанных задач.
6. Оптимальное управление. В разделе оптимального управления рас-ся задача оптимального терминального управления на примере задачи оптимального быстродействия, приводятся условия, позволяющие найти ее решение. Приводятся приложения теории оптимального управления в экономике.