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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Рис. 1.20 Метод равных цен
В методе ветвей и границ каждая вершина a
n
оценивается функцией
(
)() ()
.
nnn
aaqaQ ψ+=
Эта функция содержит две составляющие. Функция q(a
n
) оценивает стоимость пути σ(a
n
) от на-
чальной вершины a
0
до вершины a
n
.
Функция ψ(a
n
) называется функцией прогноза, обещанием, оценкой. Эта функция прогнозирует, ка-
кая наилучшая (минимальная) стоимость пути от вершины a
n
до конечной вершины.
Метод ветвей и границ на каждом шаге раскрывает ту вершину, для которой функция оценки Q(a
n
)
– минимальна.
Выбор функции ψ(a
n
) – это всегда нестандартная, творческая задача. От правильного задания функ-
ции ψ(a
n
) зависит не только эффективность метода, т.е. число раскрытых вершин, но и сам результат. В
отличие от вышерассмотренных методов в методе ветвей и границ оптимальный (в глобальном смысле)
путь может быть потерян, если ψ(a
n
) выбрана неправильно.
Если допустить, что для каждой вершины a
n
известна функция ψ(a
n
), которая точно позволяет на-
звать стоимость дальнейшего пути от a
n
до конечной вершины при условии, что этот путь оптимален.
Таким образом, ψ(a
n
) – максимально возможная стоимость при движении от точки a
n
к конечной. Дока-
зано, что в этом случае метод ветвей и границ будет более эффективен, так как найдет именно опти-
мальный путь при минимальном числе раскрытых вершин.
Рассмотренную ранее задачу коммивояжера решим методом ветвей и границ, считая, что откуда-то
известен алгоритм ψ
*
(a
n
) – точная функция прогноза.
Для первой точки а
0
(корня дерева) (рис. 1.21) можно записать
(
)()()
000
ψ aaqaQ
*
+= . Принимается,
как и раньше, q(a
0
) = 0. Функция ψ*(a
n
) "знает" цену оптимального пути.
Раскрывается вершина , ее дочерними вершинами являются вершины , и . Потери
q(a
i
) для этих вершин указаны на ребрах.
123
123
1
0
13
14
12
124
14
143
14321
1432
2
5
8
15
3
8
3
2
9
2
2
15
3
3
6
7
10
11
4
6
5
8
9
9
2
1
9
1
13
14
12
142
143
2
15
3
8
3
11
26
2
9
14
3
9
1
13
12
14

Страницы