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

1. В качестве показателя эффективности целесообразно взять объем бруса, м³.

2. В качестве управляемой переменной задачи следует взять длину бруса l. При этом длина бруса l связана с поперечным размером b следующими зависимостями:

d= d_k - (d_k-d_o ) l / l_o;

b²=2d²,

где

1. Целевая функция:

Постановка задачи.

1. В качестве показателя эффективности целесообразно взять полные затраты на построение противопожарной загородки, руб, включающие в себя транспортные расходы W_t и оплату труда рабочих W_w а также потери лесных угодий от огня W_f.

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

3. Целевая функция:

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

• методы исключения интервалов;
• методы полиномиальной аппроксимации;
• методы с использованием производных.

Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют.

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

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

Процесс применения методов поиска на основе исключения интервалов включает два этапа:

• этап установления границ интервала;
• этап уменьшения интервала.

где

x_o - произвольно выбранная начальная точка;

Искомый интервал 65<x^*<185.

Метод деления пополам

Найти W(x) на отрезке [a,b].

Шаг 1. x_m=(a+b)/2; L=b-a; вычислить W(x_m).

Шаг 2. x₁=a+L/4; x₂=b-L/4; вычислить W(x₁) и W(x₂).

Шаг 3.

Шаг 4.

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

Сущность метода. Интервал поиска делится на две равные части так, чтобы отношение длины большого отрезка к длине всего интервала было равно отношению

Найти W(x) на отрезке [a,b].

Шаг 1. Вычисляем коэффициент дробления отрезка [a,b] k=(- 1)/2.

Шаг 2. x₁=a+(1-k)(b-a), вычислить W(x₁).

Шаг 3. x₂=a+k(b-a), вычислить W(x₂).

Шаг 4.

Шаг 5.

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

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

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

Если целевая функция W(x) в точках x₁, x₂, x₃ принимает соответствующие значения W₁, W₂, W₃, то можно определить коэффициенты a_о, a₁, a₂ таким образом, что значения квадратичной функции

q(x) = a_o + a₁(x-x₁) + a₂(x-x₁)(x-x₂) (3.2)

совпадут со значением W(x) в трех указанных точках. Вычислим q(x) в трех указанных точках.

Шаг 2. Вычислить W(x₁) и W(x₂).

W(x₁) > W(x₂),

Шаг 4. Вычислить W(x₃) и найти

Wmin = min{ W(x₁),W(x₂), W(x₃)},

Xmin = x_i, соответствующая Wmin.

Шаг 5. По x₁, x₂, x₃ вычислить x^*, используя формулу для оценивания с помощью квадратической аппроксимации.

Шаг 6. Проверка окончания

Шаг 7. Выбрать Xmin или x^* и две точки по обе стороны от нее. Обозначить в естественном порядке и перейти к шагу 4.

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

• метод хорд;
• метод касательных;
• метод средней точки.

Сущность метода. Основан на алгоритме исключения интервалов, на каждой итерации которого рассматривается одна пробная точка R. Если в точке R выполняется неравенство W'(R) < 0, то в следствии унимодальности функции точка оптимума не может лежать левее точки R. Аналогично, если W'(R) > 0, то интервал x>R можно исключить.

Пусть в интервале [a,b] имеются две точки N и P, в которых производные W'(N)<0 и W'(P)>0. Оптимальная точка x^* расположена между N и P.

Шаг 1. Положить P=b, N=a, причем W'(a)<0 и W'(b)>0.

Шаг 2. Вычислить R=(P+N)/2 и W'(R).

Как следует из логической структуры, процедура поиска по методу средней точки основана на исследовании только знака производной.

Рис. 3.3.Схема метода хорд

Шаг 1. Следующее приближение к стационарной точке x^* определяется по формуле

Как видно из алгоритма, метод хорд реализован на исследовании как знака производной, так и ее значении. Поэтому он более эффективен, чем метод средней точки.

W'(x,x_k) = W'(x_k) + W''(x_k)(x-x_k). (3.5)

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

Рис.3.4. Схема метода касательных

Шаг 1. Следующее приближение к стационарной точке x^* определяется по формуле

x_k+1 = x_k - [W'(x_k)/W''(x_k)].

Шаг 2. Вычислить W'(x_k+1), W''(x_k+1)

x₁=1, W'(1)=-12, W"(1)=36, x₂=1-(-12/36)=1.33

x₂=1.33, W'(1.33)=-3.73, W"(1.33)=17.6, x₃=1.33-(-3.76/17.6)=1.54

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

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