Методы исследования операций при принятии решений. Бодров В.И - 18 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Рис. 1.21 Метод ветвей и границ
Функция ψ
*
(a
ι
) вычисляет оптимальный путь от соответствующей вершины до конечной. Исполь-
зуя граф (рис. 1.14), можно подсчитать, какие значения, как гипотезу, примет функция ψ
*
(a
i
): ψ
*
( ) =
9;
ψ
*
( ) = 11; ψ
*
( ) = 6.
Таким образом, Q( ) = 11; Q( ) = 26 и, наконец, Q( ) = 9. Эти значения внесены в соот-
ветствующие вершины (рис. 1.21).
Наилучшей, согласно оценке Q, является вершина . Раскрывая ее, получают вершины и
.
Очевидно, что q( ) = 11; q( ) = 6.
С помощью графа полного перебора (рис. 1.14) устанавливают, что прогноз ψ
*
(а
ι
) был бы следую-
щим: ψ
*
( ) = 1; ψ
*
( ) = 3. Таким образом, Q( ) = 22; Q( ) = 9, поэтому раскрытию
подлежит вершина и т.д.
Для нахождения оптимального пути методом ветвей и границ с идеальной (абсолютно точной)
функцией прогноза потребовалось раскрыть всего 4 вершины, именно столько вершин, сколько их на
оптимальном пути, исключая конечную.
Этот алгоритм выводит на оптимальный путь, так как он дает сразу точное знание того, какова же
будет цепь того или иного пути.
Однако абсолютно точную функцию прогноза ψ
*
(a
i
) найти невозможно. Вместо ψ
*
(a
i
) используется
какая-либо другая функция ψ(a
i
), являющаяся оценкой функции ψ
*
(a
i
). Очевидно, чем ближе функция
ψ(a
i
) к ψ
*
(a
i
), тем меньше границ нужно перебрать, чтобы найти оптимальный путь. При неправильном
выборе ψ(a
i
) может оказаться, что нашли и посчитали за оптимальный путь, который в действительно-
сти таковым не является.
Доказано, что если для всех a
i
выполняется условие
ψ(a
i
) ≤ ψ
*
(a
i
), (1.1)
то алгоритм метода ветвей и границ найдет оптимальное решение.
Если условие (1.1) не соблюдается, то алгоритм может пропустить оптимальный путь.
9
12
13
14
12
13
14
14
143
142
143
142
143
142
143
143
142

Страницы