Метод множителей Лагранжа
Для решения задачи ЛНП с ограничениями равенствами
Найти
max f(x1, x2, x3, …..xn) (1)
g1(x1, x2, x3, …..xn) = b1
g2(x1, x2, x3, …..xn) = b2
.................. (2)
gm(x1, x2, x3, …..xn) = bm
Функции f, g1, g2, …, gm дифференцируемы (непрерывны и имеют частные производные).
§ все ограничения – равенства.
§ нет условий не отрицательности или дискретности переменных.
§ число уравнений меньше числа переменных (m<n).
В курсе математического анализа такую задачу называют задачей на условный экстремум или классической задачей оптимизации.
Условный экстремум функции f(x1, x2, x3, …..xn), при ограничениях находят с помощью метода множителей Лагранжа.
1. Составляют функцию Лагранжа F вида:
F (x1, x2, x3, …..xn, £1, £2, …., £m) =
f(x1, x2, x3, …..xn) + ∑ i=1,m £I [bi – gi(x1, x2, x3, …xn)]
Т.е. функция плюс сумма разностей свободных членов и функций ограничений, каждая из которых умножается на множитель £i.
Переменные £1, £2, …., £m (их столько сколько ограничений) - множители Лагранжа (неизвестные).
2. Затем находят частные производные и приравнивают их 0.
 |
(3)
Система уравнений (3 – система из (n+m) уравнений, содержащая (n+m) неизвестных.
x1, x2, x3, …..xn, £1, £2, …., £m
Решение системы уравнений (3) – это точка, в которой может иметь место экстремум функции. Далее необходимо исследовать эти точки.
Последовательность решения методом множителей Лагранжа
1. Составляем функцию Лагранжа.
2. Находим частные производные от функции Лагранжа по переменным xi и £I и приравниваем их к нулю.
3. Решая систему уравнений (3), находим точки, в которых целевая функция задачи может иметь экстремум.
4. Среди точек, подозреваемых на экстремум, находят такие, в которых
достигается экстремум, и вычисляют значения функции в этих точках.
Таким образом, основная идея метода заключается в переходе от задачи на условный экстремум к задаче отыскания экстремума специально построенной функции Лагранжа, без ограничений.
Пример.
F = 4х1 + х12 + 8х2 + х22 → min (4)
х1 + х2 = 180 (5)
1. Составим функцию Лагранжа
F (x1, x2, £) = 4х1 + х12 + 8х2 + х22 + £(180 - х1 - х2)
2. Вычислим частные производные по х1 и х2, £ и приравняем их 0.
 |
Решаем систему уравнений:
4 + 2х1 = £
8 + 2х2 = £
180 - х1 - х2 = 0
4 + 2х1 = 8 + 2х2 х1 - х2 = 2
х1 - х2 = 2 х1 = 91
х1 + х2 = 180 х2 = 89
Точка (х1 = 91, х2 = 89) является подозрительной на экстремум. Используя вторые частные производные, можно показать, что в этой точке минимум.
Геометрическая интерпретация задачи
Геометрический способ решения задачи НЛП
1. Находят область допустимых решений задачи определяемую
ограничениями, если она пуста, то задача не имеет решения. В отличии от ЛП задачи, эта область не всегда является выпуклой.
2. Строят гиперповерхность функции цели.
3. Определяют гиперповерхность наивысшего для максимума и наилучшего
для уровня или устанавливают неразрешимость задачи из-за неограниченности функции цели сверху или снизу на множестве допустимых решений.
4. Находят точку области допустимых решений, через которую проходит
гиперповерхность наивысшего или наилучшего уровня и определяют в ней значение функции.
Пример
Дата добавления: 2015-08-29; просмотров: 44 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| Метод Гегеля.Диалектическая логика | | | Метод наименьших квадратов |