Реферат: Классические методы безусловной оптимизации

,

не равен нулю (см. соответствующую теорему в курсе МА)

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

Подставляем  из (3) в целевую функцию (1), имеем:

                    (5)

Исследуемая функция  на экстремум можно произвести методом Эйлера – методом безусловной оптимизации непрерывно дифференцируемой функции.

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

Недостаток метода исключения: трудности, а иногда и невозможность получения системы выражений (3). Свободный от этого недостатка, но требующий выполнения условия (4)  является ММЛ.

5.2. Метод множителей Лагранжа. Необходимые условия в классической задаче условной оптимизации. Функция Лагранжа

ММЛ позволяет исходную задачу классической условной оптимизации:

                                                                                (1)

                                                                (2)

Преобразовать в задачу безусловной оптимизации специально сконструированной функции – функции Лагранжа:

,                                           (3)

где ,  - множители Лагранжа;

.

Как видно,  представляет собой сумму, состоящую из исходной целевой функции  и "взвешенной" суммы функций ,  - функции, представляющие их ограничения (2) исходной задачи.

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

Используя концепция зависимых и независимых переменных  - зависимые переменные;  - независимые переменные, тогда представим (5) в развернутом виде:

                                                  (5')

Из (2) с очевидностью следует система уравнений вида:

,                                                                          (6)

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

Представим (6) в "развернутом" виде, используя концепцию зависимых и независимых переменных:

,                                      (6')

Заметим, что (6') в отличии от (5') представляет собой систему, состоящую из  уравнений.

Умножим каждое -ое уравнение системы (6') на соответствующий -ый множитель Лагранжа. Сложим их между собой и с уравнением (5') и получим выражение:

       (7)

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

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

Структуру такой системы уравнений легко получить приравняв выражение в квадратной скобке под знаком первой суммы нулю:

,               (8)

Перепишем (8) в виде

,                  (8')

Система (8') представляет собой систему из  линейных уравнений относительно  известных: . Система разрешима, если  (вот почему, как и в методе исключения в рассматриваемом случае должно выполняться условие ). (9)

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

                        (10)

Система уравнений (8) состоит из  уравнений, а система уравнений (10) состоит из  уравнений; всего  уравнений в двух системах, а неизвестных

: ,

Недостающие  уравнений дает система уравнений ограничений (2):

,

Итак, имеется система из  уравнений для нахождения  неизвестных:

             (11)

Полученный результат – система уравнений (11) составляет основное содержание ММЛ.

Легко понять, что систему уравнений (11) можно получить очень просто, вводя в рассмотрение специально сконструированную функцию Лагранжа (3).

Действительно

,                                                           (12)

,                                                                           (13)

Итак, система уравнений (11) представима в виде (используя (12), (13)):

                                                                              (14)

Система уравнений (14) представляет необходимое условие в классической задаче условной оптимизации.

Найденное в результате решение этой системы значение вектора  называется условно-стационарной точкой.

Для того, чтобы выяснить характер условно-стационарной точки  необходимо воспользоваться достаточными условиями.

5.3 Достаточные условия в классической задаче условной оптимизации. Алгоритм ММЛ

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

Относительно просто, подобно тому, как были получены достаточные условия в задаче на безусловный экстремум. Можно получить достаточные условия и в задаче классической условной оптимизации.

Результат этого исследования:

где  - точка локального условного минимума.

где  - точка локального условного максимума,  - матрица Гессе с элементами

,

Матрица Гессе  имеет размерность .

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

,

тогда достаточные условия будут иметь вид:

,  - точка локального условного минимума.

,  - точка локального условного максимума.

Доказательство: Алгоритм ММЛ:

1)                составляем функцию Лагранжа: ;

2)                используя необходимые условия, формируем систему уравнений:

3)                из решения этой системы находим точку ;

4)                используя достаточные условия, определяем, является ли точка  точкой локального условного минимума или максимума, затем находим

1.5.4. Графо-аналитический метод решения классической задачи условной оптимизации в пространстве  и его модификации при решении простейших задач ИП и АП

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

; ; ;

В  - общая касательная для функции  и функции , представляющей ОДР .

Как видно из рисунка точка  - точка безусловного минимума, точка  точка условного локального минимума, точка  - точка условного локального максимума.

Докажем, что в точках условных локальных экстремумов кривая  и соответствующие линии уровня

; .

Из курса МА известно, что в точке касания выполняется условие

где  - угловой коэффициент касательной, проведенной соответствующей линией уровня;  - угловой коэффициент касательной, проведенной к функции

Известно выражение (МА) для этих коэффициентов:

;

Докажем, что эти коэффициенты равны.

;

потому что об этом "говорят" необходимые условия

.

Вышесказанное позволяет сформулировать алгоритм ГФА метода решения классической задачи условной оптимизации:

1)       строим семейство линий уровня целевой функции:

; ;

2)       строим ОДР, используя уравнение ограничения

3)       с целью внесения исправления возрастания функции , находим  и выясняем характер экстремальных точек;

4)       исследуем взаимодействие линий уровня и функции , находя при этом из системы уравнений  координаты условно стационарных точек – локальных условных минимумов и локальных условных максимумов.

5)       вычисляем

Следует особо отметить, что основные этапы ГФА метода решения классической задачи условной оптимизации совпадают с основными этапами ГФА метода решения задач НП и ЛП, отличие лишь в ОДР , а также в нахождении местоположения экстремальных точек в ОДР (например, в задачах ЛП эти точки обязательно находятся в вершинах выпуклого многоугольника, представляющего ОДР ).

5.5. О практическом смысле ММЛ

Представим классическую задачу условной оптимизации в виде:

                                                                                (1)

                                                               (2)

где  - переменные величины, представляющие в прикладных технических и экономических задачах переменные ресурсы.

В пространстве  задача (1), (2) принимает вид:

                                                                                (1')

где  - переменная величина.        (2')

Пусть  - точка условного экстремума:

При изменении  изменяется

, т.е.

Соответственно изменится и значение целевой функции:

Вычислим производную:

.                                                                (3)

                                                            (4)

                                                                                     (5)

Из (3), (4), (5).                                                             (6)

Из (5).                                                                           (5')

Подставим (5') в (3) и получаем:

                                                   (6')

Из (6), что множитель Лагранжа  характеризует "реакцию" значение (ортогональна значению целевой функции) на изменения параметра .

В общем случае (6) принимает вид:

;                                                                             (7)

Из (6), (7), что множитель ,  характеризует изменение  при изменении соответствующего -того ресурса на 1.

Если  - максимальная прибыль или минимальная стоимость, то ,  характеризует изменения этой величины при изменении ,  на 1.

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

Пара  называется седловой точкой, если выполняется неравенство.

                                                            (1)

Очевидно, что из (1).                        (2)

Из (2), что .                                                  (3)

Как видно система (3) содержит  уравнений, подобных тем  уравнениям, которые представляют необходимое условие в классической задаче условной оптимизации:

                                                                               (4)

где  - функция Лагранжа.

В связи с аналогией систем уравнений (3) и (4), классическую задачу условной оптимизации можно рассматривать как задачу о нахождении седловой точки функции Лагранжа.