WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 |
1 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Методы оптимизации. Часть 2 Практикум По специальности 010501 (010200) – Прикладная математика и информатика Воронеж 2005 2 Утверждено научно-методическим советом факультета ПММ от 14.06.2005, протокол №6.

Составители: Белоусова Е.П.

Коструб И.Д.

Практикум подготовлен на кафедре нелинейных колебаний факультета ПММ Воронежского государственного университета. Рекомендуется для студентов 3го курса дневного отделения.

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

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

4 ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ Рассмотрим функцию n переменных (f x,...,xn1 ), заданную на некотором множестве пространства Rn. Известно, что если f (x) дифференцируема в точке (M x,...,xn1 ), то в этой точке существуют частные производные (f x,...,xn1 ) i, =1,...,n xi и наоборот, если фукнция (f x,..., xn1 ) имеет частные производные по всем аргументам в некоторой окрестности точки (M x10 0,x0,...,x0 ), причем все эти 2 n частные производные непрерывны в самой точке M0, то указанная функция дифференцируема в точке M0.

Говорят, что функция f (x) имеет в точке M0 локальный максимум ( локальный минимум), если найдется такая -окрестность точки M0, в пределах которой значение (f M0 ) является наибольшим (наименьшим) среди всех значений f (x) этой функции.

Если функция (f x,...,xn1 ) обладает в точке (M x10 0,x0,..., x0 ) частными 2 n производными первого порядка по всем переменным,...,x xn1 и имеет в этой точке локальный экстремум, то все частные производные первого порядка обращаются в точке M0 в нуль, т.е.

f f f M( ) = 0, M( ) = 0,..., M( ) = 0.

x1 0 x2 0 xn Точки, в которых обращаются в нуль все частные производные первого порядка функции f (x), называются стационарными точками этой функции.

МИНИМИЗАЦИЯ ФУНКЦИИ N ПЕРЕМЕННЫХ В ЗАДАЧЕ БЕЗ ОГРАНИЧЕНИЙ.

КЛАССИЧЕСКИЙ МЕТОД Пусть есть задача I(u) inf, (1) u Rn. (2) n Пусть u* является точкой локального минимума функции I : R R и функция I(u) является дифференцируемой в этой точке, т.е. существует uI )(, тогда * (I u*) = 0, где 0 – нулевой вектор из Rn.

Для формулировки достаточного условия безусловного экстремума введем понятие второй производной функции n переменных. Пусть есть точка u0 из пространства Rn. Зададим некоторое приращение h. Тогда, если приращение значений функции можно записать в виде (I u h) -+ I(u00 ) = I (u0),h + (A u0)h,h + (x0,h), (3) где квадратные скобки обозначают скалярное произведение векторов, (A u0 )- симметричная матрица порядка n, u(,h) удовлетворяет условию u(, h) lim = 0, 0h h то функция I(u) является дважды дифференцируемой в точке u0. Обозначим вторую производную через (I u0 ). Если производная существует, то элементы ее выписываются следующим образом 2 (I u0) 2 (I u0 ) 2 (I u0)...

uu uu u 21 n.

(I u0) =.........

2 (I u0) 2 (I u0) 2 (I u0) uu uu u1n 2n n n Теорема: если точка Ru является стационарной точкой функции I(u) * и в этой точке существует вторая производная (I u*), то для того чтобы u* была точкой локального минимума функции I(u) должно выполняться неравенство (I u*) 0. (4) Если же (I u*) является положительно определенной матрицей, т.е.

(I u*) > 0, (5) то u* - точка локального минимума функции I(u).

Критерий Сильвестра: для того, чтобы симметричная матрица (I u*) была положительно определенной необходимо и достаточно, чтобы все ее главные миноры были положительны.

Если точка u* - точка минимума функции I(u) и существует uI )(, то * выполняются условия необходимость: (I u ) = 0,I (u** ) 0, достаточность: если в некоторой точке u* выполнены условия:

(I u ) = 0,I (u** ) > 0, то u* - точка минимума функции I(u).

Пример 1. Минимизировать функцию (I u) u1 -= u u21 + u2 - 2u + u21 inf.

Посчитаем первые производные по каждой переменной и приравняем их к нулю I I u2 -= u21 - 2 = 0, -= + 2u u21 + 1 = 0.

u1 u Из системы уравнений u2 u21 -- 2 = u2 +- 4u21 + 2 = найдем стационарную точку. Она будет иметь вид = (u 1,0). Составим матрицу * из вторых производных:

2 (I u) 2 (I u) 2 (I u) 2 (I u) =,2 -=,1 -=,1 =.u1 uu uu u21 По критерию Сильвестра она будет положительно определена, так как последовательные главные миноры этой матрицы соответственно равны =,2 21 = 3.

Таким образом, точка u* является точкой минимума функции I(u) и значение в этой точке равно I(u) = -1. Остается проверить, какой минимум реализует точка u* - локальный или глобальный. Для этого рассмотрим произвольное приращение в точке u*, т.е. введем в рассмотрение новую точку u по правилу (u u* += h1,u* + h ) = (1 + h12,h2 ) и посчитаем в ней значение целевой функции (I u) (1 += h1)2 - (1 + h )h21 + h2 - 2(1 + h ) + h21 = -1+ h1 - h h21 + h2 = 2 h2 h2 +- h1 (1 - + ( )) = I(u*) +, h1 hгде - некоторая положительная величина. Отсюда следует, что u* - это точка глобального минимума.

Пример 2. Минимизировать функцию (I u) u1 u2 --= 4u + 6u21 inf.

Посчитаем частные производные первого порядка и приравняем их к нулю (I u) (I u) u2 -= 4 = 0, -= u2 + 6 = 0.



u1 1 uСтационарная точка имеет вид = 2u,u21 = 3. Значение функции в этой точке равно (I u*) = 5. Вычислим значения вторых производных функции I(u) в точке подозрительной на экстремум. Получаем 2 (I u) 2 (I u) 2 (I u) 2 (I u) =,2 = =,0 -=. uu uu u1 21 Главный минор второго порядка 2 = -.4 Отсюда следует, что точка = (u 2 3, ) * не является точкой минимума. Подтвердим это. Введем в рассмотрение другую точку = (u 2 + h,3 + h21 ) и посчитаем в ней значение минимизируемой функции.

Оно равно (I u) (2 += h1)2 - (3 + h2 )2 - 4(2 + h ) + 6 3( + h21 ) = h1 h2 +- 5.

hПоложим = 2h h12. Тогда (I u) -= 3h1 + 5 < I(u*2 ). Если h2 =, то 1 (I u) (1 -= h) + 5 = + 5h > I(u*2 ). Отсюда следует, что u* - не является 1 4 точкой локального минимума.

Пример 3. Минимизировать функцию (I u) u1 += u4 - (u + u21 )2 inf.

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

Получим (I u) (I u) 3 u4 -= 2(u + u21 ) = 0, u4 -= 2(u + u21 ) = 0.

u1 1 u2 Найдем отсюда критические точки. Их будет три и они имеют следующий вид:

= (u 0,0),u21 = (11, ),u3 = (-1,-1).

Вычислим в этих точках вторые частные производные и составим в каждой из них матрицу Якоби:

2 (I u) 2 (I u) 2 (I u) 2 (I u) 12u1 -= 2; = -= ;2 12u2 -= 2.

uu uu u1 u21 Посчитаем значение матрицы Якоби в каждой из найденных точек. Они соответственно равны - - A =, 0(,0) -- у которой первый главный минор отрицательный и равный -2, а второй главный минор – нулевой. Рассмотрим поведение целевой функции в окрестности точки ~ (0,0). Возьмем две другие точки u = (h,-h), u = (h,h) и посчитаем в них значения функции. Они равны (I u) 2h = 0,I(~)u = 2h44 - 4h2 = 2h2 (h2 - 2) < 0.

Отсюда следует, что точка (0,0) не является точкой экстремума. Матрица Якоби в точке (1,1) имеет вид - A =.

1( 1, ) -- Оба последовательных главных минора положительны. Следовательно, исследуемая точка является точкой экстремума. Вычислим матрицу Якоби в последней точке. Она равна - A = 1(,-- 1) - 102.

Очевидно, что точки (1,1) и (-1,-1) являются точками локального минимума.

Посчитаем в них значение целевой функции. Оно равно (I u*) 1 += 1 - (22 ) = -2.

Задания для самостоятельной работы Найти все значения параметра k, при которых точка (1,0) является точкой экстремума для функции - 3a (I u) k3u1eu2 -= k2a ln(u + )u ((a ++ b -1)k - b)u1 + kcu2 + 2bu1ua при условиях: а) а=-2, b=2, с=8; б ) а=3/2, b=-1/2, c=-3/2.

ЗАДАЧА НА УСЛОВНЫЙ ЭКСТРЕМУМ ФУНКЦИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ.

МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА Предположим, что поставлена задача об отыскании минимума функции I(u) при условии, что u принимает значения в некотором множестве U Rn, т.е.

I(u) inf, (6) u U Rn. (7) Здесь множество U может задаваться различными способами. Например, {uU = Rn | gi (u) = 0,i =1,...,s}, (8) где (g u) = gii (u1,...,u ),i =1,...,s.

n Для решения задачи (6)-(8) надо выписать функцию Лагранжа s (L,,...,n,u) = 0I(u) + igi (u). (9) =1i Теорема: пусть u* - точка локального минимума в задаче (6)-(8) и в окрестности этой точки функции I(u) и (g u),i =1,...,s являются непрерывно i дифференцируемыми, тогда имеют место следующие соотношения:

* * 1) существует набор констант,...,, * таких, что 0 1 s s * || 0, i =0i s * 2) * (I u ) + gi* (u ) = 0, 0 i* =1i * 3) для того, чтобы 0 достаточно, чтобы векторы u u (g u ),g2* u (u ),...,gs* (u*) были линейно независимы.

СПОСОБ РЕШЕНИЯ ЗАДАЧИ НА УСЛОВНЫЙ ЭКСТРЕМУМ 1. По исходной задаче (6)-(8) необходимо выписать функцию Лагранжа.

2. Выписать систему уравнений.

L u 0,(,u) =. (10) L,(,u) = u * 3. Рассмотрев отдельно два случая: = 1(если задача на минимум), * * = -1(если задача на максимум) и = 0, найти все стационарные 0 точки задачи (6)-(8).

4. Проведя дополнительные исследования, установить, какие из стационарных точек являются точками локального минимума и локального максимума для задачи (6)-(8) или доказать, что решения нет.

Для задач с ограничениями типа равенств, можно не обращать внимание на тип экстремума и, убедившись, что 0 0, полагать 0 равным любой константе.

Пример 1. Минимизировать функцию (I u) = 4u + 3u21 inf при ограничении 2 uu =+ 1.

1 Составим функцию Лагранжа. В данном случае она имеет вид (L,,u1,u2) = 0 (4u1 + 3u2 ) + 1(u1 + u2 -1).

10 Посчитаем частные производные от этой функции по соответствующим переменным:

L L += 24 10 u1; = + 23 10 u2.

u1 uСоставим систему вида (10), приписав в нее ограничение из условия задачи + 24 10 u1 = + 23 10 u2 = 2 uu =+ 1.

1 Предположим сначала, что 0 =.0 Из системы сразу следует, что 1 = 0. Это нас не устраивает. Поэтому будем считать, что 0 =1. Тогда система приобретает вид + 24 u11 = 23 + u21 = 0.

2 uu =+ 1 2 Отсюда u1 -=, u2 -=. Подставляя их в третье уравнение системы, 1 находим множитель Лагранжа из уравнения + =.1 Он принимает 2 1 5 два значения = ±. Если = -, то точка подозрительная на 1 2 4 * экстремум имеет вид 1,* ==. Значение функции в этой точке равно 5 5 4 * ~ (I * )=5. Если =, то u1 -=,~* = -.Значение функции в этой точке u2 5 * ~ равно (I )u -= 5. Рассмотрим поведение функции I(u) вблизи точки *.

4 Пусть (u +=,h + )h принадлежит множеству U. Подставим ее в наше 5 4 2 ограничение ( )h ++ ( + )h =1. Отсюда легко заметить, что 1 5 4( h 3h21 ) =+ - h( + h2 ). Подставим точку u в целевую функцию.





1 Получим 4 3 * 2 *(I u) 4( += )h + 3( + )h = 5 + 4h1 + 3h2 = I( ) - h( + h2 ) I( ).

21 5 5 Следовательно, точка * доставляет наибольшее значение функции.

Пример 2. Минимизировать функцию (I u) u1 += u2 inf, при ограничении u3 + 4u21 =1.

Составим функцию Лагранжа для поставленной задачи. Она имеет вид (L,,u1,u2 ) = 0(u1 + u2 ) + (3u11 + 4u2 -1).

10 Частные производные соответственно равны L L = u2 + 31; = u2 + 41.

10 u1 u Составим систему уравнений для нахождения стационарных точек и параметров u2 + 31 = u2 + 41 = 0.

u3 4u21 =+ Если 0 = 0, то очевидно что 1 = 0. Это решение нас не устраивает.

Поэтому будем полагать 0 =.1 В этом случае система приобретает вид u2 + 311 = u2 4+ = 0.

u3 4u21 =+ 3 9 Отсюда легко посчитать, что u -= 11 u, = -21,- 1 - 1 =.2 2 2 3 Поэтому = - u, = u, = и оптимальная точка имеет вид 11 25 25 3 4 * = (u, ) и значение функции в ней равно (I u*) =. Покажем, что 25 25 эта точка является точкой минимума. Для этого составим приращение 3 (u +=,h + ),h удовлетворяющую ограничению 25 3 (3 )h ++ 4( + )h =1. Отсюда очевидно, что h3 + 4h21 = 0 и 25 h -=.h Посчитаем значение функции 3 4 3 4 3 1 2 2 2 (I u) ( += )h + ( + )h = ( + )h + ( - )h = + > Ih (u*2 ).

1 2 1 1 25 25 25 25 4 125 Пример 3. Минимизировать функцию uu (I u) e = inf при ограничении + =1uu.

Составим функцию Лагранжа uu (L,,u1,u2 ) = 0e + (u11 + u2 -1).

Частные производные имеют вид L L uu uu 21 1 = ue + 12 ; = ue + 11.

u1 0 u2 Выпишем соответствующую систему уравнений для определения параметров и оптимальной точки:

uu ue + 12 = uu ue + 11 = 0.

uu =+ Рассмотрим случай, когда = 0. Тогда и = 0. Нас это не устраивает.

0 Пусть =1. Получаем следующую систему:

uu uu 21 ue + = 0 (e u u12 ) =- 0 = uu 12 uu uu uu 21 21 ue + = 0 ; ue + = 0 ; ue + = 0.

11 11 uu =+ 0 uu =+ 0 uu == 1/ 22 22 /1 4 /1 Откуда: = - /1 e2. Соответственно: = (u 1/ 2,1/ 2), (J u ) = e.

Возьмем произвольную точку = (u 1/ 2 + h,1/ 2 + h ) такую, что /1 2 + h +1/ 2 + h21 = 1, т.е. + hh = 0 или = -hh. Значит:

21 = (u 1/ 2 + h,1/ 2 - h11 ). Вычислим значение целевой функции в этой точке.

1( / 2 h )(1/ 2-+ h11 ) 4-h1 /1 (J u) e == e1/ e = J(u ). Получаем, что u доставляет целевой функции наибольшее значение.

Задания для самостоятельной работы Минимизировать следующие функции:

1) (J u) u1 += u2 inf 2) (J u) u u2u3 = inf 2 21 4 uu =+ 1. + uu + u3 = 1.

1 2 3) (J u) = u u u3 inf 2 2 uu ++ u3 = 1, + uu + u3 = 0.

1 2 ДОСТАТОЧНОЕ УСЛОВИЕ ЛОКАЛЬНОГО МИНИМУМА В ЗАДАЧАХС ОГРАНИЧЕНИЯМИ ТИПА РАВЕНСТВ Приведем достаточные условия локального условного минимума. Будем предполагать, что векторы (g u ),g2* u (u ),...,gs* u (u*) являются линейно 1u ** независимыми в точке.u Пусть u(,, ) - решение системы * 0* L,0 j == 1,...,n (11) u j (g u) 0,i == 1,...,s.

i Вектор u разобьем на две части. Одна является (n-s) – мерным вектором. В -sn дальнейшем ее будем обозначать через Ru, вторая является s-мерным s вектором, ее мы будем обозначать через Rv, т.е.

u1 v u =... v, =...

.

u vs -sn Так как векторы (g u*,v*),i = 1,...,s предполагаются линейно независимыми, iu то переменные v можно выбрать так, чтобы в окрестности точки u(,v** ) выполнялись условия теоремы о неявных функциях, и система уравнений (g u,v) = 0,i = 1,...,s определяет неявные функции (v u),i = 1,...,s в i i окрестности точки u(,v** ). Задачу (6)-(7) можно записать в виде I(u,v) inf, (12) -sn (g u,v) 0,i == 1,...,s,u,R v Rs. (13) i Пусть функции,I gi,i = 1,...,s дважды непрерывно дифференцируемы.

Введем обозначения 2L 2L 2L 2L......

2 uu vv u1 v -sn 1 1s, Luu =......... L, =.........

vv 2L 2L 2L 2L......

uu vv u2-sn s1 vs n1 -s 2L 2L 2L 2L......

uv uv vu vu 11 1s 11 -sn Luv =......... L, =........., vu 2L 2L 2L 2L......

uv uv vu vu n1 s ns -- s s1 -sn s g1 g1 g1 g......

(g u,v) u1 u v1 vs -sn (g u,v) =... g, =......... g, =..........

u v gs gs gs (g u,v) gs......

s u1 u v1 vs -sn Теорема. Пусть выполняются условия:

** 1. u(,v**,, ) – стационарная точка функции Лагранжа.

2. Функции,I gi,i =1,...,s дважды непрерывно дифференцируемы в некоторой окрестности точки u(,v** );

3. В точке u(,v** ) матрица (g u*v,v*) имеет обратную.

4. Матрица (размера (n-s)x(n-s)) 1T LD -= Luvgv1g - gT (gv )-- Lvu + gT (gv )-1T Lvvg-1gu, (14) uu uu u v ** вычисленная в точке u(,v**,, ) положительно определенная.

Тогда точка u(,v** ) является точкой локального минимума задачи (6)(8). Согласно критерию Сильвестра, симметрическая матрица является положительно определенной тогда и только тогда, когда все последовательные миноры на главной диагонали матрицы положительны.

НЕКОЛЬКО ПРИМЕРОВ РЕШЕНИЯ ЗАДАЧ Пример 1. Минимизировать функцию (J )u = u u21 u3 inf при ограничениях u2 u + u u3 = 12, u2 - u21 = 8.

21 1. Выпишем функцию Лагранжа (L u,,) = 00 u1u2u3 + 1(2u1u2 + u2u3 -12) + 2 (2u1 - u2 - 8).

2. Найдем частные производные функции Лагранжа L = uu + 21u2 + u1 20 L = uu + 21u1 + 1u3 - uL = uu + 1uu3 10 3. Решаем систему uu + 21u2 + 22 = 20 uu + 21u1 + 1u3 - 2 = 10 uu + 1u2 = 10 u2 u21 u2u3 =+ u2 u21 =- Рассмотрим случай 0 = 0. Система примет вид:

u2 + 22 = u2 + 1u3 - 2 = = 0u.

Pages:     || 2 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.