Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Владимирский государственный университет им. Столетовых

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

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

.pdf

Скачиваний:

Добавлен:

26.02.2023

Размер:

459.93 Кб

Скачать

☆

1 / 21 2 > Следующая >>>

3178

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра высшей математики

МЕТОДЫ ОПТИМИЗАЦИИ

Методические указания для проведения лабораторных работ

Н.Ф. Палинчак

Липецк Липецкий государственный технический университет

2017

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра высшей математики

МЕТОДЫ ОПТИМИЗАЦИИ

Методические указания для проведения лабораторных работ

Н.Ф. Палинчак

Липецк Липецкий государственный технический университет

2017

УДК 519.8

П142

Рецензент – д.-р техн. наук, проф. А.М. Шмырин

Палинчак, Н.Ф.

П142 Методы оптимизации: методические указания для проведения лабораторных работ [Текст] / Н.Ф. Палинчак. – Липецк: Изд-во Липецкого государственного технического университета, 2017. – 16 с.

Методические указания и задания составлены в соответствии с ФГОС-3 и

предназначены для студентов третьего и четвертого курсов физико-

технологического факультета по направлениям подготовки «Механика и математическое моделирование» и «Системный анализ».

Табл. 4. Библиогр. 5 назв.

университет», 2017

Лабораторная работа № 1

Методы одномерной безусловной оптимизации

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

Задание для лабораторной работы

1. Для заданной целевой функции (табл. 1) найти аналитическое решение

задачи одномерной минимизации f ( x ) min ,	x X ,	X R и найти
промежуток X R , на котором функция унимодальна.

2.Произвести графический анализ функции с отображением первой и второй ее производных.

3.Найти минимум функции методом обратного переменного шага для заданной точности и начальной точки x 0 .

4.Найти минимум функции методом Пауэлла для заданной точности и

начальной точки x 0 .

5.Определить начальный промежуток унимодальности a 0 , b0 , взяв за основу

первые несколько шагов метода обратного переменного шага.

6.Найти минимум функции методом локализации оптимума для заданной точности .

7.Определить минимум функции методом половинного деления для заданной точности и константы различимости .

8.Найти минимум функции методом золотого сечения с заданной точностью.

9.Произвести поиск минимума функции методом Фибоначчи для заданной точности и константы различимости .

10.Найти минимум функции (табл. 2) с использованием табличного процессора

Excel одним или несколькими методами по заданию преподавателя.

11.Проверить результаты вычислений с использованием надстроек Excel “Подбор параметра” и “Поиск решения”.

12.Сделать выводы об эффективности работы методов.

Таблица 1.

Варианты индивидуальных заданий для ручного расчета

№ вари-	Вид функции f ( x )												Нач. точка x 0	Точность	Константа
анта
1		x			2						2 x 1		-10	0, 6	0, 05
					2


2	x		2				15					x 5	5	0, 5	0, 04
			2


3	x		2				30					x 7	0	0, 5	0, 02
			2


4						x		2			5 x		-15	0, 5	0, 01
								2


5	5 x				2						35 x 1		18	0, 6	0, 03
					2


6			2 x					2			25 x		12	0, 5	0, 01
								2


7			3 x						2		15 x		-8	0, 7	0, 02
									2


8			5 x						2		2 x		10	0, 6	0, 02
									2


9	3 x				2						20 x 1		7	0, 5	0, 04
					2


10	2 x				2						45 x 5		-2	0, 6	0, 02
					2


11		6 x						2			88 x		5	0, 7	0, 02
								2


12					27				x 3 x				20	0, 45	0, 03
					27

13	x	2				12						x 10	5	0, 45	0, 03
		2


14	x	2				16						x 13	-5	0, 7	0, 04
		2


15	x		2							25 x 8			3	0, 5	0, 02
			2


16						x		2			9 x		14	0, 5	0, 03
								2


17						x		2			6 x		-12	0, 6	0, 04
								2


18				16					x 4 x				15	0, 6	0, 03
				16

19	9 x					2			5 x 3				-15	0, 5	0, 02
						2


20	3 x			2							38 x 2		8	0, 5	0, 01
				2


21	3 x				2			18 x 6					13	0, 6	0, 03
					2


22				x			2			15 x			10	0, 45	0, 02
							2


													4

Продолжение табл. 1

23			x		2			30						x 3					0	0, 6	0, 02
					2


24			x		2			28					x 2						-2	0, 5	0, 01
					2


25							8		x 2 x										-10	0, 55	0, 04
							8

																						Таблица 2.
														Варианты индивидуальных заданий для расчета в Excel

№ вари-	Вид функции f ( x )																		Нач. точка x 0	Точность		Константа
анта
1								x	3										10	0,06		0,015
									3
											x 2

							3
							3

2			x	3			6 x						2	9 x					8	0,05		0,01
				3									2


3										x		2							15	0,05		0,01
												2


									x 2

4								x	4										-20	0,05		0,01
									4
											x 3

							4
							4

5		x	4																12	0,06		0,02
			4
								2 x 2						( x 0 )

	4
	4

6													3						20	0,05		0,01
6				2 x 3									3			x		2	20	0,05		0,01
				2 x 3												x

7							( x 1)								2				10	0,07		0,02
															2


								x 2 1

8													x 2						-8	0,06		0,02
													2
								xe					2
								xe

9						x 2 ln											x		16	0,05		0,015

10																			15	0,06		0,02
10			3 x 2 ( x 5 )																15	0,06		0,02

11										x		2							-10	0,07		0,025
												2


									2 x

12		x	4																-13	0,065		0,02
			4
								2 x 2						( x 0 )

	4
	4

																			5

Продолжение табл. 2

13	( x	1 )	2	-12	0,045	0,01
			2


	x

14						x		2			3								18	0,07	0,025
								2


							x 2

15			4									3						2	-8	0,05	0,02
15	3 x 8 x												6 x						-8	0,05	0,02
	3 x 8 x												6 x

16										ln		x							25	0,05	0,01

											x

17					3 x							2							-13	0,06	0,02
17																			-13	0,06	0,02


						x 2

18		x	2		1														16	0,06	0,015
18																			16	0,06	0,015
											( x				0 )

				x
				x

19	(1		x				2			) ( x				3			1 )		-20	0,05	0,02
19																			-20	0,05	0,02


20					( 4				x )					3					-12	0,05	0,01
20																			-12	0,05	0,01


					9 ( 2 x )

21																			1	0,06	0,025
21				x					2 x 2										1	0,06	0,025

22	(1		x				2		) (1					x			3	)	14	0,045	0,01
22																			14	0,045	0,01


23																			-18	0,06	0,02
23			x 2											x					-18	0,06	0,02

24																			15	0,05	0,01
24	3 ( x 2 ) 2											( 2 x 1)							15	0,05	0,01

25				( x				5 ) e								x			-8	0,055	0,02
25																			-8	0,055	0,02


				Методические указания
Функция		f ( x )	называется унимодальной на отрезке a 0 ,					b0 ,	если она
непрерывна на		a 0 ,	b0 , и	существуют числа и			, a 0		b0 , для
которых выполняются следующие условия:
1)	на отрезке a 0 ,			функция	f ( x )	монотонно убывает;
2)	на отрезке , b0			функция	f ( x )	монотонно возрастает;

3) при x ,	f ( x ) f * min	f ( x ) .
	a 0 , b 0
Теорема. Если функция	f ( x ) дважды дифференцируема на отрезке a 0 , b0 и
f ( x ) 0 в любой точке этого отрезка, то		f ( x ) – унимодальная функция на
отрезке a 0 , b0 .

Метод обратного переменного шага

Пусть

функция

y f ( x )

является

унимодальной

на

некотором

промежутке. Предположим, что произвольная точка

x 0

этого

промежутка

является исходной для поиска точки

x *

локального минимума и число

–

заданная

точность

нахождения

x * .

Обозначим

через

произвольное

приращение аргумента x .

Вычислить x1

x 0

0 , y 0

f ( x 0 )

f ( x1 )

f ( x 0

0 ) .

Если

то

x (1 ) x

Вычислить

x ( 0 )

(1 )

(1 ) f ( x (1 ) ) ,

y (1 ) f ( x

(1 ) )

f ( x

) .

Если y

(1 )

y (1 )

то

x ( 2 )

(1 )

и т. д. На некотором

k -

м шаге

y ( k ) y

( k ) .

Если при этом

, то принимаем

* x ( k ) .

противном

случае

переходим

3.,

точка

x ( k )

является

исходной для

продолжения вычислений.

Если

y 0 , то

x 0 x1 –

начальная

точка

вычисления,

–

приращение аргумента ( 0

1 ).

Далее вычисления продолжаем по 2. или 3.

до достижения заданной точности.

4. Если y

, то

x *

x 0 x1

при

. В противном случае перейти к 3.

Метод Пауэлла

Пусть задана начальная точка

x 0 ,

приращение

x 0 ,

–

заданная

точность.

Вычислить x1

x 0

x , y 0

f ( x 0 )

f ( x1 ) .

2.	Вычислить x 2 . Если y 0							y1 ,		то x 2		x 0 2 x . Если				y 0		y1 ,			то x 2		x 0 x .
Вычислить y 2		f ( x 2 ) .
3.	Вычислить			x	1	x	0		a	1	,	где				1			y	2	y	0		y	1	y	0	,
3.	Вычислить		x		1		0			1	,	где	a	2						2		0			1		0	,
						2			2 a 2					2	x 2	x			x 2		x 0			x1 x
						2			2 a 2						x 2	x	1		x 2		x 0			x1 x			0

y y

x1 x 0

4.Вычислить f ( x ) .01 .a

Найти y min

y 0 , y1 , y 2 и точку x min , соответствующую y min .

x *

Если

, то

. Иначе перейти к следующему пункту.

min

Выбрать из точек x min

ту, где значение функции меньше, и две точки по

обе стороны от неё. Если выбранная точка является «крайней», то отбрасывается точка с наибольшим значением функции. Перейти к 3.

Метод локализации оптимума

Пусть задан интервал a , b – промежуток унимодальности функции f ( x ) и

– заданная точность.

Найти шаг разбиения

b a

. Если h ,

то x *

a b

. В

противном

случае перейти к 2.

Вычислить x1 a h ,

x 2

a 2 h , x 3 a 3 h .

Вычислить f ( x1 ) , f ( x 2 ) ,

f ( x 3 ) .

Найти y min

f ( x1 ),

( x 2 ),

f ( x 3 ) и точку x min

, соответствующую y min .

x min

h ,

x min

–

новый промежуток

унимодальности.

Обозначить

x min h

a ,

x min

h b

и перейти к 1.

Общая схема сужения промежутка унимодальности

Пусть функция y f ( x ) является унимодальной		на отрезке a 0 , b0 .
Возьмём внутри отрезка a 0 , b0 две точки x1 и	x 2 : a 0 x1	x 2 b0 . Вычислим
8

f ( x	1	)	и f			( x		2	) . Если	f ( x			1	) f ( x			2	) ,	то	точка				минимума x *	находится на
	1							2					1				2
отрезке				a	0	, x		2	. Если f	( x	1	)		f ( x	2	)		, то x *		находится на отрезке					x	1	, b	0	. Если
					0			2			1				2											1		0
f ( x	1	)		f ( x		2	)	, то x * находится на отрезке												x	1	, x	2	. Вычисления заканчиваются,
	1					2															1		2
когда длина интервала,										содержащего									x * ,	становится меньше точности									. В

качестве точки локального минимума можно приближенно принять середину последнего отрезка.

Различные методы				отличаются выбором точек x1 и x 2 . В методе
половинного деления точки x1						и x 2	выбираются на расстоянии от середины
отрезка: x		a 0 b0	, x		a 0	b0	.
	1	2		2		2

В методе золотого сечения точки x1 и x 2 располагаются симметрично относительно середины отрезка и делят его в пропорции золотого сечения:

x1	3	5	( b0 a 0 ) a 0 ,	x 2	5	1	( b0	a 0 ) a 0 . Кроме того, x1 является
	2				2

золотым сечением отрезка a 0 , x 2						,	а	x 2 – золотым сечением отрезка x1 , b0 ,

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

Метод Фибоначчи аналогичен методу золотого сечения, только выбор точек происходит на основе других соотношений. Последовательность чисел

Фибоначчи

определяется

следующим образом:

F 0

F1 0 , Fi

Fi 1 Fi 2 ,

i 2 , 3, До начала вычислений определяют число n

вычислений функции из

условия

a 0

Точки,

которых

производятся

вычисления,

определяются по следующим формулам:

x ( k )

F n k 2

( b

) , x

( k )

Fn k 1

( b

) , k 0 ,1, , n 2 .

F n k

При

k n 2 точки x

( k )

и x

( k )

совпадают и соответствуют середине отрезка.

Поэтому полагаем x

( n 2 )

x ( n 2 )

и заканчиваем вычисления.

1 / 21 2 > Следующая >>>

Соседние файлы в папке новая папка 1

#
26.02.2023552.85 Кб1641013.pdf
#
26.02.2023433.67 Кб0641025.pdf
#
26.02.2023372.32 Кб0641029.pdf
#
26.02.2023490.99 Кб0641038.pdf
#
26.02.2023473.2 Кб0641039.pdf
#
26.02.2023459.93 Кб1641041.pdf
#
26.02.2023607.81 Кб0641042.pdf
#
26.02.2023258.4 Кб0641044.pdf
#
26.02.20232.16 Mб4641047.pdf
#
26.02.2023465.01 Кб2641052.pdf
#
26.02.2023378.87 Кб0641637.pdf