Материал: Laboratornaya_rabota_3i4-n

4 7

1 [2] 1

2 0 0

3 2 0

R = 4 0 0

5 0 0

6 0 3

7 0 0

1* 2* 3* 4* 5 6* 7

1 0 1 2 3 3 2 5

2 1 0 1 2 2 1 4

3 2 1 0 1 3 2 3

D = 4 3 2 1 0 4 3 2

5 3 2 3 4 0 [1] 4 [17]

6 2 1 2 3 1 0 3

7 5 4 3 2 4 3 0 21 .

7

Далее выбираем min  d_1j = 17, соответствующую позиции №5. Среди по-

J=1

меченых элементов пятой строки матрицы D {d₅₁, d₅₂, d₅₃, d₅₄, d₅₆} находим, минимальный: d₅₆ = 1. Помечаем все элементы пятого столбца матрицы D. В шестой позиции размещен элемент №1. Поэтому просматриваем первую строку матрицы R, находим max r_ij=2 для модуля №4. Размещаем модуль №4 в позицию №5, исключаем из дальнейшего рассмотрения четвёртый столбец матрицы R:

1

1 1

2 0

3 0

R = 4 0

5 0

6 3

7 0

I₇

I₅ I₆

I₂ I₃ I₄

I₁

I₇

I₅ I₆

I₂ I₃ I₄

I₁

а) б)

Рис.3.1

Рис.3.2

1 2 3 4 5 6 7

1 0 1 2 3 3 2 5

2 1 0 1 2 2 1 4

3 2 1 0 1 3 2 3

D = 4 3 2 1 0 4 3 2

5 3 2 3 4 0 1 4

6 2 1 2 3 1 0 3

7 5 4 3 2 4 3 0 21

Последний седьмой модуль, следовательно, попадает в оставшуюся свободной седьмую позицию. Результат размещения дан на рис. 3.3.

t₇

t₆

t₅

t₂

t₃

t₁

t₄

Рис.3.3.

Суммарная длина соединений получилась равной 35 условным единицам.

4. Алгоритм предварительного размещения

Алгоритм включает такую последовательность действий [3]:

1. Для каждой строки матрицы R определить сумму элементов в каждой

7

строке матрицы r_i =  r_ij , j = 1,…, n.

j=1

2. Найти минимум среди r₁, i = k.

3. Поместить элемент k в первую по порядку 1,…,n незанятую позицию 1.

4. В матрице R вычеркнуть k-ю строку, а элементы k-го столбца без вычеркнутого n_k элемента с отрицательным знаком переписать с k-го на 1-е место.

5. Если число строк в матрице не равно нулю, идти к 2.

6. Вычислить матрицу расстояний D.

7. Подсчитать суммарную длину соединения L по формуле (3.1).

Конец.

ПРИМЕР 3.2

Необходимо по критерию минимума суммарной длины соединений разместить 7 ячеек в 7 позиций (рис.3.4).

Матрица смежности графа имеет вид

1 2 3 4 5 6 7 _i=1⁷n_ij

1 0 4 12 3 6 9 10 44

2 4 0 7 5 4 11 14 45

3 12 7 0 9 8 13 5 54

R₁ = 4 3 5 9 0 3 7 1 28

5 6 4 8 3 0 2 11 34

6 9 11 13 7 12 0 2 44

7 10 14 5 1 11 2 0 43

Решение

Определим суммарное число связей каждой ячейки с остальными.

7

Минимальное значение  n_ij = 28. Это означает, что четвертая ячейка

J=1

должна быть закреплена на первом установочном месте, находящемся с краю.

Преобразуем исходную матрицу следующим образом. Исключим из матрицы четвертую строку (ячейка закреплена, и на оставшиеся места претендовать не может), элементы четвертого столбца матрицы запишем со знаком « – » и, имитируя установку четвертой ячейки на 1-е место, переставим 4-й столбец на 1-е место в матрице. Преобразованная матрица имеет вид:

4 1 2 3 5 6 7  n_ij

1 -3 0 4 12 6 9 10 38

2 -5 4 0 7 4 11 14 35

3 -9 12 7 0 8 13 5 36

R₂ = 5 -3 6 4 8 0 2 11 28

6 -7 9 11 13 12 0 2 40

7 -1 10 14 5 11 2 0 41

Минимальную сумму связей имеет 5-й элемент матрицы. Это означает, что 5-я ячейка закрепляется на втором месте.

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

Окончательное распределение элементов на позициях дано на рис.3.4.

Если считать, что расстояние между рядом расположенными ячейками рав-но условной единице длины, то для полученного размещения суммарная длина равна 345 единицам условной длины.