21. Метод дихотомии

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

Рис. 5.6 Обозначения, используемые в методе дихотомии

точках интервала неопределенности позволяет его сузить. Можно таким образом выбрать эти точки, что интервал неопределенности будет минимальным. На рис. 5.6 показаны обозначения, используемые в этой схеме. Если значение целевой функции при x₁ больше, чем при x₂ то новый интервал неопределенности равен Z₁=z₁+z₂. в противном случае он определяется выражением Z₂=z₂+z₃. Задача состоит в том, чтобы одновременно минимизировать Z₁ и Z₂, удовлетворив условиям

Из равенства можно исключить z₂. Тогда

Так как величина Z задана, то правые части этих уравнений будут тем меньше, чем больше z₁ и z₃. Следовательно, оптимум со­ответствует условию

Но тогда z₂=0, что противоречит условию z₂>0.

Пусть z₂ имеет некоторое очень малое значение е. Тогда из z₁ и z₃ вычтем по е/2. В результате после вычисления первой пары

Рис. 5.7 Метод дихотомии

значений целевой функции при близких значениях х интервал неопределенности сузится, как показано на рис. 5.7, и коэффициент дробления будет равен

В пределе, при е0, f1/2. В дальнейшем при использовании метода дихотомии выполняются те же операции, что и при использовании метода деления интервала пополам. Отметим, однако, что для достижения одинаковых сужений интервала неопределенности метод дихотомии требует вычисления целевой функции в точках на одну меньше.

22. Метод золотого сечения

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

Рис. 5.8 Обозначения, используемые в методе золотого сечения

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

Сущность этого метода состоит в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большого отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего отрезка. На рис. 5.8 показан интервал неопределенности Z, состоящий из отрезков z₁ и z₂, отношение длин которых опдеделяется правилом золотого сечения

Кроме того, z₁+z₂=Z. Из первого уравнения следует !!!вверху 2 внизу 1!!!!!!z=Zz₂. Подставляя сюда значение Z из второго уравнения и деля обе части на z вверху 2 внизу 1!!!!!, получаем

Решая это квадратное уравнение, находим для положительного корня значение

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

Рис. 5.9 Метод золотого сечения

Поэтому, чтобы уменьшить неопределенность еще в 1/0,618 раза, потребуется дополнительно вычислить только одно значение це­левой функции в точке, определяемой правилом золотого сече­ния.

При п>2 эффективность метода золотого сечения выше, чем у метода дихотомии, так как при каждом последующем вычислении целевой функции интервал неопределённости сокращается в 1/0,618 раза. После вычисления N значений целевой функции коэффициент дробления интервала неопределенности составляет

f = 0,618^N-1

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

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