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

Рис. 3.4. Матрица  соединений

Далее,  выполняя  операцию  блока  3,  вычислим  все  значения  DWij, т.е. значения  DW12 , DW23 , DW34 , DW13 , DW14   и  DW24 .  Эти  значения  будем  вычислять  по  формуле  (3.13):

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

Таким  образом, получили  все  6  значений  DWij :         DW12  = 11, DW34 = 10, DW14 = 6, DW23 = 7, DW13 = 0, DW24  = 0.

Далее, выполняя  операцию  блока  4, из  всех  значений  DWij   выбираем  максимальное. Им является  DW12 = 11, и  так  как  оно  положительное,  то,  согласно  операции  блока  5,  производим  перестановку  местами  модулей  1  и  2.  Схема  расположения  модулей  после  перестановки  показана  на  рис. 3.6. Выпишем  для  нее  координаты  модулей : х1 = 3, х2 = 1, х3 = 3, х4 = 1, y1 = 4, y2 = 3, y3 = 1, y4 = 1. Аналогичным  образом  вычислим  все  значения  DWij   уже  для  нового  размещения  модулей.  Заметим,  что  значения  Sij  остались  прежними,  а  координаты  хi  ,   yj  после  перестановки  изменились.

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

Аналогично,  вычислив  остальные  значения  DWij,   получим  DW23 = 0, DW34 = -10, DW13 = -4, DW14 = -1  и  DW24 = -4  и переходим  к выполнению  операции  блока  4,  т.е.  находим  (DWij )max . Им является  DW23 = 0,  переходим  к  выполнению  операции  блока  5, т.е. проверяем  условие  DW23  £ 0 . Условие  выполняется, поэтому  управление  передается  блоку  7.  Это означает,  что  оптимизация  наступила  и  необходимо  вычислить  суммарную  длину  соединений  для  оптимального  размещения, т.е. для  размещения, полученного  после  перестановки  местами  первого  и  второго  модулей.

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

.

 


Следует  отметить, что  в  этой  формуле  значения  Sij  по-прежнему  определяются  элементами матрицы  соединений, показанной на  рис. 3.4, а  координаты  модулей  xi    и   yj    будут  определяться  схемой  размещения  модулей,  полученной  после  перестановки  местами  первого  и  второго  модулей  и  изображенной  на  рис. 3.6. Подставив в  формулу  значения Sij , xi    и   yj   и проведя  необходимые  вычисления, получим  W12 = 36 ед. длины, т.е. после оптимизации  суммарная  длина  соединений  стала  равной  36  ед. длины, а  в  начальном  состоянии  она  была  равна  47 ед. длины, т.е.  уменьшилась  на  11 ед.  Это  уменьшение  должно  равняться  сумме  значений  DWij  , по которым  производились  перестановки  модулей.  В  нашем  случае  была  одна  перестановка  и  DW12=11, что совпадает  с  величиной  уменьшения  суммарной  длины  соединений.  Это  значит,  что  расчеты  проведены  верно.

В качестве примера решения задачи размещения модулей на коммутационном поле с минимизацией суммарной длины соединений с помощью ПЭВМ рассмотрим следующий.

Исходные данные: количество модулей = 12; схема соединений представлена матрицей смежности (табл. 3.1); координаты начального размещения модулей представлены в         табл. 3.2

Таблица 3.1

Матрица смежности