Алгоритмы компоновки, использующие методы целочисленного программирования

Для упрощения будем считать, что схема представлена взвешенным графом коммутационной схемы G = (E, U), где E - множество вершин, соответствующих элементам схемы, U - множество ребер соответствующих цепей, и матрицей соединений R=||rij||nЧn, n строки и столбцы которой соответствуют элементам схемы, а rij равен весу, приписанному соединению элементов еi и ej.

Пусть каждому элементу eiE приписан некоторый вес pi>0 (i=1, 2, …, п). Например, pi может быть связан с размерами элемента, мощностью, рассеиваемой элементом, и т.п. Далее, пусть заданы ограничения на формирование узлов: максимальная вместимость узла k в максимальное число выводов на узле v.

Требуется осуществить при этих условиях компоновку элементов из E в узлы Tl (l=1, 2,…, г) таким образом, чтобы количество межузловых соединений было минимальным.

Введем матрицу переменных X=||xil||nЧг, в которой xil=1, если eiTl, xil=0 в противном случае. Поскольку элемент ei может находиться лишь в одном узле,

(2.1)

Ограничение на вместимость узла Tl приводит к следующим неравенствам:

(2.2)

Число внешних соединений узла Tl может быть записано в виде

(2.3)

Действительно, хil=(1 - хil) = 1 тогда и только тогда, когда eiTl, а ejTl (

ejTs, sl).

Получим теперь выражение для критерия оптимизации. На основании (2.3) количество межузловых соединений:

(2.4)

где r0 - внешние соединения схемы.

Таким образом, задача состоит в минимизации функции (2.4) при ограничениях (2.1), (2.2) и дополнительных ограничениях:

(2.5)

Отметим, что при pi=l (i=l, 2,…, n) ограничение (2.2) равносильно ограничению на число элементов в узле.

Описанная задача оптимизации представляет собой задачу нелинейного целочисленного программирования, для которой отсутствуют эффективные методы решения.

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

Набор ограничений на формирование узлов выделяет допустимые узлы из всех возможных.

Разбиение Т1 Т2,…, Tг называется допустимым, если каждый узел Ts (s=1, 2, …, г) является допустимым. Набор ограничений называется регулярным, если из допустимости узла следует допустимость любого подмножества элементов этого узла. Очевидно, что ограничение на число элементов в узле является регулярным, а на число внешних соединений узла - нет.

Рассмотрим схему рисунке 3. Пусть ограничение по числу выводов v=3, тогда узел Т={е1, е2, е3, е4, е5} является допустимым, однако Т'={е1 е2, е4, е5} является недопустимым узлом, поскольку имеет четыре внешних соединения.

Рисунок 3 - Нерегулярное ограничение

Пусть схема соединений задана графом G = (E, V, W). Рассмотрим некоторое разбиение Кг ={T1, Т2,…, Tг} схемы на допустимые узлы.

Эквивалентная задача минимизации функции:

(2.5)

в которой ms=|Js| равно числу цепей, связанных с элементами узла Ts.

Рассмотрим теперь семейство P={Ts} непустых подмножеств множества удовлетворяющее следующему условию:

(2.6)

Тs - допустимый узел. Отметим, что условие (2.6) разрешает повторные вхождения элементов в некоторые узлы: в общем случае Ts∩Tl ≠Ш при s≠l.

Имеет место следующая теорема: если набор ограничений регулярный, то минимум числа межузловых соединений при условии, что каждый элемент входит точно в один узел, равен минимальному числу межузловых соединений при условии, что каждый, элемент входит, по крайней мере, в один узел (2.6).

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

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

Проектирование устройства автоматической компенсации доплеровской частоты для СДЦ РЛС 5Н84А
Широкое применение радиолокационной техники в военных целях (воздушная и наземная разведки, навигация, вывод на траекторию ракет различного назначения) вызвало в последние годы бурное р ...

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