новая папка 1 / 641041

Лабораторная работа № 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