Рассмотрим задачу
с одним ограничением-равенством:
,
(13)
(14)
В соответствии с
методом множителей Лагранжа
эта задача преобразуется в
следующую задачу безусловной
минимизации:
(15)
Функция называется функцией
Лагранжа. Здесь – множитель Лагранжа.
Пусть при заданном
значении = 0 безусловный
минимум функции по переменной х
достигается в точке и удовлетворяет
уравнению
.
Тогда, как не трудно видеть, минимизирует (13)
с учетом (14), поскольку для всех значений
х, удовлетворяющих (15), и
Разумеется, нужно подобрать
значение = 0 таким образом,
чтобы координата точки безусловного
минимума удовлетворяла равенству
(14). Это можно сделать, если, рассматривая
как переменную, найти безусловный минимум
функции Лагранжа (15) в виде функции , а
затем выбрать значение , при котором выполняется
равенство (14).
Пример.
Решить задачу
при ограничении
Построим функцию Лагранжа:
и определим ее безусловный
минимум. Найдем стационарную точку функции
Лагранжа, приравняв нулю компоненты ее
градиента:
Для того чтобы проверить,
соответствует ли стационарная
точка минимуму, вычислим
матрицу Гессе функции Лагранжа, рассматриваемой
как функция от x:
Эта матрица положительно
определена, так как для любого
ненулевого вектора :
*
Это означает, что L в точке и имеет
точку глобального минимума. Оптимальное
значение находится путем подстановки
значений и , откуда
Таким образом, условный
минимум достигается при
а минимальное значение есть .
Очень часто оказывается, что
решение системы
в виде явной функции переменной
получить нельзя. Тогда значения x и находятся
путем решения следующей системы, состоящей
из n+1 уравнений
с n+1 неизвестными:
,
Решить такую систему можно
каким-либо численным методом.
Для каждого из решений вычисляется матрица
Гессе функции Лагранжа, рассматриваемой
как функция от x. Если она положительно
определена, то решение – точка минимума.
Метод множителей Лагранжа
можно распространить на случай,
когда задача имеет несколько
ограничений в виде равенств:
,
Функция Лагранжа принимает
вид
Здесь – множители Лагранжа,
то есть неизвестные параметры, значения
которых нужно определить. Приравнивая
частные производные L по x нулю, получаем
следующую систему
Если найти решение
этой системы в виде функций
от вектора затруднительно, то можно
расширить последнюю систему путем включения
в неё равенств:
Решение расширенной
системы, состоящей из N+K уравнений
с N+K неизвестными,
определяет стационарную точку функции L. Затем реализуется
процедура проверки на минимум или максимум,
которая проводится на основе вычисления
элементов матрицы Гессе функции Лагранжа,
рассматриваемой как функция от x.
3.2 Задачи с ограничениями
в виде неравенств
Рассмотрим задачу
(16)
с ограничениями неравенствами
(17)
Пусть область (17) (обозначим
ее D) – непустое,
ограниченное замкнутое множество. Функция
Лагранжа для задачи (16) с ограничениями
(17) определяется формулой
, (18)
где – вектор множителей Лагранжа:
В точке локального
минимума x* задачи (17),
каждое из ограничений (18) выполняется
либо в виде равенства = 0, либо в виде неравенства
< 0. Ограничения первого вида называются
активными ограничениями. Остальные
ограничения называются неактивными ограничениями.
Если точка и ограничения 0,
активны, то условие линейной независимости
градиентов функций активных ограничений
в точке x* называется условием регулярности ограничивающих
функций в точке x*. Это условие
означает, что, например, при n=2 количество
ограничивающих функций, проходящих через
точку x*, не должно
превышать 2 и в точке x* векторы не должны быть коллинеарны.
Например, на рисунке 3 в ситуации
(а) количество ограничивающих функций,
проходящих через точку x*, превышает
размерность вектора варьируемых параметров,
в ситуации (б) в точке x* градиенты ограничивающих
функций коллинеарны.
Рисунок 3 Ситуации, в которых
Не выполняется условие регулярности
двумерной задачи
Большое значение в теории и
вычислительной практике имеет следующая
теорема (теорема Куна-Таккера для задачи
условной оптимизации с ограничениями
типа неравенств).
Теорема. Пусть функция f(x) и функции имеют непрерывные
частные производные в некоторой окрестности
точки x*, и пусть эта точка является
точкой локального минимума функции f(x) при ограничениях 0, удовлетворяющих
в точке x* условию регулярности ограничивающих
функций. Тогда существуют такие неотрицательные
множители Лагранжа , что для функции
Лагранжа точка x* является стационарной
точкой, т.е.
Отметим, что теорема
не запрещает того, чтобы все
множители Лагранжа были равны
нулю.
Смысл этой теоремы
можно пояснить следующим примером.
Рассмотрим двумерную
(n=2) задачу (16),
(17), в которой область допустимых значений D задается тремя
ограничивающими функциями. Положим, что
множество D имеет вид, представленный
на рисунке 4.
Для всех граничных
точек области D (рисунок 4),
очевидно, выполняются условия регулярности
ограничивающих функций.
Если точка x* находится
внутри множества D (т.е. является
стационарной точкой функции f(x)), то теорема
будет справедлива, если положить все
множители Лагранжа i
равными нулю.
Рисунок 4 К теореме Куна-Таккера
Пусть теперь точка x* находится
на одной из дуг, например, на дуге AB, т.е. пусть
ограничениеявляется активным
ограничением, а остальные ограничения
– неактивными ограничениями. Тогда в
этой точке и справедливость теоремы вытекает
из правила множителей Лагранжа для задачи
с ограничениями типа равенств, если
положить .
Пусть, наконец, точка x* находится
в одной из угловых точек множества D, например, в
точке B, т.е. пусть
ограничения , являются активными
ограничениями, а ограничение – неактивным
ограничением. Тогда можно положить и
справедливость теоремы вытекает из правила
множителей Лагранжа для задачи с ограничениями
типа равенств.
Теорема Куна – Таккера
означает, что в ее условиях вместо задачи
условной оптимизации (16), (17) можно решать
задачу безусловной оптимизации функции
Лагранжа (18).
Необходимым условием
существования локального минимума
этой задачи в некоторой точке x* является условие
4 Задача
По
плану производства продукции предприятию
необходимо изготовить 200 изделий. Эти
изделия могут быть изготовлены двумя
технологическими способами. Производственные
затраты на изготовление n изделий первым способом равны 4n+n2, а для второго способа – 8n+n2. Сколько изделий надо изготовить
каждым способом, чтобы общие затраты
на производство продукции были бы минимальными.
Решение:
Обозначим число изделий, изготовленных
первым способом через – х1, вторым способом – х2. Тогда суммарные затраты на
изготовление продукции по плану составят: f(x1,x2)=4x1+2x1+8x2+2x2.
При
этом общее число изделий должно быть
равно 200, т.е.
x1+x2=200.
Получим
математическую модель задачи:
f(x1,x2)=4x1+2x1+8x2+2x2
x1+x2=200
x1 x2
Для
ее расчета применим метод множителей
Лагранжа.
Составим
функцию Лагранжа
L(x1,x2,)=4x1+2x1+8x2+2x2+(200-x1-x2)
Найдем
частные производные функции L по x1, x2, и
приравняем их к нулю:
Исключим
из этой системы ,
например, выразим из
первого уравнения
и подставим найденное значение во второе
уравнение системы, получим:
Таким
образом, по необходимому условию экстремума
дифференцируемой функции получим стационарную
точку М(101,99) возможного условного экстремума
функции f(x1,x2).
Дальнейшее
исследование этой точки будем проводить,
как и в случае безусловного экстремума.
Найдем
частные производные второго порядка:
Для рассматриваемого
примера производные постоянны и не зависят
от значений х1 и х2. Поэтому a11=2, a12=0, a21=0, a22=2. Вычислим определитель:
Так
как определитель больше нуля и a11=2>0, следовательно, в точке М(101,99) функция f(x1,x2) имеет минимум:
Заключение
Метод
множителей Лагранжа применяют для решения
задач такого же класса сложности, как
и при использовании обычных методов исследования
функций, но при наличии ограничений на
независимые переменные. К требованию
возможности получения аналитических
выражений для производных от критерия
оптимальности при этом добавляется аналогичное
требование относительно аналитического
вида функций, задающих ограничения.
В
основном при использовании метода множителей
Лагранжа приходится решать те же задачи,
что и без ограничений. Некоторое усложнение
в данном случае возникает лишь от введения
дополнительных неопределенных множителей,
вследствие чего порядок системы уравнений,
решаемой для нахождения экстремумов
критерия оптимальности, соответственно
повышается на число ограничений. В остальном,
процедура поиска решений и проверки их
на оптимальность отвечает процедуре
решения задач без ограничений.
Множители
Лагранжа можно применять для решения
задач оптимизации объектов на основе
уравнений с частными производными и задач
динамической оптимизации. При этом вместо
решения системы конечных уравнений для
отыскания оптимума необходимо интегрировать
систему дифференциальных уравнений.
Следует
отметить, что множители Лагранжа используют
также в качестве вспомогательного средства
и при решении специальными методами задач
других классов с ограничениями типа равенств,
например, в вариационном исчислении и
динамическом программировании. Особенно
эффективно применение множителей Лагранжа
в методе динамического программирования,
где с их помощью иногда удается снизить
размерность решаемой задачи.
Условия
экстремума функции, которые рассмотрены
выше, позволяют найти, так называемый,
безусловный экстремум. Однако, в большинстве
практических задач принятия решения
требуется принять решение - определить
экстремум критерия оптимальности при
условии, что на независимые переменные
наложены ограничения, имеющие вид равенств.
Типичными примерами подобных задач служат
задачи, в которых требуется оптимальным
образом распределить заданное количество
ресурсов, чтобы принятая оценка эффективности
процесса имела при этом максимальное
или минимальное значение. Для решения
таких задач в классическом анализе используется
метод неопределенных множителей Лагранжа.
Сами задачи получили название задач на
условный экстремум.
Список использованных источников
1. Березин И.С., Жидков
Н.П. Методы вычислений. Том 1 и 2. –
М.: “Наука”, 1994-398 с.
2. Бахвалов Н.С. Численные
методы. – М.: “Наука”, 1993-412с.
3. Калиткин Н.Н. Численные
методы. – М.: “Наука”, 1991-516 с.
4. Зуховицкий С.И., Авдеева Л.И.
Линейное и выпуклое программирование.–
М.: “Наука”,1994-488 с.
5. Васильев Ф.П. Численные
методы решения экстремальных
задач. - М.: Наука, 1980-168 с.
6. Сухарев А.Г., Тимохов
А.В., Федоров В.В. Курс методов
оптимизации. - М.: Наука, 1986-656 с.
7. Поляк Б.Т. Введение в
оптимизацию. - М.: Наука, 1983-332 с.
8. Сеа Ж. Оптимизация. Теория
и алгоритмы. - М.: Мир, 1973-524 с.
9. Зангвилл У. Нелинейное
программирование. Единый подход. -
М.: Сов. радио,1973-446 с.
10. Банди Б. Методы оптимизации
(вводный курс). - М.: Радио и связь,1988-498
с.