Характеристика методов решения задач оптимизации

При ответе конкретной задачи оптимизации исследователь в первую очередь обязан выбрать математический способ, что приводил бы к конечным итогам с мельчайшими затратами на вычисления либо же давал возможность взять громаднейший количество информации об искомом ответе. Выбор того либо иного способа в значительной мере определяется постановкой оптимальной задачи, и применяемой математической моделью объекта оптимизации.

На данный момент для ответа оптимальных задач используют по большей части следующие способы:

способы изучения функций хорошего анализа;
способы, основанные на применении неизвестных множителей Лагранжа;
вариационное исчисление;
динамическое программирование;
принцип максимума;
линейное программирование;
нелинейное программирование.

Сейчас создан и удачно используется для ответа определенного класса задач способ геометрического программирования.

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

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

Динамическое программирование хорошо подходит для ответа задач оптимизации многостадийных процессов, в особенности тех, в которых состояние каждой стадии характеризуется довольно маленьким числом переменных состояния. Но при наличии большого числа этих переменных, т. е. при высокой размерности каждой стадии, использование способа динамического программирования затруднительно благодаря ограниченных быстродействия и количества памяти вычислительных автомобилей.

Пожалуй, наилучшим методом при выборе способа оптимизации, самый пригодного для ответа соответствующей задачи, направляться признать изучение опыта и возможностей применения разных способов оптимизации. Ниже приводится краткий обзор математических способов ответа оптимальных задач и примеры их применения. Тут же дана только краткая черта указанных областей и методов их применения, что до некоей степени может уменьшить выбор того либо иного способа для ответа конкретной оптимальной задачи.

Способы изучения функций хорошего анализа являются самые известные способы ответа несложных оптимальных задач, с которыми известны из курса матанализа. Простой областью применения данных способов являются задачи с известным аналитическим выражением критерия оптимальности, что разрешает отыскать не сверхсложное, кроме этого аналитическое выражение для производных. Полученные приравниванием нулю производных уравнения, определяющие экстремальные ответы оптимальной задачи, очень редко удается решить аналитическим методом, исходя из этого, как, правило, используют счётные автомобили. Наряду с этим нужно решить совокупность конечных уравнений, значительно чаще нелинейных, для чего приходится применять численные способы, подобные способам нелинейного программирования.

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

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

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

По большей части при применении способа множителей Лагранжа приходится решать те же задачи, что и без ограничений. Некое усложнение в этом случае появляется только от введения дополнительных неизвестных множителей, благодаря чего порядок совокупности уравнений, решаемой для нахождения экстремумов критерия оптимальности, соответственно увеличивается на число ограничений. В остальном, проверки поиска и процедура решений их на оптимальность отвечает процедуре ответа задач без ограничений.

Множители Лагранжа возможно использовать для ответа задач оптимизации объектов на базе уравнений с частными производными и задач динамической оптимизации. Наряду с этим вместо решения совокупности конечных уравнений для отыскания оптимума нужно интегрировать совокупность дифференциальных уравнений.

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

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

Вариационные способы разрешают в этом случае свести ответ оптимальной задачи к интегрированию совокупности дифференциальных ‘ уравнений Эйлера, каждое из которых есть нелинейным дифференциальным уравнением второго порядка с граничными условиями, заданными на обоих финишах промежутка интегрирования. Число уравнений указанной совокупности наряду с этим равно малоизвестных функций, определяемых при ответе оптимальной задачи. Каждую функцию находят в следствии интегрирования приобретаемой совокупности.

Уравнения Эйлера выводятся как нужные условия экстремума функционала. Исходя из этого полученные интегрированием совокупности дифференциальных уравнений функции должны быть проверены на экстремум функционала.

При наличии ограничений типа равенств, имеющих вид функционалов, используют множители Лагранжа, что позволяет перейти от условной задачи к абсолютной. самые значительные трудности при применении вариационных способов появляются при ответа задач с ограничениями типа неравенств.

Заслуживают внимания прямые способы ответа задач оптимизации функционалов, в большинстве случаев разрешающие свести исходную вариационную задачу к задаче нелинейного программирования, решить которую время от времени несложнее, чем краевую задачу для уравнений Эйлера.

Динамическое программирование является эффективным способом ответа задач оптимизации дискретных многостадийных процессов, для которых критерий оптимальности задается как аддитивная функция параметров оптимальности отдельных стадий. Без особенных затруднений указанный способ возможно распространить и на случай, в то время, когда критерий оптимальности задан в второй форме, но наряду с этим в большинстве случаев возрастает размерность отдельных стадий.

По существу способ динамического программирования является алгоритмом определения оптимальной стратегии управления на всех стадиях процесса. Наряду с этим закон управления на каждой стадии находят методом решения частных задач оптимизации последовательно для всех стадий процесса посредством способов изучения функций хорошего анализа либо способов нелинейного программирования. Результаты ответа в большинстве случаев не смогут быть выражены в аналитической форме, а получаются в виде таблиц.

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

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

Принцип максимума используют для ответа задач оптимизации процессов, обрисовываемых совокупностями дифференциальных уравнений. Преимуществом математического аппарата принципа максимума есть то, что ответ может определяться в виде разрывных функций; это характерно многим задачам оптимизации, к примеру задачам оптимального управления объектами, обрисовываемыми линейными дифференциальными уравнениями.

Нахождение оптимального ответа при применении принципа максимума сводится к задаче интегрирования совокупности дифференциальных уравнений процесса и сопряженной совокупности для запасных функций при граничных условиях, заданных на обоих финишах промежутка интегрирования, т. е. к ответу краевой задачи. На область трансформации переменных смогут быть наложены ограничения. Совокупность дифференциальных уравнений интегрируют, используя простые программы на цифровых счётных автомобилях.

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

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

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

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

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

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

Заглавием “способы нелинейного программирования” объединяется многочисленная несколько численных способов, многие из которых приспособлены для ответа оптимальных задач соответствующего класса. Выбор того либо иного способа обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, нужной точностью ответа, мощностью имеющейся счётной автомобили и т.д. Последовательность способов нелинейного программирования фактически всегда используется в сочетании с другими способами оптимизации, как, к примеру, способ сканирования в динамическом программировании. Помимо этого, эти способы являются основой построения совокупностей автоматической оптимизации — оптимизаторов, конкретно использующихся для управления производственными процессами.

Геометрическое программирование имеется способ ответа одного особого класса задач нелинейного программирования, в которых ограничения и критерий оптимальности задаются в виде позиномов — выражений, воображающих собой сумму произведений степенных функций от свободных переменных. С подобными задачами время от времени приходится сталкиваться в проектировании. Помимо этого, кое-какие задачи нелинейного программирования время от времени возможно свести к указанному представлению, применяя аппроксимационное представление для ограничений и целевых функций.

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

Ответственной чёртом любой оптимальной задачи есть ее размерность п, равная числу переменных, задание значений которых нужно для однозначного определения состояния оптимизируемого объекта. В большинстве случаев, ответ задач высокой размерности связано с необходимостью исполнения громадного количества вычислений. Последовательность способов (к примеру, дискретный принцип и динамическое программирование максимума) специально предназначен для ответа задач оптимизации процессов высокой размерности, каковые смогут быть представлены как многостадийные процессы с довольно низкой размерностью каждой стадии.

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

вид математического описания процесса;
тип ограничений на переменные процесса
число переменных.

Предполагается, что ответ оптимальной задачи для процессов, обрисовываемых совокупностями конечных уравнений, определяется как конечный комплект значений управляющих действий (статическая оптимизация процессов с сосредоточенными параметрами), а для процессов, обрисовываемых совокупностями обычных дифференциальных уравнений, управляющие действия характеризуются функциями времени (динамическая оптимизация процессов с сосредоточенными параметрами) либо пространственных переменных (статическая оптимизация процессов с распределенными параметрами).

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