нием задачи, при этом Fmax = 41.

5.4. Метод допустимых направлений Зойтендейка

Метод допустимых направлений Зойтендейка пригоден для решения задач с достаточно сложными функциями цели и ограничениями. Рассмотрим последовательность решения нелинейной задачи с линейными ограничениями, когда экстремум достигается на границе области допустимых значений переменных (ОДЗП). Предполагается, что F(x) имеет непрерывные частные производные в каждой точке допустимой области

max{F (x) Ax ≤ B, xi ≥ 0,i =1, n, x0 X }.

Из начальной точки x0, лежащей внутри ОДЗП, движение осуществляется по направлению вектора градиента F(x0 ) до тех пор, пока не будет достигнута

граница области (рис. 5.2).

В общем случае двигаться до границы необязательно, так как максимум F(x) может достигаться и до встречи с ней. В рассматриваемом случае F(x) все время возрастает, поэтому остановитьcя следует в точке x1 на граничной прямой.

Определим аналитически координаты точки x1. Они зависят от величины шага α0 в направлении вектора F(x0 ) и записываются как x1 = x0 + α0 F(x0 ) . Значение α0 выбирается таким образом, чтобы точка x1 принадлежала ОДЗП и,

кроме того, функция цели F(x) должна достигать максимума по параметру α0 в рассматриваемом направлении.

89

ремещение вдоль вектора α1k S k выводит за пределы ОДЗП, определяемой выражением aTj (xk +α1k S k ) = b j , и кроме этого вычисляется αk2 , при котором переме-

Графически условию максимизации скалярного произведения F(xk )T S k соответствует выбор такого вектора S k , который составляет с вектором F(xk ) наименьший острый угол ϕ по сравнению с любым вектором, выходящим из точки xk и лежащим в ОДЗП. Процесс прекращается при достижении точки xk, в которой максимум F(xk )T S k = 0 . Это значит, что соответствующие векторы вза-

имно перпендикулярны и дальнейшее увеличение целевой функции в данной области невозможно, а точка xk является искомой точкой максимума функции F(x).

На рис. 5.2 движение из точки x1осуществляется в направлении S1 вдоль граничной прямой до тех пор, пока функция F(x) возрастает, т.е. до точки x2 . Далее движение идет вдоль другой границы в направлении S 2 и заканчивается в точке x3 , в которой max{ F(x3 )T S 3} = 0, т.е. нет нового направления S3 , кото-

рое ведет к увеличению F(x). В точке x3 функция цели достигает глобального максимума в рассматриваемой области.

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

(рис. 5.3).

x0 =[2;1] .

ОДЗП решения задачи приведена на рис. 5.4. 1-й шаг. Рассмотрим решения задачи:

Находится направление вектора градиента в точке x0 , F(x0 ) =[8; 6], тогда координаты очередной точки x11 = 2 + 8α0 ; x12 =1 + 6α0 (см. пример 4.5).

91

x11 = 2 +8α0 = 2 + 0,568 = 2,568 ; x12 =1 + 6α0 =1 + 0,425 =1,425;

F(x1) =[5,12; 4,01].

4-й шаг. Движение в направлении F(x1) выводит за пределы ОДЗП, поэто-

му очередная точка поиска вычисляется по выражению αk +1 = xk + αk S k , где S k– новое направление движения, которое составляет минимальный острый угол с вектором градиента и направлено либо внутрь, либо по границе ОДЗП. При этом очередная точка должна принадлежать ОДЗП, а функция цели при переходе к очередной точке должна увеличиваться максимальным образом.

Направление S k находится, как решение задачи

где aTj – вектор коэффициентов при переменных во втором ограничении, на котором находится точка х1.

Отсюда следует, что S21 = −S11, тогда

При движении из точки x1 в точку x2 следует двигаться по граничной прямой в направлении S1, как показано на рис. 5.4.

5-й шаг. Координаты точки х2 определяются выражением: x2 = x1 + α1S1 или

Находится интервал изменения α1 , при котором х2 принадлежит ОДЗП:

93

Второе ограничение опущено, так как точка х2 принадлежит соответствующей ему прямой, тогда − 3,62 ≤ α0 ≤ 2,01.

6-й шаг. Находится α1 , которое обеспечит максимум функции F(x) в направлении S1.

Для этого координаты точки х2 подставляются в функцию F(x), тогда

F(α1) = 29,58 −1,01(α1)2 +1,22α1;

ddFα1 = −2,02α1 +1,22 = 0 , α1 = 0,6.

Значение α1 принадлежит интервалу, найденному в п. 5, поэтому для расчета координат точки х2 принимается α1 = 0,6 :

x12 = 2,568 + 0,71 0,6 = 2,994 ≈ 3;

x22 =1,425 − 0,71 0,6 = 0,999 ≈1.

Вычисляются составляющие вектора градиента в точке х2:

F(x2 )T =[− 4 3 +18 − 2 1;−2 3 − 2 1 +12]=[4; 4].

Направление вектора F(x2 ) перпендикулярно направлению S1, следова-

тельно, найденная точка х2 = [3; 1] обеспечивает максимум функции F(x) с учетом ограничений на переменные: Fmax = 41.

В пакете MATLAB решение задач нелинейного программирования реализуется с помощью программ QP и СONSTR.

94