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

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 система ограничений (6.2) определяет область допустимых решений задачи (ОДР).

В отличие от ЗЛП она не всегда является выпуклой.

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

Указанная точка может находиться как на границе ОДР, так и внутри нее.

Класс ЗНЛП значительно шире класса задач линейного программирования.

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

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

Рассмотрим частные случаи, когда целевая функция сепарабельная (является суммой n функций f_j (x_j)) или квадратичная.

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

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

Рассмотрение ЗНЛП начинают с классической задачи оптимизации.

Задачи такого рода имеют место, если система (6.2) содержит только уравнения, отсутствуют условия неотрицательности и целочисленности переменных, а функции g_i(x₁,x₂,...,x_n) и f(x₁,x₂,...,x_n) непрерывны и имеют частные производные не ниже второго порядка.

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

Рассмотрим пример решения ЗНЛП с двумя переменными.

Так же как и в линейном программировании, они могут быть решены графически.

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

x₁+x₂³ 1,

2 x₁+ 3 x₂ £12,

x₁³ 0, x₂³ 0.

Р е ш е н и е. Область допустимых решений представля-ет собой многоугольник АВСЕ (рис. 2.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), то вершина А — точка глобального максимума.

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

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

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

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

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