Ченцов С.В. Автоматизированное проектирование средств и систем управления

Подождите немного. Документ загружается.

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

201

описания схем в виде ГЭК или ВГС в данном случае наиболее естественны,

причем с точки зрения адекватности модели физическому содержанию задачи

преимущество имеет представление схемы с помощью ГЭК.

С точки зрения реализации вычислительных процедур, наиболее

просто описание схемы с помощью ВГС (матрицы соединений

R).

Пусть конструктивному узлу сопоставимо некоторое непустое под-

множество элементов схемы

= {e

,…,e

}

Произвольный вариант компоновки представляет собой разбиение

множества элементов схемы

на непересекающиеся подмножества

, Т

, ..., Т





,..., ,..., ,

ss s s

Te e e

0; ; , 1, 2,..., ,

TT slsl



 

(14.10)







Разбиение

(14.10)

определяет

γ +

1 новых схем соединений:

схем

внутриузловых соединений и одну схему межузловых соединений.

Схема внутриузловых соединений для некоторого узла

(s = 1, 2, ..., γ)

задаёт соединения между элементами этого узла и на нее распространяют-

ся все основные понятия.

Дадим формальное определение схемы межузловых соединений. Будем

считать, что схема задана графом элементных комплексов

G = (Е, V, W)

или

взвешенным графом схемы

G = (Е, U).

Разбиению (14.10) соответствует

разбиение множества вершин

графа схемы на непересекающиеся под-

множества.

Определим граф межузловых соединений

с помощью следующего

преобразования «склеивания»:

Каждое подмножество



заменим одной вершиной

(

= 1, 2,

..., γ).

Все ребра, инцидентные вершинам из

, считаем инцидентными

вершине

(

= 1, 2, ..., γ).

При представлении схемы графом

G = (Е, U)

получим граф

G’ = (Т, U’),

в котором множество вершин

Т = {t

}

соответствует узлам

схемы, а множество ребер

U’ = {u’

}

с приписанным к ним весом

опре-

деляет связи между соответствующими узлами.

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

202

Очевидно, что







silj

TeTe

ijsl

rr'

(14.11)

где

–

элемент матрицы соединений

исходной схемы.

По аналогии с (14.8) под связностью схемы межузловых соединений

в этом случае будем понимать величину









rS ,

(14.12)

где

определяется выражением

(14.11)

Таким образом

при задании ВГС схема межузловых соединений опи-

сывается графом

G’ = (Т, U’)

которому соответствует матрица соединений

'||'||







. Матрица

– симметрическая, с нулевой главной диагона-

лью. Элемент матрицы

вычисляется из

(14.11)

Пусть теперь исходная схема задана графом

G = (E,V,W)

. После при-

менения к нему указанного выше преобразования получим граф межузловых

соединений

G’

= (Т, V’,W’),

в котором множество вершин

соответствует

узлам схемы, а множество вершин

и рёбер

W’

задают межузловые соеди-

нения (комплексы) (рис. 14.5,

а б

Рис. 14.5

Определение межузлового комплекса

аналогично определению

эле-

ментного комплекса: узлы

играют роль элементов. На рис.14.5 показано пре-

образование схемы при разбиении на узлы

= {e

, e

}, T

= {e

, e

= {e

, e

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

203

Следует отметить, что некоторые цепи становятся внутренними, дру-

гие переходят в схему межузловых соединений.

В общем случае размеры

межузловых цепей меньше размеров соответствующих цепей исходной

схемы:

р(v’

) ≤ р(v

Например,

р(v

) =

р(v’

) =

По аналогии с

(14.9)

связность схемы межузловых соединений опре-

делится выражением







FppS

')1'('

(14.13)

в котором

– количество межузловых цепей;

p’

– размер цепи.

Граф межузловых соединений может быть описан матрицей комплек-

сов

Q’

||q’

γ×F

, строки которой соответствуют узлам, а столбцы – межуз-

ловым цепям. Элемент матрицы

q’

1, если узел

связан цепью

с другим узлом, и

q’

в противном случае.

Решение задач компоновки связано с расчетом таких характеристик,

как число внутриузловых и межузловых соединений, число внешних соеди-

нений отдельных узлов и т. д. При использовании ВГС для представления

схемы расчет указанных характеристик не вызывает затруднений и может

быть легко выполнен по матрице соединений

В дополнение к

(14.11)

(14.12)

приведем выражение для расчета числа внешних соединений

узла









sis

(14.14)

где

r’

определяется выражением

(14.11).

Использование ГЭК для описания исходной схемы в наибольшей

степени отвечает специфике задачи компоновки. В этом случае для поста-

новки задачи и реализации соответствующих алгоритмов удобно использо-

вать аппарат алгебры множеств.

Сопоставим элементу схемы

множество связанных с ним цепей:

= {j

, … ,j

Пусть необходимо определить число общих цепей для двух элемен-

тов –

. Очевидно, оно равно числу цепей, входящих одновременно в

множества

, т. е. числу

цепей в пересечении этих множеств: J

= J

i 

Например, если

= {1, 2, 3, 5, 7}, а J

= {2, 4, 7}, то общие цепи определяют-

ся множеством

= {2, 7}.

Операция объединения множеств J

и J

определяет множество це-

пей

sisi

JJJ 



 , связанных по крайней мере с одним из элементов е

, или е

Операция дополнения множества

определяет множество цепей J’

не связанных с элементом е

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

204

Рассмотрим еще одну операцию – разность множеств J

и J

. Она выде-

ляет те цепи элемента

, которые не связаны с элементом е

: J

i-s

\ J

. Из-

вестно, что разность множеств может быть выражена следующим образом:

isi

JJJ





Назовем симметрической разностью двух множеств J

и J

мно-

жество

issisi

JJJ



  . Симметрическая разность в данном случае определяет

множество цепей, связанных только с одним из элементов

- или е

. Напри-

мер, если

7} 5, 3, 2, {1, J

 , а 7} 4, {2, J



, то

}4,5,3,1{



si

Пусть

– число цепей в множестве J

, тогда число цепей в множест-

вах

J ,







определяется из выражений

sisiis

mmmm









(14.15)

issisi

mmmm









(14.16)

isisi

mmm







(14.17)

issisi

mmmm 2









(14.18)

Назовем значение m

конъюнкцией элементов е

и е

, а значение



дизъюнкцией.

Если

R = ||r

n×n

– матрица соединений, полученная заданием для каж-

дого комплекса полного графа элементарных соединений, то

= m

. В связи

с этим матрицу

R иногда называют матрицей конъюнкций.

По аналогии определим матрицу дизъюнкции

С = ||c

n×n

, строчки и

столбцы которой соответствуют элементам схемы, а

jiij





. Матрица С –

симметрическая, с нулевой главной диагональю

(с

= 0, i=1, 2, ..., n). Эле-

мент матрицы

выражается через элементы матрицы R:







ijijij

rrrc

(14.19)

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

между группами элементов.

Множество цепей, связанных с элементами некоторого узла

}...,...,,{

kis

eeeT 

, определяется выражением

1

 

(14.20)

где J

– множество цепей элемента е



Т.

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

205

Рассчитаем число внешних цепей для узла Т при некотором разбиении

схемы, т. е. число цепей, связывающих элементы из

T с элементами, не при-

надлежащими узлу

Т. Для упрощения обозначим множество цепей некото-

рого узла

, через J

. Цепи, связанные с элементами, не принадлежащими

узлу, определяются выражением









(14.21)

Тогда число внешних цепей узла

рассчитывается по формуле

|||)(|



JJJv





 

(14.22)

где

– пересечение множеств цепей узлов Т

и Т

С помощью известного в комбинаторике принципа включения и ис-

ключения, позволяющего определить число элементов в множестве, образо-

ванном объединением заданных множеств, формулу (14.22) можно привести

к следующему виду:

















lll

llsl

...,,...,,

...,

||)1(

(14.23)

где



lslsl

...,,

– пересечение множеств цепей узлов



lls

TTT ,...,,

суммирование

производится по всем комбинациям размерностью 2, 3,...,

γ.

Проиллюстрируем расчет по (14.23)

для узла T

: |J

| = 3, |J

| = 1,

213

| = 1, отсюда v

= 3 + 1 – 1 =3.

Заметим, что когда

= 2, т. е. схема задана элементарными соедине-

ниями, все пересечения множеств в (14.23)

при λ ≥ 2 будут пусты, а

(14.23)

сводится к (14.14). Кроме того, для связности схемы (учитывая

(14.14)

, имеет место соотношение







vS .

(14.24)

При задании ГЭК аналогичная формула (14.24) принимает вид









FvS .

(14.25)

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

206

Учитывая, что исходные М цепей схемы при компоновке распределя-

ются на внутриузловые цепи и межузловые цепи, можно представить выра-

жение для связности схемы и в таком виде:

MJS









||' .

(14.26)

Пусть даны элементы

, …, e

и для каждой пары элементов заданы

весовые коэффициенты

(i, j = 1,2, …, n), определяющие «степень связи»

элементов друг с другом. Таким образом, считаем, что схема задана матри-

цей соединений

R = ||r

n×n

Пусть также имеется некоторый фиксированный набор позиций для

размещения элементов l

, l

, …, l

(m ≥ n). Будем полагать, что m = n. Если

m>n, то можно ввести m-n фиктивных элементов, не связанных с остальны-

ми. Определим расстояние

между парами позиций. В любом случае, если

на коммутационном поле фиксированы позиции для размещения элементов,

то можно задать матрицу соединений

D=||d

n×n

, в которой элемент d

равен

расстоянию между центрами позиций

и l

. Очевидно, что матрица D – сим-

метрическая с нулевой диагональю

=0, i=1,2, …, n).

Произвольное размещение элементов в позициях представляет собой

некоторую перестановку

p = p(1), …, p(i), …, p(n), где p(i) задает номер пози-

ции, присвоенный

i-му элементу. Таким образом, всего имеется n! различных

вариантов размещения элементов.

Рассмотрим задачу минимизации суммарной длины (МСВД) соедине-

ний при следующих предположениях. Соединения будем считать условно

исходящими из геометрических центров элементов. Кроме того, предполага-

ем совпадение центров элементов и позиций. Как правило, при решении за-

дачи размещения необходимо учитывать предварительное закрепление неко-

торых элементов в позициях и соединения элементов с внешни

ми выводами.

Сопоставляя внешним выводам элемент

и фиксируя расположение элемен-

тов, получим упрощенное представление коммутационного поля. Очевидно,

что длина соединений между элементами

и e

оценивается величиной

p(i)p(j)

. Обозначим через L

множество всех фиксированных элементов,

включая элемент

; тогда суммарная взвешенная длина соединений элемента

с элементами из L

оценивается по формуле







sipijiip

dra

)()(

(14.27)

где

p(i)s

– расстояние между элементом e

, находящимся в позиции p(i), и

элементом

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

207

Учитывая сказанное, а также симметричность матриц R и D, запишем

выражение для суммарной взвешенной длины соединений при произволь-

ном размещении:

 

 



iipjpipij

adrpF

11 1

)()()(

)(

(14.28)

Таким образом, задача размещения по критерию МСВД соединений со-

стоит в минимизации функционала (14.28)

на множестве перестановок p.

Данная задача является вариантом общей математической модели, впервые

рассмотренным Купмансом и Бекманом и получившим название задачи

квадратичного назначения.

Определим матрицу переменных

X = ||x

n×n

, строчки которой соответ-

ствуют элементам, а столбцы –позициям. Переменная

= 1, если элемент e

находится в

позиции, и x

= 0 в противном случае. Легко установить взаим-

но-одназначное между матрицей

X и некоторой перестановкой элементов в

позициях. Поэтому

X называют перестановочной матрицей или матрицей на-

значений. Очевидно, что матрица

X содержит в каждом столбце j и в каждом

строке

i одну единицу:

1, 1, 2, ..., ,







(14.29)

1, 1,2,..., .







(14.30)

С учётом введённых обозначений задачу размещения можно записать в

форме обобщённой задачи квадратичного назначения: найти матрицу

, для

которой

)

min()(

1,1 1,

 

 



ikikjsikksij

xaxxdrXF

(14.31)

Отметим, что линейный член в (14.31)

представляет собой функционал

обычной (линейной) задачи о назначении. Последняя формулируется сле-

дующим образом. Пусть задана некоторая матрица

A = ||a

n×n

, строчки ее

соответствуют некоторым объектам, а столбцы – местам их назначения. Эле-

мент

оценивает некоторую условную стоимость назначения объекта i на

место

j. Задача состоит в нахождении такого назначения объектов по местам

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

208

(без повторений), при котором суммарная стоимость всех назначений мини-

мальна. В другой терминологии задача сводится к минимизации





iip

)(

(14.32)

на множестве перестановок P = {p}, A = ||a

n×n

– заданная матрица коэффи-

циентов.

Отметим, что к задаче линейного назначения сводится ряд частных за-

дач оптимизации, возникающих при размещении элементов и при распреде-

лении их выводов. Из (14.28)

следует, что задача размещения несвязанного

множества элементов эквивалентна задаче линейного назначения.

Основная идея метода ветвей и границ состоит в разбиении всего мно-

жества допустимых решений задачи на некоторые подмножества, внутри ко-

торых осуществляется упорядоченный просмотр решений с целью выбора

оптимального. Для всех решений, входящих в выделенные подмножества,

вычисляется нижняя граница минимального значения целевой функции. Как

только нижняя граница становится больше значения целевой фу

нкции для

наилучшего из ранее известных решений, то подмножество решений, соот-

ветствующее этой границе, исключается из исходной области решений. Это

обеспечивает сокращение перебора. Процесс поиска, сопровождаемый раз-

биением поля решений и вычислением нижних границ, продолжается до тех

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

Различия модификации общего метода применительно к задаче разме-

щения (квадратичного назначения) отличаются способами расчёта нижних

границ функционала (14.28)

и способами разбиения поля решений.

Пусть имеется множество элементов

, …, e

, … ,e

и множество пози-

ций

, …, l

, … ,l

. Для описания процесса поиска решений введём дерево

решений. Ребра первого яруса дерева пусть соответствуют назначениям эле-

мента

, рёбра второго яруса – возможным вариантам назначения элемента

в свободные позиции и т. д.

На рис.14.6

показана часть дерева полного дерева решений, в котором

отмечены возможные назначения при условии, что элемент

назначен в по-

зицию

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

209

Рис. 14.6

Произвольному размещению элементов соответствует в полном дереве

некоторый путь, исходящий из начальной вершины. Для каждой вершины

дерева можно рассчитать нижнюю границу целевой функции для множества

путей (размещений), связанных с этой вершиной. Если граница больше зна-

чения целевой функции для известного размещения, то дальнейшее продви-

жение по дереву в данной вершине прекращается, поско

льку оно приводит к

заведомо неоптимальным решениям.

Частичным размещением

q будем называть назначение элементов

множества

= {e

, …, e

} в позиции множества L

= {l

, …, l

, …,l

}

в соответствии с правилом j = q(i), k ≤ n. Ясно, что

q  , где p – некоторое

размещение

n элементов, в котором k имеют размещение q. Частичному раз-

мещению

q соответствует в дереве решений путь, проходящий через верши-

ны отдельных назначений.

Если в процессе продвижения по дереву нижние границы не рассчиты-

ваются и соответственно не производится усечений дерева, то метод ветвей и

границ сводится к полному перебору.

Рассмотрим способы вычисления нижних границ функционала (14.28)

при частичных размещениях

q. Обозначим первый член в выражении F(p)

через

w(p), а второй через v(p):

)()()( pvpwpF





(14.33)

Нижняя граница для

F(p) получена суммированием нижних границ для

w(p) и v(p). Обозначим их соответственно b

, b

и b

Для вычисления

воспользуемся следующим свойством: если

r = (r

, …, r

) и d = (d

, …, d

) – два вектора, то минимум скалярного

произведения

r и d, т. е. минимум





ipi

)(

на множестве всех перестановок p,

соответствует расположению составляющих вектора

r в возрастающем по-

рядке, а составляющих вектора

d – в убывающем.

Нижняя граница для

F(p)

p(2)=n

p(2)=j+1

p(2)=j-1

p(2)=1

p(1)=n

…

p(1)=j

p(1)=1

… … …

…

ТЕМА 6. АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ ССУ

Лекция 14. Математическое моделирование ССУ при конструировании



Автоматизированное проектирование средств и систем управления. Курс лекций

210

vwF

bbb





(14.34)

должна быть соотнесена начальной вершине дерева решений.

Пусть теперь имеется некоторое частичное размещение

q, определяю-

щее назначение элементов из множества

в позиции из множества L

. Тогда

можно легко рассчитать вклад в общую длину соединений уже размещенных

элементов и вычислить новую нижнюю границу соединений.

Запишем (14.28)

для F(p) в следующем виде:





   





kk k k k

EiEsEiEsEi

iipspiqisspiqis

adrdrqFpF

''''

)()()()()(

)()(,

(14.35)

где E’

– множество не размещенных элементов для частичного размещения

q 

Структуру (14.34)

можно записать в компактной форме:

)()()()()( pupvpwqFpF

qqq





(14.36)

где F(q) – длина межсоединений размещённых элементов; члены w

(p) и v

(p)

аналогичны членам выражения (14.33)

и соответствуют межсоединениям не-

размещенных элементов; u

(p) представляет собой суммарную длину соеди-

нений размещенных элементов с неразмещенными.

Поскольку F(q) полностью определяется частными размещениями q,

для вычисления новой нижней границы для F(p) необходимо рассчитать

нижние границы для остальных членов выражения (14.36)

. Границы для w

(p)

и u

(p) рассчитываются по матрицам R и D, а нижняя граница для v

(p) опре-

деляется решением задачи линейного назначения неразмещенных элементов

E’

в незанятые позиции L’

Выбор направления поиска в дереве решений может быть организо-

ван различными способами. Как правило, очередное ветвление произво-

дится из вершины дерева с наименьшим значением нижней границы.

Далее поиск продолжается в соответствии с общей схемой метода вет-

вей и границ. Процесс заканчивается тогда, когда в просмотренной части

дерева решений отсутствуют вершины, для которых нижняя гр

аница мень-

ше, чем у наилучшего из известных решении. Это решение может быть ли-

бо получено одним из рассматриваемых в данной главе приближенных алго-

ритмов, и в этом случае доказывается оптимальность решения, либо опре-

делено в процессе поиска путем завершения некоторого частичного разме-

щения q. В последнем случае в дере

ве решений определяется путь, соответ-

ствующий оптимальному размещению.

В заключение сделаем ряд замечаний об эффективности метода ветвей

и границ для решения задачи размещения. Как уже указывалось, расчет

нижних границ при частичных размещениях осуществляется с целью усече-