Особенности одномерных моделей оптимизации

Имеются две причины изучения методов оптимизации функции одной переменной. Первая из них заключается в том, что на одномерных задачах можно демонстрировать многие трудности, с которыми приходится сталкиваться при решении нелинейных оптимизационных задач. Нет необходимости для разъяснения этих трудностей обращаться к многомерным задачам, иногда менее понятным. Вторая причина состоит в том, что во многих методах решения нелинейных оптимизационных задач со многими переменными на том или ином шаге, по существу, используются алгоритмы оптимизации для одной переменной. Следовательно, для применения методов, предназначенных для решения оптимизационных задач общего вида, требуется знакомство с методами оптимизации одномерных моделей.
Начнем с того, что в рамках всего последующего обсуждения ограничимся рассмотрением "максимизации" в смысле оптимизации. [Если в реальной задаче требуется минимизировать целевую функцию f(х), то можно переформулировать модель, максимизируя —f(x).)
Сначала рассмотрим задачу максимизации линейной функции одной переменной с(х)=(с₀+c₁x) (см. рис. 11.1). Ответ здесь настолько тривиален, что он даже не обсуждается в задачах линейномго программирования, однако в данном случае он используется как отправная точка для рассмотрения оптимизационных методов в нелинейных ситуациях.

Рис. 11.1. Целевая функция неограниченна

Если на х не налагается никаких ограничений, то при любом ненулевом с₁ значение целевой функции может быть сделано сколь угодно большим. Если же х может принимать только ограниченные значения, т. е. a₁≤x≤a₂, то x=a₁ оптимально при с₁<0, а x=a₂ − при с₁>0. Следовательно, оптимальным всегда является решение, соответствующее границе интервала. Однако, если мы откажемся от допущения о линейности функции с(х), становятся возможными и другие ситуации.
Одна из таких возможностей состоит в том, что с(х) достигает максимального значения при конечном значении х, хотя на х не налагается никаких ограничений (рис. 11.2).

Рис. 11.2. Целевая функция имеет оптимум при х=2

Однако, даже если значение х заключено в пределах сегмента [a₁,a₂]. решение для граничной точки может и не быть оптимумом. Так, если величина х должна находиться в пределах сегмента [О,3], то оптимальное значение х в примере 2 не соответствует ни одной из граничных точек этого сегмента (х=0 или х=3), а, как отмечалось выше, расположено внутри сегмента (х=2).
В примере 3 (рис. 11.3), как и в примере 1, значение с(х) неограниченно возрастает, если только на х не наложено ограничений. Однако в отличие от примера 1 сколь угодно большого значения с (х) можно здесь достичь как при достаточно большом, так и при достаточно малом значении х.

Рис. 11.3. Целевая функция неограниченно растет как при x→+∞, так и при x→−∞
В примере 4 (рис. 11.14) показано, что возможно также достижение сколь угодно больших значений с(х), даже если значение х ограничено, скажем, пределами сегмента [0,1]. Здесь в точке х=1 имеет место разрыв функции с(х); если х стремится к 1 слева, с (х) неограниченно возрастает.

Рис. 11.4. Целевая функция неограниченно растет в ограниченном интервале [0;1]
Наконец, с(х) может быть ограничено сверху, и все же может отсутствовать конечное значение х, при котором с(х) достигает максимума. Это характерно для примера 5 (рис. 11.5), где величина х не ограничена. Заметим, что для всех конечных значений х с(х) меньше 1, однако с(х) можно сколь угодно приблизить к 1, приняв величину х достаточно большой. При этом 1 именуется верхней гранью функции c(х).

Рис. 11.5. Целевая функция не имеет максимума при конечном x
Наконец, целевая функция может иметь разрыв в одной или нескольких точках - см.рис. 11.6.

Рис. 11.6. Целевая функция терпит разрыв при x=1.

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

1. x∈[a₁,a₂], т.е. −∞<a₁<x<a₂<∞

2. функция с(х) непрерывна и ограничена сверху для всех х на отрезке [a₁,a₂]

Важным следствием этих двух допущений является то, что с(х} достигает максимума при значении х, находящемся на отрезке [a₁,a₂]. Другими словами, будем изначально предполагать, что решение задачи нелинейной оптимизации существует, и рассмотрим методы егшо отыскания. Очевидно, что алгоритмы оптимизации должны предусматривать возможности того, что экстремум целевой функции может достигаться как внутри заданного интервала [a₁,a₂], так и на его границах. Так, например, в примере 3 оптимум всегда достигается при одном из экстремальных значений x, т. е. при x=a₁ или х=a₂; в то же время в примере 2 такое экстремальное значение х соответствует оптимуму только в том случае, если х=2 не принадлежит множеству внутренних точек отрезка [a₁,a₂].