Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

5.2.2. Метод штрафных функций

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

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

f(x) → max

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

g(x) ≤ b, x ≥ 0,

где g(x) – выпуклая функция.

В соответствии с идеей метода штрафных функции исходную задачу условной оптимизации преобразуем в задачу безусловной оптимизации

F(x) = f(x) + H(x).

Штрафная функция H(x) определяется ограничениями исходной задачи и имеет вид

shukaev286.wmf

где параметры αi(x) играют роль весовых коэффициентов. Излишне говорить, что штраф желателен только в недопустимых точках, поэтому

shukaev287.wmf

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

shukaev288.wmf (5.18)

где λ ∈ [0; 1]. Из этого выражения следует, что если предыдущая точка находится в области допустимых решений исходной задачи, то второе слагаемое в квадратной скобке равна нулю и переход к последующей точке определяется только градиентом целевой функции. Если же эта точка не принадлежит области допустимых решений, то за счет этого слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом чем меньше αi, тем быстрее находится приемлемое решение, однако точность его определения снижается. Поэтому итерационный процесс обычно начинают при малых αi и продолжая его αi постепенно увеличивают.

Укрупненный алгоритм метода штрафных функций состоит из следующих шагов.

Шаг 0. Определение исходного допустимого решения.

Шаг 1. Выбирают шаг вычислений.

Шаг 2. Находят частные производные от целевой функции f(x) и функции g(x).

Шаг 3. По формуле (5.18) находят координаты точки, определяющей возможное новое решение задачи.

Шаг 4. Новую точку проверяют на допустимость по ограничениям исходной задачи. Если нет, то переход на шаг 5. При допустимости найденного решения исследуется необходимость перехода к следующему допустимому решению. При необходимости такого перехода возврат на шаг 1. В противном случае найдено приемлемое допустимое решение исходной задачи.

Шаг 5. Устанавливают значения αi и переходят на шаг 3.

Пример 5.3. Необходимо максимизировать целевую функцию

shukaev289.wmf (5.19)

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

(x1 – 7)2 + x2 – 7)2 ≤ 18, x1, x2 ≥ 0. (5.20)

Решение. Целевая функция данной задачи – отрицательно-определенная квадратичная функция и, следовательно, вогнута, а область допустимых решений – выпукла. Следовательно, эта задача является задачей выпуклого программирования для уяснения процесса поиска оптимального решения дадим геометрическую интерпретацию этой задачи. Построим область допустимых решений (рис. 5.1), определяемой ограничениями (5.20) и линии уровня, определяемые целевой функцией (5.19). Этими линиями служат окружности с центром в точке (0; 0). Точка касания одной из этих окружностей с областью допустимых решений в виде круга с центром в точке Е и является искомой точкой максимального значения целевой функции.

pic_5_1.tif

Рис. 5.1. Геометрическая интерпретация задачи

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

Шаг 0. За исходное допустимое решение примем x0 = (6; 7).

Шаг 1. Шаг вычислений выберем равным λ = 0,1.

Шаг 2. Представив функцию ограничения в виде

g(x) = 18 – (x1 – 7)2 + (x2 – 7)2

и определим частные производные от f(x) и g(x)

shukaev290.wmf shukaev291.wmf

shukaev292.wmf shukaev293.wmf

Теперь используя формулу (5.18) приступим к построению последовательности точек.

Итерация 1.

Шаг 3. Так как x0 = (6; 7) принадлежит области допустимых решений, то второе слагаемое в квадратной скобке формулы (5.18) равен нулю. Тогда координаты следующей точки x1 вычисляем по усеченной формуле (5.18)

shukaev294.wmf

shukaev295.wmf

Шаг 4. Полученное решение проверяем на допустимость по ограничениям исходной задачи

g(x1) = (4,8 – 7)2 + (5,6 – 7)2 = (–2,2)2 + (–1,4)2 = 6,8 < 18.

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

Итерация 2.

shukaev296.wmf

shukaev297.wmf

g(x2) = (3,84 – 7)2 + (4,48 – 7)2 < 18; f = –34,816.

Итерация 3.

shukaev298.wmf

shukaev299.wmf

g(x3) = (3,072 – 7)2 + (3,584 – 7)2 > 18.

Итерация 4. Полученное на итерации 3 решение не является допустимой, поэтому для определения нового решения используем формулу (5.18) с учетом второго слагаемого квадратной скобки

shukaev300.wmf

shukaev301.wmf

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

shukaev302.wmf i = 1, …, m,

где в качестве начального значения α берут любое неотрицательное число.

Воспользуемся вторым подходом, тогда

shukaev303.wmf

и по формуле (5.18) получим

shukaev304.wmf shukaev305.wmf

При этом g(x(4)) ≈ –8,181.

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

Эту задачу можно остановить на 13-й итерации когда

shukaev306.wmf shukaev307.wmf

g(x(13)) ≈ 0,251; f(x(13)) = –32,337.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074