Методы решения задач на условный экстремум

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Понятие условного экстремума. Постановка задачи

2. Метод неопределенных множителей Лагранжа

3. Метод исключения переменных

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

Заключение

Литература

экстремум условный лагранж переменная



Введение

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

В математике исследование задач на максимум и минимум началось очень давно - двадцать пять веков назад, Долгое время к задачам на отыскание экстремумов не было сколько-нибудь единых подходов. Но примерно триста лет назад - в эпоху формирования математического анализа - были созданы первые общие методы решения и исследования задач на экстремум.

В данной курсовой работе рассматриваются некоторые методы исследования функции на условный экстремум. К ним относятся: метод неопределенных множителей Лагранжа, метод исключения части переменных, метод штрафных функций.



1. Понятие условного экстремума. Постановка задачи

Пусть на открытом множестве заданы функции

(1)

. Обозначим через множество точек , в которых все функции , обращаются в нуль:

(2)

Уравнения

(3)

называются уравнениями связи.

Определение 1. Пусть на задана функция . Точка называется точкой условного экстремума функции относительно (или при выполнении) уравнения связи (3), если она является точкой обычного экстремума этой функции, рассматриваемой только на множестве .

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

Предполагают, что

1) Функции и имеют непрерывные частные производные первого порядка на открытом множестве .

2) и ранг матрицы в каждой точке множества равен , т.е. числу строк.

Это означает, что функции системы (1) независимы в любой окрестности каждой точки .

Пусть ; согласно условию 2, в точке хоть один из определителей вида

отличен от нуля; пусть для определенности в точке

. (4)

Тогда в силу теоремы о неявных функциях систему уравнений (3) в некоторой окрестности точки можно разрешить относительно переменных :

(5)

Подставляя (5) в функцию , получим функцию

(6)

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

Точка является точкой (строгого) условного экстремума для функции относительно уравнения связи (3) в том и только том случае, когда точка является точкой обычного (строгого) экстремума для функции (6). Это непосредственно следует из того, что условия (3) и (5) равносильны.

2. Метод неопределенных множителей Лагранжа

Теорема 1. Пусть точка является точкой условного экстремума функции при выполнении уравнений связи (3). Тогда существуют такие числа , что в точке выполняются условия

(7)

Следствие. Положим

(8)

где - числа, указанные в теореме. Функция (8) называется функцией Лагранжа. Если точка является точкой условного экстремума для функции, то она является стационарной точкой для функции Лагранжа, т.е. в этой точке

(9)

Доказательство теоремы. Пусть - точка условного экстремума для функции и пусть в этой точке для определенности выполняется условие (4). Тогда точка является точкой обычного экстремума для функции , поэтому в точке

Или

,

откуда, пользуясь инвариантностью формы первого дифференциала, для точки имеем

(10)

Подставляя (5) в (3) и дифференцируя получившееся тождество в некоторой окрестности точки, а значит, и в самой точке, получим

(11)

В формуле (11), также как и в формуле (10), дифференциалы есть дифференциалы независимых переменных, а дифференциалы есть дифференциалы функций .

Каковы бы не были числа , умножая равенство (11) в точке для функции на , и складывая их между собой и с равенством (10), получим

(12)

Выбрав так, чтобы в точке выполнялись равенства

(13)

Это всегда возможно, так как (13) является системой линейных относительно уравнений с определителем

не равным нулю.

При таком выборе имеем

(14)

Здесь уже все дифференциалы есть дифференциалы независимых переменных и, значит, сами являются независимыми переменными, которые могут принимать любые значения. Беря , а все остальные дифференциалы, входящие в формулу (14), равными нулю, получим

(15)

Тем самым мы доказали существование таких , что выполняются условия (13) и (15), т.е. условия (7).

Теорема доказана.

Алгоритм нахождения экстремума функции методом множителей Лагранжа

Пусть требуется найти экстремум функции n переменных f(x₁,x₂,…,x_n) при условии, что переменные x₁,x₂,…,x_n связаны соотношениями (ограничениями)

среди которых количество m ограничений-равенств меньше числа n переменных, а количество и r ограничений-неравенств может быть произвольным.

Для нахождения значений {x₁,x₂,…,x_n}=Х, необходимо доставляющих экстремумы функции f(X), можно воспользоваться методом неопределенных множителей Лагранжа:

1. Ограничения-неравенства g(X)0 приводятся к виду (Х)0, где (Х) = - g(X).

2. Полученные ограничения-неравенства

в свою очередь приводятся к ограничениям-равенствам путем введения +r дополнительных переменных

В результате задача поиска условного экстремума примет канонический вид:

в котором соотношение m++r < n++r указывает на возможность получения множества допустимых решений, а значит, и нахождения среди них тех, которые доставляют экстремум f(X).

3. Составляется функция Лагранжа:

Ф(x₁,…,x_n,₁,…,_m++r) = f(x₁,x₂,…,x_n)+₁q₁+₂q₂+…+_m++rq_m++r,

в которой дополнительные переменные {₁,…,_m++r}= называются неопределенными множителями Лагранжа.

Для составленной функции Лагранжа можно ставить задачу нахождения безусловного экстремума

Ф(Х,) extr,

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

4. Для функции Ф(Х,) составляются необходимые условия существования экстремума:

Ф(Х,)=0

Или

5. Полученную систему уравнений Ф(Х,)=0 решают, и в результате решения находят значения

,

удовлетворяющие необходимым условиям существования экстремума.

6. Для решения вопроса о том, существует ли в найденных точках максимумы или минимумы следует воспользоваться достаточными условиями существования экстремумов, которые для гладких функций Ф() формулируются следующим образом:

если в некоторой точке матрица вторых производных положительно определена, то в анализируемой точке лежит минимум функции f(Х);

если отрицательно определена максимум.

Если Ф(Х,) негладкая, то можно использовать достаточные условия вида, например, для максимума:

Ф(Х,*) Ф(Х*,*) = Ф(Х*,),

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

Пример №1. Найти экстремумы функции

z = 6 - 4x - 3y

при условии, что переменные x,y удовлетворяют уравнению

x² + y² = 1

Решение.

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

F(x,y) = 6 - 4x -3 y + л(x² + y² - 1)

Необходимые условия дают систему,

решив которую, найдем:

Находим

и вычисляем второй дифференциал функции Лагранжа

в этой точке условный минимум, z_min = 1

в этой точке условный максимум, z_max =11

3. Метод исключения переменных

Метод исключения переменных сводит задачу на условный экстремум к задаче на безусловный экстремум.

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

z = x² + y²

при условии связи

x + y ? 2 = 0.

Решение.

1. Разрешаем уравнение связи (2) относительно y

y = 2 ? x

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

u(x) = x² + (2 ? x)² = 2x² ? 4x + 4

2. Исследуем функцию u(x) на экстремум (безусловный).

Дифференцируя u(x) и приравнивая производную нулю, получаем

u'(x) = 4x ? 4 = 0,

находим стационарную точку x₀ = 1.

Так как производная при переходе через точку x₀ = 1 меняет знак с ” ? ” на ” + ”, то в этой точке функция u(x) имеет минимум.

Из уравнения (3) определяем y₀ = 2 ? x₀ = 1. Следовательно, точка (1, 1) -- точка условного минимума функции z = x² + y² при x + y ? 2 = 0.

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

Идея метода принадлежит Куранту.

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

Переход от задачи условной оптимизации к задаче безусловной оптимизации осуществляют посредством включения в целевую функцию ''штрафов" за нарушение ограничений задачи.

Пусть исходная задача имеет следующий вид:

f(x)>min, x?R^N

при ограничениях

g_j(x) ? 0, j = 1, …, J,

h_k(x) = 0, k = 1, …, K.

Тогда преобразованная задача определится выражением:

P(x, R) = f(x) + ?(R, g(x), h(x)),

где ? - штрафная функция от ограничений задачи, а R - штрафной параметр. Наличие штрафного параметра R вызвано тем, что введение штрафной функции сильно деформирует поверхность целевой функции, что приводит к ухудшению обусловленности преобразованной задачи. Поэтому параметр R служит "регулятором" веса штрафной составляющей в целевой функции, и процесс решения задачи разбивается на ряд вспомогательных задач с различными значениями параметра R и контролем сходимости их решений.

Виды штрафов

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

Квадратичный штраф

Этот вид штрафа используется для учета ограничений-равенств и имеет вид:

? = R{h(x)}².

Значение штрафа резко возрастает при отклонении h(х) от нуля. Несмотря на увеличение параметра R, стационарная точка штрафной функции P(x,R) стремится к х*, так как в пределе h(x^(t)) = 0, где t - номер итерации: t = 1, 2, …, Т.

Функция ? непрерывна и имеет непрерывную производную, откуда следует, что если f(x) и h(x) непрерывны и дифференцируемы x то стационарную точку можно найти аналитически.

Прочие виды штрафов

Рассматриваемые ниже виды штрафов используются, в основном, для ограничений-неравенств g(x).

Логарифмический штраф имеет вид

? = -R *ln[g(x)].

Этот штраф положителен для всех х, таких, что 0<g(х)<1, и отрицателен при g(х)>1. Логарифмический штраф - это барьерная функция, не определенная в точках, где g(x)<0. Поэтому на начальном этапе поиска, когда значение шага поиска велико, необходимо обеспечить защиту процедуры от попадания рабочей точки в недопустимую область.

Штраф, заданный обратной функцией, имеет вид

? = R [1/g(x)].

Как и предыдущий, является барьерным штрафом. В допустимой области вблизи границы значение штрафа положительно и быстро убывает при продвижении внутрь допустимой области. На самой границе значение P(x,R) не определено, как и в предыдущем случае возможно появление недопустимых точек.

Штраф типа квадрата срезки имеет вид

?=R[g(x)]²,

Где

[б]=

Этот штраф является внешним и недопустимые точки не создают проблем по сравнению с допустимыми. Различие заключается в том, что в допустимых точках штраф равен нулю. Этот вид штрафа удобен тем, что Р(х,R) непрерывна и определена всюду. Параметр R положителен и увеличивается от итерации к итерации.

ПРИМЕР 1. Пусть требуется минимизировать

f(x) = (x₁ - 4)²+ (x₂ - 4)²

при ограничениях

h(x) = x₁ + x₂ - 5 = 0.

Преобразуем задачу, вводя квадратичный штраф

P(x, R) = (x₁ - 4)² + (x₂ - 4)² + (1/R)( x₁ + x₂ - 5)².

Экстремум P(x, R) находим аналитически:

= 2(x₁-4) + (x₁+x₂-5) =0;

= 2(x₂-4) + (x₁+x₂-5) =0,

и совместное решение дает

x₁ = x₂ =.

Устремляя R к 0, получим

х* = [2.5 2.5]^T и f(x*) = 4.5.

Обсудим проблемы численных подходов к решению задачи. Из решения

x₁ = x₂ =.

следует, что при вариации R от 0 до достаточно больших значений решение задачи будет изменяться от x₁= x₂= 10/4= 2.5 до x₁=x₂=4 (решение задачи без учета ограничений). Таким образом, увеличивая штрафной параметр R, мы уменьшаем "вес" ограничения в целевой функции Р(х, R). Итак, зафиксировав значение R и воспользовавшись одной из рассмотренных в первой части процедур численного нахождения экстремума, мы найдем приближенное решение х^(0), где верхний индекс означает номер вариации R^(0). Выбирая далее R^(t) из условия: R⁽⁰⁾> R⁽¹⁾ > R⁽²⁾> … > R^(t), мы получим приближения х⁽¹⁾, x⁽²⁾, …, х^(t) к х*.

Справедлив вопрос, а нельзя ли сразу принять R = 0 или близкое к нулю значение и найти решение задачи. Во-первых, R выполняет роль весового коэффициента, регулирующего значимость ограничения в составе преобразованной целевой функции. С уменьшением R стационарная точка функции P(x,R) смещается в сторону более точного выполнения ограничения h(x)= 0. Во-вторых, с изменением R существенно возрастает крутизна "склонов" поверхности функции вблизи стационарной точки, что существенно затрудняет работу алгоритмов безусловной оптимизации.

Это и обуславливает итеративность процесса, когда новая итерация начинается из точки, более близкой к точке х* с начальным шагом, не превышающим конечного значения шага поиска на предыдущее итерации.



Заключение

В этой работе мы рассмотрели некоторые методы решения задач на условный экстремум.

Метод исключения части переменных может применяться лишь в простейших ситуациях.

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



Литература

1. Л.Г.Раскин «Анализ сложных систем и элементы теории оптимального управления. М., «Советское радио»1976г. »

2. В.В.Тихомиров «Рассказы о максимумах и минимумах. М.: «Наука».1986г. »

3. Фихтенгольц Г.М. «Курс дифференциального и интегрального исчисления. Том 1. ФИЗМАТЛИТ. 1962г.»

Размещено на Allbest.ru

...