Тема 2.10. Методы решения задач нелинейного программирования.

Оглавление | Назад | Далее | Глоссарий понятий

Пример 2.10.1

Выше шла речь о локальном экстремуме функции n переменных. Как правило, в практических задачах необходимо определить наибольшее и наименьшее значения функции (глобальный экстремум) в некоторой области. Говорят, что функция z = f (X) имеет в точке X0 заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(X) ≤ f(X0) или соответственно выполняется для любой точки X € D.
Если область D замкнута и ограничена, то дифференцируемая функция z = f (X) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса).

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

Условный экстремум. Пусть необходимо найти экстремум функции z = f (x1, x2, ..., xn ) при условии, что переменные x1, x2, ..., xn удовлетворяют, уравнениям

φi (x1, x2, ..., xn ) = 0, i = 1, 2, ..., m, m < n
(2.32)

Предполагается, что функции f и φ, имеют непрерывные частные производные по всем переменным. Уравнения (2.32) называют уравнениями связи. Говорят, что в точке удовлетворяющей уравнениям связи (2.32), функция z = f (X) имеет условный максимум (минимум), если неравенство f(X0) ≥  f(X) (f(X0) ≤  f(X)) имеет место для всех точек X, координаты которых удовлетворяют уравнениям связи.
Легко заметить, что задача определения условного экстремума совпадает с задачей нелинейного программирования.
Один из способов определения условного экстремума применяется в том случае, если из уравнений связи (2.32) m переменных, например x1, x2, ..., xn, можно явно выразить через оставшиеся n - m переменных:

xi = ψi (xm + 1 , ..., xn ), i = 1, 2, ..., m,
(2.33)

Подставив полученные выражения для xf в функцию z, получи
мzi = f(ψi (xm + 1 , ..., xn ), ..., ψm (xm + 1 , ..., xn ), xm + 1 , ..., xn )

или

z = F(xm + 1 , ..., xn )
(2.34)

Задача сведена к нахождению локального (глобального) экстремума для функции (2.34) от n - m переменных. Если в точке функция (2.34) имеет экстремум, то в точке функция z = f (x1, ..., xn ) имеет условный экстремум.

Пример 2.10.2

Метод множителей Лагранжа

Другой способ определения условного экстремума начинается с построения вспомогательной функции Лагранжа, которая в области допустимых решений достигает максимума для тех же значений переменных x1, x2, ..., xn, что и целевая функция z.
Пусть решается задача определения условного экстремума функции z = f (X) при ограничениях (2.32)
Составим функцию

(2.38)

которая называется функцией Лагранжа. X, — постоянные множители (множители Лагранжа). Отметим, что множителям Лагранжа можно придать экономический смысл. Если f (x1, x2, ..., xn ) — доход, соответствующий плану X = (x1, x2, ..., xn ), а функция φi (x1, x2, ..., xn ) — издержки i-го ресурса, соответствующие этому плану, то X, — цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка). L(Х) — функция n + m переменных (x1, x2, ..., xn , λ1, λ2, ..., λn ). Определение стационарных точек этой функции приводит к решению системы уравнений

(2.39)

Легко заметить, что , т.е. в (2.48) входят уравнения связи. Таким образом, задача нахождения условного экстремума функции z = f (X) сводится к нахождению локального экстремума функции L(X). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума — исследования знака второго дифференциала d2L(X) в стационарной точке при условии, что переменные приращения Δxi - связаны соотношениями

(2.40)

полученными путем дифференцирования уравнений связи. Рассмотрим пример.

Пример 2.10.3

Если число переменных n = 2, нелинейные задачи можно решать геометрически. Ограничения должны быть записаны в виде неравенств

φi (x1, x2 ) ≤ bi , i = 1, 2, ..., m,
(2.41)

а целевая функция иметь вид

z = f(x1, x2 )
(2.42)

Как и в случае геометрического решения задач линейного программирования, сначала необходимо построить область допустимых решений (ОДР) — множество точек плоскости, удовлетворяющих неравенствам (2.41). Но в отличие от задач линейного программирования здесь ОДР не обязательно будет выпуклой и может быть даже разрывной. Экстремум функции может достигаться и внутри области, и на границе. После построения ОДР следует записать уравнения линий уровня целевой функции — множество точек плоскости, в которых целевая функция (2.42) постоянна: f(x1, x2 ) = C, и определить направление возрастания (убывания) целевой функции, построив, например, линии уровня для разных значений С.
Затем, перемещая линию уровня в нужном направлении в ОДР, найти точки области, в которых целевая функция принимает оптимальное значение.

Пример 2.10.4

Упражнения

Оглавление | Назад | Далее | Глоссарий понятий

Hosted by uCoz