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

; . (2)

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

. (3)

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

3. Методы решения задач оптимизации

Определение 3

Пропорционально-градиентный метод - один из видов метода градиентного спуска, при котором длина шага на (i+1) - м приближении определяется из условия

, , . (6)

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

Определение 4

Метод наискорейшего спуска - один из градиентных методов оптимизации, при котором положение точки в (i+1) - м приближении определяется из условия

, где . (7)

На рисунке 0. 1. изображена геометрическая иллюстрация этого метода для случая минимизации функции двух переменных. Из начальной точки перпендикулярно линии уровня в направлении - спуск продолжают до тех пор, пока не будет достигнуто минимальное вдоль луча значение функции . В найденной точке этот луч касается линии уровня . Затем из точки проводят спуск в направлении, перпендикулярном линии уровня, до достижения и т.д. Следует отметить, что чрезвычайно большое значение при использовании численных методов имеет выбор начальной точки . Так, для случая, приведенного на рисунке, выбор в качестве начальной точки приведет к тому, что каждая итерация будет приближать решение к седловой точке , а не к точке минимума .

Рис1. Геометрическая интерпретация метода наискорейшего спуска при минимизации функции двух переменных

В качестве критерия окончания итераций при использовании численных методов оптимизации, как правило, используют следующие условия

, (8)

, (9)

, (10)

где ,, - заданные положительные числа. Нередко используются различные сочетания критериев (8) - (10) или критерии, основанные на понятии относительной погрешности. Надежные и универсальные критерии окончания счета, которые были бы применимы к широкому классу задач и гарантировали бы достижение требуемой точности, в настоящее время неизвестны.

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

Рис.2. Графики функций двух переменных, для максимизации которых градиентные методы неприменимы

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

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

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

, =1,2,., (11)

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

В методе барьеров при решении задачи максимизации в форме (2) целевая функция заменяется семейством функций

, =1,2,. (12)

где - барьерная функция, которая характеризуется свойством стремиться к - при приближении к границам допустимой области изнутри, а определяется аналогично (11). При решении любым из численных методов задачи безусловной оптимизации (11) или (12) при =1,2,., может быть получена последовательность экстремальных точек , сходящаяся к экстремальной точке исходной задачи (2). Переход от задачи максимизации к задаче минимизации при использовании метода штрафных функций и метода барьеров осуществляется изменением знака штрафной или барьерной функции.

оптимизационное моделирование функция алгоритм

5. Области применения моделей оптимизации