Eng | Rus | Ukr
Исследование операций
24.12.2008

<< prev | ^up^ | next >>

5.2. МЕТОД МНОЖИТЕЛЕЙ лагранжа

Метод множителей Лагранжа позволяет отыскивать максимум áили минимумñ функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа. Пусть задана задача НП при ограничениях-равенствах вида

минимизировать                     (5.2.1)

при ограничениях

                            (5.2.2)

Предположим, что все функции - дифференцируемы. Введем набор переменных  (число которых равняется числу ограничений), которые называются множителями Лагранжа, и составим функцию Лагранжа такого вида:

              (5.2.3)

Справедливо такое утверждение [18]: для того чтобы вектор  являлся решением задачи (5.2.1) при ограничениях (5.2.2), необходимо, чтобы существовал такой вектор , что пара векторов удовлетворяла бы системе уравнений

                          (5.2.4)

                       (5.2.5)

 Покажем необходимость условий (5.2.4), (5.2.5) на простом примере:

минимизировать                    (5.2.6)

при ограничениях

                                (5.2.7)

Ограничения (5.2.7) определяют допустимую область , которая представляет собой кривую в пространстве  и является результатом пересечения  и .

Допустим, что рассматриваемая задача имеет точку минимума в : , функции  имеют непрерывные производные первого порядка на некотором открытом множестве и градиенты

линейно независимы.

Если две переменные в уравнениях (5.2.7) можно выразить через третью в виде , то подставив их в целевую функцию (5.2.6), преобразуем исходную задачу в следующую задачу без ограничений, которая содержит лишь одну переменную :

минимизировать .               (5.2.8)

Поскольку градиенты , непрерывны и линейно независимы, то можно применить известную теорему математического анализа о неявной функции и найти стационарную точку , а потом .

Приведенный подход можно в принципе распространить и на случай функции  переменных  при наличии  ограничений-равенств:

                        (5.2.9)

Если функции  удовлетворяют условиям теоремы о неявной функции, то  из  переменных уравнений (5.2.9) можно выразить через остальные  переменных, подставить их в  и таким образом преобразовать задачу минимизаци с ограничениями в задачу безусловной минимизации с  переменными. Однако такой подход трудно реализовать на практике, поскольку очень трудно разрешить уравнения (5.2.9) относительно некоторых переменных. В общем случае это совсем невозможно.

Поэтому рассмотрим другой подход, который базируется на методе множителей Лагранжа.

Пусть - точка минимума , определяемого выражением (5.2.8). В соответствии с известной теоремой математического анализа о неявной функции можно записать

                 (5.2.10)

Аналогичные соотношения получим для ограничений

          (5.2.11)

Запишем уравнения (5.2.10), (5.2.11) совместно в виде

                              (5.2.12)

где

 .

Поскольку вектор  не является нулевым, то из (5.2.12) следует, что . Из этого следует, что вектора-строки
  матрицы A должны быть линейно зависимы. Следовательно, существуют три таких скаляра  не все равные 0, что

.                     (5.2.13)

Скаляр а не может равняться 0, так как в соответствии с предположением  и -линейно независимы. Поэтому после деления (5.2.13) на , получим

                     (5.2.14)

Таким образом, для задачи минимизаци с ограничениями (5.2.6) существуют такие , для которых справедливо уравнение (5.2.14) и которые одновременно не обращаются в нуль. Итак, справедливость условий (5.2.4) для случая n=3 показана.

Таким образом, для отыскания минимума (5.2.6) при условиях (5.2.7) необходимо найти стационарную точку функции Лагранжа:

Для того чтобы найти искомые значения , необходимо решить совместно систему уравнений (5.2.14), (5.2.5). С геометрической точки зрения условие (5.2.14) означает, что  лежит в плоскости, натянутой на векторы

Теперь рассмотрим общий случай для произвольных  . Пусть задана задача НП в виде (5.2.1), (5.2.2), все функции  имеют непрерывные частные производные на множестве . Пусть -подмножество множества , на котором все функции , то есть . Тогда справедлива такая теорема о множителях Лагранжа [2].

Теорема 5.7. Допустим, що существует такая точка , в которой достигается относительный экстремум задачи НП (5.2.1) при условиях (5.2.2). Если ранг матрицы  в точке  равен , то существуют  чисел , не все из которых равны нулю одновременно, при которых

                       (5.2.15)

Эта теорема обосновывает метод множителей Лагранжа, который состоит из следующих шагов.

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

Находят частные производные       

Решают систему уравнений

                  (5.2.16)

и отыскивают точки , удовлетворяющие системе (5.2.16).

 Найденные точки  дальше исследуют на максимум (или минимум).

        Пример 5.5. Имеются два способа производства некоторого продукта. Обозначим через  количество продукта, произведенного первым или вторым способом соответственно. Издержки производства при каждом способе зависят от объемов производства  следующим образом:

 

Пусть за некоторый промежуток времени необходимо произвести ровно  единиц продукции (то есть ), распределив ее между двумя способами таким образом, чтобы минимизировать общие издержки.

Составим функцию Лагранжа для этой задачи:

откуда

Решая эту систему, найдем оптимальные объемы производства :

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004