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

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

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

R(i,j) =

D(i,j) =

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

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

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

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

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

Fоц = Fp + 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оц не обнаружено, следовательно, в данном случае полученный результат действительно представляет собой оптимальный вариант размещения элементов по позициям.


7390415883287126.html
7390478552223512.html
    PR.RU™