Понятие задачи нелинейного программирования

ТЕМА 2.5. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

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

(1)

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

(2)

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

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

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

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

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

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

Графический метод.

Процесс нахождения решения задачи нелинейного программирования (1) – (2) с использованием её геометрической интерпретации включает следующие этапы:

1⁰. Находят область допустимых решений задачи, определяемую соотношениями (2) (если она пуста, то задача не имеет решения).

2⁰. Строят гиперповерхность .

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

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

3.1. Найти максимальное значение функции

(3)

при условиях

(4)

(5)

Р е ш е н и е. Так как целевая функция (3) нелинейная, то задача (3) – (5) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник ОАВС (рис. 3.1). Следовательно для нахождения её решения нужно определить такую точку многоугольника ОАВС, в которой функция (3) принимает максимальное значение. Построим линию уровня , где h – некоторая постоянная, и исследуем её поведение при различных значениях h. При каждом значении h получаем параболу, которая тем выше отдалена от оси Оx₁, чем больше значение h (рис. 3.1). Значит, функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС. В данном случае это точка D (рис. 3.1), в которой линия уровня касается стороны АВ многоугольника ОАВС.

Координаты точки D можно найти из системы уравнений

(6)

Решая эту систему, получим . Итак, при

Как видим, в задаче (3) – (5) точка максимального значения целевой функции не является вершиной многоугольника решений. Поэтому процедура перебора вершин, которая использовалась при решении задач линейного программирования, неприменима для решения данной задачи.

Поиск по сайту: