Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

d 2 (x*, y*) 0 ,

то точка x* является точкой минимума.

Ответ:	f	min	8,	x *	12, x *
		min		1	2
При	решении			большинства

задач проверка условия

(x* ), i

_____

линейной

независимости

векторов

1, m

затруднена,

так

как

точка

х*

заранее

неизвестна.

Однако это

требование

является существенным.

Пример 4. Найти условный экстремум в задаче

f0 (x)

min

f1 (x)

x13 x22

Решение.

1. Запишем функцию Лагранжа:

(x, y) x1 y1 (x13

x22 )

2. Выпишем необходимые условия экстремума :

а)

Ф(x, y)

3y x

Ф(x, y)

2 y1x2

б)

Ф(x, y)

x 3

Из второго равенства следует, что либо y1 =0, либо x2

0 .

При

первое

равенство

невозможно

(1=0),

значит

0. Но

из

третьего

равенства получаем

первое

равенство

снова

не выполняется

(1=0). В итоге

получаем, что

система несовместна и точек, подозрительных на экстремум, нет.

Однако,

проанализировав

исходную постановку

задачи,

нетрудно убедиться, что она разрешима. Из ограничения следует,


что	x	0 (так как x	( 3 x )2 ). Поэтому точка x*=(0,0) является
	1	1	2

решением данной задачи. Принцип Лагранжа не работает, потому

что в точке x* нарушено требование линейной независимости градиентов:

f1 (x*) ( 3(x1* )2 ,2x2* ) (0,0) .

Ответ: fmin 0, x1* x2* 0.

Чтобы избежать проверки линейной независимости градиентов в рассмотрение вводится так называемая расширенная функция Лагранжа:

~(x, y0 , y) y0 f0 (x) m yi (bi fi (x))

Те ор е м а 5 (расширенный принцип Лагранжа). Пусть х* -

точка	локального			экстремума		функции	f0 (x) ,	причем
		_____
fi (x), i		0, m	непрерывно дифференцируемы в окрестности точки
х.	Тогда		существует		такой	ненулевой		вектор
( y * , y* )		Rm 1, y*		( y * ,..., y * ), что для расширенной функции
0				1	m

Лагранжа

~(x, y0 , y) y0 f0 (x) m yi (bi fi (x))

выполняются следующие равенства:

1)	x	(x, y0 , y*) 0
2)	y	(x, y0 , y*) 0

В результате отыскание подозрительных на экстремум точек может осуществляться по следующему алгоритму:

Шаг 1. Составить расширенную функцию Лагранжа:

~ (x, y

, y)

(x)

(x))

Шаг 2. Записать необходимые условия экстремума:

1)	x	(x, y0	, y)	0
	x
2)	y	(x, y0	, y)	0
	y

Шаг 3. Решить систему для двух случаев:

1)y0=0;

2)y0=1.

Врезультате найти подозрительные на экстремум точки x*.

Возвратимся к примеру 4.

1. Составим расширенную функцию Лагранжа:

(x, y0 , y) y0 x1 y1 (x13 x22 )

2. Выпишем необходимые условия экстремума:

a)	(x, y)	y0	3 y1 x12 0,

	x1
	x1
	(x, y)	2 y1 x2		0,

	x2
	x2
b)	(x, y)	x13	x22	0

	y1
	y1

3. Положим y0=0.

Решая полученную систему, находим единственную точку (0,0). При y0=1, как мы уже выяснили, система несовместна.

Задачи для самостоятельного решения

3.1.1 Доказать, что всякая точка локального минимума в задаче выпуклого программирования является точкой глобального минимума.

3.1.2. Найти условный экстремум в задачах:

а) x 2	x 2	extr		б) x 2	x 2	extr
1	2			1	2
(x 1)2		x 2	4	x 2	x 2	1
1		2		1	2

3 . 1 . 3 . Д ок а з а т ь , ч т о ограничение вида fi (x) bi можно эквивалентно переписать как ограничение-равенство с помощью введения новой переменной ui :

fi (x) ui2 bi .

3.1.4. Получить необходимые условия экстремума для задач

а) f (x) extr	;	б) f0 (x)	extr
	;		,
x 0		f1 (x)	b

cведя их к задачам с ограничениями-равенствами.

3.2. Графическое решение задач нелинейного программирования

Если допустимое множество R , то задача оптимизации, как правило, может быть решена графически.

Определение. Кривые, задающиеся уравнениями

f (x1 , x2 ) C ,

называются линиями уровня функции f (x1, x2 ) .

Пример 1. Решить графически задачу нелинейного программирования

f (x , x )			(x	4)2 (x 2)2	min,
	1	2	1	2
x1	x2		3,		(1)
x1	2x2		4,		(2)

x1 , x2 0

Решение: Допустимое множество задачи изображено на рис.3.2.1. Линиями уровня целевой функции являются концентрические окружности с центром в точке (4,2). Минимальному значению целевой функции соответствует окружность минимального радиуса, пересекающая допустимую область. Такая окружность будет касаться границы области на прямой (1). Дальнейшее уменьшение радиуса приводит к линиям уровня, не имеющим общих точек с областью.

Рисунок 3.2.1. Допустимое множество решений

Координаты точки касания можно найти, приравнивая значения производных (x2 )'x1 из уравнений прямой и окружности. Дифференцируя уравнение окружности

(x1	4)2 (x2			2)2		C,
и рассматривая x2 как неявную функцию от						x , получим
						1
'			2(x1	4)
(x2 ) x
(x2 ) x			2(x2	2) .
1			2(x2	2) .
1
Из уравнения прямой		находим (x )'			=1. В итоге выписывается
		2		x
				1

равенство:

12(x1 4)

2(x2 2) , т.е. x2 2 x1 4 .

Добавив уравнение прямой,		которой принадлежит точка касания,
получим систему:
x1	x2	3,
x2	x1	2 .

Ее решением является точка

X * ( 5 , 1 ) 2 2 .

Источник: https://studfile.net/preview/16565974/

Смотрите также:



_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27
'Образ–Я' и его развитие средствами диалога
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)