А.В.Шатина МО 2012 версия 20.09.2013

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ “МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ”

А.В. ШАТИНА

МЕТОДЫ ОПТИМИЗАЦИИ. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

УЧЕБНОЕ ПОСОБИЕ

МОСКВА 2012

2

ББК 22.18 Ш 28

УДК 519.6

Рецензенты: д.ф.-м.н. В.Г. Вильке, к.ф.-м.н. Т.П. Краснослободцева.

Ш 28 Шатина А.В. Методы оптимизации. Практические занятия: Учебное пособие / Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования “Московский государственный технический университет радиотехники, электроники и автоматики”.- М., 2012. – 194 с.

Учебное пособие создано на основе курса «Методы оптимизации», предназначенного для студентов, обучающихся по специальностям «Прикладная математика», «Прикладная математика и информатика», «Информационные системы и технологии».

Материал изложен в форме 14 занятий и включает в себя следующие разделы: конечномерные гладкие экстремальные задачи, элементы выпуклого анализа, задачи линейного программирования, задачи классического вариационного исчисления, задачи оптимального управления.

Табл. 56. Ил. 15. Библиогр.: 10 назв.

Печатается по решению редакционно-издательского совета университета.

ISBN 978-5-7339-0892-2

© А.В. Шатина, 2012

© МГТУ МИРЭА, 2012

	3
	СОДЕРЖАНИЕ
Занятие 1.	Гладкие конечномерные задачи без ограниче-
	ний .........................................................................	4
Занятие 2.	Гладкие конечномерные экстремальные зада-
	чи с ограничениями типа равенств ....................	12
Занятие 3.	Гладкие конечномерные экстремальные зада-
	чи с ограничениями типа равенств и нера-
	венств ....................................................................	24
Занятие 4.	Элементы выпуклого анализа. Выпуклые за-
	дачи .......................................................................	35
Занятие 5.	Графический метод решения задач линейного
	программирования ...............................................	47
Занятие 6.	Симплекс–метод решения задач	линейного
	программирования ...............................................	57
Занятие 7.	Транспортная задача ...........................................	77
Занятие 8.	Простейшая задача классического вариацион-
	ного исчисления ...................................................	95
Занятие 9.	Задача Больца .......................................................	109
Занятие 10.	Изопериметрическая задача ...............................	122
Занятие 11.	Задача с подвижными концами ..........................	133
Занятие 12.	Задача Лагранжа ...................................	............... 146
Занятие 13.	Задача оптимального управления ......................	160
Занятие 14.	Задача оптимального управления (продолже-
	ние) ........................................................................	172
	Ответы к задачам для самостоятельного реше-
	ния..........................................................................	182
	Библиографический список.................................	193

4

Занятие 1. Гладкие конечномерные задачи без ограничений

Пусть f : X R – функция n действительных переменных,

X R	n	– множество, на котором функция определена,	R	n	–	n -

мерное арифметическое евклидово пространство, элементами ко-
торого являются упорядоченные совокупности	n	действительных
чисел x x1,..., xn .

В пространстве R	n	вводятся операции сложения и умноже-
ния на число:
x y x1	y1,..., xn yn					x, y X	,
x x1,..., xn			x R	n	,	R .

Расстояние между элементами в

R	n

вводят следующим об-

разом:

x, y

n xi

i1

y
		2
	i

. Это расстояние называют евкли-

довым. Если в			R
	n	то x,
x	2
	xi
	i1

n	ввести норму элемента

y x y .

x

по формуле

	Постановка задачи состоит в нахождении экстремума функ-
ции	f x :
		f x extr.					з
		ˆ	называется точкой абсолютного
	Определение. Точка x X
или	глобального	минимума		(максимума)			функции
f : xˆ absmin f xˆ absmax f ,			если	x X выполнено неравен-
ство	f x f xˆ f x f xˆ .		Величина		f xˆ	называется чис-
ленным значением задачи и обозначается					Smin	Smax . Если экс-

тремум не достигается, то следует указать последовательность
точек xn , на которой f xn Smin Smax при n .		▲
Определение. Точка xˆ X	называется точкой локального
минимума (максимума) функции	f : xˆ locmin f xˆ locmax	f ,

5

если 0 такое,

что для любой точки

x X

,

удовлетворяющей

условию x xˆ

, выполнено неравенство

f x f xˆ f x f xˆ .

▲

Теорема 1. (Необходимые условия локального экстремума

1-го порядка)

Если xˆ xˆ1,..., xˆn – точка локального экстремума функции

n переменных

f x f x1

,..., xn

и функция

f

дифференцируема

ˆ

в точке x , то

f xˆ

0,...,

f xˆ

0 .

■

f xˆ 0

x

x

n

1

Точки xˆ , в которых f

xˆ 0, называются стационарными.

Теорема 2. (Необходимые условия локального экстремума

I-II порядка)

Пусть функция f от

n

переменных определена в некоторой

окрестности точки

xˆ xˆ1

,..., xˆn

и имеет непрерывные частные

производные до 2-ого порядка включительно в точке

ˆ

x . Если

xˆ locmin f

ˆ

f ,

то

f xˆ 0

,

f xˆ h, h 0,

x locmax

f xˆ h, h 0 ,

h R	n

где

f xˆ h, h	n		2	f xˆ
					i	j
		x		x	h h
	i, j1				j
			i

.

■

Теорема 3. (Достаточные условия локального экстремума

I-II порядка)

Пусть функция

f

от

n

переменных определена в некоторой

окрестности точки

ˆ

ˆ

ˆ

и имеет непрерывные частные

x

x1

,..., xn

ˆ

производные до 2-ого порядка включительно в точке x . Если

1)

ˆ

f

x 0 ,

2

2

n

2)

f

h, h h

f

h R и некото-

xˆ

xˆ h, h h

ром 0 , то

ˆ

f

ˆ

■

x locmin

x locmax f .

Условие 2) теоремы 3 является условием положительной

6

(отрицательной) определенности квадратичной формы

f xˆ h, h

с матрицей

Axˆ

	2	f xˆ
x		x	j
	i

  

n . При практическом i, j 1

применении теоремы 3 возникает вопрос, будет ли квадратичная форма положительно или отрицательно определенной. Критерием положительной (отрицательной) определенности квадратичной формы является критерий Сильвестра.

n

Критерий

Сильвестра.

Квадратичная

форма

a

ij

h h

j

i

aij a ji

i, j1

положительно определена

все главные миноры

A a

матрицы

ij

n

положительны:

i, j 1

a

a

a

0,

11

12

0,...,

det A 0.

1

2

n

11

a

a

21

22

n

aij a ji отрицательно

Квадратичная

форма

aij hi h j

i, j 1

определена

k			0,
1		k

k

1,2,...,

n

.

■

Теорема 4. (Достаточные условия локального экстремума I-II порядка для функции двух переменных)

Пусть функция	f	двух переменных определена в некоторой
ˆ		ˆ	ˆ
окрестности точки x x1			, x2 , имеет непрерывные частные про-
			ˆ	ˆ
изводные до 2-го порядка включительно в точке x и				f x 0 .

а) Если 1 б) если 1 в) если 2

г) если 2

0, 2	0		ˆ		f ;
			, то x locmin
0, 2	0		ˆ	locmax	f ;
		, то x

0 , то xˆ locextr f ;

0, то требуется дополнительное исследование. ■

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

7

Теорема Вейерштрасса. Непрерывная функция на непустом ограниченном замкнутом подмножестве конечномерного пространства достигает своих абсолютных максимума и мини-

мума.		■
Следствие. Если функция f	непрерывна на Rn	и

lim	f x
x

			, то она достигает своего абсо-
lim		f x
	x

лютного минимума (максимума) на любом замкнутом подмноже-

стве пространства R		n	.									■
Пример 1.	f x , x			2			3x2 x	2	x3	12x 15x	2	3 extr.
	1						1		2	1
Выпишем	необходимые							условия локального экстремума
1-го порядка:
			f				6x x		12 0,
								2
			x				1
					1
			f
							3x2	3x2		15 0.
			x
						2	1		2

Решая полученную систему уравнений, находим стационарные точки:

P	1;2 ,	P2 2;1 ,		P3 1; 2 , P4 2; 1 .
1
Для исследования стационарных решений составим матрицу
вторых производных функции			f	:

							2	f x
							x
A x , x										2
									1
	1		2				2	f		x
						x		2	x
										1
Для точки		P	1; 2 :
		1
12	6
A 1;2		,				12 0,
					1
6	12

Для точки P2 2;1 :

	2	f x
x x
			2			6x	2	6x
	1								1		.
2 f x						6x		6x
									2
							1
		2
	x2

2 108 0 P1 1;2 locmin f .

8

6	12				6 0,			108 0 P 2;1 locextr f .
A 2;1		,		1			2
	6							2
12

Для точки P3 1; 2 :

A 1; 2

Для точки

P4

12	6			12 0,
		,
6	12		1
P 1; 2 locmax
	3
2; 1 :

f

2 108 0

.

	6	12
A 2; 1			,
	12	6
	P
		4

	6 0,
1
2; 1 locextr

f

2	108 0

.

Далее,

f n, n f n,0

4n3 27n 3 при12n 3 при n

n .

;

Поэтому

S	min	, S	max

.

Пример 2.

f

x	,
1

Ответ:				1;2 locmin
				S	min		,	S
x	2	x6	x6			x x		2
		1			2		1

f	; 1; 2 locmax
max .
3	extr.

f

;

●

Необходимые условия локального экстремума 1-го порядка имеют вид:

		f		6x15 3 x1 x2 2 0,
		x1
		f		6x25 3 x1 x2 2 0.
		x2

Решая ные точки:

полученную
P						P
1	3	2;	3	2	,	2

систему уравнений, найдем стационар-

0;0 .

Для проверки условий 2-го порядка выпишем матрицу вторых производных функции f :

9

	2 f x	2 f x
	x12	x1 x2
A x1, x2	2 f x
		2 f x
	x2 x1	2
		x2

	30x4 6 x x				6 x x
	1	1		2		1	2		.
	6 x x		2		30x4	6 x x		2
		1			2		1

С помощью теоремы 4 проведем исследование полученных стационарных точек.

	Для точки						1		3		3			имеем:
										2;		2
							P
							3		2			3		2
3		3				48				12							3				3
	2;		2															2 0,				4 0
A							3					3			,		48			2	2160
									2				2			1
						12				48

P locmin

1

f

.

Для точки		P2 0;0 имеем:
	0	0		0, 2	0		критерий Сильвестра не да-
A 0;0			, 1
	0	0

ет ответа на вопрос об экстремуме функции	f	.
Рассмотрим окрестность точки P2 0;0		в пространстве	R	2	.

При h 0

имеют место соотношения:

f h; h 2h	6	0		f 0;0 ,	f h;0 h	6	h	3	0

f

0;0

.

Откуда следует, что

P	0;0 locextr
2

f

.

Для решения вопроса об абсолютном экстремуме, вычислим

предел

lim

f x .

Перейдем

к

полярным

координатам:

x

r 0; , t 0; 2 . Тогда

x1

r cos t,

x2 r sin t,

x

r,

f x r6 cos6 t sin 6 t r3 cos t sin t 3

r

6

1 0,75sin

2

2t 2

2r

3

sin

3

t 4

1

r

6

2

2r

3

4

lim

f x .

x

Согласно

следствию

теоремы

Вейерштрасса

3

absmin

f

3

8 .

P

2;3

2

f ,

S

min

2;3

2

1

10

Ответ:

3	2;	3	2	absmin

f

;

S	min	8, S	max

. ●

Пример 3.

f x	; x	2
1

	x x	2	12 x
		2
	1		1

x
2

extr

.

Необходимые условия 1-го порядка имеют вид:

f			x2 12 2x			x			0,
x			2		1			2
	1
	f				24 2x						0.
			x x				3x
	x
		2	1	2		1				2

Решая полученную систему алгебраических уравнений, находим стационарные точки:

1	3;	6	,	2	0;12 ,	3	t	;0	,	t ;		.
P				P		P

Для проверки условий рых производных функции

2-го порядка выпишем матрицу вто- f :

														2		f x					2	f x
														x				2		x x
			A x , x
																	1					1		2
							1	2						2 f				x		2 f x
													x				x						2
																					x2
																2		1
							2x2											24x			4x x								3x	2	.
									2											2				1				2		2
		24x				4x x					3x				2			24x			2x			2			6x x
				2						2					2															2
							1												1				1						1
В точке	P	3;6				:
	1
			72				36							72 0,														2592 0
A 3; 6									,																2
			36				54						1
											3;6 locmax f .
							P
										1
В точке P2 0;12 :
288					144								288 0,																0 1442 0
A 0;12								,																		2
	144						0					1
							P2 0;12 locextr																f .
Для точки			P3 t;0 ,					t ; :