Метод обратного размещения

Тема Параллельно-последовательное размещение

Для каждого из неразмещенных элементов ei принадлежащих E(I) I=вычисляется некоторая оценка.

Вычисляется также некоторая оценка и для каждого посадочного места. Все элементы и посадочные места упорядочиваются и осуществляется одновременное размещение всех элементов в позиции.

Пусть матрица С=||сij||m*n; D=||dij||n*n-матрицы расстояний между позициями.

В соответствие с указанным методом для каждого элемента ei рассчитывается суммарное число связей i-го элемента с остальными частями схемы (1)

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

Все оценки связанности упорядочиваются по возрастанию, а оценки длины - по убыванию:

Элемент устанавливается в позицию Pj(1), Pj(2) и т.д. Это связано с тем, что min скалярное умножение двух векторов будет тогда, когда компоненты первого вектора упорядочены по возрастанию, а элементы другого по убыванию.

Пример:

Распишем матрицы С и D

e1 e2 e3 e4 e5

e1

e2

e3

e4

e5

P1 P2 P3 P4 P5

P1

P2

P3

P4

P5

Lначальное=1+10+6+4+1+1+1=24

Упорядочим сi по возрастанию, di по убыванию.

с1э=10 с2э=2 с3э=2 с4э=7 с5э=7

d1п=6 d2п=5 d3п=7 d4п=6 d5п=8

таким образом второй элемент размещаем в 5-ю позицию, 3ий в 3ю позицию, 4й в 1ю, 5й в 4ю, 1й в 2ю.

Окончательный вариант размещения приведен на рисунке:

Lсуммарная=18 (18<24!)- что и требовалось доказать

Дата добавления: 2014-01-14