2014-09-02
1098
Даны элементы х1, х2,…, хn и для каждой пары элементов заданы весовые коэффициенты rij (j,i=1, 2,…, n), определяющие «степень связности» элементов друг с другом. Схема задана матрицей соединений R=||rij||nxn. На коммутационном поле имеется набор фиксированных позиций l1, l2,…, lm (m³n) для размещения элементов. Будем считать m=n. Расстояние dij между парами позиций определяется по ортогональной метрике (при проведении соединений по каналам параллельным координатным осям).
dij = ïxi –xjï + ïyi –yjï
Можно задать матрицу расстояний D=||dij||nxn. Элемент dij равен расстоянию между центрами позиций li, и lj. Расстояние между позициями по вертикали и горизонтали принимается за 1.
| l1 l2 l3 l4 l5 l6 l7 l8 l9 l10 l11 l12 | |
| l1 | 0 1 2 3 1 2 3 4 2 3 4 5 |
| l2 | 1 0 1 2 2 1 2 3 3 2 3 4 |
| l3 | 2 1 0 1 3 3 1 2 4 3 2 3 |
| l4 | 3 2 1 0 4 3 2 1 5 4 3 2 |
| l5 | 1 2 3 4 0 1 2 3 1 2 3 4 |
| l6 | 2 1 2 3 1 0 1 2 2 1 2 3 |
| D = l7 | 3 2 1 2 2 1 0 1 3 2 1 2 |
| l8 | 4 3 2 1 3 2 1 0 4 3 2 1 |
| l9 | 2 3 4 5 1 2 3 4 0 1 2 3 |
| l10 | 3 2 3 4 2 1 2 3 1 0 1 2 |
| l11 | 4 3 2 3 3 2 1 2 2 1 0 1 |
| l12 | 5 4 3 2 4 3 2 1 3 2 1 0 |
Произвольное размещение элементов в позиции имеет n!вариантов. Для ЭВМ с быстродействием порядка 100000 оп/с общее время перебора всех вариантов составляет тысячи часов.
|
|
|
Рассмотрим задачу минимизации суммарной взвешенной длины (МСВД) соединений.
Предположим:
· соединения исходят из геометрических центров элементов и их позиций (центры совпадают);
· некоторые элементы закреплены в позициях;
· учитываются соединения элементов с внешними выводами (внешние выводы – условный элемент х0).
Рассмотрим упрощенно коммутационное поле.
 |
Рис.6.2.2 Коммутационное поле
Длина соединений между элементами xi, и xj выражается величиной rij dp(i)p(j).
Ls - множество всех фиксированных элементов, включая х0.
Тогда суммарная взвешенная длина соединений элемента xi с элементами из Ls оценивается по формуле
a ip(i) = ∑ ris d p(i)s, где
sÎLs
d p(i)s - расстояние между, находящимся в позиции p(i), и элементом хs.
Выражение для суммарной взвешенной длины соединений при произвольном размещении:
n n n
F (p) = 1/2 ∑ ∑ rij d p(i)p(j) +∑ a ip(i).
i=1 j=1 i=1
Т.о. задача размещения по критерию МСВД (минимизации суммарной взвешенной длины) соединений заключается в минимизации функционала F (p). Этот вариант математической модели – задача квадратичного назначения. Для решения задачи квадратичного назначения используют алгоритмы (алгоритмы последовательного размещения по связности, метод обратного размещения, непрерывные модели и механические аналоги и т.д.), основанные на методе ветвей и границ.
