Классификация и общая постановка задач нелинейного программирования

Задачи нелинейного программирования – большой класс разнообразных задач, из которых будем рассматривать только сводящиеся к задачам линейного программирования.

Ранее в задачах линейного программирования полагалось, что себестоимость, цена и др. показатели эффективности на ед. продукции не зависят от изменения объема производства. Однако в общем случае зависимости между переменными в ограничениях и целевой функции не могут быть линейными. Например, себестоимость единицы продукции снижается при увеличении объема производства.

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

Если обозначить целевую функцию и ограничения через обобщенную функцию h (x_j), то все многообразие задач нелинейного программирования можно свести к классификации (табл. 7.1).

В общем виде задача НЛП состоит в определении максимума (минимума) функции

f (x 1, x 2,..., xn) (1)

при условии, что ее переменные удовлетворяют условиям

где f и g_i некоторые известные функции n переменных; b_i – заданные числа.

Здесь имеется в виду, что в результате решения задачи будет определена точка x ⁰ = (x ₁⁰, x ₂⁰,..., x_n ⁰), координаты которой удовлетворяют соотношениям (2), и такая, что для всякой другой точки x = (x ₁, x ₂,..., x_n), удовлетворяющей условиям (2), выполняется неравенство

f (x ₁⁰, x ₂⁰,..., x_n ⁰) ³ f (x ₁, x ₂,..., x_n) при max целевой функции или

f (x ₁⁰, x ₂⁰,..., x_n ⁰) £ f (x ₁, x ₂,..., x_n) – при min целевой функции.

Если f и g_i – линейные функции, то задача (1), (2) – задача линейного программирования.

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

Нелинейные задачи решаются с помощью метода кусочно-линейной аппроксимации или метода множителей Лагранжа. В задачах квадратичного программирования применяется метод Била, Баранкина–Дорфмана, градиентные методы (метод Франка–Вулфа, штрафных функций, метод возможных направлений). В градиентных методах итерационный процесс осуществляется до того момента, пока градиент функции f (x) в очередной точке x_{k + 1} не станет равным нулю или пока | f (x_{k + 1})– f (x_k)|£e (достаточно малое положительное число, характеризующее точность полученного решения).

Таблица 6.1