Индивидуальные задания 4

Найти экстремум функции при заданных ограничениях методом последовательного изменения координат, выбрав одну из начальных точек и задав приращение координат по указанию преподавателя (x=0,1 ÷1).

1. Найти

при условиях

2. Найти

при условиях

3. Найти

при условиях

4. Найти

при условиях

5. Найти

при условиях

6. Найти

при условиях

7. Найти

при условиях

8. Найти

при условиях

9. Найти

при условиях

10. Найти

при условиях

11. Найти

при условиях

12. Найти

при условиях

13. Найти

при условиях

14. Найти

при условиях

15. Найти

при условиях

Задание. Записать блок-схемы метода последовательного изменения координат а) на максимум целевой функции; б) на минимум целевой функции.

Индивидуальные задания 5

Решить задачи 1-15 индивидуального задания 4 с точностью ε = 0,05 и приращением .

Градиентные методы Метод наискорейшего подъема (для самостоятельного изучения)

Рассмотрим случай поиска безусловного экстремума выпуклой функции max F=Z(X)

1.Выберем произвольную начальную точку

2.Подсчитаем значение функции Z( ) и вектора (в данной точке)

3.Осуществляем движение в направлении градиента, т.е. определяем координаты новой точки , исходя из условия:

Этой формуле соответствует n координатных равенств:

x₁ = ( )

x₂ = ( )

…………………………

x_n = ( )

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

Z( =Z(t)

(Z(t) получаем при подстановке в функцию Z)

5.Определяем число , т.е. такое значение t, при котором Z(t) достигает максимума:

= 0, отсюда находится

1. Полагаем и , если значения функции в новой точке оказалось больше, чем в начальной , т.е. при условии:

Z( )= заменить Z( ) на Z( ).

Далее переходим к пункту 2.

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

Рассмотрим пример

Найти max z =

Выбираем начальную точку

I| итерация.

1. Подсчитаем Z и

Z = -

= (-2х₁;-х₂)

=(-2;-1)

2. Осуществляем движение по градиенту:

3. Z(t)=Z( = - (1-2t) - 0,5(1-t) = - (1-4t+4t ) – 0,5(1-2t+t ) = - 4,5t +5t –1,5

-9t+5=0→ = 5/9 ≈ 0,55

Проверим с помощью второй производной, будет ли точка точкой экстремума:

∂²Z/∂t² = -9 < 0, т.е. в точке - максимум.

6. Вычислим Z(t*):

Z(t*) = - 4,5∙(5/9) + 5∙(5/9) -1.5≈ - 4,25ּ25/81 + 25/9-1,5=

= - 1,3887 +2,78 - 1,5= - 0,1087  - 0,11;

Z(t*) > Z( ); (- 0.11 > -1,5); т.е. примем точку за начальную , подставив в координатные равенства найденные значения

(1-2·t; 1-t); (1-2·0,55; 1-0,55); (-0,1; 0,45)→ = (-0,1; 0,45).

Далее повторяются операции, выполненные на первой итерации, начиная с пункта 2.

II итерация.

2. Подсчитаем Z и

Z =Z(- 0,1; 0,45) = - (-0,1)² – 0,5(0,45)² = - 0,01 - 0,50,2025 = = - 0,01 – 0,10125  - 0,11.

= (-2х₁;- х₂) = ( - 2ּ( - 0,1); - 0,45)

=(0,2; - 0,45)

3. Осуществляем движение по градиенту:

x₁ = - 0,1 + 0,2t; x₂ = 0,45 – 0,45t;

4. Z(t)=Z( заменить на

Z(t)= - (- 0,1 + 0,2t) - 0,5(0,45 – 0,45t ) =- (0,01 - 0,04t + 0,04t ) –

- 0,5(0,2025 - 0,405t+0,2025t ) = - 0,01 + 0,04t - 0,04t - 0,10125+ +0,2025t - 0,10125t = - 0,14125t + 0,2425t – 0,11125  - 0,14t + 0,24t – 0,11.

3. Находим max Z(t): = - 0,28t+0,24; → = 0; →

- 0,28t+0,24 =0→ ≈ 0,86.

Проверим с помощью второй производной, будет ли точка точкой экстремума:

∂²Z/∂t² = - 0,28 < 0, т.е. в точке - максимум.

6. Вычислим Z(t*):

Z(t*) = - 0,14(0,86) +0,24(0,86) –0,11= - 0,1035+0,2064 – 0,11 ≈ - 0,0071;

Z(t*) > Z( ); (- 0,0071 > - 0,11); т.е. примем точку за начальную , подставив в координатные равенства найденные значения

x₁ = - 0,1 + 0,2t; x₂ = 0,45 – 0,45t;

(- 0,1 + 0,2t; 0,45 – 0,45t);

(- 0,1 + 0,2ּ 0,86; 0,45 – 0,45ּ 0,86);

(0,072; 0,063)→ = (0,072; 0,063).

Далее повторяются операции, выполненные на первой итерации, начиная с пункта 2.

Процесс продолжается до нахождения точки экстремума. Он может быть конечным, тогда в точке * grad Z( *)=0 и вычисления завершаются. А может оказаться, что найдено решение с некоторой точностью ε, т.е. приближенно. В последнем случае, если за определенное число шагов (итераций) решение не будет найдено, то оптимальным считается последнее из найденных.

Замечание. Название метода связано с тем, какой экстремум ищется в задаче: если максимум целевой функции, то метод наискорейшего подъема, если минимум целевой функции, то метод наискорейшего спуска.