Нелинейное программирование

Нелинейное программирование [nonlinear programming] — раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и (или) областью допустимых решений, определенной нелинейными ограничениями. В экономике это соответствует тому, что результаты (эффективность) возрастают или убывают непропорционально изменению масштабов использования ресурсов (или, что то же самое, масштабов производства) — например, из-за деления издержек производства на предприятиях на переменные и условно-постоянные, из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чем предыдущую, из-за влияния экстерналий (см.Внешняя экономия, внешние издержки) и т.д.

В краткой форме задачу Н.п. можно записать так:

F (x)  →  max

при условиях   g (x)  ≤ bx  ≥ 0.

где xвектор искомых переменных, F (x)  — целевая функция, g (x)  — функция ограничений (непрерывно дифференцируемая), bвектор констант ограничений (выбор знака  ≤ в первом условии  здесь произволен, его всегда можно изменить на обратный).

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

Иначе говоря, задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. При этом не оговаривается форма ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция — нелинейна, а ограничения — линейны; целевая функция — линейна, а ограничения (хотя бы одно из них) — нелинейны; и целевая функция, и ограничения нелинейны.

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

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

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

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

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

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

Рис. Н.4  Нелинейное программиро­вание(заштрихована область допустимых решений)