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

3.1. Общая задача нелинейного программирования Постановка задачи.

Если в задаче математического программирования целевая функция z ( x ) и (или) хотя бы одна из функций системы ограничений _i ( x ) нелинейна, то такой раздел называется нелинейным программированием (НЛП). Методы НЛП получили широкое применение при расчете экономически выгодных партий запуска деталей в производство, при определении экономически выгодной партии поставки, распределении ограниченных ресурсов, размещении производительных сил и т.д.

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

z=f (x₁, x₂, ... x_n) (3.1)

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

g_i (x₁, x₂, ..., x_n)=b_i, i=1, 2, ..., k, (3.2)

g_i (x₁, x₂, ..., x_n)<=b_i, i=k+1, k+2, ..., m.

Если f и g — линейные функции, то задача (3.1), (3.2) является задачей линейного программирования.

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

Примеры задач нелинейного программирования (экономические).

1. На развитие предприятий отрасли на планируемый год выделено 220 млн. руб. Эти средства могут быть распределены между тремя предприятиями. Каждый вариант распределения обеспечивает к концу года определенный доход отрасли. Учитывая возможные варианты распределения капитальных вложений между предприятиями и получаемый при этом доход, определить такой вариант распределения капиталовложений, при котором доход отрасли является максимальным.

2. Между n предприятиями отрасли необходимо распределить выпуск некоторой однородной продукции. Затраты, связанные с производством x_i (i=1,..., n) единиц продукции на j-ом предприятии, зависят от объема производства и определяются функциями f_j (x_i). Зная, что продукции должно быть изготовлено не менее b единиц, составить такой план производства продукции предприятиями отрасли, при котором общие затраты, связанные с ее производством, минимальны.

3. В m отправления сосредоточена однородная продукция в количествах, равных a₁, ..., а_m единиц. Эту продукцию нужно перевезти в n пунктов назначения в объемах, равных b₁, ..., b_n единиц. Цены, связанные с перевозкой единицы продукции, зависят от объемов перевозимой продукции и определяются функциями f_ij (x_ij), где x_ij (i=1, ..., m; j=1, ..., n) — количество единиц продукции, перевозимой из i - го отправления в j - ый пункт назначения. Определить, сколько единиц продукции из i - го пункта отправления в j - ый пункт назначения следует доставить, чтобы вся продукция была перевезена в пункты назначения в необходимых объемах при минимальной общей стоимости перевозок.

Геометрическая интерпретация задачи нелинейного программирования.

В евклидовом пространстве Е_n система ограничений (3.2) определяет область допустимых решений задачи (ОДР). В отличие от ЗЛП она не всегда является выпуклой.

Если определена ОДР, то нахождение решения задачи (3.1), (3.2) сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: f (x₁, x₂, ..., x_n)=h. Указанная точка может находиться как на границе ОДР, так и внутри нее.

Класс ЗНЛП значительно шире класса задач линейного программирования. Основные результаты в нелинейном программировании получены при рассмотрении задач, в которых система ограничений линейная, а целевая функция нелинейная. Даже в таких задачах оптимальное решение может быть найдено только для узкого класса целевых функций. Рассмотрим частные случаи, когда целевая функция сепарабельная (является суммой n функций f_j (x_j)) или квадратичная.

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

Рассмотрение ЗНЛП начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (3.2) содержит только уравнения, отсутствуют условия не отрицательности и цело численности переменных, а функции g_i (x₁, x₂, ..., x_n) и f (x₁, x₂, ..., x_n) непрерывны и имеют частные производные не ниже второго порядка. Классические методы оптимизации при этом являются теоретическим аппаратом, позволяющим в ряде случаев обосновать разработку соответствующего вычислительного метода.

Рассмотрим пример решения ЗНЛП с двумя переменными. Так же как и в линейном программировании, они могут быть решены графически.

П р и м е р 1. Найти минимальное и максимальное значения сепарабельной функции Z=(x₁ 4)2+(x₂6)2 при ограничениях

x₁+x₂1,

2x₁+3x₂12,

x₁0, x₂0.

Р е ш е н и е. Область допустимых решений представляет собой многоугольник АВСЕ (рис. 3.1). Если положить Z=Q (Q>0), то получим уравнение окружности (x₁4)2+(x₂6)2=0. С уменьшением (увеличением) Q (квадрата радиуса) значения функции Z соответственно уменьшаются (увеличиваются).

Проводя из точки М как из центра окружности различных радиусов, получаем: минимальное значение функция Z(D)=196/13 принимает в точке D (24/13; 36/13), в которой окружность касается области решений. Точка D не является угловой, ее координаты находят в результате решения системы уравнений, соответствующих прямым MD и CE.

Функция Z имеет два локальных максимума: в вершине А(1;0) функция Z(A)=45, в вершине E (6; 0) функция Z(E)=40. Так как Z(A)>Z(E), то вершина А — точка глобального максимума.

Процесс нахождения решения ЗНЛП (3.1), (3.2) с использованием ее геометрической интерпретации включает следующие этапы:

1. Находят ОДР задачи, определяемую соотношениями (3.2) (если она пуста, то задача не имеет решения).

2. Строят гиперповерхность F (x₁, x₂, ..., x_n)=h.

3. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (3.1) сверху (снизу) на множестве допустимых решений.

4. Находят точку ОДР, через которую проходит гиперповерхность наивысшего (наинизшего) уровня, и определяют в ней значение функции (3.1).