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

51

матрицы (рис. 4.4), а координаты

модулей

при

начальном размещении запишем так :

x1 = 1, x2 = 3, x3 = 3, x4 = 1, y1 = 3, y2 = 4, y3 = 1, y4 = 1.

S

2

3

4

1

1

0

2

3

1

2

2

0

1

4

3

3

1

0

2

4

1

4

2

0

N-1

N

Wo

Sij (

xi xj

yi yj

)

i=1

j i 1

=S12 (

x1

x2

y1

y2

)+S13 (

x1

x3

y1

y3

) +

+ S

(

x1

x

4

y y

) +S23

(

x x

y y

) +

14

1

4

2

3

2

3

y

4

2

А2

3

А1

4

1

2

3

1

1

А4

2

А3

0

1

2

3

x

+S24 (

x x

y y

) + S (

x x

y y

) =

2

4

2

4

34

3

4

3

4

= 2 (

3 4

) + 3 (

1 3

3 1

) +

1 3

+1 (

1 1

3 1

) +1 (

3 3

4 1

) +

52

+ 4 (

3 1

4 1

) + 2 (

3 1

1 1

) =

= 2 3 3 4 1 2 1 3 4 5 2 2 = 6 + 12 + 2 + 3 + 2 0 + 4 = 47 ед.,

т.е. суммарная длина соединений до оптимизации равна

47

единицам

длины.

Далее,

выполняя

операцию

блока

3,

вычислим

все

значения

Wij, т.е.

значения

W12 ,

W23 , W34 , W13 ,

W14

и

W24 .

Эти

значения будем

вычислять

по формуле (4.13):

N

Wij

( Sik

SJK ) (| xi

xk |

| yi

yk |

| x j

xk |

| y j

yk |)

k 1 i

k j

4

W12

(

S1k

S2K ) (| x1

xk |

| y1

yk |

| x2

xk |

| y2

yk |)

k

3 т.к.k

1k

2

(S13

S23)

(| x1

x3 |

|

y1

y3 |

| x2

x3 |

|

y2

y3 |)

(S14

S24 )(| x1

x4 |

| y1

y4 |

| x2

x4 |

| y2

y4 |)

(3 1)(|1 3|

| 3

1|

| 3

3|

| 4

1|)

(1

4)(|1

1|

| 3

1|

| 3

1|

| 4

1|)

11

ед.

Аналогично, получим

W23

(S21

S31 ) (| x2

x1 |

| y2

y1 |

| x3

x1 |

| y3

y1 |)

(S24

S34 ) (| x2

x4 |

| y2

y4 |

| x3

x4 |

| y3

y4 |)

7 ед.

W34

(S31

S41 ) (| x3

x1 |

| y3

y1 |

| x4

x1 |

| y4

y1 |)

(S32

S42 ) (| x3

x2 |

| y3

y2 |

| x4

x2 |

| y4

y2 |)

10 ед.

W13

(S12

S32 ) (| x1

x2 |

| y1

y2 |

| x3

x2 |

| y3

y2 |)

(S14

S34 ) (| x1

x4 |

| y1

y4 |

| x3

x4 |

| y3

y4 |)

0 ед.

W14

(S12

S42 ) (| x1

x2 |

| y1

y2 |

| x4

x2 |

| y4

y2 |)

(S13

S43 ) (| x1

x3 |

| y1

y3 |

| x4

x3 |

| y4

y3 |)

6 ед.

W24

(S21

S41 ) (| x2

x1 |

| y2

y1 |

| x4

x1 |

| y4

y1 |)

(S23

S43 ) (| x2

x3 |

| y2

y3 |

| x4

x3 |

| y4

y3 |)

0 ед.

Таким образом, получили все 6 значений

Wij : W12

= 11,

W34 = 10, W14 =

6, W23 = 7,

W13 = 0,

W24

= 0.

Далее, выполняя операцию блока 4, из всех значений

Wij

выбираем

максимальное. Им является

W12

= 11, и

так

как

оно положительное,

то,

согласно

53

модулей. Заметим, что значения Sij остались прежними,

а координаты хi ,

yj после

перестановки изменились.

W12

(S13

S32 ) (| x1

x3 |

| y1

y3 |

| x2

x3 |

| y2

y3 |)

(S14

S24 ) (| x1

x4 |

| y1

y4 |

| x2

x4 |

| y2

y4 |)

= (3 - 1)(|3 - 3| + |4 - 1| - |1 - 3| - |3 - 1|) + (1 - 4)(|3 - 1| + |4 - 1| - |1 - 1| - |3 - 1|) = -11.

Аналогично, вычислив остальные значения

Wij,

получим

W23 = 0, W34 = -

10, W13 = -4,

W14 = -1

и

W24 = -4 и переходим

к выполнению операции

блока 4,

т.е. находим (

Wij )max . Им является

W23

= 0, переходим к

выполнению

операции

блока 5, т.е. проверяем

условие

W23

0 . Условие

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

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

длины

соединений

производим

аналогичным

образом, как это делалось для начального размещения, т.е. по формуле (4.6.а):

N-1

N

Wo

Sij (

xi

xj

yi

yj

) .

i=1 j

i 1

y

4

2

А1

3

А2

1

3

2

1

4

1

А4

2

А3

0

1

2

3

x

Следует отметить, что в этой формуле значения Sij

попрежнему

определяются

элементами матрицы соединений, показанной на рис. 4.4, а

координаты

модулей xi

и yj

будут определяться схемой размещения модулей,

полученной

после перестановки местами первого и второго

модулей и изображенной на рис. 4.6.

Подставив в

формулу

значения Sij , xi и yj

и проведя необходимые

вычисления,

54

получим W12 = 36 ед. длины, т.е. после оптимизации

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

стала равной 36

ед. длины, а в начальном состоянии

она была равна 47 ед. длины,

т.е. уменьшилась

на 11 ед. Это уменьшение должно равняться сумме значений Wij

1

2

3

4

5

6

7

8

9

10

11

12

1

0

4

1

0

0

2

2

0

0

0

1

0

2

4

0

0

0

0

0

1

0

0

0

1

0

3

1

0

0

4

2

0

0

1

0

1

1

0

4

0

0

4

0

1

0

0

1

1

2

1

1

5

0

0

2

1

0

0

0

4

3

1

0

2

6

2

0

0

0

0

0

4

0

0

1

3

1

7

2

1

0

0

0

4

0

0

0

0

0

0

8

0

0

1

1

4

0

0

0

1

0

0

2

9

0

0

0

1

3

0

0

1

0

4

0

3

10

0

0

1

2

1

1

0

0

4

0

3

1

11

1

1

1

1

0

3

0

0

0

3

0

0

12

0

0

0

1

2

1

0

2

3

1

0

0

Номера и координаты модулей

Суммарная

(от 1 до 12)

длина

1

2

3

4

5

6

7

8

9

10

11

12

соединений,

усл.ед.

до

x

2

3

3

1

1

2

1

1

2

2

3

3

153

оптимизации

y

1

2

3

2

4

4

3

1

2

3

1

4

после

x

2

1

3

3

1

3

1

2

1

2

2

1

91

оптимизации

y

1

1

4

3

4

2

1

4

3

3

2

2