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

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

Пусть 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. В связи с этим получение точного решения задачи одним из известных методов трудновыполнимо даже при использовании ЭВМ высокой производительности. Тем не менее рассмотренные модели могут быть основой для разработки эвристических алгоритмов компоновки.

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

Применение системы автоматического проектирования на ИП Суслова
Почти все крупные предприятия используют в своей работе возможности компьютерной техники, в частности CAD, CAM, САЕ технологии, т.к. они предоставляют ряд преимуществ, таких как ...

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

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