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

Напомним сначала постановку задачи линейного программирования:

найти Постановки задачи нелинейного программирования - student2.ru , такой что

Постановки задачи нелинейного программирования - student2.ru

на множестве допустимых решений, заданных ограничениями

Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru Постановки задачи нелинейного программирования - student2.ru .

Задача нелинейного программирования формулируется аналогично:

найти вектор Постановки задачи нелинейного программирования - student2.ru , (или точку Постановки задачи нелинейного программирования - student2.ru ), такой (такую), что целевая функция достигает максимума (минимума):

Постановки задачи нелинейного программирования - student2.ru (4.5)

на множестве допустимых решений, заданных ограничениями

Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru (4.6)

Задача сводится к нахождению условного экстремума функции Постановки задачи нелинейного программирования - student2.ru при ограничениях, которые задаются неравенствами.

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

Оставляя в стороне вопрос о существовании решения поставленной задачи, можно предложить следующий алгоритм решения:

- находим стационарные точки (подозрительные на экстремум) функции Постановки задачи нелинейного программирования - student2.ru и сохраняем те из них, координаты которых удовлетворяют условиям (4.6);

- находим точки, в которых может достигаться экстремум функции Лагранжа:

Постановки задачи нелинейного программирования - student2.ru

- вычисляем значения целевой функции Постановки задачи нелинейного программирования - student2.ru во всех найденных точках и находим её глобальный максимум (или минимум).

Если функцию Постановки задачи нелинейного программирования - student2.ru интерпретировать как доход (стоимость), а Постановки задачи нелинейного программирования - student2.ru — как объемы некоторых ресурсов, то множители Лагранжа Постановки задачи нелинейного программирования - student2.ru показывают, как изменится максимальный доход (минимальная стоимость), если количество ресурса Постановки задачи нелинейного программирования - student2.ru -го вида увеличить на единицу.

Пример. Найти наибольшее и наименьшее значения целевой функции (т.е. её глобальные Постановки задачи нелинейного программирования - student2.ru и Постановки задачи нелинейного программирования - student2.ru ) целевой функции

Постановки задачи нелинейного программирования - student2.ru (4.5*)

на множестве допустимых решений, заданных ограничением:

Постановки задачи нелинейного программирования - student2.ru . (4.6*)

Решение.

1. Находим стационарные точки (точки, подозрительные на экстремум) функции Постановки задачи нелинейного программирования - student2.ru и сохраняем те из них, координаты которых удовлетворяют условиям (4.6*).

Для этого решаем систему

Постановки задачи нелинейного программирования - student2.ru , получаем Постановки задачи нелинейного программирования - student2.ru ,

т.е. точку Постановки задачи нелинейного программирования - student2.ru , удовлетворяющую условиям (4.6*) и являющуюся внутренней точкой области допустимых решений.

2. Находим точки, в которых может достигаться экстремум функции Лагранжа:

Постановки задачи нелинейного программирования - student2.ru .

Для этого решаем систему:

Постановки задачи нелинейного программирования - student2.ru ,

получаем

Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru ,

т.е. шесть точек, лежащих на границе области допустимых решений:

Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru ,

Постановки задачи нелинейного программирования - student2.ru . Постановки задачи нелинейного программирования - student2.ru .

3. Вычисляем значения целевой функции во всех найденных точках:

Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru Постановки задачи нелинейного программирования - student2.ru ,

Постановки задачи нелинейного программирования - student2.ru Постановки задачи нелинейного программирования - student2.ru , Постановки задачи нелинейного программирования - student2.ru Постановки задачи нелинейного программирования - student2.ru .

Ответ: Постановки задачи нелинейного программирования - student2.ru , достигается при Постановки задачи нелинейного программирования - student2.ru , во внутренней точке области допустимых решений, Постановки задачи нелинейного программирования - student2.ru , достигается при Постановки задачи нелинейного программирования - student2.ru , на границе области допустимых решений.

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

Наши рекомендации