ДХ) = 4х, + 6х2 - 2xf- 2ххх2 - 2х22
1 1 3 2 х1
Рис. 21.3. Последовательность точек, ведущая к оптимуму функции
Отсюда получаем выражение для функции 1г(г):
h(r) =Д1 - 2r, 1) = -2(1 - 2rf + 2(1 - 2г) + 4.
Оптимальная длина шага г, при которой функция h(r) достигает максимума, равна 1/4. Таким образом, мы нашли, что X1 = (1/2, 1).
Итерация 2.
УДХ) = (0, 1).
Теперь следующая точка X2 определяется выражением
Х = (1,1) + К0,1) = (,1+/-).
Следовательно,
h(r) = -2(1 + rf + 5(1 + г) + .
Отсюда получаем г = 1/4 и X2 = (1/2, 5/4). Итерация 3.
УДХ2) = (-1,0). Точка X3 определяется выражением
Следовательно,
/i(r) = --(l-r)2+ -а-г)+ - 2 4 8
Отсюда получаем г = 1/4 и X = (3/8, 5/4). Итерация 4.
V/(X3) = (0, -).
Точка X4 определяется выражением
x=VWan Г35+Г
,8 4J I. А) 1,8 4 Поэтому
*(0 = -(5 + r)s+g(5 + r) + g.
Отсюда имеем г = 1/4 и X4 = (3/8, 21/16). Итерация 5.
УДХ4) = (-1,0).
Точка X5 определяется выражением
3 21 V-i,oi=fc:
Следовательно,
Х ,8l6j Л &") { 8 16
Л(Н =--(3-г) +- (3-Н+-.
v 32v ; 64v 128
Отсюда получаем г = 1/4 и Xй = (11/32, 21/16). Итерация 6.
УДХ6) = (0, -).
Так как V/(X°) = 0, вычисления можно закончить. Получена приближенная точка максимума X5 = (0,3437, 1,3125). Точный максимум достигается в точке Х* = (0,3333, 1,3333).
УПРАЖНЕНИЯ 21.1.2
1. Покажите, что метод Ньютона-Рафсона (раздел 20.1.2), применяемый к решению задачи максимизации строго вогнутой квадратичной функции, в общем случае сходится в точности за один шаг. Примените указанный метод к задаче максимизации функции
/(X) = 4,v, + 6х2 - 2.x2 - 2х,х, - 2х\.
2. Выполните не более пяти итераций метода наискорейшего спуска (подъема) для каждой из следующих задач. Во всех случаях положите Х° = О.
a) min/(Х) = (*2-*?)*+(1-х,)*.
b) max/(X) = сХ + ХГАХ, где
с = (1,3, 5),
с) min/(X) = X[-х2 +xf-х,х2.
21.2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ С ОГРАНИЧЕНИЯМИ
Общая задача нелинейного программирования с ограничениями записывается в виде:
максимизировать (или минимизировать) z = /(X) при ограничениях
g(X) <0.
Условия неотрицательности переменных X > 0 составляют часть заданных ограничений общего вида. Предполагается также, что по крайней мере одна из функций /(X) или g(X) является нелинейной, и все функции непрерывно дифференцируемы.
Универсальных алгоритмов решения задач нелинейного программирования не существует, и связано это, главным образом, с разнообразием нелинейных функций. Возможно, наиболее общим результатом, имеющим отношение к рассматриваемым задачам, являются условия Куна-Таккера. Как показано в разделе 20.2.2, эти условия являются необходимыми лишь для существования экстремума, за исключением ситуации, когда функции /(X) и g(X) являются выпуклыми или вогнутыми (тогда эти условия будут также достаточными).
В этом разделе рассматривается ряд алгоритмов решения задач нелинейного программирования, которые условно можно разделить на непрямые и прямые. В непрямых методах решение задачи нелинейного программирования сводится к решению одной или нескольких линейных задач, порожденных исходной. Прямые методы непосредственно имеют дело с исходной нелинейной задачей и позволяют построить последовательность точек, сходящуюся к точке экстремума.
В данном разделе непрямые методы представлены алгоритмами сепарабельного, квадратичного, геометрического и стохастического программирования. К числу прямых методов относится метод линейных комбинаций и метод последовательной безусловной максимизации, изложенный далее вкратце. С другими важными методами решения задач нелинейного программирования можно познакомиться, обратившись к приведенному в конце главы списку литературы.
21.2.1. Сепарабельное программирование
Функция /(ж,, х2.....хп) называется сепарабельной (разделимой), если она представляется в виде суммы п функций одной переменной /,(х,), f2(x2), /„(*„), т.е. ffx,, х2,хJ = f,(x,) + f/xj + ... + f/xj.