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

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

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

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

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

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

f(x1, x2,…, xn) (1)

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

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

Здесь имеется в виду, что в результате решения задачи будет определена точка x0 = (x10, x20,…, xn0), координаты которой удовлетворяют соотношениям (2), и такая, что для всякой другой точки x = (x1, x2,…, xn), удовлетворяющей условиям (2), выполняется неравенство

f (x10, x20,…, xn0) ³ f (x1, x2,…, xn) при max целевой функции или

f (x10, x20,…, xn0) £ f (x1, x2,…, xn) – при min целевой функции.

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

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

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

Таблица 6.1