Материал: 862

3.5. ТИПОВОЙ РАСЧЁТ «ГРАДИЕНТНЫЕ МЕТОДЫ ПОИСКА ЭКСТРЕМУМА»

3.5.1.Задание

Имеется целевая функция, в общем виде

коэффициенты а, b и c которой для 31 различного варианта заданы в прил. 2 (см. столбцы 2 – 4). Используя целевую функцию (А) и исходные данные (см. прил. 2), необходимо:

1. Определить минимум целевой функции (А) методом градиента при условии, что координаты начальной точки равны x10 x20 1 и задана точность поиска = 0,01.

2. Определить минимум целевой функции (А) методами релаксаций и крутого восхождения из исходной точки x10 и x20 (см. прил.2, столбцы 5 и 6) с заданной точностью поиска (см. прил. 2, столбец 7).

3.5.2.Образец выполнения работы

Текст задания записать в отчет. Причем, числовые значения свести в табл. 3. Для примера рассмотрим выполнение настоящей работы по варианту №31, который дает следующие исходные данные (см. прил. 2).

На основе исходных данных и формулы (А) имеем следующие исходную функцию:

R(x) x12 2x22 x1 x2 ,

которую необходимо, согласно заданию, исследовать на минимум тремя методами:

35

1)методом градиента;

2)методом релаксаций;

3)методом крутого восхождения.

Метод градиента.

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

Iшаг.

1.Определяем частные производные по осям координат от заданной функции R(xi ) x12 2x22 x1 x2 :

2. Вычисляем величины первых производных в начальной точке,

3. Вычисляем величину целевой функции в исходной (начальной) точке

R(x10, x20) x12 2x22 x1 x2 4.

4. Осуществляем первый шаг из начальной точки с координатами x10 и x20 по формуле (33). Здесь следует заметить, что при поиске минимума движение осуществляется по антиградиенту, т.е. в направлении, противоположном направлению градиента, – направлению наиболее быстрого уменьшения целевой функции. Фактор шага h принимаем равным заданной точности поиска, т.е.

h = = 0,1;

Вычисляем величину целевой функции в точках x11 и x12 :

R(x1',x2' ) (0,7)2 2(0,5)2 0,7 0,5 1,34.

36

Результаты расчетов сводим в табл. 4.

II шаг.

Вычисляем значения первых производных по осям координат в точках x11 0,7и x12 0,5:

Осуществляем третий шаг:

x13 0,51 0,1 1,25 0,385;

x23 0,23 0,1 1,43 0,087.

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

х14 = 0,3; х24 = 0,017.

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

Результатами вычислений на 5, 6,7 и 8-м шагах пополняем табл.

4.

Наконец, на последнем 8-м шаге целевая функция увеличилась по сравнению с ее величиной на 7-м шаге, поэтому оптимальным будет решение

x1min x17 0,05 0,1; x2min x27 0,074 0,1;

R(x)min = 0,011.

Таким образом, окончательно имеем, используя (37), ответ.

Ответ: R(0,05 0,1; 0,074 0,1)=0,011.

Метод релаксаций.

Имеем согласно исходным данным следующую целевую функцию:

R(xi) = x12 + 2x22 + x1x2.

Исходная точка х10 = х20 =2 (см. табл. 3).

1. Вычисляем величины первой производной по осям координат

38

На этом основании движение осуществляем по оси х2, фиксируя х10 = 2, т.е. по направлению наибольшей производной.

2. Вычисляем значение целевой функции в исходной точках

х10=2; х20=2:

R(xi) = x12 + 2x22 + x1 x2 = 22 + 2 22 + 2 2 = 16.

3. Осуществляем первый шаг поиска из точки х10 = х20=2 в точку

где ε = –1, поскольку движение осуществляется по антиградиенту (определяем минимум целевой функции), a h = , т.е. h = 0,01.

Таким образом, имеем x12 2-0,01 10 2-0,1 1,9.

4. Вычисляем значение целевой функции в новой точке

x11 2;x12 1,9:

R(xi) 22 2 1,92 2 1,92 2 1,9 15,02.

5. Сопоставляя величины целевой функции в точке, откуда шагаем (х10=2; х20=2), с точкой, куда шагаем (x11 2;x12 1,9), имеем

R(2; 2) = =16; R(2; 1,9) = 15,02; R(х10=2; х20=2) > R(x11 2;x12 1,9), т.е. 16 > 15,02. Шаг оказался удачным, поэтому следующий (второй) шаг осуществляем из последней удачной точки (2; 1,9) и при этом увеличиваем фактор шага вдвое: h = 2 = 0,02.

6. Вычисляем х22 на 2-м шаге: