Итерационные алгоритмы улучшения компоновки

Для фиксации момента окончания итерационного процесса при реализации алгоритма на ЭВМ применяются различные правила. Например, может задаваться число итераций m либо параметр д, определяющий число итераций неявным образом:

. (4.8)

Далее рассмотрим процесс расчета приращений.

Пусть задано некоторое разбиение множества Е= {e1, e2,…, еп} на узлы T1 Т2,…, Tг.

Рассмотрим сначала случай, когда схема описана матрицей соединений R=||rij||nЧn. Оценим изменение в количестве межузловых соединений при обмене местами элементов ехTi, и еуТj. Поскольку при обмене перераспределяются лишь соединения элементов ех и еу, рассмотрим более детально структуру их соединений (рисунок 6).

Рисунок 6 - Межузловые соединения: а) - до обмена, б) - после обмена.

Обозначим через Uij, множество элементов {еk: еkТi и еkТi}. Тогда в соответствии с рисунком 4, а количество межузловых соединений до обмена равно

, (4.9)

где С - число межузловых соединений не участвующих в обмене элементов.

В соответствии с рисунком 4, б после обмена количество межузловых соединений станет равным

(4.10)

Вычитая (4.10) из (4.9), получим

(4.11)

Пусть Lxj - число соединений ex с элементами узла Tj, Lyi - число соединений ey c элементами узла Ti:

, (4.12)

а Fxi - число соединений ex с элементами узла Ti и Fyj - число соединений ey с элементами узла Tj

(4.13)

Тогда (4.11) принимает вид:

(4.14)

Lxi (Lyi) и Fxi (Fyj) соответственно внешние и внутренние соединения элементов ex и ey.

Для произвольного элемента exTi удобно ввести характеристику Dx=Lxj-Fxi, представляющую собой разность числа внешних и внутренних соединений. Аналогично вводится характеристика Dу для eyTj.

С учётом принятых обозначений формула (4.14) приобретает вид

(4.15)

При обмене местами элементов exTi и eyTj наряду с изменением количества межузловых соединений L происходит перераспределение внешних соединений для узлов Ti и Tj.

При задании схемы матрицей R суммарное число выводов на узлах V=2L, поэтому

, (4.16)

где ДV (x, y) - изменение суммарного числа выводов на узлах, а Дvi(x, y) и Дvj(x, y) - изменение числа выводов на узлах Ti и Tj.

Получим теперь выражения для Дvi(x, y) и Дvj(x, y). Обратимся к рисунку 4. Число внешних выводов на узле равно числу соединений между элементами узла и элементами, не входящими в узел. В связи с этим для расчета Дvi(x, y) можно использовать (4.15), если придать входящим в нее характеристикам Dx и Dy другой содержательный смысл.

Можно считать, что имеются два узла Ti и Tj*=UijTj=E\Ti. Введем характеристики D*x и Dy:

(4.17)

Читайте также

Передаточная функция разомкнутой системы
1. Определить передаточную функцию разомкнутой системы рис.1, представить её в канонической .форме. Построить её логарифмические частотные характеристики. 2. Оценить показатели к ...

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

Моделирование мобильных систем связи
При организации сети сотовой связи для определения оптимального места установки и числа базовых станций, а также для решения других задач необходимо уметь рассчитывать характеристики сиг ...