Нелинейное программирование. Классическая задача
![]()
|
Нелинейное программирование. Классическая задачаЗадача линейного программирования, в которой целевая функция и (или) ограничения являются нелинейной функцией называется задачей нелинейного программирования (степенные, трансцендентные). Рассмотрим классическую задачу , которая была сформулирована и решена Лагранжем в 1798 году. ![]() ![]() Лагранж с помощью специальной функции свел эту задачу к задаче на безусловный экстремум, используя при этом теорему Ферма. ![]() ![]() ![]() Чтобы можно было применять функцию Лагранжа , необходимо : ![]() Задача (1)-(2) имеет решение если существует вектор ![]() ![]() ![]() ![]() ![]() Если априори известно, что задача (1)-(2) - имеет решение , то множитель ![]() Решим наш пример с помощью формализма Лагранжа ![]() ![]() ![]() Достаточное условие экстремума: для определения точки экстремума , получаемой из условия (4), (5), необходимо провести дополнительные исследования, т. Е. Использовать достаточные условия , которые заключаются в следующем: рассматривается матрица вторых производных - так называемый гессиан или матрица Гесса: ![]() ![]() Если матрица Гессе положительно определена в точке х*, то точка х* является точкой минимума ,а если отрицательно определена - то точкой максимума. Матрица называется положительно определенной , если все ее собственные числа ![]() Матрица называется отрицательно определенной если все ее собственные числа ![]() Если же матрица имеет собственные числа как положительные так и отрицательные, то о ее определенности ничего сказать нельзя. Если в неравенствах (7) и (8) имеет место знак нестрогих неравенств, то они называются положительно полуопределенными и отрицательно полуопределенными. Кроме неравенств (7) и (8), матрицы требуют дополнительных исследований для установления вида экстремума. Для определения вида экстремума используется так называемый критерий Сильвестра. Теорема: матрица ![]() ![]() ![]() Минор первого порядка ![]() ![]() ... ... ... ![]() Матрица ![]() ![]() Главные миноры должны быть знакочередующимися, причем первый минор должен быть отрицательным. ![]() это точка минимума Пример : Исследовать условный экстремум функции f0(x) в области ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Ответ: ![]() Геометрическая интерпретация с помощью линий уровня. Линии уровня это сечение плоскостями параллельными координатной плоскости Х1ОХ2 . Получаем систему концентрических окружностей ![]() Общая задача нелинейного программирования. Постановка задачи. ![]() ![]() - ограничение типа включения, U0 - простейший случай и может иметь следующий вид ![]() Обобщенное правило Лагранжа Если функции f0,f1,...,fm - дифференцируемы ;fm+1.,fm+2, ..., fs - непрерывно дифференцируемы в окрестности точки х* ,то существуют множители Лагранжа ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() - условие дополняющей нежесткости ![]() ![]() -соответствует ![]() При оптимальном решение ![]() Общая задача решается так: Сначала решается задача (1) при ограничениях (4) , т.е. классическая задача. Полученное решение подставляют в (2)и (3) и те из ограничений неравенств, которые не выполняются, добавляются как равенства к условию (4) и полученная классическая задача решается снова. И так, пока не выполним все условия (2) И (3). Замечание1: множители Лагранжа позволяют свести исходную задачу на условный экстремум (нахождение экстремума целевой функции при наличие ограничений) к задаче на безусловный экстремум нахождения минимальной функции Лагранжа (10). Используя необходимые условия экстремума для функции Лагранжа , переходим к решению системы уравнений и получаем решение ![]() Замечание 2:найденные точки , удовлетворяющие необходимому условию экстремума должны обязательно проверяться на их свойства с помощью критерия Сильвестра. Интерпретация множителей Лагранжа. ![]() ![]() Пусть эта задача имеет оптимальное решение ![]() ![]() ![]() Исследуем зависимость целевой функции (10) ![]() ![]() Исследуем зависимость ограничений (2) ![]() ![]() ![]() ![]() ![]() ![]() ![]() 0= ![]() ![]() умножаем на соответствующие ![]() ![]() ![]() ![]() ![]() просуммируем (6) по k : ![]() ![]() ![]() ![]() Объединим суммы ![]() ![]() ![]() ![]() ![]() ![]() ![]() В (7) принимаем ![]() ![]() ![]() ![]() ![]() ![]() Множители Лагранжа показывает зависимость целевой функции от значения вектора свободных членов. И если задача (1),(2) есть задача распределения ресурсов, то множители Лагранжа показывает эффективность использования того или иного ресурса. Это экономическая интерпретация множителей Лагранжа. |