Краткие теоретические сведения

Решение общей задачи нелинейного программирования методом множителей Лагранжа

ЦЕЛЬ РАБОТЫ

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

КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Задача нелинейного программирования в общей постановке формулируется следующим образом:

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

Необходимые условия Куна-Таккера, позволяющие идентифицировать стационарные точки функции Лагранжа:

имеют следующий вид:

При этом каждое решение системы уравнений (а) должно удовлетворять ограничениям неравенствам:

а для задач максимизации (минимизации)

где

Стационарные точки должны быть подвергнуты дополнительным исследованиям с помощью достаточных условий, для того, чтобы установить, действительно ли в них достигается локальный экстремум (точки перегиба также удовлетворяют условиям (а)) и какой именно(max или min). Задача осложняется, когда требуется определить глобальный экстремум, который может достигаться на границе области и в этом случае не совпадать с локальным экстремумом.

Однако в некоторых случаях могут быть использованы косвенные приемы, опирающиеся на соответствующие теоремы:

ТЕОРЕМА 1. Функция заданная в замкнутой ограниченной области достигает в ней глобального максимума и глобального минимума.

ТЕОРЕМА 2. Любой локальный максимум выпуклой или локальный минимум вогнутой функции является одновременно и глобальным.

Поэтому:

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

экстремальными значениями на границе области. Наибольшее значение соответствует глобальному максимуму, а наименьшее-глобальному минимуму. Определение экстремумов на границе сводится к решению задач. Число задач складывается из задач, получаемых из системы (а) путем поочередного наложения условия ; число задач -путем поочередного наложения условия для всех сочетаний и т.д. Последняя задача () позволяет определить стационарные точки функции ; и если эти точки удовлетворяют условию (9), то при определенных допу- щениях (см. следующий пункт) приводят к глобальному максимуму (минимуму). Первая задача () приводит к системе, состоящей из n+m уравнений и неизвестных ().

При этом решения каких-то систем уравнений могут не удовлетворять условиям (8), (9), а некоторые могут вообще не иметь решений.

Далее для полученных стационарных точек можно установить max или min либо путем простого подсчета и сравнений значений целевой функции, либо анализируя матрицу Гессе (Н):

2. Если функция выпуклая (вогнутая) и стационарная точка получена, то в ней достигается глобальный max (min).

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

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

Дата добавления: 2015-07-15