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

Справедливость теоремы устанавливается следующим образом.

Пусть L*K и L*P - соответственно минимальное значение функции (2.5) на множестве допустимых разбиений К и при более слабом условии (2.6). Область решений при условии (2.6) шире области решений задачи компоновки, поэтому L*K ≤ L*P.

Пусть Р* - некоторая совокупность узлов, для которой L (P*)=L*p. Построим из Р* некоторое разбиение К путем устранения повторных вхождений элементов в узлы ТsР*. Так как набор ограничений регулярный, то каждый из узлов К будет допустимым, при этом L*K ≤ L(К)≤ L*P, поскольку при устранение лишних вхождений число соединений не может увеличиться. Учитывая, что L*P ≤ L*K, окончательно получим L*P = L(К)=L*K, где К - разбиение, сконструированное указанным способом/

Таким образом, решение задачи компоновки может быть получено из задачи минимизации функции (2.5) при условий (2.6).

Пусть Р={Тs} - множество всех допустимых узлов. Легко показать, что при решении этой задачи можно ограничиться рассмотрением лишь множества Р' ={T1,…, Тs,…, Тр} максимально допустимых узлов.

Узел Ts называется максимально допустимым, если он имеет связную схему соединений и не является частью другого допустимого узла.

Множество Р' назовем базовым множеством узлов. Для образования базового множества сначала строятся группы по 2, 3, …, k элементов с проверкой их допустимости и максимальности. Группы, удовлетворяющие этим условиям, включаются в множество Р'.

Будем искать минимум функции (2.5) на множестве Р'. Построим матрицу X = || хsi||pЧn, строки которой соответствуют узлам из Р', а столбцы - элементам множества Е. Элемент матрицы хsi =1, если eiTs, и хsi=0 в противном случае. Присвоим строке i

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

Тогда задача минимизации функции (2.5), становится эквивалентной отысканию такого подмножества строк матрицы X, которое покрывает все столбцы матрицы X и имеет минимальный суммарный вес. Заметим, что та же задача возникает при выборе по таблице простых импликант булевой функции подмножества импликант, имеющего минимальное суммарное число переменных. Отсюда следует, что теоретически возможно на данном этапе применять классические методы минимизации булевых функций. Приведем постановку полученной задачи в виде модели линейного целочисленного программирования:

Найти минимум функции

(2.7)

при следующих ограничениях:

(2.8)

Решение задачи (2.7), (2.8) определяется набором переменных {ys}. Если ys = 1, то Ts Р' входит в решение задачи компоновки, и если ys =0, то не входит. Отметим, что если положить ms= 1, то получим задачу минимизации количества узлов компоновки: найти минимум функции

(2.9)

при ограничениях (2.8).

Рассмотренный выше способ сведения задачи компоновки к моделям линейного целочисленного программирования представляет скорее теоретический, чем практический интерес. Действительно, для схем реальной сложности число узлов р, включаемых в базовое множество, может быть много больше 1000. В связи с этим получение точного решения задачи одним из известных методов трудновыполнимо даже при использовании ЭВМ высокой производительности. Тем не менее рассмотренные модели могут быть основой для разработки эвристических алгоритмов компоновки.

Перейти на страницу: 1 2 

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

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

Разработка компьютерной сети по технологии ArcNet с подключением к Internet
Организация компьютерных сетей. Назначение: Создание компьютерных сетей вызвано практической потребностью пользователей удаленных друг от друга компьютеров в одной и той же информ ...

Разработка конструкции линейного коммутатора
Радиоэлектронная аппаратура (РЭА), в основу функционирования которой положены принципы электроники, строится на базе электронных компонентов различного назначения (микросхем, резисторов, ...

Основные разделы

Все права защищены! (с)2024 - www.generallytech.ru