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

Задача 2.3.1. На множестве решений системы ограничений

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

Решение. Линиями уровня функции z = являются окружности с центром в точке A(3;2) (рис.23). Из рисунка видно, что глобальный минимум функции z достигает в точке A(3;2), а глобальный максимум – в точке B(0;6).

рис. 23 рис.24

Задача 2.3.2. Найти глобальные экстремумы функции z = на множестве системы ограничений

Решение. На рисунке 24 множество допустимых решений заштриховано. Как видно из рисунка, оно не является выпуклым. Очевидно, что наименьшее значение функция z достигает в точке B, а наибольшее – в точке K (точка касания окружности и линии уровня).

Найдем координаты точек B и K. Точка B принадлежит прямой x+8=y и окружности Поэтому ее координаты находим из системы:

⟺ ⟺

⟺ или ,

B (5-3 3+3 ).

Точка K принадлежит линии центров с уравнением y= и окружности . Приходим к системе:

или ; K (.

Следовательно, Заметим, что точка F является точкой локального максимума, так как значение функции z в ней больше, чем значения в соседних вершинах B и C. Аналогично, точка C является точкой локального минимума.

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

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

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

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

Для задач нелинейного программирования, имеющих отличные от глобального локальные оптимумы, большинство вычислительных методов позволяет найти точку именно локального оптимума. В общем случае они не позволяют установить, совпадает ли она с точкой глобального оптимума. Тем не менее эти методы отыскания локального оптимума часто оказываются очень полезными на практике.

В теории нелинейного программирования особый интерес представляют выпуклые и вогнутые функции. Оказываются справедливыми следующие утверждения:

Пусть f(x) -выпуклая функция, заданная на замкнутом выпуклом множестве X. Тогда любой локальный минимум f(x) на X является глобальным минимумом на f(x) на X.

Если f(x) – вогнутая функция на замкнутом выпуклом множестве X, то любой локальный максимум f(x) на X является глобальным максимумом на f(x) на X.

Поясним сказанное на примере.

Задача 2.3.3. Найти глобальный максимум функции z=2x₁-x₁²+x₂ на множестве решений системы ограничений

Решение. Линиями уровня z=2x₁-x₁²+x₂ являются параболы(рис. 25). Функцию z можно рассматривать как сумму двух вогнутых функций f₁(x₁)=2x₁-x₁² и f₂(x₂)=x₂. Поэтому z -вогнутая функция. Следовательно, локальный максимум функции z будет глобальным. Z_max=4 и достигается в точке D(1;3).

рис.25

Дата добавления: 2015-11-14