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

23.06.2015

Рассмотрение изложенных выше методов показало, что вычисление целевой функции в двух точках интервала неопределенности позволяет сто сузить.
Сущность метода дихотомии, нашедшего применение в различных областях науки, в математике сводится к выбору точек х1 и х2 таким образом (рис. 5.5 и 5.6), чтобы интервал неопределенности был минимальным.

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

Если значение целевой функции при М(х1) больше, чем при М(х2), то новый интервал неопределенности (см. рис. 5.5) равен
Z1 = Z - z3 = Z1 + Z2 = (х1 - а) + (x2 - x1) = (х2 - а).

В противном случае при M(x1) ≤ M(x2) он определяется выражением
Z2 = Z - Z1 = Z2 + Z3 = (x2 - x1) + (b - x2) = (b - x1).

Задача состоит в том, чтобы одновременно минимизировать Z1 и Z2, удовлетворив условиям
z1 + z2 + z3 = Z; z1 > 0, z2 > 0, z3 > 0.

Для условия, что z2 имеет некоторое очень малое значение ε, можем написать
Z1 = Z - z3 = min; Z2 = Z - z1 = min.

Так как величина Z задана, то правые части этих уравнений будут тем меньше, чем больше z1 и z3. Следовательно, оптимум соответствует условию
Z1= Z2 = 0,5Z, или, что то же самое, z1 = z3 = 0,5Z.

Ho тогда z2 = 0, что противоречит приведенным выше условиям: z2 > 0 и z2 = ε. Следовательно, из z1 и z3 необходимо вычесть по ε/2. Тогда в результате вычисления первой пары значений целевой функции при близких значениях x1 и x2 интервал неопределенности сузится (как показано на рис. 5.6) и коэффициент дробления будет равен
f = 1/ 2 + ε/2.

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