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

Для упрощения будем считать, что схема представлена взвешенным графом коммутационной схемы 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).

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

Надежность работы ВОЛП
В данной работе рассматривается проблема обеспечения надежности эксплуатируемых линейно-кабельных сооружений при воздействии внешних факторов - влияние молнии, воздействие коррозии, меха ...

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

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