ГОСы 2012

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

Математическая модель задачи нелинейного программиро­вания в общем виде формулируется следующим образом: найти вектор   = (х₁, x₂, …, x_n), удовлетворяющий системе ограни­чений

 и доставляющий экстремум (наибольшее или наименьшее зна­чение) целевой функции

где x_j — переменные, j = ; L, f, g_i — заданные функции от n переменных, b_i — фиксированные значения.

Нелинейное программирование применяется при прогнози­ровании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудова­ния и т.д.

Для задачи нелинейного программирования в отличие от линейных задач нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программи­рование, градиентные методы, приближенные методы реше­ния, графический метод.

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

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

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

В течение последних двух десятилетий из нелинейного программирования выделились самостоятельные разделы:

• выпуклое программирование,
• квадратичное программирование,
• целочисленное программирование,
• стохастическое программирование,
• динамическое программирование и др.

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

Среди задач выпуклого программирования более подробно изучены задачи квадратичного программирования. В этих задачах целевая функция – квадратична, а ограничения – линейны.

В задачах целочисленного программирования неизвестные параметры могут принимать только целочисленные значения.

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

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

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

По количеству локальных критериев в целевой функции методы нелинейного программирования делятся на:

• однокритериальные,
• многокритериальные.

По длине вектора  методы делятся на:

• однопараметрические или одномерные (n=1),
• многопараметрические или многомерные (n>1).

По наличию ограничений методы нелинейного программирования делятся на:

• без ограничений (безусловная оптимизация),
• с ограничениями (условная оптимизация).

По типу информации, используемой в алгоритме поиска экстремума методы делятся на:

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

Ни один метод нелинейного программирования не является универсальным. В каждом конкретном случае необходимо приспосабливать применяемый метод к особенностям решаемой задачи.