Материал: Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС. Муратов А.В., Скоробогатов В.С

Н А Ч А Л О

1

Ввод матрицы соединений, координат

начального размещения модулей

2

Вычисление суммарной длины соединений

начального размещения

3

Вычисление матрицы Wij для

всех пар модулей

4

Поиск максимального элемента матрицы ( Wij)max

Да

5

( Wij)max 0

7

Вычисление суммарной длины соединений для

оптимального размещения

l

(x

x

)2

(y

y

)2

;

(4.1)

ij

i

j

i

j

lij*

| xi

x j |

| yi - y j | ,

(4.2)

где li j и

l*i j -

расстояние между

i-й

и j-й позициями или между

модулями, установленными в эти позиции;

xi , yi - координаты

i-й

позиции;

xj , yj - координаты

j-й позиции;

Исходными

данными

для

решения задачи

будут: матрица соединений,

N

Wi

Si k li k ,

i k.

(4.3)

k

1

48

1

N N

Wo

Sij ij,

i j,

(4.4)

2 i=1 j 1

где

li j

- расстояние между i- м

и j- м модулями,

Si j

- количество связей между ними.

В

формуле 4.4 перед суммой

ставится коэффициент

1/2, так

как при

длина связей между i-м и j-м, а второй раз как

длина связей между j -м и i-м модулями.

Фактически же эта длина должна учитываться только один раз. Чтобы

избавиться от

этого коэффициента и от условия i j формулу 4.4.a можно записать в виде:

N-1

N

Wo

Sij ij.

(4.4.a)

i=1

j i 1

1 N N

W

o

S

ij

(x

i

x

j

)2

( y

i

y

j

)2 , i j .

(4.5)

2 i 1 j

1

N-1

N

Wo

Sij

(xi

xj)2

(yi

yj)2 .

(4.5.а)

i=1

j

i

1

W *

1 N

N

S

(| x

x

|

| y

y

|) , i

j .

(4.6)

ij

i

j

i

j

o

2 i 1

j

1

N-1

N

Wo

Sij (

xi

xj

yi

yj

) .

(4.6.а)

i=1

j

i

1

Wi j =W0

Wi j ,

где Wi

j - суммарная длина всех соединений после перестановки местами i-го и

j-го модулей.

Если

Wij

0, то перестановка

целесообразна. Если же

Wi j 0 , то

непереставляемые модули на

Wi

j не влияют. Поэтому запишем

W

j

(W

W

j

)

(W 1

W 1 ) ,

(4.7)

i

i

i

j

W1 - суммарная длина соединений i-го модуля, переставленного в j-ю позицию,

i

со всеми остальными;

W1j - суммарная длина соединений j-го модуля , переставленного в i-ю позицию,

со всеми остальными.

Аналогично формуле (4.3) , записанной для Wi , запишем

N

W j

S j k

l j k ,

k

j .

(4.8)

k

1

W 1

N

S

i k

l

j k

,

к

j .

(4.9)

i

k

1

W 1j

N

S j k

li k ,

к

j .

(4.10)

k

1

N

N

N

N

Wi j (

Si k li k

S j k l j k ) (

Si k l j k

S j k li k )

k

1

k 1

k 1

k 1

N

[(Si k li k

S j k l j k ) (Si k l j k S j k li k )]

k

1

N

Wij

(Sik Sjk)( ik - jk) ,

где к i, к j, i j. (4.11)

k=1

Получив формулу (4.11) для определения значений

Wij , используем ее в блок-

является то, что вычисление Wij производится для всех пар модулей

( блок № 3 ), далее

из всех значений

Wi j выбирается максимальное значение ( блок № 4 ) и , если это

максимальное значение положительно, то соответствующие

i-й

и j-й

модули

переставляются

местами (блоки № 5 и № 6). Как показывают статистические данные,

Wi j .

Подставив в

эту

формулу

вместо

lik и ljk

их выражения

из

(4.1)

и (4.2),

получим

N

x )2

)2

x )2

)2 .

W

(S

ik

S

jk

)( (x

( y

y

k

(x

j

( y

j

y

k

(4.12)

ij

i

k

i

k

k

1

*

N

W

(S

ik

S

jk

) (| x

i

x

k

|

| y

i

y

k

|

ij

k

1

|

x j

xk |

|

y j

yk

|)

i

j

k ,

(4.13)

Таким образом получили формулу для

определения

Wi

j

при

оптимизации

размещения модулей, расположенных на прямоугольном

или на

каком-либо

другом

по форме коммутационном поле.

Используя полученные формулы (4.6) и (4.13), по блок-схеме алгоритма,

аналогичной приведенной

на рис. 4.2, была составлена

программа

решения

задачи

оптимизации размещения модулей, расположенных на коммутационном поле.

В качестве примера рассмотрим

вариант схемы

рис. 4.5,

в

котором цифра у