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

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

Если DW_ij > 0, то перестановка целесообразна. Если же , то нецелесообразна, т.к. не уменьшает .

При перестановке местами i-го и j-го модулей суммарная длина  меняется на величину, равную изменению длины связей переставляемых модулей с остальными, а непереставляемые модули на  не влияют. Поэтому запишем

,                 (3.7)

где - суммарная длина соединений i-го модуля, стоящего в i-й позиции, со всеми остальными до перестановки; 

-суммарная длина соединений j-го модуля, стоящего в j-й позиции, со всеми остальными до перестановки;

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

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

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

,           k.           (3.8)

                 ,          kj.           (3.9)

                 ,          kj.         (3.10)

Подставив значения   W_i, W_j,  и  , определяемые соответственно формулами (3.3),  (3.8), (3.9) и (3.10), в формулу (3.7), получим

.

А после преобразования получим

,    где    к¹i,   к¹j,  i¹j.  (3.11)

Получив формулу (3.11) для определения значений DW_ij , используем ее в блок-схеме алгоритма оптимального размещения модулей (рис. 3.2). Особенностью алгоритма является то, что вычисление DW_ij производится для всех пар модулей          (блок № 3), далее  из  всех   значений    выбирается   максимальное   значение (блок № 4) и, если это максимальное значение положительно, то соответствующие     i-й   и   j-й      модули     переставляются      местами  (блоки № 5 и № 6). Как показывают статистические данные, алгоритм оптимального размещения с выбором максимального положительного значения  DW_{i j}  дает более глубокую оптимизацию по сравнению с алгоритмом, в котором перестановка модулей производится при первом появившемся положительном значении DW_{i j} .

Подставив  в  эту  формулу    вместо  l_ik и l_jk их выражения  из  (3.1)   и  (3.2),   получим

(3.12)

.           (3.13)

Таким образом получили формулу  для  определения  DW_ij   при  оптимизации  размещения  модулей,  расположенных  на  прямоугольном   или  на  каком-либо  другом   по  форме   коммутационном  поле.

Используя полученные формулы (3.6) и (3.13), по блок-схеме алгоритма, аналогичной приведенной  на рис. 3.2, была составлена  программа  решения  задачи  оптимизации размещения  модулей,  расположенных  на коммутационном  поле.

В качестве  примера рассмотрим   вариант   схемы, показанной на рис. 3.5,   в   котором цифра у линии соединения показывает число связей между соответствующей парой модулей, а их координаты при начальном размещении показаны на      рис. 3.3. Матрица соединений показана на рис. 3.4.

Для примера работы алгоритма оптимизацию размещения модулей схемы, показанной на  рис. 3.5, проведем ручным способом с помощью  алгоритма  парных  перестановок.        

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

=++

+++

++=

=++

+++

++=

= = 6 + 12 + 2 + 3 + 2 0 + 4 =       47 ед., т.е. суммарная  длина  соединений  до  оптимизации  равна  47  единицам  длины.

Рис. 3.3. Координаты начального размещения модулей (в условных единицах длины)