Задача линейного программирования

10

ГЛАВА 2. Метод множителей Лагранжа.

2.1. Решение задач НП с ограничениями – равенствами.

              Одним из самых известных и широко используемых методов решения задач нелинейного программирования является метод множителей Лагранжа. Как уже отмечалось выше, он принадлежит к семейству аналитических методов, в основе которых лежит определение экстремума функции.

              Метод множителей Лагранжа позволяет отыскивать максимум (или минимум) функций при ограничениях – равенствах. Основная идея метода заключается в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой специально построенной функции Лагранжа.

              Пусть требуется найти

                                                 min f (х1,х 2,…, хn)                               (2.1)

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

                                                 h1 (х1,…,хn)=0,

                                                  h2 (х1,…,хn)=0,

                                                  ························                                  (2.2)

                                                  hm (х1,…,хn)=0.

              Предположим, что функции f, h1, h2,…, hm дифференцируемы.              Введём набор переменных 1, 2,…,m (по числу ограничений), которые называются множителями Лагранжа, и составим так называемую функцию Лагранжа следующего вида:

L (х1,х 2 ,…,хn,1,…,m)=f (х1,х2,…,хn)+(х1,х2,…,хn).         (2.3)

Тогда для того, чтобы вектор х0 = {,…,} является решением задачи (2.1)при ограничениях (2.2), необходимо существование такого 0= {,…,}, что пара векторов {х0,0} удовлетворяет системе уравнений:              , j = ,                                                 (2.4)

                            , i = .                                            (2.5)

Покажем необходимость условий (2.5) и (2.4) для следующего простого примера.

              Найти

min f (х1,х 2, х3)                                                                             (2.6)

при условиях

h1 (х1,х 2, х3)=0,

                               h2 (х1,х 2, х3)=0,                                                                            (2.7)

Ограничения (2.7) определяют собой допустимую область S, которая представляет собой кривую в R(3) и определяется пересечением h1(х) и h2(х).

Допустим, что данная задача имеет точку минимума в

S1: х* = (,,…,), функции f, h1, h2 обладают непрерывными производными первого порядка на некотором открытом множестве и градиенты

,

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

              Если две переменные в уравнениях (2.7) можно выразить через третью в виде х2=u(х1) и х3= v(х1), то, подставляя их в целевую функцию (2.6), преобразуем исходную задачу в следующую задачу без ограничений, которая содержит одну – единственную переменную х1:

min f (х1, u(х) 1, v(х1))                                                                        (2.8)             

Так как градиенты , i= 1,2 предполагаются непрерывными и линейно – независимыми, то можно применить известную из анализа теорему о неявной функции и найти стационарную точку , а затем и =u() и =v().

              Указанный подход можно в принципе распространить и на случай функций n переменных f(х), х= (х1,х2,…,хn)т при наличии m ограничений – равенств:

                            h1(x)=0, h2(x)=0,…, hm(x)=0                                                              (2.9)

Если функции h1,…,hm удовлетворяют условиям теоремы о неявной функции, то m из n переменных уравнений (2.9) можно выразить через остальные (n – m) переменных, подставить их в f(х) и таким образом преобразовать задачу минимизации с (n – m) переменными. Однако такой подход очень трудно реализовать на практике, так как очень трудно разрешить уравнения (2.9) относительно некоторых m переменных.

              Поэтому рассмотрим другой подход, использующий метод множителей Лагранжа.

              Пусть - точка минимума, определяемого уравнением (2.8).

Согласно известной теореме анализа о неявной функции можно записать              .                                     (2.10)

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

                            , i= 1,2.                                (2.11)

Запишем уравнения (10) и (11) совместно в виде

,                                                                (2.12) 

где

A=[f(x*)h1(x*)h2(x*)]                                           (2.13)   

Так как вектор не является нулевым, то из (2.12) следует, что det A=0. Отсюда следует, что вектор – столбцы матрицы  А линейно – зависимы. Следовательно, существуют три такие скаляра a, b и с, не все равные нулю, что

                            af(x*)+bh1(x*)+ch2(x*)=0

Постоянная а не может равняться нулю, так как согласно предположению  h1 иh2– линейно – зависимы. Поэтому после деления (13) на а приходим к (14):

f(x*)+h1(x*)+h2(x*)=0                                  (2.14)

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

              Следовательно, для отыскания минимума (2.6) при условиях (2.7) необходимо отыскать критическую точку функции Лагранжа L(х,…,)= f(х)+ 1h1(х)+ 2h2(х). Для того чтобы найти искомые 1,2, и  х*, решается совместно система уравнений (2.5) и (2.14).

              С геометрической точки зрения условие (2.14) означает, что f(x*) лежит в плоскости, натянутой на векторы hi(x*).

              Рассмотрим теперь общий случай произвольного n. Пусть задача нелинейного программирования  задана в виде (2.1), (2.2), все функции f(х), hi (х) i=(m<n) – вещественные функции на множестве R(n), имеющие непрерывные частные производные. Пусть S – подмножества множества R(n), на котором все функции hi(х)=0, i=, т.е.

                            S = (х : hi (х) = 0, i = ).

Тогда справедлива следующая теорема о множителях Лагранжа.

Теорема. Допустим, что существует такая точка х*, в которой достигается относительный экстремум (2.1) при условиях (2.2). Если ранг матрицы I = i = ; j = в точке х* равен m, то существуют m вещественных чисел 1,2,…,m, не все из которых равны нулю одновременно, при которых

.                                                                     (2.15)

Заметим, что если ввести функцию Лагранжа L(х,)=f(х)+ihi(х), то данная теорема определяет необходимые условия, при которых задача (1), (2) может быть сведена к нахождению решения уравнения L(х,) = 0.

На основании вышеизложенного метод множителей Лагранжа можно сформулировать следующим образом:

1.      Составляют функцию Лагранжа L(х,).

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

, j = ; i = .

3. Решают систему

                            =0, j =

                            = hi (х) =0, i = .                                                     (2.16)

и отыскивают точки х0 = {,…,}, удовлетворяющие системе (2.16).

              Найденные точки исследуют далее на минимум (или максимум). Для этого обычно используют определения и теоремы определения экстремумов, изложенные в Приложении.

2.2.Теорема Куна – Таккера. Решение задач НП с ограничениями – неравенствами.

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

              Пусть требуется найти

                                                 min f (х1,х 2,…, хn)                               (3.1)

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

                                                 g1 (х1,…,хn)0,

                                                  g2 (х1,…,хn)0,

                                                  ························                                  (3.2)

                                                  gm (х1,…,хn)0,

тогда вектор оптимального решения Х* должен удовлетворять следующим условиям:

=,                                               (3.3)

                            , , i = .                                                  (3.4)

              При рассмотрении задач минимизации  f(х) при условиях gi(х)0 может случиться так, что не существует таких , i = , при которых без дополнительных предположений о природе функций gi(x), были бы справедливы уравнения (3.3) и (3.4). Эти дополнительные предположения называют условиями регулярности ограничений. (В частности, в случае ограничений – равенств в качестве таких условий мы использовали линейную независимость векторов – градиентов ограничений).

              Выше мы получили условия оптимальности (3.3) и (3.4) для задач нелинейного программирования с линейными ограничениями. Обобщим эти условия на случай задачи (3.1) – (3.2), когда все ограничения нелинейны. 

Условия оптимальности решения задачи нелинейного программирования формулируются в следующей теореме Куна – Таккера, имеющей исключительно важное значение для теории нелинейного программирования.

              Теорема. Пусть f,gi(х), i= обладают непрерывными частными производными на некотором открытом множестве Rn, содержащем х*. Если х* является точкой минимума функции f(х) при ограничениях gi(х)0, i= ,удовлетворяющих условию регулярности в виде линейной зависимости, то существуют такие неотрицательные множители Лагранжа 1, 2,…,m , что

,

, .

Определим функцию Лагранжа следующим образом:

L (х,)=f (х)+.

Тогда теорему Куна – Таккера можно записать:

,

,

              Заметим, что множители Лагранжа в задаче нелинейного программирования с ограничениями – равенствами являются знаконеопределенными, тогда как в теореме Куна – Таккера они должны быть положительными.

              Итак, нами рассмотрена теоретическая часть метода. Следующая глава будет посвящена практической её части, то есть решению задачи при помощи метода множителей Лагранжа.