Задачи с ограничениями.

Лекция 8.

Теория и методы решения задач оптимизации при наличие ограничений составляют предмет исследования одного из разделов прикладной математики – математического программирования.

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

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

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

(1).

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

при .

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

1. равна нулю во всех точках пространства проектирования, удовлетворяющих заданным ограничениям – неравенствам;

2. стремится к бесконечности в тех точках, в которых эти неравенства не выполняются.

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

Теперь рассмотрим случай, когда в задачи оптимизации заданы ограничения двух типов – равенства и неравенства:

(2).

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

(3).

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

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

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

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

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

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