Планирование

Содержание:

1. Численные методы безусловной оптимизации первого порядка…………..3

1.1 Минимизация функций  многих переменных. Основные положения…..9

1.2 Метод наискорейшего спуска…………………………………….……….10

1.3 Метод сопряженных градиентов…………………………………….……12

2. Аналитическая часть………………………………………………………..16

2.1 Вопросы по теме…………………………………………………………….16

2.2 Тест …………………………………………………………………………16

2.3 Примеры задач……………………………………………………………..18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Численные методы безусловной оптимизации первого порядка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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