новая папка 1 / 641041
.pdfЛабораторная работа № 2
Методы многомерной безусловной оптимизации
Цель работы: знакомство с методами многомерной безусловной оптимизации и их освоение, сравнение эффективности применения этих методов для конкретных целевых функций.
Задание для лабораторной работы
1.Найти решение задачи безусловной оптимизации для заданной целевой функции (табл. 3), используя теоремы о необходимых и достаточных условиях экстремума. Провести анализ найденного решения и установить, на каком множестве D оно является глобальным.
2.Провести графический анализ функции, отобразив ее в виде совокупности линий уровня.
3.С заданной точностью найти приближенное решение задачи безусловной
минимизации f ( x1 , x 2 ) m i n, |
( x1 , x 2 ) D для заданной начальной точки |
||||
x |
( 0 ) ( x |
( 0 ) |
, x |
( 0 ) ) : |
|
|
|
1 |
|
2 |
|
−методом Гаусса-Зейделя;
−симплекс-методом;
−одним из градиентных методов.
Построить траектории поиска, совместив их в одних осях координат с линиями уровня.
4.Сделать выводы об эффективности методов, сравнивая количество расчетов функции для достижения заданной точности.
5.Найти минимум заданной функции (табл. 4) с использованием надстройки
Excel “Поиск решения”.
10
Таблица 3. Варианты индивидуальных заданий для ручного расчета
№ вари- |
Вид целевой функции |
Начальная точка |
Точность |
|||
анта |
f ( x1 , x 2 ) |
|
|
|
|
|
x |
( 0 ) |
x |
( 0 ) |
|
||
|
|
|||||
|
|
|
||||
|
|
1 |
2 |
|
1 |
( x1 |
4 x |
2 ) |
2 |
|
( x 2 |
5 ) |
2 |
|
10 |
-5 |
0,15 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
2 |
( x1 |
x 2 ) |
2 |
( x 2 |
|
4 ) |
2 |
|
9 |
5 |
0,3 |
|||||
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
( x1 |
3 x |
2 ) |
2 |
|
( x 2 |
2 ) |
2 |
|
4 |
10 |
0,25 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
4 |
( x1 |
3 x |
2 ) |
2 |
|
( x 2 |
1) |
2 |
|
0 |
8 |
0,15 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
5 |
( x1 |
5 x |
2 ) |
2 |
|
( x 2 |
1) |
2 |
|
8 |
10 |
0,35 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
( x1 |
2 x |
2 ) |
2 |
|
( x 2 |
3 ) |
2 |
|
0 |
10 |
0,18 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
7 |
( x1 |
2 x |
2 ) |
2 |
|
( x 2 |
3 ) |
2 |
|
-7 |
-7 |
0,2 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
8 |
( x1 |
x 2 ) |
2 |
( x 2 |
|
2 ) |
2 |
|
6 |
-1 |
0,18 |
|||||
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
( x1 |
3 x |
2 ) |
2 |
|
( x 2 |
5 ) |
2 |
|
10 |
10 |
0,35 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
10 |
( x1 |
9 x |
2 ) |
2 |
|
( x 2 |
1) |
2 |
|
-6 |
5 |
0,25 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
11 |
( x1 |
2 x |
2 ) |
2 |
|
( x 2 |
9 ) |
2 |
|
15 |
12 |
0,15 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
12 |
( x1 |
x 2 ) |
2 |
( x 2 |
|
6 ) |
2 |
|
10 |
8 |
0,18 |
|||||
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
( x1 |
x 2 ) |
2 |
( x 2 |
|
1) |
2 |
|
5 |
6 |
0,15 |
|||||
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
( x1 |
2 x |
2 ) |
2 |
|
( x 2 |
3 ) |
2 |
|
7 |
6 |
0,25 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
( x1 |
2 x |
2 ) |
2 |
|
( x 2 |
4 ) |
2 |
|
-4 |
7 |
0,3 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
16 |
( x1 |
2 x |
2 ) |
2 |
|
( x 2 |
5 ) |
2 |
|
-15 |
5 |
0,2 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
( x1 |
6 x |
2 ) |
2 |
|
( x 2 |
1) |
2 |
|
-5 |
-3 |
0,2 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
18 |
( x1 |
5 x |
2 ) |
2 |
|
( x 2 |
6 ) |
2 |
|
-10 |
-5 |
0,18 |
||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
( x1 4 x 2 ) |
2 |
( x 2 |
3 ) |
2 |
-5 |
6 |
0,22 |
||||||||
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
Продолжение табл. 3
20 |
|
|
|
( x1 |
|
6 x |
2 ) |
2 |
|
( x |
2 |
|
2 ) |
2 |
|
|
-10 |
|
7 |
0,22 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21 |
|
|
|
( x1 |
|
7 x |
2 ) |
2 |
|
( x |
2 |
|
2 ) |
2 |
|
|
8 |
|
6 |
0,3 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
22 |
|
|
|
( x1 |
|
8 x |
2 ) |
2 |
( x |
2 |
1) |
2 |
|
|
-5 |
|
-5 |
0,2 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
23 |
|
|
|
( x1 x 2 ) |
2 |
|
( x 2 7 ) |
2 |
|
|
10 |
|
2 |
0,25 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
24 |
|
|
|
( x1 |
|
8 x |
2 ) |
2 |
( x |
2 |
2 ) |
2 |
|
|
-10 |
|
5 |
0,35 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
|
( x1 |
|
5 x |
2 ) |
2 |
( x |
2 |
3 ) |
2 |
|
|
-10 |
|
-5 |
0,21 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Варианты индивидуальных заданий для расчета в Excel |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
№ вари- |
|
|
|
|
Вид целевой функции |
|
Начальная точка |
Точность |
||||||||||||||||||||||||||
анта |
|
|
|
|
|
|
|
|
|
|
|
|
f ( x1 , |
|
x 2 ) |
|
|
|
|
|
|
|
|
( 0 ) |
|
( 0 ) |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
1 |
|
x 2 |
|
1 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
10 |
0,1 |
|
|
|
|
|
|
|
x |
1 |
8 x |
2 |
6 x1 x 2 1 |
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
2 |
|
|
|
|
|
|
|
|
|
|
|
x 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
2 |
0,25 |
|||
|
|
|
|
|
|
|
|
|
|
e 2 |
|
|
( x |
1 |
x 2 ) |
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
2 |
|
|
|
2 |
x1 x 2 3 x1 6 x 2 |
|
-5 |
|
8 |
0,12 |
|||||||||||||||||||
|
|
|
|
x1 |
|
x |
2 |
|
|
|
|
|
|
|
||||||||||||||||||||
4 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
2 |
4 ( x 2 x1 ) |
|
|
9 |
|
5 |
0,13 |
|||||||||||||
|
|
|
|
|
|
x1 |
|
x |
2 |
|
|
|
|
|
|
|||||||||||||||||||
5 |
|
|
|
|
2 |
|
|
2 |
x1 x 2 x1 x 2 1 |
|
|
4 |
|
10 |
0,05 |
|||||||||||||||||||
|
|
|
|
x |
1 |
|
x 2 |
|
|
|
|
|
|
|||||||||||||||||||||
6 |
|
|
3 |
|
2 |
6 x1 x 2 39 x1 18 x 2 20 |
|
15 |
|
18 |
0,1 |
|||||||||||||||||||||||
|
|
x |
1 |
x 2 |
|
|
|
|
|
|
||||||||||||||||||||||||
7 |
|
( x1 3 ) |
2 |
|
( x 2 |
2 ) |
2 |
( x1 |
x 2 4 ) |
2 |
|
8 |
|
10 |
0,05 |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
2 x |
2 |
|
x |
3 |
|
4 x1 3 x 2 6 |
|
-5 |
|
7 |
0,2 |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
1 |
|
2 |
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
|
2 |
|
|
|
2 |
x1 x 2 3 x1 6 x 2 |
|
|
6 |
|
-1 |
0,08 |
||||||||||||||||||
|
|
|
|
x1 |
|
x |
2 |
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
2 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
8 |
0,1 |
|
|
|
|
|
|
4 x |
1 x 2 2 x1 |
2 x 2 8 |
|
|
|||||||||||||||||||||||||
|
|
x1 |
x |
2 |
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
2 |
|
|
2 |
|
|
|
2 |
|
|
0,5 |
|
-1,5 |
0,15 |
|||
|
|
|
|
|
2 x |
1 |
x1 x 2 |
5 x1 |
|
x |
2 |
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
2 |
|
x |
2 |
4 ( x 2 x1 ) 6 |
|
|
7 |
|
6 |
0,15 |
||||||||||||||||||
|
|
|
|
|
2 x1 |
|
2 |
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
Продолжение табл. 4
13 |
|
|
|
|
|
x |
2 |
|
x |
2 |
|
x1 x 2 3 x1 6 x 2 |
-4 |
7 |
0,08 |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
1 |
2 |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
2 |
|
|
|
2 |
4 x1 x 2 4 x1 4 x 2 |
-5 |
-3 |
0,2 |
||||||||||||||
|
|
|
|
8 x |
1 |
|
2 x 2 |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
15 |
|
|
|
|
|
|
|
|
|
x1 |
|
x 2 |
|
|
50 |
|
20 |
|
|
|
|
10 |
-5 |
0,08 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x 2 |
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
|
|
|
|
x |
2 |
2 x |
2 |
2 ( x1 4 x 2 ) 5 |
-5 |
6 |
0,12 |
|||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
1 |
2 |
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
2 |
|
|
2 |
|
2 ln x1 18 ln x 2 |
|
10 |
7 |
0,15 |
|||||||||||
|
|
|
|
|
|
x1 |
x |
2 |
|
|
|
|
|
|||||||||||||||
18 |
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
3 |
15 x1 x 2 |
|
|
|
8 |
6 |
0,13 |
||||||
|
|
|
|
|
|
|
|
|
x1 |
x |
2 |
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
( x1 3 ) |
4 |
( x1 2 x 2 ) |
2 |
|
10 |
10 |
0,05 |
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
20 |
|
|
|
|
|
|
|
2 |
|
|
2 |
) |
|
|
|
|
e |
( x 12 x 22 |
) |
1 |
|
-5 |
-5 |
0,2 |
||||
|
|
|
|
|
( x1 |
x 2 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
21 |
x |
4 |
2 x |
2 |
5 x |
2 |
|
2 x |
2 |
x 2 2 x 2 |
2 ( x1 0 ) |
8 |
12 |
0,25 |
||||||||||||||
|
|
|
|
|||||||||||||||||||||||||
|
1 |
1 |
2 |
1 |
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
22 |
x |
4 |
2 x |
2 |
5 x |
2 |
2 x |
2 |
x 2 2 x 2 |
2 |
( x1 0 ) |
-10 |
5 |
0,35 |
||||||||||||||
|
|
|
|
|||||||||||||||||||||||||
|
1 |
1 |
2 |
1 |
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
23 |
|
|
4 |
|
|
|
|
2 |
|
|
|
|
2 |
x 2 2 x 2 1 |
|
( x1 0 ) |
10 |
-5 |
0,1 |
|||||||||
|
|
|
x1 |
2 x |
2 |
2 x |
1 |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
24 |
|
|
4 |
|
|
|
|
2 |
|
|
|
|
2 |
x 2 2 x 2 1 |
|
( x1 0 ) |
-15 |
12 |
0,05 |
|||||||||
|
|
|
x1 |
2 x |
2 |
2 x1 |
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
2 |
|
|
|
|
2 |
4 x1 6 x 2 |
7 |
|
-6 |
5 |
0,15 |
|||||||||
|
|
|
|
|
|
x1 |
3 x |
2 |
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Методические указания
Метод Гаусса-Зейделя (метод покоординатного спуска)
В методе Гаусса-Зейделя задача многомерной оптимизации сводится к многократному использованию метода одномерной оптимизации.
|
Для некоторой начальной точки |
x |
( 0 ) |
|
( x ( 0 ) |
, x ( 0 ) , , x |
( 0 ) ) |
фиксируем все |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
n |
|
|
координаты |
вектора |
|
( x1 , x 2 , , x n ) |
|
кроме |
первой |
и |
находим |
точку |
||||||||
x |
|
||||||||||||||||
минимума |
x |
(1 ) |
функции F ( x |
1 |
) |
f |
( x |
1 |
, x ( 0 ) , , x ( 0 ) |
) . |
Получаем |
точку |
|||||
|
|
|
1 |
|
|
|
|
|
|
2 |
n |
|
|
|
|
||
( x (1 ) |
, x ( 0 ) , , x |
( 0 ) ) . Фиксируем в точке |
( x |
(1 ) |
, |
x ( 0 ) , , x ( 0 ) ) |
все координаты кроме |
||||||||||
1 |
2 |
n |
|
|
|
|
|
|
1 |
|
2 |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
второй и находим точку минимума x (1 ) |
функции F ( x |
2 |
) |
f ( x |
(1 ) |
, x |
2 |
, , |
x |
( 0 ) ) . |
||||||||||
|
2 |
|
|
|
|
|
|
|
1 |
|
|
|
|
n |
||||||
После n шагов завершаем первый цикл, получая точку x (1 ) ( x |
(1 ) |
, |
x (1 ) |
, , |
x |
(1 ) ) . |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
|
n |
Повторяем цикл до тех пор пока для некоторого заданного |
|
|
0 |
|
не будет |
|||||||||||||||
выполнено условие остановки: |
|
x ( k 1 ) |
x ( k ) |
|
|
для всех |
i |
1, |
2 , , n . |
|
При |
|||||||||
|
|
|
||||||||||||||||||
|
|
i |
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
выполнении этого условия полагаем |
|
* |
|
x ( k 1 ) . |
|
|
|
|
|
|
|
|
|
|
|
|
||||
x |
|
|
|
|
|
|
|
|
|
|
|
|
Симплекс-метод
Рассмотрим симплекс-метод для минимизации |
|
|||
переменных. |
Пусть задана |
начальная точка |
x ( 0 ) ( x ( 0 ) |
, |
|
|
|
1 |
|
симплекс с |
вершинами |
x (1 ) x ( 2 ) x ( 3 ) |
вычисляется |
|
функции двух |
x |
( 0 ) ) . Начальный |
|
2 |
|
по формулам: |
|
(1) |
|
|
( 0 ) |
|
1 |
|
|
|
|
( 0 ) |
|
|
|
1 |
|
|
|
|
( 2 ) |
|
|
( 0 ) |
|
1 |
|
( 0 ) |
|
1 |
|
|
|
|||
x |
|
x |
1 |
|
|
|
a , |
|
x |
2 |
|
|
|
|
|
|
|
a , |
x |
|
|
x |
1 |
|
|
a , x |
2 |
|
|
|
|
|
a , |
||
|
2 |
|
|
|
|
|
|
|
2 |
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
2 |
3 |
|
|
|
|
|
|
|
2 3 |
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
( 3 ) |
|
|
( 0 ) |
|
( 0 ) |
|
|
|
1 |
|
|
, |
где |
|
− |
длина |
|
ребра |
|
симплекса (выбирается |
||||||||||||||
x |
|
x |
1 |
, |
x 2 |
|
|
|
|
|
|
a |
a |
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
произвольным |
образом). |
|
|
Вычисляем |
значения |
f ( x (1 ) ) , |
|
f ( x ( 2 ) ) , f ( x ( 3 ) ) . |
Выбираем точку, в которой функция принимает наибольшее значение, и
заменяем её на новую точку x ( 4 ) . Если заменяем x (1 ) , то x ( 4 ) x ( 2 ) x ( 3 ) x (1 ) .
Если |
заменяем x ( 2 ) , |
то |
x ( 4 ) x (1 ) x ( 3 ) x ( 2 ) . |
Если |
заменяем |
x ( 3 ) , то |
x ( 4 ) |
x (1 ) x ( 2 ) x ( 3 ) . |
В |
результате получаем |
новый |
симплекс. |
Процесс |
продолжается до тех пор, пока вновь найденная вершина снова не потребует
замены. Если при этом длина ребра a меньше , то вычисления закончены и за приближенное значение x * берут точку из последнего симплекса, в которой функция принимает наименьшее значение. Если a , то необходимо
уменьшить размеры симплекса. Предположим, что последний симплекс имеет
вершины x ( k ) x ( k 1 ) |
x ( k 2 ) |
и в вершине x ( k ) |
целевая функция принимает |
наименьшее значение. |
Тогда |
новый симплекс |
x ( k ) x ( k 3 ) x ( k 4 ) имеет |
|
|
14 |
|
вершины x ( k 3 ) |
1 |
x ( k ) x ( k 1 ) , |
x ( k 4 ) |
1 |
x ( k ) x ( k 2 ) . Вычисления продол- |
|
2 |
2 |
|||||
|
|
|
|
жают до тех пор, пока длина ребра симплекса не станет меньше заданной точности .
Градиентные методы
Суть всех градиентных методов заключается в использовании вектора
градиента f |
|
f |
f |
f |
|
для определения направления движения к |
||
|
|
, |
|
, , |
|
|
||
|
|
|
||||||
|
|
x1 |
x 2 |
|
|
|
||
|
|
x n |
|
оптимальной точке. Общий алгоритм всех градиентных методов заключается в
построении из |
некоторой начальной точки |
x ( 0 ) последовательности |
приближений: |
x ( k 1 ) x ( k ) ( k ) S ( k ) , где S ( k ) – |
единичный вектор в |
направлении градиента целевой функции, ( k ) – величина шага в направлении градиента, k 0 , 1, .
Библиографический список
1.Алексеев, В.М. Сборник задач по оптимизации. Теория. Примеры. Задачи / В.М. Алексеев, Э.М. Галлеев, В.М. Тихомиров. – Москва: Физматлит, 2005. –
256с.
2.Васильев, Ф.П. Методы оптимизации / Ф.П. Васильев. – Москва: Факториал Пресс, 2002. – 824 с.
3.Лесин, В.В. Основы методов оптимизации: учеб. пособие / В. В. Лесин,
Ю.П. Лисовец. – 3-е изд., испр.– Санкт-Петербург: Издательство «Лань», 2011.
– 352 с.
4.Методы безусловной одномерной оптимизации: рек. к выполнению лаб. и
практ. работ / С.А. Шипилов. – Новокузнецк: НФИ КемГУ, 2001. – 24 с.
5.Методы безусловной многомерной оптимизации: рек. к выполнению лаб.,
практ. и курсовых работ / С.А. Шипилов. – Новокузнецк: НФИ КемГУ, 2000. –
31 с.
15
Методы оптимизации
Методические указания для проведения лабораторных работ
Палинчак Наталья Ференцовна
Редактор Т.А. Семенихина |
|
Подписано в печать |
Формат 60х84 1/16. |
Бумага офсетная. Ризография. Объем 1,0 п. л. Тираж 60 экз. Заказ №
Издательство Липецкого государственного технического университета. Полиграфическое подразделение Издательства ЛГТУ.
398055, Липецк, ул. Московская, 30
16