11.Математическая постановка задачи компоновки с использованием модели гг

Рассмотрим ту же задачу, т.е. задачу нахождения матрицы решений ξ для данного варианта разбиения. На элементы матрицы ξ_ij накладываются те же ограничения (3.2 и 3.3), что и выше.

Отметим, что каждая цепь v_k в блоке b_j может потребовать либо один, либо ноль выводов. Для того чтобы цепь v_k потребовала один вывод необходимо и достаточно, чтобы хотя бы один элемент, инцидентный данной цепи, был бы расположен в блоке b_j, и хотя бы один элемент, инцидентный данной цепи, включая элемент e₀, был бы расположен вне блока b_j.

Математически вышесказанное записывается следующим образом.

– сумма элементов, инцидентных цепи v_k и расположенных в блоке b_j.

– сумма элементов, инцидентных цепи v_k и расположенных вне блока b_j.

Введем в обозначения функцию:

С учетом данного обозначения выражение

будет справедливо, если цепь v_k содержит хотя бы один элемент e_i в блоке b_j. Выражение

справедливо, если цепь v_k содержит хотя бы один элемент вне блока b_j.

Число внешних выводов блока b_j, которые требуют цепи v_k, определяется из выражения:

.

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

определяет количество блоков, в которых содержатся элементы, инцидентные цепи v_k. Количество межблочных связей, которые требует цепь v_k (без учета элемента e₀), определяется из выражения:

.

Количество межблочных связей, которые требует цепь v_k с учетом внешнего разъема e₀, определяется из выражения:

.

Для определения суммарного числа межблочных связей просуммируем выражение (3.13) по всем цепям v_k .

Задача (3.14) это задача нелинейного целочисленного программирования с булевыми переменными.

Теперь вернемся к нашему примеру (рис. 3.1).

Матрица инцидентности (цепей) ГГ имеет вид:

			v1	v2	v3	v4	v5	Т.о., элементы hik известны.
		e0	1	0	1	1	1
H	=	e1	1	1	0	0	0
		e2	1	1	1	0	0
		e3	0	1	0	1	0
		e4	1	0	0	0	1

Матрица решений ξ для нашего примера имеет вид:

			b1	b2
		e1	ξ11	ξ12		1	0	Т.о., элементы ξij для нашего варианта компоновки тоже известны.
ξ	=	e2	ξ21	ξ22	=	1	0
		e3	ξ31	ξ32		0	1
		e4	ξ41	ξ42		0	1

Формула (3.13), примененная для каждой цепи v_k, показывает, что каждая из них требует только один вывод.

Формула (3.14) для нашего варианта разбиения (компоновки) дает следующее число межблочных связей:

Блочная организация схемы рисунка 3.1 при таком варианте размещения приведена на рисунке 3.3.