Размещение элементов методом ветвей и границ

Задача: используя метод ветвей и границ найти вариант размещения 6-ти элементов на 6-ти позициях платы размером 1x6 позиций.

Исходные данные: матрица весовых коэффициентов R(i, j), задающая для каждой пары элементов вес соединяющего их проводника, D(i, j) - матрица длин проводника между двумя элементами.

Алгоритм данного метода основан на поиске оптимального расположения элементов на позициях путём последовательного переборе всевозможных сочетаний элементов, ещё не закреплённых на определённых позициях.

Расчёты ведутся производятся по следующим формулам:

F_p = nn r(i, j)*d(i, j), IX(1, n), jX(i, n),

w = n sort_k(r(i, j))*sort_k(d(i, j)), iX(1, n), jX(n+1, N), kX(1, n)

U = n sort_k(r(i, j))*sort_k(d(i, j)), iX(n+1, N), jX(n+2, N)

F_оц = F_p + w + U

Исходные данные введём в программу на языке Pascal. Недостатком данной программы является отсутствие анализа ветвления при получении одинаковых минимальных значений функции F_оц в разных позициях для одного элемента. Упрощённый алгоритм, после нахождения минимального значения, выбирает в качестве оптимальной ту позиции, в которой данное значение было получено впервые. Таким образом, применение данного алгоритма даёт гарантированного верный результат лишь в случае отсутствия ветвления. Это обстоятельство необходимо проанализировать по итогам расчётов.

Распечатка результатов вычислений, выполненных программой приведена ниже:

Input data:

R-table (weight) D-table (lenght)

---------------- ----------------

0 2 2 3 9 4 0 1 2 3 4 5

2 0 1 10 5 6 1 0 1 2 3 4

2 1 0 3 4 7 2 1 0 1 2 3

3 10 3 0 7 8 3 2 1 0 1 2

9 5 4 7 0 11 4 3 2 1 0 1

4 6 7 8 11 0 5 4 3 2 1 0

---------------- ----------------

*** Calculation for vertex #1 ***

Put vertex #1 into position of vertex #1:

1 2 3 4 5 6

Fp==0

w=9*1+4*2+3*3+2*4+2*5+=44

U=11*1+10*1+8*1+7*1+7*2+6*2+5*2+4*3+3*3+1*4+=97

-------

Fest=141

Put vertex #1 into position of vertex #2:

2 1 3 4 5 6

Fp==0

w=9*1+4*1+3*2+2*3+2*4+=33

U=11*1+10*1+8*1+7*2+7*2+6*2+5*3+4*3+3*4+1*5+=113

-------

Fest=146

Put vertex #1 into position of vertex #3:

3 2 1 4 5 6

Fp==0

w=9*1+4*1+3*2+2*2+2*3+=29

U=11*1+10*1+8*1+7*2+7*2+6*3+5*3+4*4+3*4+1*5+=123

-------

Fest=152

Put vertex #1 into position of vertex #4:

4 2 3 1 5 6

Fp==0

w=9*1+4*1+3*2+2*2+2*3+=29

U=11*1+10*1+8*1+7*2+7*2+6*3+5*3+4*4+3*4+1*5+=123

-------

Fest=152

Put vertex #1 into position of vertex #5:

5 2 3 4 1 6

Fp==0

w=9*1+4*1+3*2+2*3+2*4+=33

U=11*1+10*1+8*1+7*2+7*2+6*2+5*3+4*3+3*4+1*5+=113

-------

Fest=146

Put vertex #1 into position of vertex #6:

6 2 3 4 5 1

Fp==0

w=9*1+4*2+3*3+2*4+2*5+=44

U=11*1+10*1+8*1+7*1+7*2+6*2+5*2+4*3+3*3+1*4+=97

-------

Fest=141

Fmin=141 n_min=1

*** Calculation for vertex #2 ***

Put vertex #2 into position of vertex #2:

1 2 3 4 5 6

Fp=2*1+=2

w=9*2+4*3+3*4+2*5+10*1+6*2+5*3+1*4+=93

U=11*1+8*1+7*1+7*2+4*2+3*3+=57

-------

Fest=152

Put vertex #2 into position of vertex #3:

1 3 2 4 5 6

Fp=2*2+=4

w=9*1+4*3+3*4+2*5+10*1+6*1+5*2+1*3+=72

U=11*1+8*1+7*2+7*2+4*3+3*4+=71

-------

Fest=147

Put vertex #2 into position of vertex #4:

1 4 3 2 5 6

Fp=2*3+=6

w=9*1+4*2+3*4+2*5+10*1+6*1+5*2+1*2+=67

U=11*1+8*1+7*2+7*3+4*3+3*4+=78

-------

Fest=151

Put vertex #2 into position of vertex #5:

1 5 3 4 2 6

Fp=2*4+=8

w=9*1+4*2+3*3+2*5+10*1+6*1+5*2+1*3+=65

U=11*1+8*1+7*2+7*2+4*3+3*4+=71

-------

Fest=144

Put vertex #2 into position of vertex #6:

1 6 3 4 5 2

Fp=2*5+=10

w=9*1+4*2+3*3+2*4+10*1+6*2+5*3+1*4+=75

U=11*1+8*1+7*1+7*2+4*2+3*3+=57

-------

Fest=142

Fmin=142 n_min=6

*** Calculation for vertex #3 ***

Put vertex #3 into position of vertex #3:

1 6 3 4 5 2

Fp=2*5+2*2+1*3+=17

w=9*1+4*3+3*4+10*1+6*2+5*4+7*1+4*1+3*2+=92

U=11*1+8*2+7*3+=48

-------

Fest=157

Put vertex #3 into position of vertex #4:

1 6 4 3 5 2

Fp=2*5+2*3+1*2+=18

w=9*1+4*2+3*4+10*1+6*3+5*4+7*1+4*1+3*2+=94

U=11*1+8*2+7*3+=48

-------

Fest=160

Put vertex #3 into position of vertex #5:

1 6 5 4 3 2

Fp=2*5+2*4+1*1+=19

w=9*1+4*2+3*3+10*2+6*3+5*4+7*1+4*2+3*3+=108

U=11*1+8*1+7*2+=33

-------

Fest=160

Put vertex #3 into position of vertex #6:

1 6 2 4 5 3

Fp=2*5+2*1+1*4+=16

w=9*2+4*3+3*4+10*1+6*2+5*3+7*1+4*2+3*3+=103

U=11*1+8*1+7*2+=33

-------

Fest=152

Fmin=152 n_min=6

*** Calculation for vertex #4 ***

Put vertex #4 into position of vertex #4:

1 6 2 4 5 3

Fp=2*5+2*1+3*3+1*4+10*2+3*2+=51

w=9*2+4*4+6*1+5*3+7*1+4*3+8*1+7*1+=89

U=11*2+=22

-------

Fest=162

Put vertex #4 into position of vertex #5:

1 6 2 5 4 3

Fp=2*5+2*1+3*4+1*4+10*1+3*3+=47

w=9*2+4*3+6*2+5*3+7*1+4*2+8*1+7*2+=94

U=11*1+=11

-------

Fest=152

Put vertex #4 into position of vertex #6:

1 6 2 3 5 4

Fp=2*5+2*1+3*2+1*4+10*3+3*1+=55

w=9*3+4*4+6*1+5*2+7*2+4*3+8*1+7*2+=107

U=11*1+=11

-------

Fest=173

Fmin=152 n_min=5

*** Calculation for vertex #5 ***

Put vertex #5 into position of vertex #5:

1 6 2 5 4 3

Fp=2*5+2*1+3*4+9*3+1*4+10*1+5*2+3*3+4*2+7*1+=99

w=4*2+6*3+7*1+8*2+11*1+=60

U==0

-------

Fest=159

Put vertex #5 into position of vertex #6:

1 6 2 5 3 4

Fp=2*5+2*1+3*4+9*2+1*4+10*1+5*3+3*3+4*1+7*2+=98

w=4*3+6*2+7*2+8*1+11*1+=57

U==0

-------

Fest=155

Fmin=155 n_min=6

Calculation complete

|1|6|2|5|3|4|

The smallest Fest is 155

На выходе получаем массив, содержащий номера позиций, в которые помещается элементы с номером элемента массива:

Отсортируем данные в строке «Позиция» по возрастанию, тогда увидим в каком порядке расположены элементы на плате:

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