Метод Эйлера – классический метод решения задач безусловной оптимизации.

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

Алгоритм этого метода достаточно прост:

1) используя необходимые условия формируем систему в общем случае нелинейных уравнений. Отметим, что решить аналитически эту систему в общем случае невозможно; следует применить численные методы решения систем нелинейных уравнений (НУ) (см. " ЧМ" ). По этой причине метод Эйлера будет аналитически-численным методом. Решая указанную систему уравнений находим координаты стационарной точки .;

2) исследуем ДКФ и матрицу Гессе , которая ее представляет. С помощью критерия Сильвестра определяем, является ли стационарная точка точкой минимума или точкой максимума;

3) вычисляем значение целевой функции в экстремальной точке .

Методом Эйлера решить следующую задачу безусловной оптимизации: найти 4 стационарные точки функции вида:

.

Выяснить характер этих точек, являются ли они точками минимума, или Седловыми (см. [3]). Построить графическое отображение этой функции в пространстве и на плоскости (с помощью линий уровня).

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

 

 

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

 

Классическая задача условной оптимизации и методы ее решения: Метод исключения и Метод множителей Лагранжа (ММЛ).

Как известно, классическая задача условной оптимизации имеет вид:

(1)

 

(2)

График, поясняющий постановку задачи (1), (2) в пространстве .

(1')

(2')

,

- уравнения линий уровня.

Итак, ОДР в рассматриваемой задаче представляет собой некоторую кривую, представленную уравнением (2').

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

Задачу (1'), (2') можно решить методом исключения (подстановки), решив уравнение (2') относительно переменной , и подставляя найденное решение (1').

.

Исходная задача (1'), (2') таким образом преобразована в задачу безусловной оптимизации функции , которую легко решить методом Эйлера.

 

Метод исключения (подстановки).

Пусть целевая функция зависит от переменных:

 

, называются зависимыми переменными (или переменными состояния); соответственно можно ввести вектор

.

Оставшиеся переменных называются независимыми переменными решения.

Соответственно можно говорить о вектор-столбце:

и вектора .

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

(1)

 

(2)

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

(3)

Всегда ли система уравнений (2) разрешима относительно зависимых переменных - не всегда, это возможно лишь в случае, когда определитель , называемый якобианом, элементы которого имеют вид: , не равен нулю (см. соответствующую теорему в курсе МА).

 

 

(4)

 

 

ЛК №7

27.03.2003

 

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

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

(5)

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

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

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

 

1.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) представляет необходимое условие в классической задаче условной оптимизации.

 

 

ЛК №8

03.04.2003

 

 

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

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

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: