Различные алгоритмы градиентного метода (для самостоятельного изучения)
В любых алгоритмах используется движение по направлению вектора градиента, но алгоритмы отличаются по способу движения по направлению градиента.
1. Движение осуществляется до критической точки (как это осуществлялось в алгоритме наискорейшего подъёма или наискорейшего спуска). В этом случае определяется величина t* , которая задаёт глубину продвижения.
2. Движение осуществляется на заданный
шаг ∆t , после чего снова
определяется градиент z(
0
) (градиентный метод движения шагами).
В этом случае координаты новой точки определяем из условия:
=
0
+ ∆t ∙
z
0
, или
х1 = х10 + ∆t∙
(
0
);
х2 = х20 + ∆t∙
(
0
);
…
хn = хn0
+ ∆t∙
(
0
); где ∆t – заданная
величина.
3. Если для выбора направления движения используются несколько z , вычисленных на предыдущих шагах, то такой метод получил название метода сопряжённых градиентов. В этом случае учитываются граничные значения нескольких z; новое значение градиента определяется как их линейная комбинация.
Индивидуальные задания 6
В задачах 1 – 12 найти решение методом наискорейшего подъёма (спуска).
1. Найти min z = (х1 -1)2 + (х2 -1)2 ; 0 (2,2)
2. Найти max z = x12 + 2x1ּx2 + 2x22 ; 0 (1,0)
3. Найти max z = x12 + 4x1ּx2 + x22 ; 0 (1,0)
4. Найти min z = x12 - 2x1ּx2 + 3x22 ; 0 (2,1)
5. Найти max z = x12 - 2x1ּx2 + 2x22 ; 0 (2,1)
6. Найти min z = 2x1 + x2 - x22 ; 0 (1,-1)
7. Найти min z = -x12 + 2x1ּx2 - 4x22 ; 0 (1,1)
8. Найти max z = 3x12 + 4x1ּx2 + 6x22 ; 0 (-1,-1)
9. Найти min z = 2x1 + 3x2 - x12 - 2x22 ; 0 (1,2)
10. Найти max z = (х1 -2) 2 + 2x22 ; 0 (2,1)
11. Найти max z = 9x1 - 8x2 – 0,5 x12 - 2x1ּx2 ; 0 (1,2)
12. Найти min z = -10x1 - x12 + 2x1ּx2 + x22; 0 (1,1)
Индивидуальные задания 7
В задачах 1 – 30 найти решение методом наискорейшего подъёма (спуска). Число неудачных испытаний М = 5. При вычислении производных через конечные разности ∆х = 0,1.
1. Найти max z = 2x1 + 3x2 - 2x22
при условиях: x1 + 4x2 ≤ 4
x1 + x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
2. Найти max z = 2x1 + 3x2 – x12 - 2x22
при условиях: x1 - x2 ≥ 0
- x1 + 2x2 ≤ 2
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
3. Найти max z = x1 + 5x2 – 2x12 + 2x1ּx2 - 2x22
при условиях: 2x1 + x2 ≥ 2,0
3x1 + x2 ≤ 4
x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
4. Найти min z = x1 - 3x1 + x12 - 2x22
при условиях: x1 - 2x2 ≤ 8
x2 ≤ 3
x1 ≥ 0; x2 ≥ 0
5. Найти max z = x12 + 4x2 - x22
при условиях: x1 + x2 ≤ 6
x1 - x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
6. Найти min z = x12 - 4x2 + x22 - 3x2
при условиях: x1 - x2 ≤ 3
x1 ≤ 5
x1 + 2x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
7. Найти min z = x12 - 2x1 + 2x22 - x2
при условиях: 2x1 - 3x2 ≤ 0
x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
8. Найти max z = x12 + x22 - 2x1 - 2x2 + 2
при условиях: x1 + x2 ≥ 1
2x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
9. Найти max z = x12 + x22 -2x1 + 2x2 + 3
при условиях: x1 + 2x2 ≥ 3
2x1 - x2 ≤ 1
x1 + x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
10. Найти min z = 2x12 + 2x22 - x1
при условиях: 2x1 + x2 ≤ 3
-x1 + 2x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
11. Найти min z = x12 + x22 - 4x1 + 1
при условиях: x1 + x2 ≤ 10
2x1 - x2 ≤ 10
x1 ≥ 0; x2 ≥ 0
12. Найти max z = 4x12 + 4x22 - 8x1 - 2 x2 + 1
при условиях: 5x1 + x2 ≥ 6
3x1 - 2x2 ≤ 1
x1 + 2x2 ≥ 3
x1 ≥ 0; x2 ≥ 0
13. Найти max z = 4x12 + x22 + 2x1
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
14. Найти max z = 9x12 + 4x22 + 2x1 – 7
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
15. Найти max z = x12 + x22 - 3x1 - 2 x2
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
16. Найти max z = 4x1 + 5x2 - 2x22
при условиях: x1 + 3x2 ≤ 6
x1 + x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
17. Найти max z = 5x1 + 3x2 – x12 - 2x22
при условиях: x1 - x2 ≥ 0
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
18. Найти max z =3 x1 + 5x2 – 2x12 + 2x1ּx2 - 2x22
при условиях: 2x1 + x2 ≥ 2
2x1 + x2 ≤ 4
x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
19. Найти min z = 3x1 - 3x2 + x12 - 2x22
при условиях: x1 - 2x2 ≤ 8
x2 ≤ 4
x1 ≥ 0; x2 ≥ 0
20. Найти max z = 2x12 + 4x2 -3x22
при условиях: x1 + x2 ≤ 5
x1 - x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
21. Найти min z = 2x12 - 4x2 + x22 - 3x2
при условиях: x1 - x2 ≤ 3
x1 ≤ 4
x1 + 2x2 ≥ 1
x1 ≥ 0; x2 ≥ 0
22. Найти min z = 4x12 - 2x1 + 2x22 - x2
при условиях: 2x1 - 3x2 ≤ 0
x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
23. Найти max z =3x12 + x22 - 2x1 - 2x2 + 2
при условиях: x1 + x2 ≥ 1
2x1 + x2 ≤ 6
x1 ≥ 0; x2 ≥ 0
24. Найти max z = 4x12 + x22 - 2x1 + 2x2 + 3
при условиях: x1 + 2x2 ≥ 3
2x1 - x2 ≤ 1
x1 + x2 ≤ 3
x1 ≥ 0; x2 ≥ 0
25. Найти min z = 2x12 + 2x22 -x1 +2x2
при условиях: 2x1 + x2 ≤ 4
-x1 + 2x2 ≥ 1
x2 ≤ 2
x1 ≥ 0; x2 ≥ 0
26. Найти min z = x12 + x22 - 4x1 + 2x2+ 10
при условиях: x1 + x2 ≤ 6
2x1 - x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
27. Найти max z = 2x12 + 4x22 - 4x1 - 2 x2 + 3
при условиях: 5x1 + x2 ≥ 1
3x1 - 2x2 ≤ 2
x1 + 2x2 ≥ 3
x1 ≥ 0; x2 ≥ 0
28. Найти max z = 4x12 + x22 + 2x1+ 3x2
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 5
x1 ≥ 0; x2 ≥ 0
29. Найти max z = 9x12 + 4x22 + 2x1 – x2 + 5
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 6
x1 ≥ 0; x2 ≥ 0
30. Найти max z = x12 + 3x22 - 3x1 - 2 x2 + 4
при условиях: x1 - x2 ≥ 0
x1 + x2 ≤ 6
x1 ≥ 0; x2 ≥ 0
Задание. Составить блок-схему метода наискорейшего подъема (спуска).