N
9
10
2
4
7
6
8
3
1
5
Qi
0.06
0.04
0.03
0.09
0.07
0.08
0.02
0.15
0.17
0.13
с(xi)
Yk
f(Yk)
iYk
?l*
0,06
0,1
9,10
0,15
4,9
0,19
4,10,9
0,22
7,4,9
0,26
7,4,10,9
0,3
3,4,9
0,34
3,4,10,9
0,37
3,7,4,9
0,41
7,3,4,10,9
11
0,44
2,7,3,4,10,9
12
0,47
1,3,4,9
13
0,51
1,3,4,10,9
14
0,54
2,1,3,4,10,9
15
0,58
7,1,3,4,10,9
16
0,61
1,2,7,3,4,10,9
Метод ветвей и границ использует последовательно-параллельную схему построения дерева возможных вариантов. Первоначально ищут допустимый план и для каждого возможного варианта определяют верхнюю границу целевой функции. Ветви дерева возможных вариантов, для которых верхняя граница ниже приближенного решения, из дальнейшего рассмотрения исключают.
Эффективность вычислительных алгоритмов зависит от точности и простоты способа определения верхней границы возможных решений и точности определения приближенного решения. Чем точнее способ определения верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Например, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вычислительной работы.
Страницы: 1, 2, 3, 4