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

При этом она однородна по λ: если пара(a, λ) является ее решением, то и любая пара вида (a, tλ), где t ∈,тоже будет решением.Все решения системы (3) естественно разбиваются на две группы:те, у которых λ0 = 0, и те, у которых λ0≠ 0. Решения из первойгруппы называются нерегулярными, а решения из второй группы —регулярными. Для регулярных решений λ0 можно положить равнымпроизвольной (отличной от нуля) константе.4) Проверяем, являются ли найденные точки экстремальными длязадачи (1).Для проверки из пункта 4) можно использовать теорему Вейерштрасса и следствия из нее. Если все функции φi в задаче (1) дваждынепрерывно дифференцируемы, то можно также использовать следующее достаточное условие экстремума.Теорема 4.2 (достаточное условие экстремума). Пусть a ∈ Ω исуществует такой вектор λ, что λ0≥ 0 и L′x(a, λ) = 0. Если длялюбого вектора dx ≠ 0, удовлетворяющего условиям φ′i(a)dx = 0,i = 1, . . . , m, выполняется неравенствоL′′xx(a, λ)dx2 > 0,то в точке a достигается строгий локальный минимум функцииφ0(x) на множестве Ω. Если же имеет место неравенствоL′′xx(a, λ)dx2< 0,то в точке a достигается строгий локальный максимум.Рассмотрим несколько примеров.Пример 3. Найти экстремумы функции F(x, y) = 4x + 3y намножестве, заданном уравнением x2 + y2 = 1.Решение. Запишем задачу в стандартном видеСоставим для нее функцию ЛагранжаL(x, y, λ) = λ0(4x + 3y) + λ1(x2 + y2 − 1)и вычислим частные производныеПосле этого нужно решать системуРассмотрим два случая.a) Пусть λ0 = 0. Тогда система принимает видОна разрешима лишь при λ1 = 0. Следовательно, λ = (0, 0), и в этомслучае подозрительных на экстремум точек нет.б) Пусть λ0 ≠ 0. Тогда можно положить λ0 = 1:Из последней системы вытекает, чтоЗначит, и получаем две подозрительные на экстремумточкиПо условию задачи экстремумы целевой функции требуется найтина множестве, задаваемом уравнением x2 + y2 = 1, то есть на окружности. Поскольку окружность компактна, а целевая функция непрерывна, то по теореме Вейерштрасса она достигает своих максимума иминимума на этой окружности.Для определения точек максимума и минимума найдем значенияцелевой функции F в потенциальных точкахэкстремума:Так как других потенциальных точек нет, то глобальный максимумдостигается в точке и равен он 5, а глобальныйминимум достигается в точке и равен он −5.Ответ: один глобальный максимум и глобальныйминимум Других локальных экстремумов нет.Пример 4. Найти экстремум функции F(x, y) = exyна прямойx + y = 1.Решение. Запишем задачу в стандартном видеСоставимфункциюЛагранжанайдем ее частные производныеи образуем с их помощью системуДалее рассмотрим два случая.a) Пусть λ0 = 0. Тогда система принимает видПолучается, что λ0 = λ1 = 0, и экстремальных точек нет.б) Пусть λ0 ≠ 0. Положим тогда λ0 = 1:Из первых двух уравнений следует, что x = y, а из третьего — чтоx = y = 1/2. Итак, получена единственная подозрительная наэкстремум точкаТак как прямая x + y = 1 не компактна, теорема Вейерштрасса вэтой задаче не применима. Попробуем определить тип экстремума внайденной точке с помощью достаточного условия (теоремы 4.2).Оно утверждает, что тип экстремума определяется знаком второгодифференциала функции ЛагранжаL(x, y, λ) = exy + λ1(x + y − 1)по отношению к переменным x, y на множестве векторов (dx, dy) ≠ 0,удовлетворяющих условиюd(x + y − 1) = dx + dy = 0.Найдем второй дифференциал от функции Лагранжа:При условии dx + dy = 0 получаем, что dy = −dx иЗначит, в точке (1/2, 1/2) строгий локальный максимум.Выясним, будет ли он глобальным. Очевидно, на прямойx + y = 1выполняется соотношение y = 1 − x. ПоэтомуF(x, y) = F(x, 1 − x) = ex(1−x) → 0 при x → ±∞.В силу этих соотношений на прямой x + y = 1 можно выбрать такойбольшой отрезок [A, B], что вненего функция F будет строго меньше,чем F(1/2, 1/2), а на самом отрезке [A, B] у нее будет единственнаяточка максимума (1/2, 1/2). Значит, этот максимум глобальный.Ответ: единственный глобальный максимум достигается в точке(x,y)= (1/2, 1/2) и равен e1/4 , а других экстремумов нет.4.Экономическая интерпретация множителей ЛагранжаМножители Лагранжа рассматривались выше как параметры, значения которых выбираются таким образом, чтобы выполнялись ограничения задачи. С экономической точки зрения множители Лагранжа интерпретируются как неявные (теневые) цены ресурсов, определяемых ограничениями; оптимальные значения множителей Лагранжа играют важную роль в анализе чувствительности решений [4]. Для того чтобы пояснить эту интерпретационную схему, рассмотрим следующую оптимизационную задачу с двумя переменными и одним ограничением в виде равенства:минимизировать f(xl, х2)при ограничении g1(x1, х2)=b1где постоянная величина bi характеризует наличие некоторого ресурса.L(x; νi)=f(x)—ν1[g1(x)—b1].Предположим, что стационарная точка функции L соответствует глобальному минимуму.Пусть ν01 – оптимальное значение множителя Лагранжа,ах0–оптимальное решение задачи. Далее, пусть минимум функции L(x; ν1) при ν1 = ν01 достигается в точке x=x0, причем g(x0)=b1 и f(x0)=L(х0; ν01)=f0. Очевидно, что оптимальные значения (х0; ν01) связаны функциональной зависимостью с величиной b1, задающей границу наличия дефицитного ресурса.Изменения f0 (оптимального значения f), обусловленные изменениями b1, описываются частной производной . По правилу дифференцирования сложной функции имеемДифференцируяобе части ограничения g1(x) – b1=0,Умножим обе части равенства на ν01, и вычтем:Так как х0 и удовлетворяют выше приведенным уравнениям, равенство приводится к видуТаким образом, из этой формулы следует, что скорость изменения оптимального значения f, вызываемого изменением b1, определяется оптимальным значением множителя Лагранжа ν01. Другими словами, величина изменения оптимального значения целевой функции, обусловленного единичным увеличением правой части ограничения, т. е. величина, которая определена как неявная цена, задается множителем Лагранжа. В зависимости от знака ν01 значения f0 при изменении b1 могут увеличиваться или уменьшаться.В случае когда рассматривается оптимизационная задача с К ограничениями и n переменными, в которой требуетсяминимизировать f(x)при ограничениях gk{x)=bk, k=1, 2, .... К,пользуясь аналогичной схемой рассуждений, можно показать, чтоЗаключениеПринятие решений – область, в которой широко используются методы оптимизации.Было рассмотрено необходимые и достаточные условия оптимальности для задач условной оптимизации. Изучен метод множителей Лагранжа для решения конечномерных гладких задач с равенствами.Список использованной литературыМоисеев Н. Н. Численные методы в теории оптимальных систем. — М.: Наука, 1971. — 424 с.Гирсанов И. В. Лекции по математической теории экстремальных задач. — М.; Ижевск: НИЦ «Регулярная и хаотическая динамика», 2003. — 118 с. — ISBN 5-93972-272-5.Sargent, Thomas J. (1987). "Search". Dynamic Macroeconomic Theory. HarvardUniversityPress. pp. 57–91. ISBN 9780674043084.Dorfman, Robert (1969). "An Economic Interpretation of Optimal Control Theory". AmericanEconomicReview. 59 (5): 817–831. JSTOR 1810679.