Решебник_МО

Требуемая точность достигнута, но из табл. 3 видно, что процесс поиска «блуждал» вокруг экстремальной точки. По результатам вычислений решением задачи будем считать Х*= Х5= (0,0595; 0,0402), minf(Х*) = 0,00631.

ПРОПОРЦИОНАЛЬНЫЙ ГРАДИЕНТНЫЙ МЕТОД

В этом методе длина очередного рабочего шага прямо пропорциональна величине градиента исследуемой точки, т.е. hk=

Пропорциональный градиентный поиск следует начинать с определения приемлемого значения α. Как правило, в качестве начальной величины берут произвольное значение α0≤1, а на каждом

шаге уменьшают α вдвое, пока не получат положительный результат (f(хk+1)>f(хk) при поиске максимума или f(хk+1)<f(хk) при поиске

минимума). Процедуру поиска записывается следующим образом:

61

xik 1 xik k f (X k ) , i=1,2,…,n;xi

где 0<<1 – произвольно выбранная постоянная (одна и та же для всех итераций) величина изменения шага.

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

Учитывая монотонность уменьшения приращений k+1=f(Xk+l) f(Xk) на каждом шаге, процесс вычислений можно остановить, как только k+1≤ε, где ε – заранее заданная малая величина, определяемая точностью измерительной аппаратуры.

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

Пропорциональный градиентный метод реализуется следую-

3.Если результат оказался удачным, то переходят к п. 4, в противном случае дробят значение (к+1=к/2) и переходят к п. 4.

4.Вычисляют значение градиента в точке хк+1: f (xk+1).

62

5. Если условие остановки алгоритма | f (Хk+1)| выполнено, то поиск заканчивается, при этом Х*=Хк+1 и f*=f(Xk+1). Иначе полагают к=к+1 и переходят к п. 2.

Пример 17. Минимизируйте функцию f(X)=9x12+16x22–90x1–128x2.

Поиск начинайте в точке Х0=(1; 0), α0=0,06<1, δ=0,0,5.

Решение. Эту задачу легко решить с помощью классических

*(–128) = 8, f(Х1) = f(5,5;8) = –222,75.

Сравнение значений функции в точках Х0 и Х1 показывает, что шаг поиска оказался удачным (f(X1)<f(X0) при поиске минимума), и, следовательно, не нужно менять величину шага, т.е. 1 = 0. Полагая

63

Из таблицы видно, что в точке Х3 получен отрицательный результат поиска, так как не произошло улучшение значения целевой функции f(X3)=f(X2), и, следовательно, необходимо изменить значение шага: 3= δ* 2=0,5* 2=0,03.

В точке Х4 обе производные функции обратились в ноль, и, следовательно, процесс поиска закончен. По результатам вычислений решением задачи будет Х*= Х4= (5;4), min f(Х*) = –481.

Сравнение значений функции в точках Х0 и Х1 показывает, что шаг поиска оказался неудачным (f(X1)<f(X0) при поиске максимума), и,

дальнейшие вычисления сведем в табл. 5.

64

Объем вычислений по сравнению с методом градиента сокращается, поиск ускоряется. В качестве признака окончания поиска

координаты начальной и конечной точек подъема.

Пример 19. Пусть требуется найти методом наискорейшего спуска минимум функции f(X) = 9x12+16x22–90x1–128x2, если начальная

конечной точек спуска.

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

х21 в целевую функцию и получим функцию одной переменной : f(х11(),х21( )) = 9*(1+72 )2+16*(81 )2–90*(1+72 )–128*(81 ) =

= 3088002–21568–81. Найдем производную полученной функции и, приравняв ее к нулю, определим частный максимум:

результаты дальнейших вычислений сведем в табл. 6.

66

В точке Х4 обе частные производные функции равны нулю, следовательно, процесс поиска закончен.

По результатам вычислений решением задачи будет Х*=Х4=(5; 6), f(Х*)= –481.

Пример 20. Пусть требуется найти методом наискорейшего подъема максимум функции f(X)=6x1–2x3–3x12–2x22–x32, если начальная

конечной точек подъема.

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

f(Х0) =1.

Представим переменные х11 и х21 в виде функций одной переменной α согласно правилам градиентного поиска: хiк+1=хiк+ *

Подставим выражения для х11, х21 и х31 в целевую функцию и

получим функцию одной переменной : f(х11(),х21(),х31( )) = 6*(6 )–2*(–1)–3*(6 )2–2*(0)2–(–1)2= = –10862+36 +1.

67

Найдем производную полученной функции и, приравняв ее к

нулю, определим частный максимум: f ( ) = –216 +36 = 0 = 0,167.

Подставим в выражения для х11, х21 и х31 найденное значение

: х11=0+6*0,167=1, х21=0+0*0,167= 0 и х21= –1+0*0,167= –1, таким образом получена координата новой точки исследования Х1=(1; 0; –1).

В новой точке повторим процесс поиска: f(Х1)=4, r1= f ( X 1 ) =0,x1

функции равны нулю, следовательно, процесс поиска закончен.

По результатам вычислений решением задачи будет Х*=Х1=(1; 0; –1), f(Х*)= 4.

ГРАДИЕНТНЫЕ МЕТОДЫ В ЗАДАЧАХ С ОГРАНИЧЕНИЯМИ

Если оптимум целевой функции находится внутри допустимой области G(X) изменения переменных X, то присутствие ограничений не влияет на процесс поиска решения и поиск оптимума осуществляется практически так же, как и в случае без ограничений. Если же оптимум функции находится за пределами допустимой области, то отыскание наибольшего значения целевой функции при ограничениях на X становится существенно сложнее.

Одним из эффективных методов решения задач с ограничениями является метод штрафных функций. Этот метод позволяет сводить задачи на условный экстремум к задачам на безусловный экстремум, переходя к задаче оптимизации вспомогательной функции R(X)=f(X)+H(X), в которой на X ограничения не накладываются.

Добавление слагаемого Н(Х) (отрицательного в задачах на максимум) к функции f(X) – специальный штраф за неточное выполнение ограничений gj(X)=0, j=I,2,...,m.

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

68

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

Рассмотрим алгоритм равномерного градиентного метода для решения задач с ограничениями. Учитывая, что наряду с ограничениями вида gj(X)≥0, j=1,2,...,m существуют также ограничения на знак переменных хi≥0, получим алгоритм градиентного метода в следующем виде:

В формуле h представляет собой шаг градиентного поиска. Если точка Xk находится в допустимой области, то второе слагаемое в квадратных скобках равно нулю (αj(Хk)=0), а процесс поиска протекает так же, как и при отсутствии ограничений. Если на очередном шаге нарушается хотя бы одно ограничение, соответствующий коэффициент αj(Хk) становится отличен от нуля, и это немедленно отражается на приращениях координат, которые направляют поиск в допустимую область.

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

Пример 21. Максимизировать функцию f(x)=x1+2x2–x12–0,5x22 при ограничениях –2х1–3х2+6≥0; –х1–4х2+5≥0; х1,х2≥0.

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

Выберем значения Х0=(0; 0); h = 0,2; α = 2. Тогда алгоритм движения по каждой из координат для равномерного градиентного

метода примет вид

x1k+1 = max{0, xlk+0,2*[(1–2xlk)+α1(Xk)*(–2)+α2(Xk)*(–1)]}; x2k+1 = max{0, x2k+0,2*[(2–x2k)+α1(Xk)*(–3)+α2(Xk)*(–4)]}.

Чтобы перейти к расчету координат точки X1, найдем сначала значения α1(X0) и α2(X0), зависящие от того, удовлетворяет ли точка X0 ограничениям задачи. Поскольку в точке (0; 0) оба ограничения

69

выполняются, то α1 = 0, α2 = 0. Итак, в начальной точке поиска имеем

X0=(0; 0), f(X0)=0, α1(X0)=0, α2(X0)=0.

Первый шаг. Выполняем расчет координат точки X1:

х11= max{0; 0+0,2*[(l–0)+0+0]}= 0,2, х21= max{0; 0+0,2*[(2–0)+0+0]}=

= 0,4. Проверяя ограничения, видим, что в точке Х1=(0,2; 0,4) оба выполняются, следовательно, α1(X1)=0; α2(X1)=0. Вычисляем значение функции f(X1)=0,88.

f(Х5)= –1,04. При переходе границы допустимой области движущаяся точка исследования отброшена назад в допустимую область, причем довольно далеко от границы. При меньших значениях h или α «отскок» от границы был бы также меньшим.

Далее поиск продолжается согласно вышеописанному алгоритму.

Пример 22. Максимизировать функцию f(x) = 8x1+32x1x2–2x12–4x22 при ограничениях: 3х1–5х2+30 ≥0, 5х1+х2–15 ≥0, х1 ≥0, х2 30.

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

Выберем значения начальной точки исследования Х0=(4; 6); начальный шаг поиска h0= 0,5, коэффициент пропорциональности

70