ТЕОРИЯ ОПТИМИЗАЦИИ И Алгоритмов / Методы_оптимизации

131

Задача 2. Заданы задача безусловной минимизации f (x)→ min,

x R2 ,

где f(x) – квадратичная функция, допустимая погрешность ε, начальная точка x(0). Решить задачу методом Ньютона.

Контрольная работа №4

Контролируемые разделы курса: метод аппроксимирующего программирования, метод штрафных функций.

В контрольную работу включены две задачи.

Задача 1а. Метод аппроксимирующего программирования. Заданы задача условной минимизации

f (x)→ min, p1(x)≤ b1, p2 (x)≥ b2,

x R+2 ,

начальная точка x(0). Произвести линеаризацию исходной задачи

(составить задачу линейного программирования) в окрестности точки x(0).

Задача 1б. Метод аппроксимирующего программирования. Заданы задача условной минимизации

f (x)→ min, p1(x)≤ b1, p2 (x)≥ b2,

x R+2 ,

текущая точка x(k-1), константа β (0<β<1). Известно решение x0 задачи линейного программирования, полученной в результате линеаризации исходной задачи в окрестности точки x(k-1). Определить точку x(k).

Задача 2а. Метод штрафных функций. Заданы задача условной минимизации

132

f (x)→ min, p1(x)≤ b1, p2 (x)≥ b2, x R2 ,

начальная точка x[0], начальное значение штрафного параметра R0. Составить расширенную функцию P(x, R0).

Задача 2б. Метод штрафных функций. Задана задача условной минимизации

f (x)→ min, p(x)≤ b,

x R.

Решить аналитически методом внешней точки.

Контрольная работа №5

Контролируемые разделы курса: метод отсечений, метод ветвей и границ.

В контрольную работу включены две задачи.

Задача 1. Метод отсечений. Рассматривается задача целочисленного линейного программирования. Задана итоговая сим- плекс-таблица задачи L1. Составить начальную симплекс-таблицу

задачи L2.

Задача 2. Метод ветвей и границ. Задана задача целочисленного линейного программирования

f (x)→ max, p1(x)≤ b1, p2 (x)≤ b2,

x R+2 ; x1, x2 − целые.

Выполнить нулевой и первый этапы метода ветвей и гра-

ниц.

133

ОТВЕТЫ

1. Задача безусловной оптимизации

1.Функция f (x) = 1− x3 экстремумов не имеет.

2.Функция f (x) = 1− x4 имеет в точке x = 0 глобальный максимум.

	3.	Функция	f (x) = x4 − 4x3 + 4x2 −1 имеет в точках x = 0 и
x = 2	глобальный минимум, а в точке x = 1												− локальный макси-
мум.
	4.	Функция	f (x) = x2x		− 3x x − x + 2x									+ 5	локальных экс-
тремумов не имеет.			1	2				1	2		1	2
	5.	Функция	f (x) = x3	+ x3 − 3x x							имеет в точке						x = (1, 1)
			1			2			1	2
локальный минимум.
	6.	Точка x = (1, 2, 0) является точкой локального миниму-
ма	функции		f (x) = 2x x			2	x	3	+ x2		+ x2	+ x2			− 4x x	3	− 2x	2	x	−
				1						1	2			3	1					3

−2x1 − 4x2 + 4x3 .

7.Точка x = (2, 1) является точкой локального минимума

функции		f (x) = x3 + x3 − 3x2 − 3x x											+ 3x		+ 3x −1.
						1	2		1	1	2			1			2
2.		Задача условной оптимизации
1.		Функция					f (x) = x1 + x2					в допустимой									области X =
={x R	2	: x	2	+ x	2	= 1} имеет в точке x =											2	,	2		условный ло-
			1		2
																2			2
кальный максимум, а в точке										x =			−	2	, −			2		− условный ло-
														2				2
кальный минимум.
2.		Функция					f (x) = x2			+ x2		+ x2			в		допустимой области
									1		2			3
X = {x R3 : 4x2						+ x2 + 2x		3	= 14}		имеет в						точках				x = (2, 2, 1) и
				1			2

							134
x = (2, − 2, 1) условные локальные минимумы.
		a			a		a
3. Точка x	=			,		,		является	точкой					условного мак-
					3
		3					3
симума функции				f (x) = x1x2 x3 в					допустимой									области
X = {x R3 : x + x	2	+ x		3	= a}.
1
3. Квадратичное программирование
1. Выполняются 0-я итерация: Б0={z1, z2, w1, w2}, ДБР0=(6,
															1			1		1
3, 1, 4); 1-я итерация: Б1={z1, x2, w1, w2}, ДБР1=														4,			,		, 2		;
															2			2		2
										3		1			1
2-я итерация: Б2={z1, x1, w1, w2}, ДБР2=									3,		,			, 2			; 3-я ите-
										4		4			2

рация: Б3={z1, x1, v2, w2}, ДБР3=(2, 1, 1, 2); 4-я итерация: Б4={λ1, x1, v2, w2}, ДБР4=(2, 1, 3, 2). В результате получаем x = (1, 0) , f = −4 .

2. Выполняются 0-я итерация: Б0={z1, z2, w1, w2}, ДБР0=(1, 2, 6, 4); 1-я итерация: Б1={z1, x2, w1, w2}, ДБР1=(1, 1, 4, 2); 2-я ите-

																	4			2
	рация: Б2={z1,				x2, x1,	w2},				ДБР2= 1,					1,				,		; 3-я итерация:
																	3			3
								1			2		5			1
	Б3=={λ2, x2, x1, w2}, ДБР3=									,		, 1		,	1		. В результате получа-
									3		3		9			9
	5			2
							4
	ем x = 1		,		, f = 2			.
				3			9
	9

4. Численные методы минимизации унимодальных функций

1. а) ∆8 = [0,85;1,65] , x 1,55 , f −0,2475 ; б) ∆9 = [1,2; 2,0] , x 1,6 , f −0,24 .

			135
2.	∆8	= [1,219;1,563] ,	x 1,463 ,	f −0,2486.
3.	∆4	= [0,88;1,76] , x 1,56 , f		−0,2464.
4.	∆4	= [0,944;1,888] ,	x 1,528 ,	f −0,2492.

5. Численные методы оптимизации многоэкстремальных функций

1.x 3,0, f −1,704.

2.x 3,17, f −1,993.

3.x 3,25, f −1,980.

6. Градиентные методы

1. Выполняются 0-я итерация, 1-я и 2-я итерации при λ = 1, 3-я итерация при λ = 0,5 , 4-я итерация при λ = 0,25 . В ре-

зультате получаем x (1,007; −0,166), f −6,111.

2.	Выполняются					0-я		итерация, 1-я итерация при
λ1 = 0,256 , 2-я итерация при							λ2 = 0,478. В результате получаем
x (0,979;−0,201) ,					f −6,120.
7. Метод Ньютона
				1,2	0,1	−
							0,5
1.	A	−1		2,2	0,6	− 1
			=					.
			−1,8		− 0,4		1

2.Выполняются 0-я и 1-я итерации, получаем точное ре-

шение x = (1;−0,25) , f = −6,125.

3.Выполняются 0-я, 1-я и 2-я итерации. В результате по-

лучаем x (1,033; 4,033) , f −9,997.

8. Метод аппроксимирующего программирования

1. x0 = (13,5; 0), λ1 = 0,0625. В результате получаем

136

x (1) = (4,594; 2,813).

= (0,5; 6,9),

2.

Выполняются

1-я итерация: x 0

λ = 0,24,

x (1) = (2,40;1,66);

= (2,49; 2,03),

1

= 0,7,

2-я

итерация:

x 0

λ2

x (2) = (2,46;1,92).

В

результате

получаем

x (2,46;1,92) ,

f

4,38.

9. Метод штрафных функций

x(1) (R) =

4 + 5R

4 + 5R

1.

а)

Стационарная

точка

,

,

x = (2,5; 2,5) ,

f = 4,5;

1+ 2R

1+ 2R

б)

допустимая

(внутренняя)

стационарная

точка

x

(R) =

13 − 9 + 4R

,

13 − 9 + 4R

,

x

= (2,5; 2,5) ,

f

= 4,5.

(1)

4

4

2.

Допустимая

(внутренняя)

стационарная

точка

x

(R) =

1+ 9 + 8R

,

5 +12R + 9 + 8R

,

x

= (1,1) ,

f

= 2.

(1)

4

8

10. Метод отсечений

x(0)

1

(x(0))= 13;

1. Решаются задача L0:

= 0, 6

,

f

задача

2

L1: x(1) = (0, 6),

f (x(1))= 12. В

x = (0, 6),

результате

получаем

f = 12 .

(0)

1

4

(0)

2

2. Решаются задача L0: x

= 3

, 1

,

f (x

) =

12

; за-

2

5

5

8

5

(1)

=

(1)

) =

2

дача L1: x

3

, 1

,

f (x

12

; задача L2 (производящая

18

9

9

строка x2 ): x(2)

= (3,

2),

f (x(2) ) = 12 .

В

результате получаем

																				137
	x		= (3, 2) , f = 12 .
					11. Метод ветвей и границ
																												1
					1. Решается задача L0:															x(0) = 0, 6											,	ξ 0 = 13,								Θ0 = −∞
																											2
	(ветвление								из			0-й		вершины						по			x2(0) ).						Решается									задача							L1:
	x(1)				1					ξ 1 = 12				1			Θ1 = −∞ ; задача L2 не имеет допустимых
				=			, 6		,						,
					4									4
	решений: Θ2									= −∞ (ветвление из 1-й вершины по x(1)). Решаются
																																			1									1
	задача L3: x(3) = (0, 6), ξ 3 = 12,																			Θ3		= 12; задача L4: x(4) =
																																									1, 4						,
																																												2
				= 10 , Θ4 = 12. В результате получаем x = (0, 6),
	ξ 4																																				f = 12.
																				(0)				1			4						0					3				0
					2. Решается задача L0: x																=		3			, 1			,			ξ		= 10					,	Θ			= −∞
																								2														5
																											5
	(ветвление								из			0-й		вершины						по			x	(0) ).				Решаются										задача							L1:
																							1
		(1)								1					1												(2)								1					2					2
	x			= (3, 2) , î							= 10 , Θ = 10 ; задача L2: x																				=		4, 1					, ξ			= 10							,
																																			5										5
	Θ2			= 10			(ветвление из 2-й вершины по x2(2) ). Решается задача L3:
		(3)					1					3			1			3
	x			=	4			, 1		, ξ			= 10				, Θ		= 10 ; задача L4 не имеет допустимых
							6								3
	решений: Θ4									= 10			(ветвление из 3-й вершины по x(3) ). Решаются
																																			1
	задача L5: x(5)										= (4, 1) ,						ξ 5 = 10 , Θ5						= 10 ; задача L6:															x(6)			= (5, 0) ,
	ξ 6		= 10 ,								Θ6 = 10 .								В						результате														получаем
	x		= {(3, 2), либо (4, 1), либо (5, 0)},																				f = 10.

138

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1.Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимизации: Учеб. для студ. втузов. − М.: Изд-во МГТУ, 2001.

2.Банди Б. Методы оптимизации. Вводный курс. – М.: Радио и связь, 1988.

3.Карманов В.Г. Математическое программирование. − М.: Физматлит, 2000.

4.Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. – М.: Наука, 1969.

5.Лесин В.В., Лисовец Ю.П. Основы методов оптимиза-

ции: Учеб. пособие для втузов. − М.: Изд-во МАИ, 1995.

6.Мину М. Математическое программирование. – М.:

Наука, 1990.

7.Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978.

8.Растригин Л.А. Системы экстремального управления. −

М.: Наука, 1974.

9.Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: В 2-х кн. – М.: Мир, 1986.

10.Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. – М.: Наука, 1986.

11.Таха Х. Введение в исследование операций: В 2-х кн. –

М.: Мир, 1985.

12.Химмельблау Д. Прикладное нелинейное программирование. – М.: Мир, 1975.

139

СОДЕРЖАНИЕ

Введение……………………………………………………...…….3

1.Задача безусловной оптимизации….………....…...……..…….5

1.1.Функция одной переменной……………………………...…..6

1.2.Функция многих переменных……………………………….12

2.Задача условной оптимизации………………………………...18

3.Квадратичное программирование……………..….…………..26

4.Численные методы оптимизации унимодальных функций…35

4.1.Пассивный метод поиска минимума………………………..36

4.2.Активные методы поиска минимума……………………….38

5.Численные методы оптимизации многоэкстремальных функций.…...…………………………………………….…...……47

6.Градиентные методы………………...……………...………….56

7.Метод Ньютона….………………………...………….………...63

8.Метод аппроксимирующего программирования…………….70

9.Метод штрафных функций…………………………………….80

10.Методы отсечений…………………………………………….91

11.Метод ветвей и границ……………………………………....103

Индивидуальные задания «Задача выбора портфеля ценных бумаг»………………………………….………...……………….116 Контрольные работы………………………………………….…129

Ответы…………………………………………………………….133

Библиографический список….……………………………..…...138

140

Харчистов Борис Федорович

Методы оптимизации

Учебное пособие

Ответственный за выпуск Харчистов Б.Ф. Редактор Проценко И.А. Корректор Селезнева Н.И.

ЛР № 020565 от 23.06.1997 г. Подписано к печати 20.04.2004 г.

Формат 60×84 116 . Бумага офсетная.

Офсетная печать. Усл. п. л. − 8,7. Уч.-изд. л. – 8,4. Заказ № 118. Тираж 150 экз.

«С»

Издательство Таганрогского государственного радиотехнического университета

ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Таганрогского государственного радиотехнического университета

ГСП 17А, Таганрог, 28, Энгельса, 1