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

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

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

Проект цифровой радиорелейной линии г. Волгоград – г. Астрахань
Связь всегда имела большое значение в жизни людей. Особенную важность связь приобрела в последние годы, поскольку многие сферы деятельности человека, например бизнес, напрямую зависят от ...

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

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