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

Рассмотрим задачу определения максимального значения вогнутой функции f(x₁, x₂, ..., x_n) при условиях g_i(x₁, x₂, ..., x_n)b_i (i=1, ..., m), x_j0 (j=1, ..., n), где g_i(x₁, x₂, ..., x_n) — выпуклые функции.

Вместо того, чтобы непосредственно решать эту задачу, находят максимальное значение функции F(x₁, x₂, ..., x_n)=f_i(x₁, x₂, ..., x_n)+H(x₁, x₂, ..., x_n), являющейся суммой целевой функции задачи, и некоторой функции H(x₁, x₂, ..., x_n),определяемой системой ограничений и называемой штрафной функцией.

Штрафную функцию можно построить различными способами. Наиболее часто она имеет вид

где

а _i>0 — некоторые постоянные числа, представляющие собой весовые коэффициенты.

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

(3.21)

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

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

1. Определяют исходное допустимое решение.

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

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

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

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

6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.

П р и м е р 2.  Найти максимальное значение функции

(3.22)

при условиях

(3.23)

(3.24)

Р е ш е н и е. Целевая функция данной задачи представляет собой отрицательно-определенную квадратичную форму и, значит, вогнута. В то же время ОДР задачи, определяемая ограничениями (3.23) — (3.24), — выпуклая. Следовательно, задача (3.22) — (3.24) является задачей выпуклого программирования. Для нахождения ее решения применим метод штрафных функций. Прежде чем это сделать, построим ОДР задачи и линии уровня, определяемые целевой функцией (3.22). Этими линиями служат окружности с центром в точке (0; 0). Точка касания одной из этих окружностей ОДР и является искомой точкой максимального значения целевой функции.

Положим X₀ =(6, 7). Возьмем =0, 1, обозначим через

g (x₁, x₂)=18–(x₁–7)²–(x₂–7)²

и определим частные производные от функций f (x₁, x₂) и g (x₁, x₂) по переменным x₁ и x₂:

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

1 итерация. Так как точка X₀ =(6, 7) принадлежит ОДР задачи, то второе слагаемое в квадратных скобках формулы (3.21) равно нулю. Значит, координаты следующей точки X₁ вычисляем по формулам

Проверим теперь, принадлежит ли эта точка ОДР задачи. Для этого найдем g (X₁)=18–4,84–1,96=11,2. Так как g (X₁)>0, то X₁ принадлежит ОДР. В этой точке f (X₁)=–54,4.

2 итерация. Находим

f (X²)=–34,816.

Проверяя таким образом остальные точки, на 12 итерации имеем:

Сравнивая значения целевой функции, найденные в точках, полученных после 10 и 12 итераций, видно, что они с точностью до 10^-1 совпадают. Это говорит о близости точки, найденной на последней итерации, к точке максимального значения целевой функции. Такой же вывод можно сделать, если исследовать векторы-градиенты функций f (X) и g (X) в точке X⁽¹²⁾. В этой точке

Вычислим отношения одноименных координат векторов:

–8,01/5,99–1,337;

–8,016/5,984 –1,339.

Как видно, они почти равны между собой. Это означает, что векторы и практически коллинеарные. Так как к тому же точка X⁽¹²⁾ находится вблизи границы ОДР (поскольку , то и можно считать приемлемым решением задачи. Это решение при необходимости можно уточнить дальнейшими шагами до полной коллинеарности градиентов целевой и ограничительной функций. Последовательность точек, получаемых во время нахождения решения задачи, наглядно иллюстрируется рис. (3.2).