НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Определение. Задача математического программирования, в которой либо целевая функция, либо ограничения, либо и то, и другое нелинейны, называется нелинейной.

Задачи нелинейного программирования на практике возникают довольно часто, например, когда затраты растут непропорционально количеству закупленных или произведённых товаров – эффект «оптовости».

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

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

На рис. 1множества - выпуклые, множества выпуклыми не являются.

	а)			в)		г)

Рис. 1

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

На рис. 2изображён график функ-ции одной переменной, являющейся выпуклой на всей числовой прямой.

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

Если функция вогнутая на выпуклом множестве , то геометриче­ски это означает, что отрезок, соединяющий любые две точки её графика, лежит на графике или ниже его (рис. 3).

Если отрезок, соединяющий любые две точки графика функции, лежит ниже этого графика, то функция является строго вогнутой. Рис. 3

Если - выпуклая функция, то - вогнутая функ­ция, и наоборот.

Теорема. Пусть - выпуклая функция, заданная на замкнутом вы­пуклом множестве ; тогда любой локальный минимум на является и глобальным.

Следствие 1. Если глобальный минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.

Следствие 2. Если - строго выпуклая функция, то её глобаль­ный минимум на выпуклом множестве достигается в единственной точке.

Теорема. Пусть - выпуклая функция, заданная на замкнутом вы­пуклом множестве , и, кроме того, она непрерывна вместе со своими частными произ­водными[1] первого порядка во всех внутренних точках . Пусть - точка, в кото­рой градиент функции равен нулю. Тогда в точке достигается локальный мини­мум, совпадающий с глобальным минимумом.

Градиентом функции называется вектор, проекциями кото­рого на координатные оси служат соответствующие частные производные, т.е.

.

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

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

Для вогнутых функций рассмотренные результаты можно сформулировать сле­дующим образом. Пусть - вогнутая функция, заданная на замкнутом вы­пуклом множестве . Тогда любой локальный максимум на явля­ется глобальным. Если глобальный минимум достигается в двух различных точках множества, то он достигается и в любой точке отрезка, соединяющего данные точки. Для строго вогнутой функции существует единственная точка, в которой она достигает глобального максимума. Глобальный минимум вогнутой функции, если он конечен, на замкнутом, ограниченном снизу множестве, должен достигаться в одной или несколь­ких его крайних точках.

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

Пример 1. Найти минимальное и максимальное значения функции при ограничениях

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

С уменьшением (увеличением) (квадрата радиуса) значения функции соответст­венно уменьшаются (увеличиваются).

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

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

Для двух перпендикулярных прямых

и выполняется соотношение:

(или ). Уравнение прямой : .

Тогда уравнение прямой : .

Для определения воспользуемся тем, что эта прямая проходит через точку :

, . Т.е. уравнение прямой : .

Определяем координаты точки :

Минимальное значение функции:

.

Функция имеет два локальных максимума:

в вершине функция , в вершине функция .

Так как , то вершина - точка глобального максимума.

Ответ: при , ; при , .

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

.

Найти минимальное и максимальное значения этой функции.

Решение.

Минимальное значение функция прини­мает в точке : . Функция имеет два локальных максимума:

в вершине функция ,

в вершине функция , т.е. глобальный максимум достигается в вер­шине .

Ответ: при , ;

при , .

Пример 3. Найти минимальное и максимальное значение функции

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

Решение.

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

Минимальное значение функции достигается в точках и .

Функция имеет два локальных максимума:

в точке функция и в точке функция . Точка является точкой глобального максимума.