Задания - 2004 / Задания / Job-13

(С) ИиКМ РХТУ январь 2004г. Калинкин Владимир Николаевич

1

Многомерная оптимизация.

Определение минимума или максимума функции многих переменных с заданной точностью ε при заданных границах поиска по каждой переменной [a1;b1], [a2;b2],…..,[an;bn]

																							→(0)
либо, вместо границ, может быть задано начальное приближение x .
								Градиентный метод.
Приближения к решению вычисляем по следующей итерационной формуле
→(k )	→(k −1)			→(k −1)																			пока шаг станет
x	= x	− h(k ) V					, где k=1,2,3,…,n. Итерации повторяются,
												→(k )	→(k −1)									→ →					1
неудачным и не выполнится условие ||												x	− x	||≤ ε . Вектор V									=	G					- это
																											→
																										|| G ||
									→
нормированный вектор градиента G .
Пример: Уточнить минимум функции двух переменных																			→		=(x2			+ x			−11)2			+(x			+ x2 −7)2
																		f ( x)								2
																							1								1		2
							→(0)		1	(1)			→	4	x2		+4	x	x		2	+	2 x2		−42 x					−14
с точностью ε =0,01 при x								= и h				=1. G =			1			1						2					1
															3									2	−26 x2 −
									1					4	x2		+4 x1 x2 +2 x1														22
i	→(k −1)			→(k −1)			→ (k −1)		→			→(k −1)		h(k )			→(k )					→(k )				| | h(k )			|≤ ε			примечание
	x			f ( x	)		G		|| G ||			V					x			f ( x				)
1	1,0000			106,00000			-46,000		59,666			-0,771		1,000			1,7710			45,27395							нет					шаг удачный
	1,0000						-38,000					-0,637					1,6369
2	1,7710			45,27395			-49,209		57,194			-0,860		1,000			2,6314			3,77986							нет					шаг удачный
	1,6369						-29,148					-0,510					2,1465
3	2,6314			3,77986			-19,831		19,913			-0,996		1,000			3,6272			21,97380							нет					шаг неудачный
	2,1465						-1,808					-0,091					2,2373
4	2,6314			3,77986			-19,831		19,913			-0,996		0,333			2,9630			0,49362							нет					шаг удачный
	2,1465						-1,808					-0,091					2,1767
5	2,9630			0,49362			0,881		6,081			0,145		0,333			2,9147			0,88443							нет					шаг неудачный
	2,1767						6,017					0,989					1,8473
6	2,9630			0,49362			0,881		6,081			0,145		0,111			2,9469			0,10991							нет					шаг удачный
	2,1767						6,017					0,989					2,0669
7	2,9469			0,10991			-2,495		2,820			-0,885		0,111			3,0451			0,09424							нет					шаг удачный
	2,0669						1,313					0,466					2,0152
8	3,0451			0,09424			3,721		3,987			0,933		0,111			2,9415			0,16288							нет					шаг неудачный
	2,0152						1,432					0,359					1,9753
9	3,0451			0,09424			3,721		3,987			0,933		0,037			3,0106			0,00464							нет					шаг удачный
	2,0152						1,432					0,359					2,0019
10	3,0106			0,00464			0,827		0,872			0,948		0,037			2,9755			0,02844							нет					шаг неудачный
	2,0019						0,278					0,318					1,9901
11	3,0106			0,00464			0,827		0,872			0,948		0,012			2,9992			0,00011							нет					шаг удачный
	2,0019						0,278					0,318					1,9981
12	2,9992			0,00011			-0,095		0,124			-0,767		0,012			3,0084			0,00419							нет					шаг неудачный
	1,9981						-0,080					-0,642					2,0058
13	2,9992			0,00011			-0,095		0,124			-0,767		0,004			3,0023			0,00023							да					шаг удачный
	1,9981						-0,080					-0,642					2,0007
14	3,0023			0,00023			0,183		0,195			0,936		0,004			2,9985			0,00011							да					шаг удачный
	2,0007						0,069					0,351					1,9993
15	2,9985			0,00011			-0,122		0,134			-0,915		0,004			3,0022			0,00023							да					шаг неудачный
	1,9993						-0,054					-0,404					2,0009
	→*	=	2,998			0,01			→*
Ответ: x					±				f ( x ) = 0,00011
			1,999			0,01

(С) ИиКМ РХТУ январь 2004г. Калинкин Владимир Николаевич																					2
												Симплексный метод.
Строим симплекс в двух мерном пространстве (прямоугольный треугольник) за одну из
									→(0)		координаты других рассчитываем как,
вершин принимаем точку x
→(1)		→(0)		0		→(2)	→(0)			h			→отраж	→ост1		→ост2			→худш
x	= x		+			x	= x		+		, а отраженной x			= x	+ x			− x
				h						0
пример: Пример: Уточнить минимум функции двух переменных
→															→(0)			= 0.5 и h(1) =1.
f ( x) =(x2 + x					2	−11)2 +(x			+ x2		−7)2	с точностью ε =0,01 при x
			1				1			2
																		0.5
i			→(0)			→(0)			→(1)			→(1)	→(2)	→(2)
			x			f ( x	)			x		f ( x )	x	f ( x	)			h		примечание	h <ε
1		0,5000				144,12500			0,5000			103,62500	1,5000	95,62500				1
		0,5000							1,5000				0,5000							отражаем x0
2		1,5000				63,12500			0,5000			103,62500	1,5000	95,62500				1		удачно
		1,5000							1,5000				0,5000							отражаем x1
3		1,5000				63,12500			2,5000			36,12500	1,5000	95,62500				1		удачно
		1,5000							0,5000				0,5000							отражаем x2
4		1,5000				63,12500			2,5000			36,12500	2,5000	15,62500				1		удачно
		1,5000							0,5000				1,5000							отражаем x0
5		3,5000				13,62500			2,5000			36,12500	2,5000	15,62500				1		удачно
		0,5000							0,5000				1,5000							отражаем x1
6		3,5000				13,62500			3,5000			9,12500	2,5000	15,62500				1		удачно
		0,5000							1,5000				1,5000							отражаем x2
7		3,5000				13,62500			3,5000			9,12500	4,5000	100,12500				1		не удачно	нет
		0,5000							1,5000				0,5000							строим нов. симпл.
8		3,5000				9,12500			3,5000			9,52452	3,8330	27,79660				0,333
		1,5000							1,8330				1,5000							отражаем x2
9		3,5000				9,12500			3,5000			9,52452	3,1670	0,96841				0,333		удачно
		1,5000							1,8330				1,8330							отражаем x1
10		3,5000				9,12500			3,1670			2,78667	3,1670	0,96841				0,333		удачно
		1,5000							1,5000				1,8330							отражаем x0
11		2,8340				1,93905			3,1670			2,78667	3,1670	0,96841				0,333		удачно
		1,8330							1,5000				1,8330							отражаем x1
12		2,8340				1,93905			2,8340			0,92012	3,1670	0,96841				0,333		удачно
		1,8330							2,1660				1,8330							отражаем x0
13		3,1670				2,16727			2,8340			0,92012	3,1670	0,96841				0,333		не удачно	нет
		2,1660							2,1660				1,8330							строим нов. симпл.
14		2,8340				0,92012			2,8340			1,51590	2,9450	0,43112				0,111		удачно
		2,1660							2,2770				2,1660							отражаем x1
15		2,8340				0,92012			2,9450			0,10220	2,9450	0,43112				0,111		удачно
		2,1660							2,0550				2,1660							отражаем x0
16		3,0560				0,23320			2,9450			0,10220	2,9450	0,43112				0,111		удачно
		2,0550							2,0550				2,1660							отражаем x2
17		3,0560				0,23320			2,9450			0,10220	3,0560	0,10735				0,111		удачно
		2,0550							2,0550				1,9440							отражаем x0
18		2,9450				0,22277			2,9450			0,10220	3,0560	0,10735				0,111		удачно
		1,9440							2,0550				1,9440							отражаем x0
19		3,0560				0,23320			2,9450			0,10220	3,0560	0,10735				0,111		не удачно	нет
		2,0550							2,0550				1,9440							строим нов. симпл.
20		2,9450				0,10220			2,9450			0,15635	2,9810	0,04506				0,036
		2,0550							2,0910				2,0550							отражаем x1

(С) ИиКМ РХТУ январь 2004г. Калинкин Владимир Николаевич												3
21	2,9450	0,10220				2,9810	0,01225	2,9810	0,04506	0,036	удачно
	2,0550					2,0190		2,0550			отражаем x0
22	3,0170	0,02343				2,9810	0,01225	2,9810	0,04506	0,036	удачно
	2,0190					2,0190		2,0550			отражаем x2
23	3,0170	0,02343				2,9810	0,01225	3,0170	0,00985	0,036	удачно
	2,0190					2,0190		1,9830			отражаем x0
24	2,9810	0,02459				2,9810	0,01225	3,0170	0,00985	0,036	не удачно	нет
	1,9830					2,0190		1,9830			строим нов. симпл.
25	3,0170	0,00985				3,0170	0,00947	3,0290	0,02641	0,012
	1,9830					1,9950		1,9830			отражаем x2
26	3,0170	0,00985				3,0170	0,00947	3,0050	0,00085	0,012	удачно
	1,9830					1,9950		1,9950			отражаем x0
27	3,0050	0,00246				3,0170	0,00947	3,0050	0,00085	0,012	удачно
	2,0070					1,9950		1,9950			отражаем x1
28	3,0050	0,00246				2,9930	0,00166	3,0050	0,00085	0,012	удачно
	2,0070					2,0070		1,9950			отражаем x0
29	2,9930	0,00293				2,9930	0,00166	3,0050	0,00085	0,012	не удачно	нет
	1,9950					2,0070		1,9950			строим нов. симпл.
30	3,0050	0,00085				3,0050	0,00084	3,0090	0,00253	0,004
	1,9950					1,9990		1,9950			отражаем x2
31	3,0050	0,00085				3,0050	0,00084	3,0010	0,00003	0,004	удачно
	1,9950					1,9990		1,9990			отражаем x0
32	3,0010	0,00025				3,0050	0,00084	3,0010	0,00003	0,004	удачно
	2,0030					1,9990		1,9990			отражаем x1
33	3,0010	0,00025				2,9970	0,00031	3,0010	0,00003	0,004	удачно
	2,0030					2,0030		1,9990			отражаем x1
34	3,0010	0,00025				3,0050	0,00084	3,0010	0,00003	0,004	не удачно	да
	2,0030					1,9990		1,9990
	→*	3.001		0,01			→*
Ответ: x =			±				f ( x ) =0,00003
		1,999		0,01

Задания.

Уточнить точку минимума для заданной функции двумя методами, с точность ε =0.01 и h =1

1	f (x , x			) = (x		−1)2 +(x					−1)2				− x		x					→0	=	3
		2								2										2		начальное приближение x
	1				1											1
																								3
2	f (x , x				) = x4	+ 2 x2			− x			x										→0	=	3
			2											2								начальное приближение x
	1				1			2			1
																								3
3	f (x , x				) = (2 x			− x2 )2 +10							(1 − x )2							→0	=	2
			2				2															начальное приближение x
	1							1										1
																								1
4	f (x , x				) = x2	+ x		2 + x		x			+ x − x						+1			→0	=	0
			2									2						2				начальное приближение x
	1				1			2	1						1
																								0
5	f (x , x				) = (x	−1.1)2			+(x				−1.1)2 − x x									→0	=	3
			2									2									2	начальное приближение x
	1				1															1
																								3
6	f (x , x				) = x4	+ 2 x2			−1.1 x						x							→0	=	3
			2													2						начальное приближение x
	1				1			2						1
																								3

(С) ИиКМ РХТУ январь 2004г. Калинкин Владимир Николаевич

7	f (x , x	2		) =1.1 (2 x									2		− x2 )2						+10 (1 − x )2																														начальное приближение
	1																1																	1
8	f (x , x	2	) = x2					+ x			2	+ x					x		2	+1.1 x										−1.1 x										2	+1										начальное приближение
	1						1			2					1													1
9	f (x , x	2	) =(x					−1.2)2 +(x										2		−1.2)2 − x x																2															начальное приближение
	1						1																								1
10	f (x , x			2			) = x	4	+ 2 x						2		−1.2 x									x		2																							начальное приближение
	1						1								2									1
11	f (x , x		2			) =1.2 (2 x									2	− x2 )2 +10 (1 − x )2																																			начальное приближение
	1																		1																	1
12	f (x , x			2			) = x	2	+ x2				+ x x							2	+1.2 x										−1.2 x										2	+1									начальное приближение
	1						1				2						1													1
13	f (x , x		2			) = (x			−1)2				+(1.1 x									2		−1)2						−1.1 x x													2								начальное приближение
	1							1																															1
14	f (x , x			2			) =1.1 x4					+ 2 1.1 x											2		− x				x			2																			начальное приближение
	1										1											2						1
15	f (x , x		2			) =(2 x				2	− x				2 )2 +10 (1.1− x )2																																				начальное приближение
	1													1																	1
16	f (x , x			2			) = x	2	+ x2				+1.1 x								x				2		+ x				− x				2			+1.1													начальное приближение
	1						1				2									1									1
17	f (x , x			2			) = (x		−1.1)2								+(1.1 x								2		−1.1)2							−1.1 x											x				2		начальное приближение
	1							1																																			1
18	f (x , x		2			) =1.1 x4						+ 2 1.1 x											2		−1.1 x									x				2													начальное приближение
	1										1											2										1
19	f (x , x			2			) =1.1 (2 x								2	− x2 )2 +10 (1.1 − x )2																																			начальное приближение
	1																		1																				1
20	f (x , x				2		) = x2		+ x			2	+1.1 x								x					2	+1.1 x										−1.1 x									2		+1.1			начальное приближение
	1						1					2								1														1
21	f (x , x			2			) = (x −1.2)2										+(1.1 x									2	−1.2)2							−1.1 x											x					2	начальное приближение
	1							1																																				1
22	f (x , x				2		) =1.1 x4					+ 2 1.1 x2														−1.2 x								x					2												начальное приближение
	1										1												2										1
23	f (x , x			2			) =1.2 (2 x							2		− x			2 )2 +10 (1.1− x )2																																начальное приближение
	1																1																				1
24	f (x , x				2		) = x2		+ x			2	+1.1 x								x					2	+1.2 x										−1.2 x										2		+1.1		начальное приближение
	1						1					2								1															1
25	f (x , x				2		) = (x		−1)2 +(1.2 x														2		−1)2 −1.2 x																x			2							начальное приближение
	1							1																																1
26	f (x , x				2		) =1.2 x4 + 2 1.2 x																	2		− x				x			2																		начальное приближение
	1										1													2				1
27	f (x , x				2		) = (2 x				2	− x				2 )2			+10 (1.2 − x )2																																начальное приближение
	1														1																		1

4

→0	2
x	=
	1
→0	0
x	=
	0
→0	3
x	=
	3
→0	3
x	=
	3
→0	2
x	=
	1
→0	0
x	=
	0
→0	3
x	=
	3
→0	3
x	=
	3
→0	2
x	=
	1
→0	0
x	=
	0
→0	3
x	=
	3
→0	3
x	=
	3
→0	2
x	=
	1
→0	0
x	=
	0
→0	3
x	=
	3
→0	3
x	=
	3
→0	2
x	=
	1
→0	0
x	=
	0
→0	3
x	=
	3
→0	3
x	=
	3
→0	2
x	=
	1

(С) ИиКМ РХТУ январь 2004г. Калинкин Владимир Николаевич

28	f (x , x			2	) = x2	+ x2	+1.2 x				x	2	+ x − x		2	+1.2							начальное приближение
	1				1	2				1			1
29	f (x , x			2	) = (x	−1.1)2				+(1.2 x		2	−1.1)2	−1.2 x				x			2		начальное приближение
	1				1												1
30	f (x , x			2	) =1.2 x4		+ 2 1.2 x2					−1.1 x		x			2						начальное приближение
	1					1					2		1
31	f (x , x		2		) =1.1 (2 x			2		− x2 )2	+10 (1.2 − x )2												начальное приближение
	1									1							1
32	f (x , x			2	) = x2	+ x2	+1.2 x				x	2	+1.1 x			−1.1 x		2		+1.2			начальное приближение
	1				1	2				1				1
33	f (x , x		2		) = (x −1.2)2					+(1.2 x		2	−1.2)2 −1.2 x					x				2	начальное приближение
	1				1												1
34	f (x , x			2	) =1.2 x4		+ 2 1.2 x2					−1.2 x		x			2						начальное приближение
	1					1					2		1
35	f (x , x		2		) =1.2 (2 x				2	− x2 )2 +10 (1.2 − x )2													начальное приближение
	1									1							1
36	f (x	, x		2	) = x2	+ x2	+1.2 x				x	2	+1.2 x			−1.2 x			2	+1.2			начальное приближение
	1				1	2				1				1

→0

x

→0

x

→0

x

→0

x

→0

x

→0

x

→0

x

→0

x

→0

x

5

0 = 0

3 = 3

3 = 3

2 = 1

0 = 0

3 = 3

3 = 3

2 = 1

0 = 0