Общая задача нелинейного программирования

Общая задача математического программирования формулируется следующим образом: найти вектор , доставляющий экстремум функции

(9.1)

и удовлетворяющий системе ограничений

	(9.2)
	(9.3)

На некоторые переменные часто накладывается условие неотрицательности и целочисленности. Если хотя бы одна из функций в (9.1) - (9.3) является нелинейной, то и задача математического программирования считается нелинейной.

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

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

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

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

x₁≥0, х₂≥0.

Решение. Область допустимых решений представляет собой многоугольник АВСЕ (рис. 9.1). Если положить Ф=R²=const, то получим уравнение окружности
(x₁ - 4)²+(х₂ -6)²= R² с центром в точке М(4,6) и радиусом R. С уменьшением или увеличением R соответственно уменьшаются или увеличиваются значения функции Ф.

Рис. 9.1 Рис. 9.2

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

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

Пример 2. Пусть область допустимых решений останется прежней, а Ф = (x₁-4)²+(х₂-1)². Найти минимальное и максимальное значения этой функции.

Решение. Минимальное значение функция принимает в точке М (4; 1) (рис. 9.2): Ф(M) = 0. Функция Ф имеет два локальных максимума: в вершине Е (6; 0) функция Ф(E) = 5, в вершине С (0; 4) функция Ф(C) = 25, причем глобальный максимум достигается в вершине С.

Пример 3. Найти минимальное и максимальное значения функции при ограничениях

Рис. 9.3

Решение. В этом случае область допустимых решений (рис. 9.3) не является выпуклой и состоит из двух отдельных частей. Минимальное значение функции Ф = 17 достигается в точках А (1; 4) и L (4; 1). Функция Ф имеет два локальных максимума: в точке D (2/3; 6) и в точке М (7; 4/7), причем М является точкой глобального максимума.