Характеристика задач

Методы НЛП применяются для решения задач с нелинейными ф-ми переменных. В общем случае задача математического программирования записывается в виде:

Если хотя бы одна функция в модели нелинейна, имеем задачу НЛП. Размерность задачи характеризуется размерностью вектора переменных n и числом условий m ₁+ m ₂. Сложность задачи определяется не столько размерностью, сколько свойствами функций цели и ограничений. Разнообразие задач НЛП очень велико. Универсальных методов решения таких задач не существует. Имеется весьма ограниченное число точных методов и намного больше приближенных. Наиболее развиты методы решения задач выпуклого программирования. К этому классу относятся задачи НЛП с выпуклым допустимым множеством и выпуклой целевой функцией при минимизации или вогнутой при максимизации. Допустимое множество выпуклое, если все функции линейные и выпуклы при неравенстве £ или вогнуты при ³. Задачи ЛП относятся к этому классу. Главная особенность задач выпуклого программирования в том, что они унимодальны - любой их локальный оптимум является глобальным. Для ряда задач выпуклого программирования с дифференцируемыми функциями разработаны точные методы. Наибольшие сложности возникают при решении многоэкстремальных задач, которые по определению не относятся к классу выпуклых.

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

В нелинейном программировании выделяют также задачи сепарабельного программирования. Это задачи, в которых все функции сепарабельны. Функция сепарабельна, если она представляется в виде суммы функций отдельных переменных. Линейная функция – частный случай сепарабельной. Сепарабельная задача может быть одновременно и задачей выпуклого программирования.

Задачи геометрического программирования составляют отдельный класс НЛП. Все функции в таких задачах являются позиномами. Позином – функция вида

, в которой a_kj – любые действительные числа.

Задачи геометрического программирования ставятся только на минимум:

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

и если все f_i (X)– линейные функции. Первая из них – выпуклая, вторая – вогнутая. Задачи с такими функциями могут входить в класс задач выпуклого программирования. Их решение строится на преобразовании модели к линейному виду с последующим применением методов ЛП.

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