В.В.Павлов, д-р техн. наук проф., МГТУ "Станкин"
О математическом моделировании дискретного производства Представлен математический аппарат полихроматических множеств и графов как новое средство информационных технологий для моделирования технических систем.
Широкое использование теории множеств и теории графов при моделировании технических систем и дискретного производства затруднено сложностью формализованного описания в рамках этого аппарата качественно разнообразных свойств объектов, представляемых элементами множества и вершинами (ребрами) графа. Поэтому автором еще в 70-е годы были начаты исследования, направленные на устранение указанного недостатка [1, 2]; эти исследования и послужили основанием для разработки теории полихроматических графов [3, 4]. Полихроматический граф отличается от хроматического [5] тем, что в нем любая отдельная вершина и/или ребро могут быть окрашены одновременно в несколько цветов. Поскольку понятие цвета относится к категории свойств, то при моделировании технических систем и дискретного производства определенному цвету ставится в соответствие конкретное свойство моделируемого объекта.
Понятие полихроматического графа является производным от понятия полихроматического множества, которое определяется тройкой
ПS= (A, F(А), { F(аi), i = 1,..., n}), (1) где А - обычное множество [6] элементов аi, i = 1,...,n; F(аi) - множество цветов, в которые раскрашен отдельный элемент аi, или персональная раскраска этого элемента; F(А) - множество всех цветов из персональных раскрасок элементов и цветов самого ПS-множества как объекта А в целом.
Совокупность множеств {F(ai), i = 1,...,n} удобно представлять в виде булевой матрицы персональных раскрасок элементов ПS-множества ||ci(j)||= [А х F(A)], (2) где сi(j) = 1, если цвет Fj
F(аi) и сi(j) = 0 - в противном случае.
В матрице (2) i-я строка определяет множество F(ai) цветов элемента аi; j-й столбец матрицы определяет состав элементов, цвета Fj(ai) которые обуславливают существование цвета Fj(А) объекта А в целом. При использовании булевой матрицы (2) ПS-множество определяется тройкой ПS=(А, F(А),[A х F(А)]).(3) Цвет Fj(А) по отношению к Fj(аi) называется унитарным, а состав этих цветов называется унитарной раскраской ПS-множества и обозначается символом F(S). Например, состав и основные свойства элементов конструкции электродвигателя (рис. 1,a) описываются множествами элементов и унитарных цветов
A=(а1, а2, а3, а4, а5, а6, а7, а8, а9, а10, а11, а12),
F(А) = (F1, F2, F3, F4, F5, F6, F7, F8,…, F18),
а персональные цвета элементов представлены в булевой матрице (рис.1, б). Множества А, F(А) и булева матрица (рис Л, б) определяют ПS- множество элементов электродвигателя.
Взаимосвязь между Fj(А) и Fj(ai) описывается с помощью теоретико-множественных операций, но для практических целей удобнее пользоваться логическими операциями. Любой цвет Fj можно представить как логическую величину относительно заданного множества F(А):
Fj= |
{ |
1, если Fj
F(A); |
Это позволяет переходить от теоретико-множественных к логическим операциям и наоборот; правила перехода соответствуют общепринятым [1]. Взаимосвязь между Fj(A) и Fj(ai) может принимать, например, такие формы:
Fj= |
{ |
1, если |
|
Fj (ai)=1 |
(4) |
0, - в противном случае. |
Рис. 1. Конструкция электродвигателя:
а - элементы конструкции: a1 - статор; a2 - сердечник статора; а3 - сердечник ротора; а4 - обмотка статора; а5 - обмотка ротора; a6, a12 - подшипниковые щиты; а7 - вентилятор; а8 - кожух вентилятора; а9, а11 - шарикоподшипники; a10 - ротор;
б - матрица [АxF(А)] раскрасок элементов конструкции; цвета: F1 - электромагнитный контур статора и ротора; F2 - механический контур электродвигателя; F3 - воздушный зазор между сердечниками статора и ротора; F4 - свойства системы охлаждения; F5 - свойства массы; F6 - свойства формы; F7 - свойства соединения статора a1 с сердечником a2, F8 - свойства соединения статора а1 с подшипниковым щитом a6; F18 - свойства соединения шарикоподшипника а11 с подшипниковым щитом а12;
- элементы булевой матрицы сi(j) = 1
Fj= |
{ |
1, если |
|
Fj (ai)=1 |
(5) |
0, - в противном случае. |
Форма связи (4) называется дизъюнктивной (ДФС), а форма связи (5) - конъюнктивной (КФС). ДФС соответствует случаю, когда унитарный цвет Fj(А) ПS-множества существует, если существует хотя оы один элемент, имеющий цвет Fj(ai). КФС соответствует случаю, когда Fj(А) существует только при наличии цвета Fj у всех элементов А. Более общей является форма связи
Fj= |
{ |
1, если A(Fj)[ ai
A(Fj) ( |
|
Fj (ai)=1)] |
(6) |
0, - в противном случае. |
где А(Fj) есть подмножество элементов А, имеющих персональный цвет Fj(ai) При A(Fj)=a1 v a2 v ... v an
отношение (6) переходит в ДФС, а при А(Fj) = А - в КФС.
Если отношение (4) выполняется для каждого цвета Fj(А), то унитарная раскраска ПS-множества вычисляется по формуле
F(S) |
|
F(ai) |
(7) |
или, в логическом представлении, по формуле
F(S) |
|
F(ai) |
(8) |
Если для каждого цвета Fj(А) должно выполняться отношение (5), то F(S) вычисляется по формуле
F(S) |
|
F(ai) |
(9) |
или, в логическом представлении, по формуле
F(S) |
|
F(ai) |
(10) |
В случае (7) F(S) = F(А), а в случае (9) F(S)
F(А). Модели реальных объектов чаще имеют форму связи вида (6). Так, свойствами массы (F5) и формы (F6) электродвигатель (рис. 1,а) обладает при любом составе элементов конструкции, т.е. цвета F5(А), Р6(А) связаны с цветами F5(аi), F6(аi) элементов А отношениями (4). Свойством охлаждения элементов конструкции воздушным потоком (F4) электродвигатель обладает только во время работы при наличии всех его элементов, т.е. цвет F4(А) связан с цветами Р4(аi) отношением (5); напротив, свойствами F1,F2,F3,F4,F5,F6,F7,F8,...,F18 электродвигатель обладает только при определенных составах элементов, т.е. унитарные цвета Fj(A),j=1,2,3,7,8,...18 связаны с персональными цветами Fj(ai) отношениями вида (6).
Обычным графом называется пара G=(A,C), состоящая из множества A вершин и множества С ребер, связанных отношением инцидентности [5]. Примером является граф (рис.2) сопряжений элементов конструкции электродвигателя (см. рис. 1, а). Соответственно полихроматическим графом (ПG-графом) называется пара ПG = (ПSA, ПSC) состоящая из полихроматического множества ПSА вершин и полихроматического множества ПSС ребер. ПSA-множество по составу компонентов соответствует ПS-множеству (3); ПSC-множеетво имеет аналогичный состав компонентов. Поэтому при покомпонентной записи ПG-граф определяется шестеркойПG = (А, С, F(А),F(С), [АхF(A)],[СхF(C)]), (11)
где С - множество ребер; F(С) - множество цветов персональных раскрасок отдельных ребер и цветов множества С в целом; [С х F(С)] - булева матрица персональных раскрасок ребер
||ci(j)||C,F(C)= [CxF(C)](12)
по назначению аналогичная булевой матрице (2). Обычный граф G = (А, С) является бесцветным каркасом ПG-графа. Если в ПG-графе раскрашены только вершины, а ребра бесцветны, то в состав (11) не входят множество F(С) и матрица (12); примером является ПG-граф сопряжений элементов конструкции, включающий в себя бесцветный каркас (рис. 2) и булеву матрицу (см. рис. 1,6) раскраски вершин. Если в ПG-графе раскрашены только ребра, а вершины бесцветны, то в состав (11) не входят множество F(А) и матрица (2) раскраски вершин.
Все операции над ПG-графами, а также построение маршрутов, цепей, путей и другие действия отличаются от аналогичных действий с обыкновенными графами, так как здесь накладываются особенности, связанные с раскраской вершин и ребер.
Назовем унитарной раскраской ПG- графа раскраску F(G), состав цветов в которой определенным образом связан с персональными раскрасками его вершин и ребер. Унитарная раскраска F(G)А ПG-графа в зависимости от входящих вершин есть функция персональных раскрасок этих вершин. Унитарная раскраска F(G)С ПG-графа в зависимости от входящих ребер есть функция персональных раскрасок этих ребер. Унитарная раскраска F(G)C ПG-графа, с учетом одновременной зависимости от входящих вершин и ребер, есть функция унитарных раскрасок F(G)А и F(G)С.
Эти утверждения никоим образом не определяют содержание функций, связывающих унитарную раскраску ПG-графа с персональными раскрасками его вершин и ребер. Рассмотрим некоторые из таких функций, особенно полезные на теоретико-множественном и логическом уровнях моделирования технических систем.
Отношения, связывающие унитарную раскраску ПG-графа с персональными раскрасками вершин и ребер, когда унитарная раскраска F(G)А определяется по формуле (7), а F(G)C и F(G) - по формулам
F(G)C= |
|
F(ci) |
(13) |
F(GS) = F(G)A |
|
F(G)C |
(14) |
называются дизъюнктивной формой связи (ДФС), а отношения, когда F(G)А определяется по формуле (9), а F(G)С и F(G) - по формулам
F(G)C= |
|
F(ci) |
(15) |
F(GS) = F(G)A |
|
F(G)C |
(16) |
называются конъюнктивной формой связи (КФС). При ДФС унитарная раскраска ПG-графа совпадает с персональными раскрасками вершин и ребер, т.е. F(G)A = F(А) и F(G)С = F(С); при КФС унитарная раскраска ПС-графа, как правило, не совпадает с персональными раскрасками вершин и ребер. Введем единое булево векторное пространство цветов
F=(F1,F2,...,Fn),
"F(A), F(C) (F(A),F(C)
Н F) (17) Тогда множества цветов F(a1) F(c1) F(G) и другие
могут быть представлены как булевы векторы в пространстве (17), и отношения (7),
(13), (14) перейдут в логические отношения ДФС (8) и
m
F(G)C=Ъ F(cj) (18) j=1
F(G)= F(G)AЪ
F(G)C (19)
а отношения (9),
(15), (16) — в логические отношения КФС (10) и
m
F(G)C= Ù F(cj) (20) j=1
F(G)= F(G)A Ù F(G)C
(21)
Если на использование отношении ДФС и КФС не накладываются ограничения, то
вычисление раскраски F(G) можно выполнять с помощью любой тройки формул,
определяемой по схеме
Определение унитарной раскраски ПG-графа можно
представить как последовательность этапов вычисления состояний раскраски после
присоединения очередной вершины (ребра). Все состояния, кроме последнего, будут
промежуточными: конечное состояние после . присоединения последней вершины
(ребра) и будет унитарной раскраской ПG-графа. При
последовательном вычислении унитарной раскраски ПG-графа,
если существуют вершины и ребра с разными персональными раскрасками, при разных
последовательностях присоединения вершин и ребер существуют различные
промежуточные раскраски. Действительно, если имеется пара вершин
ai, aj с
разными составами цветов, то, принимая на первом шаге вычислений за начальную
вершину ai или
aj,
получим различные состояния [F(G)A]1
, и, следовательно, эти две последовательности промежуточных раскрасок будут
различными. Рассмотрим вычисление раскраски при ДФС, например по формуле (8).
Промежуточное состояние раскраски
[F(G)A]k
после присоединения очередной вершины ak
определяется по формуле
[F(G)A]k=
[F(G)A]k-1Ъ
F(ak) (23) Соотношения [F(G)A]k,
[F(G)A]k-1
и F(ak)
характеризуются следующими группами цветов:
- нереализованные в [F(G)A]k-1
цвета, которые реализутются за счет ak
_ [F(G)A]Ik=
[F(G)A]k-1 Ù
F(ak) (24)
_ где F(G)A — результат
инверсии булева вектора F(G)A - нереализованные в
[F(G)A]k-1
цвета, которые не реализуются за счет ak
_
_ [F(G)A]IIk=
[F(G)A]k-1 Ù
F(ak) (25)
_ где F(ak)
— результат инверсии булева вектора F(ak); -
реализованные в [F(G)A]k-1
цвета, которые могли бы быть реализованы и за счет
ak [F(G)A]IIIk=
[F(G)A]k-1 Ù
F(ak) (26) - реализованные в [F(G)A]k-1
цвета, которые не могли бы быть реализованными
за счет
ak
_ [F(G)A]IVk=
[F(G)A]k-1 Ù
F(ak) (27) Если цвета F(G)A должны быть частью
некоторого фиксированного множества F(A)*
Ê F(A) то вместо (23), (24) и (25)
используются формулы [F(G)A]k=
[F(G)A]k-1Ъ
F(ak)
Ù F(A)*(28)
_ [F(G)A]Ik=
[F(G)A]k-1 Ù
F(ak)
Ù F(A)* (29)
_
_ [F(G)A]IIk=
[F(G)A]k-1 Ù
F(ak)
Ù F(A)*
(30) Аналогичные
соотношения будут иметь место и при вычислении унитарной раскраски F(G)C
по
формуле (18). Рассмотрим вычисление унитарной раскраски ПG-графа при КФС,
Например, при вычислении F(G)A
по формуле (10) промежуточное состояние раскраски [F(G)A]k после присоединения очередной вершины
akопределяется по формуле [F(G)A]k=
[F(G)A]k-1 Ù
F(ak) (31) В этом случае исходя из (5), унитарная раскраска F(G)A
будет включать в себя любой цвет Fj(G)A
= 1 только при условии
" ak
Î A(Fj(G)A
=1)
(32) Более общим является случай (6), когда какой-либо цвет Fj(G)A
реализуется определенным (не обязательно единственным) набором элементов
A(Fj)
Í A, т.е. когда Fj(G)A
= 1 при условии $
A(Fj)
Í
A {
" ak
Î A(Fj
)
[Fj(ak)=1]
}
(33) Во всех случаях, когда при КФС какой-либо унитарный цвет ПG-графа
реализуется за счет нескольких элементов одновременно, персональный цвет
отдельного элемента лишь участвует в реализации унитарного цвета, а не реализует
его, как при ДФС. Поэтому вместо отношения (31) следует использовать формулу
[F(G)A]k=
F(A)* Ù F(ak)
(34) Соотношения F(G)A,
F(A) и F(ak)
характеризуются следующими группами цветов: - цвета, входящие в
F(A)*, в реализации которых
может участвовать ak [F(G)A]Ik=
F(A)* Ù F(ak)
(35) - цвета, входящие в
F(A)*, в реализации которых не
может участвовать ak
_ [F(G)A]IIk=
F(A)* Ù F(ak)
(36) - цвета, не входящие в
F(A)*, в реализации которых
может участвовать ak
_ [F(G)A]IIIk=
F(A)* Ù F(ak)
(37) - цвета,
не входящие в F(A)*, в
реализации которых не может участвовать ak
_ _ [F(G)A]IVk=
F(A)* Ù F(ak)
(38) Аналогичные соотношения будут иметь место и при вычислении
унитарной раскраски F(G)C
по формуле (20) при условии $
C(Fj)
Í
C
{
" ck
Î C(Fj
)
[Fj(ck)=1]
}
(39) В соответствии со схемой (22) возможны случаи, когда для
цветов вершин и ребер в ПG-графе могут быть приняты
разные формы связи. Аппарат полихроматических множеств и графов в изложенном
виде применим при структурном анализе и синтезе объектов моделирования.
Дополнительное использование средств иерархической системы моделирования
ИСТРА [2, 4, 7] позволяет расширить область применения ПS-множеств
и ПS-графов и на моделирование дискретного производства. В системе ИСТРА для
описания свойств любых объектов производства и производственной системы
используется единое понятие — контур, обобщающее такие понятия, как свойство и
часть объекта, в которой данное свойство реализуется. Поскольку цвет относится к
категории свойств объекта, разные цвета могут описываться в терминах контуров: i-й цвет — контур
Fi,
j-й цвет — контур
Fj, и т.д. При совместном моделировании
изделия А и производственной системы Р их свойства описываются одними и теми же
контурами, причем Fj
(A)описывает сами свойства изделия, а Fi
(P)отражает
возможность получения Fi
(A) в процессе производства в системе
Р. Производственная система и ее компоненты моделируются,
как и изделие, с помощью ПS-множеств и ПS-графов. Одна из важнейших задач технической подготовки дискретного
производства — анализ технологических возможностей производственной системы
применительно к проектируемому изделию. Эта задача успешно решается с помощью
аппарата
ПS-множеств и ПS-графов. Например, на рис.3 показана модель фрагмента производственной
системы для изготовления отверстий в деталях изделия. Эта модель представляет
собой полихроматический граф ПG = ( P, C, F(P),
[P´F(P)] )
(40) раскраска вершин которого характеризует технологические
возможности элементов производственной системы, а бесцветные дуги описывают
взаимосвязь операций со средствами технологического оснащения производства.
Возможные варианты изготовления отверстий определяются по этой модели как пути в
ПG-графе, реализующие требуемый состав
F(A)* при КФС контуров изделия и
производственной системы. Исходными данными для анализа технологических
возможностей производственной системы в целом с составом контуров
F(P)* являются данные об
исходном составе
F(A)0 контуров
изделия и данные о требуемом составе
F(A)* контуров готового изделия;
исходный состав контуров
F(A)0 формируется за
счет покупных комплектующих, полуфабрикатов и т.п. Технологические возможности
производственной системы P
по отношению к изделию A
анализируются в двух аспектах: как технологические
возможности системы P в
целом и как технологические возможности отдельных элементов
pk входящих в
P. Состав
F(P) контуров модели
производственной системы в матрице контуров [ P´F(P)]
равен объединению контуров входящих в P
элементов pk и
вычисляется по формуле (8) при замене символов
F(S) на
F(P) и
F(ai) на
F(ak). Этот состав контуров полностью пригоден только для анализа
технологических возможностей отдельных элементов производственной системы. Для
анализа технологических возможностей производственной системы в целом этот
состав контуров пригоден только при ДФС контуров
F(P) и
F(A). При КФС любой контур
Fj(P) может
реализовать контур изделия
Fj(P), и,
следовательно,
Fj(P) = 1 только при
условии, когда имеется хотя бы один требуемый набор
F(Pj ) элементов
производственной системы, совместно участвующих в реализации
Fj(A), т.е. при
выполнении условия вида (33). Поэтому для анализа, технологических возможностей
производственной системы в целом формируется состав контуров
F(P)*, в котором
Fj(P)* = 1, если в
производственной системе
P имеются все необходимые
элементы для реализации контура
Fj(A) изделия. При
ДФС этот состав равен
F(P)* = F(P), а
при КФС -
F(P)* Í F(P). Диагностирование производственной системы (ПС) применительно к
изделию
Fi.
осуществляется путем анализа составов контуров
F(Ai)0
,
F(Ai)*
изделия и контуров
F(P)*
производственной системы. Состав
F(Ai)
контуров изделия, которые могут быть реализованы при воздействии данной ПС,
вычисляется по формуле F(A)i= F(Ai )0Ъ F(P)*
(41) описывающей дизъюнктивную форму связи контуров
изделия и ПС. Если состав реализуемых контуров изделия не должен выходить за
пределы
F(Ai)*,
то F(A)i=
( F(Ai )0Ъ F(P)*
) Ù F(A)i
(42) Если при отработке технологичности изделия в ПС допускается
изменение или замена некоторых контуров в F(A)*,
то вводится область
F(Ai)S
Ê
F(Ai)* возможных,
с учетом допустимых изменений, контуров изделия. Тогда возможный состав контуров
F(Ai) вычисляется по
формуле F(A)i=
( F(Ai )0Ъ F(P)*
) Ù F(A)iS
(43) Производство изделия в данной ПС может быть завершено при
условии F(Ai)*= F(Ai ) Ù
F(P)*
(44) При диагностировании технологических возможностей ПС
выявляются: нереализованные в
F(Ai)0 контуры, которые могут быть реализованы в
данной ПС
_ F(Ai)I= F(Ai )0 Ù
F(P)*
(45) _ где F(Ai )0
— инверсия вектора F(Ai )0; нереализованные в F(Ai )0 контуры,
которые не могут быть реализованы в
_
_ F(Ai)II= F(Ai )0 Ù
F(P)*
(46) _ где
F(P)* — инверсия вектора
F(P); реализованные в F(Ai )0
контуры, которые могли бы быть реализованы и в данной ПС F(Ai)III= F(Ai )0 Ù
F(P)*
(47) реализованные в F(Ai )0
контуры, которые не могли бы быть реализованы в данной ПС
_ F(Ai)IV= F(Ai )0 Ù
F(P)*
(48) Вычисления по формулам (45), (46) выявляют и такие контуры
изделия, которые не предусмотрены в составе F(Ai )*. Если составы контуров F(Ai)I и F(Ai)II не должны выходить за пределы F(Ai )*, т.е. конструктивные изменения изделия A недопустимы, то вместо (45), (46) используются формулы
_ F(Ai)I= F(Ai )0 Ù
F(P)* Ù
F(Ai)* (49)
_
_ F(Ai)II= F(Ai )0 Ù
F(P)* Ù
F(Ai)* (50) Если составы контуров F(Ai)I и F(Ai)II могут существовать в
области F(Ai )S, т.е. допускаются конструктивные изменения в пределах F(Ai )S,
то вместо (45), (46) используются формулы
_ F(Ai)I= F(Ai )0 Ù
F(P)* Ù
F(Ai)S (51)
_
_ F(Ai)II= F(Ai )0 Ù
F(P)* Ù
F(Ai)S (52) Если условие (44) не выполняется, то изделие не может быть изготовлено в данной ПС без дополнения ее новыми средствами технологического оснащения производства.
Состав контуров, которыми должны обладать эти приобретаемые или вновь
создаваемые средства, вычисляется в общем случае по формуле (46), а с учетом
недопустимости или допустимости конструктивных изменений изделия — по фюрмуле
(50) или (52). Для выявления причин невозможности реализации контуров F(Ai)П
изделия, вычисляемых по формуле (46), (50), или (51), необходимо анализировать
технологические возможности отдельных элементов pk
Î P. Эта задача решается по модели
производственной системы с использованием матрицы контуров ПG-графа (40)
производственной системы P. Исходными данными для анализа здесь также будут
данные об исходном F(Ai )0 и требуемом конечном F(Ai)* составе контуров изделия.
Вначале определяется путь в графе G = (Р, С), а затем анализируются возможности каждого элемента pk входящего в этот путь. Анализ осуществляется с помощью
формул вида (24) — (30), если матрица контуров ПС дизъюнктивная, а если матрица
конъюнктивная — то с помощью формул (34) — (38). Примеры моделирования различных
технических систем с использованием аппарата полихроматических графов приведены
в [7].
Литература
1.Павлов
В.В.
Основы автоматизации проектирования технологических
процессов сборки летательных аппаратов. — М.:
МАГИ, 1975.-98 с.
2.
Павлов
В.В.
Математическое обеспечение САПР в производстве летательных аппаратов. — М.: МФТИ,
1978.—68 с.
3.Математическое
моделирование дискретного производства:
Сб. науч. трудов ИКТИ РАН. Выл Л / Под ред. Ю.М.Соломенцева.
- М.: ИКТИ РАН, 1993.Т-69 с.
4.Павлов
В.В.
Типовые математические модели в САПР ТПП
— М.: Мосстанкин, 1989.—75 с.
5.Зыков
А.А.
Основы теории графов. — М.: Наука, 1987.—
384с.
6.Куратовский
К., Мостовский А.
Теория
множеств. — М.:
Мир, 1970.-416 с.
7.
САПР.
Типовые математические модели объектов проектирования
в машиностроении /Методические указания РД-50-464-
84. — М.: Изд. Стандартов, 1985. —202 с. |