Задачи нелинейного программирования

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

при условиях:

причем функции и могут быть нелинейными.

Графический метод решения

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

Алгоритм графического метода

1. Построить область допустимых решений.

2. Построить семейство линий уровня, проходящих через область допустимых решений.

3. Построить вектор-градиент целевой функции, который определяет направление возрастания (убывания) функции.

4. Выбрать линию уровня, наиболее удаленную в направлении вектора-градиента (или в противоположном направлении — в задаче на минимум) и проходящую через область допустимых решений. Определить точки области, через которые она проходит.

5. Найти координаты точек экстремума и значение целевой функции в этих точках.

Пример задачи №19

Найти глобальные экстремумы функции

при ограничениях

Решение:

Построим область допустимых решений. Она состоит из двух частей: и . Линиями уровня являются параллельные

Градиент функции . Следовательно, функция достигает своего глобального максимума в точке , а в точке —глобального минимума,

Очевидно, что в точке функция имеет локальный минимум, а в точке — локальный максимум.

Пример задачи №20

Найти глобальные экстремумы функции при ограничениях

Решение:

Множество является областью допустимых решений. Линии уровня функции

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

минимум — в точке

Пример задачи №21

Определить глобальный минимум функции

на множестве решений системы

Решение:

Множество допустимых решений является выпуклым. Линии уровня функции — эллипсы с центром в точке (3; 6). Минимум достигается в точке касания прямой и некоторого эллипса из семейства линий уровня. Из уравнения прямой определим ее вектор нормали . В точке касания градиент функции направлен по нормали к линии уровня, то есть его направление совпадает с направлением нормали к прямой . Найдем градиент функции

Так как точка касания лежит на прямой ив ней градиент функции коллинеарен вектору нормали к прямой , то получаем систему из двух уравнений для определения координат этой точки:

Решением данной системы является:

откуда

при этом

Пример задачи №22

Найти экстремумы функции

при условии

Решение:

Из рисунка видно, что минимум целевой функции достигается в точке , а максимум в точке .

Точка является точкой пересечения линии уровня

и гиперболы

Найдем ее координаты.

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

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