Общая постановка задачи НП

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

Найти

при условиях

где функции f(x₁, …, x_n), g_i(x₁, …, x_n), i = 1, …, m в общем случае нелинейны.

В отличие от задач линейного программирования (ЛП) общего решения задач НП нет.

В задачах ЛП множество допустимых решений выпукло с конечным числом крайних точек. Перебирая их можно за конечной число шагов найти оптимальное решение. В задачах НП выпуклость множество допустимых решений и конечность числа его крайних точек необязательны, из-за чего возникают трудности нахождения решения задачи НП.

Решение задача НП при ограничениях - равенствах

Отыскать минимум (или максимум) функции f при таких ограничениях можно с помощью метода множителей Лагранжа.

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

Пусть требуется найти

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

Предположим, что функции f, h₁, h₂, …, h_m дифференцируемы.

Введем набор переменных λ₁, λ₂, …, λ_m (по числу ограничений), которые называются множителями Лагранжа и составим функцию Лагранжа следующего вида:

Далее находят частные производные ∂L(x,λ)/ ∂x_j, ∂L(x,λ)/ ∂λ_i и составляют систему из n+m уравнений:

Решая систему уравнений (3.4) находят точку

Далее эту точку исследуют на минимум или максимум.

Пример 3.1. Имеется два способа производства некоторого продукта. Обозначим через х₁ и х₂ объемы производства по первой и второй технологиям. Издержки производства по каждой технологии зависят от объемов производства и определяются выражениями:

С точки зрения маркетинга за определенный промежуток времени необходимо произвести строго определенный объем продукции:

h: х₁ + х₂ = С.

Для этого необходимо так спланировать объемы производства х₁ и х₂, чтобы общие издержки производства были минимальны.

Функция Лагранжа для этой задачи имеет вид:

или в развернутом виде

Где первое слагаемое представляет собой целевую функцию f. Дифференцируя функцию Лагранжа по переменным х иλ получаем систему уравнений

Решая эту систему получаем оптимальные (наилучшие) объемы производства x₁^* и x₂^* , обеспечивающие минимум совокупных расходов производства и удовлетворяющие ограничению на общий объем выпуска:

Допустим, что параметры задачи имеют следующие значения:

a0	a1	a2	b0	b1	b2	c

Тогда конкретное решение равно:

И оно удовлетворяет ограничению

Решение задача НП при ограничениях – неравенствах

Постановка задачи нахождения экстремума выглядит так:

Процедура поиска оптимального решения меняется принципиально.

1) Если минимум функции f лежит внутри области допустимых решений, задаваемых ограничениями h_i, то они не влияют на результат решения, то есть имеет место задача безусловной оптимизации;

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

Типы функций f и h и характер ограничений определяют многообразие задач НП: выпуклое и вогнутое программирование, квадратичное программирование и т.п.

Путь задача НП задана в виде:

Найти

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

Решение задачи осуществляют по следующей схеме: конструируют функцию Лагранжа описанным выше способом и формируют систему условий (условия Куна – Таккера):

Для нахождения оптимального решения x^* необходимо найти такой вектор λ^* ≥ 0, чтобы выполнялись условия (3.9).

Если функции f и h вогнуты, то условия (3.9) оказываются и достаточными.