Методы оптимизации с учетом ограничений. Графическое представление задачи

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

В большинстве случаев допустимое множество определяется ограничениями-равенствами и (или) неравенствами, т.е. рассматривается задача

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

Штрафная функция (ШФ) – это целевая функция, которая формируется следующим образом:

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

Внутренний штраф

Метод барьерных функций

Внешний штраф

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

− на большей части допустимого множества задачи эти функции близки к нулю;

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

− степень близости штрафа к нулю и степень его возрастания вблизи границы зависят от значения штрафного параметра.

Основные типы штрафов (для ограничений-равенств):

1) Квадратичный

2) Экспоненциальный

Для ограничений-неравенств:

1) Бесконечный

2) Логарифмический

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