Методы исследования функций численного анализа

Достаточные условия экстремума.

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

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

при ограничениях

Рассмотрим задачу условной оптимизации при ограничениях типа неравенств:

при ограничениях

,

где целевая функция f(x) = f (x₁,x₂,...,x_n) и функции ограничений g_i (x₁,x₂,…x_n) непрерывно дифференцируемые функции.

Необходимое условие экстремума для задачи (2.3) формулируется в виде принципа Лагранжа.

Принцип Лагранжа. Пусть х* - точка локального экстремума функции f(x), причем векторы линейно независимы. Тогда найдутся такие числа, не равные одновременно нулю, что для функции Лагранжа

выполняются следующие равенства:

Числа называются множителями Лагранжа. Система (2.4) содержит n + m уравнений с n + m неизвестными. Точки х* = (х₁*, х₂*, …, х_n*), удовлетворяющие условиям (2.2) при некоторых, называются условно-стационарными. Тип условно-стационарной точки х* определяется знаком второго дифференциала функции Лагранжа (необходимым условием второго порядка):

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

Пусть имеется точка х*, удовлетворяющая системе (1.5). Если в этой точке для всех ненулевых таких, что, то тогда х* является точкой локального минимума в задаче (2.3).

Пример. Найти условный экстремум функции при ограничении

.

Решение.

1. Составим функцию Лагранжа:

2. Запишем необходимые условия:

3. Решение системы (условно-стационарная точка) будет х₁*=1, х₂*=1,

4. Проверим достаточные условия экстремума:

5. Подставим в

6. Поскольку то в точке х* = (1; 1) – локальный минимум

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

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

Методы нелинейного программирования приме­няют для решения оптимальных задач с нелинейными функциями цели. На независимые переменные могут быть наложены ограни­чения также в виде нелинейных соотношений, имеющих вид ра­венств или неравенств. По существу методы нелинейного програм­мирования используют, если ни один из перечисленных выше ме­тодов не позволяет сколько-нибудь продвинуться в решении оптимальной задачи. Поэтому указанные методы иногда называют также прямыми методами решения оптимальных задач. Для получения численных результатов важное место отводится нелинейному программированию и в решении оптимальных задач такими методами, как динамическое программирование, принцип, максимума и т. п. на определенных этапах их применения. Названием «методы нелинейного программирования» объеди­няется большая группа численных методов, многие из которых при­способлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вы­числения критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т. д. Ряд методов нелинейного програм­мирования практически постоянно используется в сочетании с дру­гими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кро­ме того, эти методы служат основой построения систем автомати­ческой оптимизации — оптимизаторов, непосредственно при­меняющихся для управления производственными процессами.

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

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

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

Дата добавления: 2014-01-04