Рассмотрим один из них – метод множителей Лагранжа.

⇐ ПредыдущаяСтр 7 из 7

Условный экстремум находится, когда переменные х и у, входящие в функцию u=f(x, y), не являются независимыми, т.е. существует некоторое соотношение j(х, у) = 0, которое называется уравнением связи.

Тогда из переменных х и у только одна будет независимой, т.к. другая может быть выражена через нее из уравнения связи. Тогда u = f(x, y(x)).

В точках экстремума:

Кроме того:

Умножим второе равенство на число l и сложим с первым равенством.

Выражение u = f(x, y) + lj(x, y) называется функцией Лагранжа. называют множителями Лагранжа.

Для выполнения этого условия во всех точках найдем неопределенный коэффициент l так, чтобы выполнялась система трех уравнений:

Полученная система уравнений является необходимыми условиями условного экстремума. Однако это условие не является достаточным. Поэтому при нахождении критических точек требуется их дополнительное исследование на экстремум.

Для случая переменных функция Лагранжа имеет вид:

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

- функция переменных. Определение стационарных точек функции приводит к решению системы уравнений

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

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

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

Н^B = ,

где P = и Q = для всех i и j.

Матрица Н^B называется окаймленной матрицей Гессе.

Пусть имеется стационарная точка (Ф0, l0) функции Лагранжа L(Ф0, l0) и окаймленная матрица Гессе Н^B вычислена в точке (Ф0, l0). Тогда Ф0 является:

- точкой максимума, если, начиная с главного (углового) минора порядка 2m+ 1, последующие п – m угловых миноров окаймленной матрицы Гессе Н^B образуют знакопеременный числовой ряд, в котором знак первого члена определяется множителем (–1)^m⁺¹.

- точкой минимума, если, начиная с главного (углового) минора порядка 2m+ 1, последующие п–m главных (угловых) миноров матрицы НB имеют знаки, определяемые множителем (–1)^m.

Эти условия являются достаточными для определения экстремальной точки. Однако на практике, в силу большой вычислительной сложности, эти условия используются редко. Чаще наличие экстремума в стационарной точке проверяется с помощью исследования величины функции Z(X) в малой окрестности этой стационарной точки.

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

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

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

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

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

⇐ Предыдущая 1 2 3 4 5 67