Нелинейное программирование

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

а

б

в

 

 

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

 

Решение задач нелинейного программирования может давать два или более экстремума, тогда как решение линейного программирования дает один экстремум. На рис. 7.2 показан случай, соответствующий линейным ограничениям и нелинейной (квадратичной) функции цели, где она достигает максимального значения в двух точках А (локальный максимум) и В (глобальный максимум). На этом рисунке пунктиром обозначены постоянные значения функции цели f = const = α_i, сплошной линией ограничена область допустимых значений. При нелинейных ограничениях может иметь место случай многосвязной области допустимых значений, и в каждой изолированной подобласти функция цели может достигать своего одного или нескольких локальных экстремумов. На рис. 7.3 представлен случай двусвязной области, в которой функция цели достигает локальных экстремумов. Максимум в точке В – глобальный для всей области допустимых значений, в точке А – локальный.

 

 

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

 

 

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

 

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