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

Рассмотрим частный случай общей задачи нелинейного программирования (1), (2), предполагая, что система огра­ничений (2) содержит только уравнения, отсутствуют усло­вия неотрицательности переменных и функции f и g_i - непрерывные вместе со своими частными производными

(1)

(2)

В курсе математического анализа задачу (1), (2) назы­вают задачей на условный экстремум или классической задачей оптимизации.

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

(3)

находят частные производные и , рассматривают систему n+m уравнений:

(4)

с n+m неизвестными . Всякое решение системы (4) определяет точку в которой может иметь место экстремум функции . Следовательно, решив систему (4), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек про­водят так же, как и в случае безусловного экстремума.

Пример. Известен рыночный спрос на определенное изде­лие в количестве 180 штук. Это изделие может быть изготов­лено двумя предприятиями одного концерна по различным технологиям. При производстве х₁ изделий первым предприя­тием его затраты составят руб., а при изготовлении х₂ изделий вторым предприятием они составляют руб.

Определить, сколько изделий, изготовленных по каж­дой технологии, может предложить концерн, чтобы общие издержки его производства были минимальны.

Решение. Задача запишется в виде:

(5)

(6), (7)

Для нахождения минимального значения функции (5) при условии (6), т. е. без учета требования неотрицательно­сти переменных, составляется функция Лагранжа:

вычисляются ее частные производные по и приравнивается нулю:

Отсюда или . Решая это уравнение совместно с , находим , т. е. получаем координаты точки, подозрительной на экстремум. Используя вторые частные производные, можно показать, что в этой точке функция f имеет услов­ный минимум.

Такой же результат можно получить, если исследова­ние на условный экстремум функции f свести к исследова­нию на безусловный экстремум функции f _1? полученной из f в результате ее преобразований.

Таким образом, если из уравнения связи найти х₂ = 180 – x₁ и подставить это выражение в целевой функции, то получится функция одной переменной x₁.

.

или 4х₁ - 364 = 0, откуда . Ис­пользуя вторые частные производные, устанавливаем, что в данной точке функция f имеет минимальное значение.

4.3. Возможные обобщения метода множителей. Седловая точка функции Лагранжа

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

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

Это определение относится к локальной седловой точке, поскольку требование выполнить указанные в нем неравенства связано лишь с теми , которые находятся «вблизи» . В том же смысле можно говорить и обо всех , представляющих интерес в той или иной задаче; соответствующая седловая точка рассматри­вается как глобальная.

Анализ необходимых условий существования таких точек будет проведен в предположении, что часть пере­менных не имеет ограничения на знак, остальные же должны быть либо неотрицательными, либо неполо­жительными; для конкретности при и ; при и ; произвольный знак имеют х_i и λ_i при , .

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

Таким образом, для и для .

Чтобы понять, как ведут себя рассматриваемые производные при , достаточно выбрать переменную х_к с номером и провести на ее примере необходимое исследование, cчитая все остальные переменные фиксированными.

Если как функция только х_к достигает мак­симума при , то ; но если (точка максимума Ф принадлежит границе об­ласти х_к 0), то можно ожидать либо либо (рис. 7). Повторив подобные рассуждения применительно к другим нетрудно полу­чить сводку необходимых условий существования .

(1)

причем всегда

Рис. 7 Рис. 8

Для анализа, достаточных условий введем определе­ние: некоторая функция F(X) называется выпуклой на интервале [Х1,Х2], если при 0<a<1 (рис. 8). В основе опре­деления вогнутой на [Х₁, Х₂] функции лежит неравенст­во противоположного смысла, причем часто употребляются термины «выпуклая вниз», «выпуклая вверх».

Пусть Ф(Х, ) является выпуклой (вверх) по X для всех X из -окрестности Х⁰, т.е.

это значит . Выбирая таким, что (сохраняются линейные члены разложения в ряд Тейлора), получаем

или .

Слагаемое интерпрети­руется, очевидно, как

Если, все эти соотношения рассматриваются при выполненных условиях (1), то,

Следовательно, - неположительная величина и тем более . Таким образом, из (1) и предположения о выпуклости вверх но X получено неравенство, присутствующее в определении седловой точки.

Считая теперь выпуклой (вниз) по вблизи , т.е. при , нетрудно придти к выводу: . Этим подтверждается достаточность общих условий (1) и требования « должна быть выпуклой по Х и вогнутой по в окрестности » для существования «седла».