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

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

Далее,  выполняя  операцию  блока  3,  вычислим  все  значения  DW_ij, т.е. значения  DW₁₂ , DW₂₃ , DW₃₄ , DW₁₃ , DW₁₄   и  DW₂₄ .  Эти  значения  будем  вычислять  по  формуле  (3.13):

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

Таким  образом, получили  все  6  значений  DW_ij :         DW₁₂  = 11, DW₃₄ = 10, DW₁₄ = 6, DW₂₃ = 7, DW₁₃ = 0, DW₂₄  = 0.

Далее, выполняя  операцию  блока  4, из  всех  значений  DW_ij   выбираем  максимальное. Им является  DW₁₂ = 11, и  так  как  оно  положительное,  то,  согласно  операции  блока  5,  производим  перестановку  местами  модулей  1  и  2.  Схема  расположения  модулей  после  перестановки  показана  на  рис. 3.6. Выпишем  для  нее  координаты  модулей : х₁ = 3, х₂ = 1, х₃ = 3, х₄ = 1, y₁ = 4, y₂ = 3, y₃ = 1, y₄ = 1. Аналогичным  образом  вычислим  все  значения  DW_ij   уже  для  нового  размещения  модулей.  Заметим,  что  значения  S_ij  остались  прежними,  а  координаты  х_i  ,   y_j  после  перестановки  изменились.

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

Аналогично,  вычислив  остальные  значения  DW_ij,   получим  DW₂₃ = 0, DW₃₄ = -10, DW₁₃ = -4, DW₁₄ = -1  и  DW₂₄ = -4  и переходим  к выполнению  операции  блока  4,  т.е.  находим  (DW_ij )_max . Им является  DW₂₃ = 0,  переходим  к  выполнению  операции  блока  5, т.е. проверяем  условие  DW₂₃  £ 0 . Условие  выполняется, поэтому  управление  передается  блоку  7.  Это означает,  что  оптимизация  наступила  и  необходимо  вычислить  суммарную  длину  соединений  для  оптимального  размещения, т.е. для  размещения, полученного  после  перестановки  местами  первого  и  второго  модулей.

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

.

Следует  отметить, что  в  этой  формуле  значения  S_ij  по-прежнему  определяются  элементами матрицы  соединений, показанной на  рис. 3.4, а  координаты  модулей  x_i    и   y_j    будут  определяться  схемой  размещения  модулей,  полученной  после  перестановки  местами  первого  и  второго  модулей  и  изображенной  на  рис. 3.6. Подставив в  формулу  значения S_ij , x_i    и   y_j   и проведя  необходимые  вычисления, получим  W₁₂ = 36 ед. длины, т.е. после оптимизации  суммарная  длина  соединений  стала  равной  36  ед. длины, а  в  начальном  состоянии  она  была  равна  47 ед. длины, т.е.  уменьшилась  на  11 ед.  Это  уменьшение  должно  равняться  сумме  значений  DW_ij  , по которым  производились  перестановки  модулей.  В  нашем  случае  была  одна  перестановка  и  DW₁₂=11, что совпадает  с  величиной  уменьшения  суммарной  длины  соединений.  Это  значит,  что  расчеты  проведены  верно.

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

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

Таблица 3.1

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