3.2 Метод множителей Лагранжа

Пусть требуется решить задачу нелинейного программирования следующего вида:

F(,

,

где функции fи,i=непрерывны, и непрерывны их частные производные по,l=.

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

g=b.

Будем исходить из геометрической интерпретации задачи. А именно, заметим, что линия уровня с максимальным значением параметра С будет касаться линии границы в точке, являющейся оптимальным решением задачи (рис. 3.3).

Рисунок 3.3 –Геометрическая интерпретация задачи

Поскольку две гладкие линии (имеющие непрерывные частные производные) касаются друг друга в точке , то их векторы-нормали сонаправлены. Поскольку вектор-нормаль есть градиенты функций (вектор частных производных), то справедливо векторное соотношениеf’()=λg’(), гдеλесть некоторый коэффициент пропорциональности. Координаторами векторовf’() иg’(), являются значения частных производных функций f иgсоответственно в точке.

f’()=

g’()=

Из условия пропорциональности в точке имеем

;

.

Для определения значений ив которых функцияfдостигает максимума, к этим уравнениям надо добавить условие принадлежности точкиграфику функции g(,)=b.

Окончательно получаем систему уравнений, определяющую оптимальное решение поставленной задачи

Введем новую функцию

F

Тогда последняя система перепишется в виде

Функцию Fназьюают функцией Лагранжа.

Приведем ниже алгоритм метода множителей Лагранжа решения задач нелинейного программирования.

Этап 1. Составляют функцию Лагранжа

F()=f(.

Этап 2. Находят частные производные функции Лагранжа по и

i=1,n;j=1,mи приравнивают их к нулю

.

Этап З. Решают систему и определяют точки, в которых функция может иметь экстремум.

Этап 4. Проверяют полученные на этапе 3 точки на экстремум и определяют экстремальное значение функции fнайденной точки.

Рассмотрим применение изученных методов на примере решения задачи оптимальной реализации продукции, в частности для расчета экономико-математической модели при нелинейных затратах на производство. Фирма реализует автомобили двумя способами: через магазин и через торговых агентов. При реализации автомобилей через магазин расходы на реализацию составляют 4усл. ед., а при продажеавтомобилей через торговых агентов расходы составляютусл. ед. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число предназначенных для продажи автомобилей составляет 200 шт.

Составим математическую модель задачи. Целью является

минимизация суммарных расходов R=4.

Управляющие переменные- это число автомобилей, реализуемых первым и вторым способом: исоответственно (200 шт.).

Окончательно математическая модель имеет следующий вид:

R=4,

Для ее расчета применим метод множителей Лагранжа. Функция Лагранжа имеет вид

F(4+λ(200-.

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

Получим следующую систему уравнений:

Решая систему, найдем 99,= 101,= 202,f() = 20 398.

Таким образом, для получения минимальных расходов, нужно реализовать 99 автомобилей через магазин и 101 автомобиль через торговых агентов. При этом расходы на реализацию составят 20 398 усл. ед.