II. Нелинейное программирование
1. Задачи нелинейного программирования
Выше рассматривался класс задач, характеризующихся двумя обстоятельствами:
-
функцией цели 
,
- условиями ограничений, накладываемых на переменные
.
Обе функции представляли собой линейные равенства (или неравенства, например, по ограничениям). Однако существует множество задач, для которых, во-первых, эти функции могут быть нелинейными, и, во-вторых, не обязательно наличие ограничений. Заметим принципиальную разницу в применимости принципа “оптимальности” к двум вышеуказанным типам функций:
- линейная функция (линия, плоскость) не имеет экстремума, т.е. ее
геометрические образы не имеют стационарных точек;
- нелинейная функция сама может иметь стационарные точки.
Поэтому становится понятным то различие в рассмотрении экстремальных задач в отношении типа функции цели. Кроме того, даже если при наличии линейной функции цели обязательные для нее ограничения описываются нелинейными функциями, то такая задача также не может уже рассматриваться как линейная.
Итак, если любая из функций F или gi(xj) представляет собой нелинейную функцию, то такая задача относится к области нелинейного программирования. Задача называется «с ограничениями», если существуют функции типа gi(xj) , или «без ограничений», если таковые отсутствуют. В зависимости от постановки и содержания задачи нелинейного программирования (ЗНП) могут решаться в один прием, а в отдельных случаях их решение представляется в виде итерационного пошагового алгоритма. В последнем случае говорят, то данная задача относится к классу задач «динамического программирования».
Задача нелинейного программирования:
,
(i=1…m),
,
где f и g – некоторые функции n переменных х1; х2;…; хn, в такой общей постановке не имеет универсального метода решения. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций цели и ограничений, разработаны эффективные методы их решений. В частности, ряд таких методов имеется для решения ЗНП при условии, что функция цели – вогнутая (или выпуклая) функция, а область допустимых решений – выпуклая. Такие ограничения свойственны квадратичным функциям, в рамках которых и будут рассмотрены ниже приведенные методы решений ЗНП.
2. Геометрическая интерпретация задач
нелинейного программирования с ограничениями
Известно,
что для ЗЛП существует область допустимых
решений (ОДР) в виде выпуклого многоугольника
или многогранника (в том числе и в
гиперпространстве) и оптимальное решение
находится в одной из вершин этой области
(но никогда – внутри ОДР). Для ЗНП с
ограничениями также существует область
допустимых решений, но, в отличие от
ЗЛП, она не всегда является выпуклой.
Если ОДР определена, то нахождение
решения задачи сводится к определению
такой точки, принадлежащей этой области,
через которую проходит гиперповерхность
наивысшего (или наинизшего) уровня,
описываемая функцией цели 
.
Указанная точка
может находиться как на границе ОДР,
так и внутри нее.
Этими особенностями ЗНП существенно
отличаются от ЗЛП.
Процесс нахождения решения ЗНП с ограничениями с использованием геометрической интерпретации включает следующие этапы:
- находят область допустимых решений задачи;
-
строят гиперповерхность на основании
функции цели
;
- определяют гиперповерхность наивысшего (наинизшего) уровня;
- находят точку ОДР, через которую проходит гиперповерхность и опреде-
ляют для нее значения переменных и функции цели.
З
а д а ч а 23. Найти максимальное значение
функции 
при
условиях 
,
,
,
,
.
Р е ш е н и е . Так как целевая функция нелинейная, то это ЗНП. Воспользовавшись методами линейного программирования, описанными выше, и тем, что задача имеет всего две переменные, в двухкоординатной системе построим область допустимых решений (рис.14, линии ограничений пронумерованы в порядке их записи в тексте). Это будет многоугольник ОАВС.
Рис.14. К нахождению решения задачи 23
Следуя приведенному выше алгоритму, для нахождения решения задачи нужно определить такую точку многоугольника ОАВС, в которой функция цели примет максимальное значение. С этой целью построим линию уровня
,
где h – некоторая постоянная, задаваемая произвольно.
Проанализируем поведение линии уровня при различных значениях h. Будем исследовать функцию такого вида:
,
при
условии 
.
Это будет парабола со смещенным центром, направленная вверх. Смещение найдем, продифференцировав исследуемую функцию и приравняв производную нулю:
,
откуда
.
Вторая
производная 
говорит о том, что в точке х1=5 функция имеет минимум. Следовательно, смещение линии уровня, которое должно раскладываться на горизонтальное и вертикальное, будет таким: смещение по горизонтали (т.е. вдоль оси ОХ) будет равно х1=5=const, а по вертикали (т.е. по оси OY) определится из соотношения
.
Очевидно, что с изменением h будет изменяться и х2 (т.е. смещение линии уровня). Иначе, парабола при различных значениях h может смещаться вверх или вниз, скользя точкой своего минимума по вертикали NN (рис.14). Если взять любую точку в ОДР, одновременно лежащую на параболе, то она определит значения как переменных х1, х2, так и функции цели F=h. Тогда минимальное значение функции цели будет при h=15 (и соответственно F=15) при следующих параметрах : х1=5; х2=0 . Ниже оси абсцисс параболу смещать нельзя, так как она выйдет из ОДР с нарушением требования неотрицательности параметров.
Если
далее увеличивать величину параметра
х2,
т.е. перемещать параболу вверх, очевидно
увеличение как h,
так и соответственно функции цели F.
Максимального значения она достигнет
в точке D,
т.е. когда парабола точкой минимума
коснется линии АВ (и при дальнейшем
перемещении вообще покинет ОДР). Это и
будет точка оптимального решения задачи.
Ее координаты: 
;
.
Для нее значение функции цели F*
=29.
Видно, что решение задачи хотя и лежит на границе ОДР (как и в ЗЛП), но не в вершине многоугольника ОАВС (что обязательно для ЗЛП).
З а д а ч а 24. Найти максимальное и минимальное значения функции
при
условиях 
,
,
,
.
Р е ш е н и е. Областью допустимых решений задачи является треугольник АВС, рис.15.
Полагая значение целевой функции равным некоторому числу h, получаем уравнение линии уровня:
.
Это
уравнение окружности с радиусом 
и с центром в точке Е(4;
3). С увеличением
(уменьшением) числа h
соответственно
увеличиваются (уменьшаются) значения
функции F.
Однако очевидно, что точка Е
(а соответственно
h=F=0
) – это не решение задачи, так как точка
Е не
принадлежит ОДР. Проводя из точки Е
окружности
разных радиусов, видим, что первый
Рис.15. Геометрическая трактовка задачи 24
контакт
с ОДР будет иметь окружность с радиусом
R1
и произойдет это касание в точке D.
Следовательно, координаты этой точки
и будут определять минимальное значение
функции цели. Найдем их, заметив, что
линия ограничений 
будет
касательной к окружности (линии уровня)
в точке D.
Продифференцировав уравнение окружности как неявную функцию переменной х1, получим
,
откуда
.
Теперь перепишем уравнение ограничений
.
Очевидно, что угловой коэффициент этой прямой равен k=10. Тогда можем записать
или
.
Добавив уравнение ограничений, получаем систему уравнений
,
.
Ее решением будут координаты точки D, соответственно и ЗНП:
;
; 
.
Продолжая дальше увеличивать радиус проводимых окружностей (линий уровня), видим, что они начинают пересекать ОДР и этот процесс закончится, когда последняя окружность с радиусом R2 пройдет через точку С. Дальнейшее увеличение радиуса приведет к нарушению ограничений задачи. Координаты точки С можно определить решением системы уравнений:
,
.
Получаем второе решение ЗНП:
;
; 
.
З а д а ч а 25. Найти максимальное и минимальное значения функции
при
условиях 
,
,
,
.
Р е ш е н и е . Областью допустимых решений для сформулированной задачи будет многоугольник ABCDE, рис. 16, а линиями уровня – окружности
с
центром в точке К(4;
3) и радиусом
.
Рис.16. Геометрическая трактовка задачи 25
Характерно, что в данной задаче центр линий уровня находится внутри ОДР. Очевидно, что функция цели (что одно и то же – величина h) примет минимальное (неотрицательное) решение в точке К, так как именно для нее h=0. Тогда имеем первое решение:
;
; 
.
Максимальное значение функция цели будет иметь в точке С - наиболее удаленной от центра и в которой будет наблюдаться последний контакт линии уровня с ОДР. Очевидно, координаты этой точки найдем, решив систему уравнений:
,
.
Решение
следующее: 
;
; 
.
З а д а ч а 26. Найти минимальное и максимальное значение функции
при
условиях 
,
,
.
Р е ш е н и е. В отличие от ранее рассмотренных задач видим, что в данном случае функция цели - линейная, а неравенства ограничений – нелинейные. Построим область допустимых решений. Первое неравенство – дуга окружности АВ с центром в начале координат и с радиусом R=5. Второе неравенство геометрически представляет гиперболу вида
,
которая в виде кривой CD совместно с дугой окружности АВ образует ОДР, рис.17.
Рис. 17 Геометрическая трактовка задачи 26
Линия
уровня – это прямая, имеющая уравнение
.
Решения задачи получим, если линию
уровня будем параллельно самой себе
перемещать в направлении ОДР. Там, где
она в первый раз коснется ограничительной
линии ОДР, будет находиться точка,
определяющая минимум функции цели (т.к.
переменные в функции цели имеют плюсовые
множители). Там же, где линия уровня
выйдет из ОДР, т.е. в точке касания с
другой ограничительной линией, будет
находиться решение на максимум функции
цели. В первом случае это точка Е,
во втором
случае это точка N.
Для нахождения первого решения продифференцируем уравнение гиперболы как функции в неявном виде и получим:
.
Так как это угловой коэффициент касательной к гиперболе, то действительно равенство:
,
откуда
получаем 
и
соответственно 
,
.
Теперь продифференцируем уравнение окружности и получим:
,
откуда
.
Очевидно
также, что 
.
Получаем
второе решение: 
;
; 
.