автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Структурно управляемые системы

Введение

1 Модели систем и задача синтеза

1.1 Реляционные модели.

1.2 Функциональные модели.

1.3 Сетевые модели

1.4 Неформальная постановка задачи синтеза.

2 Связность и независимость

2.1 Предварительные замечания.

2.2 Связность матроидов и абстрактных графов.

2.3 Связность гиперграфов.

2.4 (1, д)-сочетания.

2.5 Примитивные вершины.

2.6 Менгеровские системы.

3 Линейные системы

3.1 Обратимые функциональные элементы.

3.2 Системы из трехполюсников.

3.3 Системы из двухполюсников.

4 Алгоритмы синтеза

4.1 Алгоритм сдвига.

4.2 Случайный поиск

4.3 Многокритериальная оптимизация.

5 Синтез планетарных механизмов

5.1 Задача синтеза.

5.2 Синтез двухстепенных механизмов.

5.3 Синтез одного класса схем механизмов с тремя степенями свободы

6 Перебор и перечисление структур

6.1 Построение блок-схем (1,3)-сочетаний . . . . . . - s

6.2 ( 1,2)-сочетания.

6.3 Перечисление (1, q)-деревьев

6.4 О числе многорежимных систем с полным использованием полюсов

7 функциональные возможности многорежимных систем

7.1 Системы с унарным управлением

7.2 Оценка числа режимов при фиксированных входе и выходе ,,,,,,,

7.3 Оценка числа режимов с учетом группы автоморфизмов блок-схемы , , 227 7-4 Функциональные возможности систем из двухполосников

7.5 Оценка числа функций сигналов многофункционального логического элемента

7.6 Построение множества режимов

7.7 Оценка числа режимов для двухкаскадных схем.

8 Планарные многорежимные системы

8.1 Планарные графы. . :

8.2 Планарные гиперграфы и системы.

8.3 Внешнепла.нарные MPC.

8.4 О максимальном числе элементов,

В этой работе предлагаются и исследуются математические модели и методы синтеза систем, у которых настройка на определенный режим работы (процесса функционирования) осуществляется путем дискретного изменения составляющих элементов и связей между ними, другими словами, путем изменения структуры системы. Такие системы далее называются многорежимными (MPC) или структурно управляемыми системами.

Многорежимные системы находят исключительно широкое применение в практической деятельности человека. Можно назвать, например, механические коробки перемены передач, повсеместно применяемые в силовых агрегатах наземного и водного транспорта, а также в металлообрабатывающих станках [59, 37, 84], [Al, А8], структурно перестраиваемые приборы СВЧ, электрические фильтры и др. радиоэлектронные устройства [3, 7, 36, 37, 39, 40], [А25, А41, А53], дискретно настраиваемые регуляторы давления с изменяемой структурой [А10, А34], многофункциональные логические модули [10, 17, 33, 94], [А44, А49] и др.

Понятно, что столь разные по своей сути системы не могут быть описаны едиными математическими средствами. В зависимости от конкретного " физического" содержания системы и целей исследования используются самые различные математические модели и соответствующие теории. В частности, это - теория систем с переменной структурой [76, 20], теория гибридных функций [77], логико-динамические системы [27, 43, 56], теория переключательных схем [49], метод селектирующих функций [50], методы комбинаторного синтеза систем [52, 54, 55], автоматные модели и сети Петри [97, 94, 88, 58], кибернетические представления систем [44], графовые и гиперграфовые модели [15, 47].

В основе математических моделей, описывающих структурные свойства многорежимных систем, в данной работе лежит теория связности гиперграфов (а как обобщение - и матроидов), предложенная и развитая в трудах автора за последние десятилетия. Она является естественным обобщением теории связности графов. Ее основные положения, а также смежные вопросы, излагаются во второй главе диссертации.

В третьей главе исследуются структурные свойства линейных многорежимных систем. Введено понятие Л—обратимого функционального элемента как обобщение обратимого элемента или симметрической функции и показано, что для любой линейной системы существует равносильная ей по выходным сигналам система, состоящая только из трехполюсных Л—обратимых модулей. Специально исследуются системы, состоящие из двухполюсных модулей.

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

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

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

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

Авторские работы по теме диссертации выделены в отдельный список и при ссылке отмечены буквой " А". В совместных работах с аспирантами, выполненных под руководством автора [А6, А12, А15, А17, А21, А28, А36, А39, А49, А63, А65 и др.], автору принадлежат постановка задач, предложенные методы решения и их обоснование. Моделирующие алгоритмы и соответствующее программное обеспечение разрабатывались под руководством автора и при его непосредственном участии.

Основные обозначения, принятые в работе сМ л - равно по определению, обозначает; М - множество действительных чисел; Ъ - множество целых чисел;

N - множество натуральных чисел; К0 = М +0;

А В - из А следует В ;

А <=$■ В - А тогда и только тогда, когда В ; х\Р(х)} - множество всех х, удовлетворяющих условию Р(х) ;

А| - мощность множества А ; га : га - множество натуральных чисел от т до га, т < п ; {а, 6, с,.} = (а, 6, с,.) - множества; . а[т : га] М {ато, скт+1,., ап}, га < га ; а[А] = {а21, аг;2,., щ[М} , где А = {г'ь г2,., г\л\} С га : га ; РгАВ - проекция множества В на А ; 8сшЯ - сечение множества Л по и> ; ц(А) - местность множества А; А С В - нестрогое вхождение А в В ;

А С В - А собственное подмножество В ; А — а = А\{а] ; А+'аМ А и {а} ;

2г - множество всех подмножеств из 2 ;

- множество всех ^-элементных подмножеств из ¿Г ;

X -Ь А - отображение / множества X в А ; / 1 2 3 . П \ <м л /1 „ч . : = / : (1 : га) (1 : п) ; у а\ «2 «з • • • ап / {/|/ множества всех возможных отображений из X в А;

П;ех Л? ~ Декартово произведение множеств А^^ 6 Л'; А ==] А - дополнение (или отрицание) А ; ] р — Р - отрицание Р ; [а\ - целая часть числа а ; м = к1 +1; а]М [а+ 0.5];

Т = Т\ + + • • • + Тъ - разбиение множества Т.

ЗАКЛЮЧЕНИЕ

В диссертации на основе введенных понятий гипердерева, гиперлеса и др. построена теория связности гиперграфов, обобщающая соответствующую теорию графов; сделано обобщение теоремы Холла о паросочета-нии на (1, д)-сочетания; предложены пути обобщения теоремы Менгера о минимаксе; исследованы гиперлеса, у которых степени вершин меньше числа вершин, инцидентных одному ребру, и построен их каталог; предложены математические модели структурно управляемых систем, у которых настройка на определенный режим работы осуществляется путем изменения структуры; на базе проведенных исследований по теории гиперграфов построена теория линейных структурно управляемых систем; показано, что для любой линейной системы существует эквивалентная ей, состоящая из А-обратимых уравнений; найдена общая формула выходного сигнала для такой системы; на основе предложенных метода случайного поиска, модифицированного для рассматриваемого класса задач метода динамического программирования, методов генерирования неизоморфных гиперлесов, построены алгоритмы синтеза структурно управляемых систем; построены алгоритмы генерирования множеств структурных схем систем; найдены оценки функциональных возможностей для различных классов систем; предложены критерии планарности графов и гиперграфов при различных ограничениях на расположение ребер и вершин, обобщающие критерии Понтрягина-Куратовского; разработанные теоретические положения были использованы в различных областях инженерной деятельности; в частности, построена теория синтеза планетарных механизмов передач, в которой впервые на всех этапах выбора схем были использованы графовые модели; все предложенные методы синтеза схем доведены до алгоритмов и программных продуктов; некоторые из них реализованы в виде диалоговых систем.

1. Абрамов В.А. Розеточные графы и геометрическая совместность схем планарных коробок передач с двумя степенями свободы // Вычислительная техника в машиностроении. - Минск, ИТК АНБССР. - 1972, июнь. - С.23-27.

2. Айгнер А. Комбинаторная теория. М.: "Мир", 1982. - 556 с.

3. Алекперов В.П. и др. Фильтры переменной структуры на основе кворум-элемента (кворум-фильтры) // Автоматика и телемеханика. 1970, N 5. С.37-39.

4. Алферов В.В., Колобаев Л.И., Черный В.Г. Структурный синтез механизмов на основе метода графов связей // Известия ВУЗов. Машиностроение.- N2. 1983.- С.28-30

5. Амбарцумян Р.В. Кинематическое проектирование плоских зубчато-рычажных механизмов с применением графов / / Теория механизмов и машин. Харьков, 1981. N30. - С.21-28.

6. Амбарцумян Р.В. Некоторые приложения теории графов к рациональному выбору паросочетаний элементов кинематических пар в многозвенных механизмах //Теория механизмов и машин. Харьков. 1983. N34. - С.3-9

7. Андреев Д.П. Механически перестраиваемые приборы СВЧ и разделительные фильтры. "Связь", 1973. - 232 с.

8. Анкудинов Г.И. Синтез структуры сложных объектов; логика-комбинаторный подход. Л. Из-во ЛГУ. 1986. - 260 с.

9. Басакер Р., Саати Т. Конечные графы и сети. М., "Наука". 1974. 368 с.

10. Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М., "Высшая школа", 1976. - 392 с.13. .Амбарцумян Р.В. К синтезу плоских генераторов заданного множества функций Теория механизмов и машин. Харьков, 1985. N38. - С.86-97.

11. Беллерт С., Возняцки Г. Анализ и синтез электрических цепей методом структурных чисел. М., "Мир", 1972. - 336 с.

12. Бернштейн Л.С., Малышев Н.Г. Применение гиперграфов для представления сложных схем // Техническая кибернетика. 1975. N5. - С.31-36.

13. Берж К. Теория графов и ее применение. М., ИЛ, 1962. 320 с.

14. Бочков П.Е., Сладков А.Б., Попов Ю.А. Проектирование многофункциональных модулей с использованием инвариантов булевых функций //Автоматика и вычислительная техника. АН Латвийской ССР, 1973. N3- С.15-20.

15. Де Брейн Н.Дж. Теория перечисления Пойа //Прикладная комбинаторная математика. М., "Мир", 1968. - С.61-106.

16. Гофман Ф.Дж., Краскал Дж.Б. Целочисленные граничные точки выпуклых многранников. // Линейные неравенства и смежные вопросы. М., ИЛ. 1959. — С. 17-54.

17. Грездов Т.И. Вопросы теории моделей переменной структуры //Математическое моделирование и теория электрических цепей. Вып.6. "Наукова думка", 1968, - С.54-70.21. . Джолдасбеков У.А. Графоаналитические методы анализа механизмов. Алма-Ата, 1983. - 256 с.

18. Джолдасбеков У.А., Тиммисов С.Г., Нурлыбаев Н.М. Применение теории графов к структурному синтезу механизмов высоких классов //Труды Каз. фил. семинара по теории машин и механизмов. Алма-Ата. 1983(84). - С.131-137.

19. Добрынин С.А., Фирсов Г.И. Применение метода структурных чисел к решению некоторых задач анализа механических колебательных систем // Решение задач машиноведения на вычислительных машинах. М., "Наука", 1974. - С.53-60.

20. Евстигнеев В.А., Касьянов В.Н. Алгоритмы на деревьях. Новосибирск. ВЦ АН СССР. 1989. - 312 с.

21. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М., "Наука", 1981. - 344 с.

22. Желудков В.И. Исследование геометрической совместности со-осных и несоосных схем планетарных механизмов с помощью графовых моделей / / Интенсификация работы перегрузочных технологических линий в речных портах. JL, 1987. - С.40-50.

23. Жук К.Д. Вопросы аксиоматического подхода к построению теории логико-динамических систем управления. // Автоматика и телемеханика. 1971. N5. - С.5-12. -1971. N6. - С.3-11.

24. Зиман Ю.Л., Рябов Г.Г. Волновой алгоритм и электрические соединения. М., 1965. - 247 с.

25. Зыков A.A. Гиперграфы //Успехи математических наук. 1974, т. XXIX, вып. 6(180). - С.89-154.30. , Зыков A.A. Основы теории графов. М., "Наука", 1987. - 381 с.

26. Зыков A.A. Теория конечных графов, I. Новосибирск, "Наука", 1969. - -544 с.32. , Казыханов Х.Р. Моделирование механизмов методом графов связей //Машиноведение. 1984. N 5. - С.3-7.

27. Калнберзинь А.Я., Чапенко В.П. Синтез многофункциональных логических элементов с использованием классификации булевых функций. // Теория конечных автоматов и ее приложения. Вып. 3. Рига. "Зинатне". 1974. - С.61-69.

28. Константинов М.С., Писарев A.M. Алгебраический метод кинематического анализа и синтеза зубчатых дифференциальных передач // Годишник Маш. електр. ин-т. София, 1960(61), 8, кн. 3 - С.33-40.

29. Кофман А. Введение в прикладную комбинаторику. М., "Наука", 1975. - 480 с.

30. Краснов В.В. Алгоритм построения математической модели электрической цепи с переменной топологической структурой //Автоматизация проектирования в электронике. Республиканский межведомственный сборник. Вып. 9. 1974. - С.7-10.

31. Крейнес М.А., Розовский М.С. Зубчатые механизмы. М., "Наука", 1972.- 428 с.

32. Кристофидес Р. Теория графов. Алгоритмический подход. м., "Мир". 1978. - 432 с.

33. Кувырков П.П., Темников Ф.Е. Комбинаторные системы. М., "Энергия". 1975. - 152 с.

34. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: "РиС", 1990.206 с.

35. Линский B.C. Алгоритмическое проектирование вычислительных цифровых устройств. ВЦ АН СССР. М., 1963. - 164 с.42. . Ловас Л., Пламер М. Прикладные задачи теории графов. М., "Мир". 1998. - 653 с.

36. Логвин В.В., Перчук В.Л. Математическая модель логико-дифференциальных систем с распределенными параметрами / / Известия АН СССР. Техническая кибернетика,- 1977. N3.- С.123-131.

37. Лупанов О.Б. О синтезе некоторых классов управляющих систем //Проблемы кибернетики.- М., Физматгиз. 1963. С.61-81.

38. Максилий И.В. Имитационное моделирование на ЭВМ. М., "РиС", 1988. - 232 с.

39. Максименко Ю.Ф. Некоторые топологические приемы исследования линейных структур / / Техническая кибернетика. -N2.1964. С.37-51,

40. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М., "Наука", 1974. - 304 с.

41. Месарович М. Основания общей теории систем / / Общая терия систем. М., "Мир", 1966. - С.15-48.

42. Миллер Р. Теория переключательных схем. I. М., "Наука", 1970. - 416 с.50. . Мищенко В.А. Метод селектирующих функций в нелинейных задачах контроля и управления. М., "Сов. радио", 1973. - 183 с.

43. Мудров В.И. Алгоритм нумерации сочетаний //Журнал вычислительной математики и математической физики. 1965, т. 5, N4. - С.776-778.

44. Направленный метод синтеза структур механических систем // Прикл. мех-ка, 26, N1. Киев. 1990 - С.126-129.

45. Ope О. Теория графов. М., "Наука", 1968.- 352 с.

46. Павлов Б.И. Функциональная структура операционной системы исследования кинематики механизмов. //Решение задач машиноведения на ЭВМ. "Наука", 1975. - С.47-52.

47. Пантелев Ю.Р. Методы комбинаторного синтеза //Препр. М.: ВНИИ прикладных автоматизированных систем. 1986. - 63 с.

48. Перчук B.J1. О некоторых свойствах дискретной подсистемы логико-дифференциальной системы //Известия АН СССР. Техническая кибернетика. 1975, N4. - С. 17-26.

49. Петренюк А.Я. Применение инвариантов в комбинаторных исследованиях // Вопросы кибернетики. Труды семинара по комбинаторной математике. Научный совет по комплексной проблеме "Кибернетика" АН СССР. 1973. - С.129-135.

50. Питерсон Дж. Теория сетей Петри и моделирование систем. -М. "Мир". 1984. 263 с.

51. Планетарные передачи. Справочник. Л,. "Машиностроение", 1977. - 535 с.

52. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: "Наука" . 1982. - 254 с.

53. Пойа Д. Комбинаторные вычисления для групп, графов и химических соединений // Перечислительные задачи комбинаторного анализа. М. "Мир". 1979. - С.36-138.

54. Постникова Л.Н. ППП ГРАФ/2. Генерация графов. Препринт 266. Новосибирск. 1980. - 36 с.

55. Пухов Г.Е., Катков А.Ф. Обратимые модели. М., "Наука", 1981. - 121 с.

56. Рейнгольд Э. и др. Комбинаторные алгоритмы. Теория и практика. М., "Мир", 1980.- 476 с.

57. Риордан Дж. Введение в комбинаторный анализ. М., ИЛ, 1963. - 288 с.

58. Розовский М.С. Комбинаторные методы синтеза зубчатых механизмов, транспортных строительных дорожных и грузоподъемных машин М., НИИ Тракторсельхозмаш, 1976. - 543 с. - Деп. в ЦНИТЭИ Тракторсельхозмаш N 511, от 15.01.77 г.

59. Розовский М.С. Представление одноосных зубчатых механизмов с помощью комбинаторных схем // Доклады АН СССР, 1969, т.184, N5. С.112-114.

60. Сачков В.Н. Комбинаторные методы дискретной математики. -М., "Наука", 1977. 319 с.

61. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М., "Наука" , 1981. - 110с.

62. Свами М., Тхуласираман К. Графы, сети, алгоритмы. -М,,"Мир". 1984. 454 с.

63. Стародубцев H.A. Соотношения для числа настроек многофункциональных логических модулей // Изв. АН СССР. Техн. кибернетика. 1972, N4.- С.145-152.

64. Тарасенков А.Д. Перечисление структурных цепей сложных планетарных механизмов //Путевые работы и гидротехнические сооружения на реках. Л. 1981. - С.61-66.

65. Тартаковский И.М., Иванов A.B. Генерирование неизоморфных структурных схем сложных планетарных механизмов. //Теория механизмов и машин 1981. N30. - С.86-89.

66. Татт У .Т. Теорема о плоских графах. / / Кибернетический сборник. М., "Мир". 1973. №10 - С.66-86.

67. Татт У.Т. Теория графов. М., "Мир". 1988. - 424 с.

68. Теория систем с переменной структурой. (Под ред. С.В.Емельянова). М., "Наука". 1970. - 237 с.

69. Терно О.Р. Гибридные функции новый метод описания сложных систем //Известия АН СССР. Техническая кибернетика. -1965. №6. - С. 37-49.

70. Трахтенберг Б.А. К теории бесповторных контактных схем // Труды Мат. ин-та АН СССР им. В.А.Стеклова. 1958. №1. -С. 227-269.

71. Уилсон Р. Введение в теорию графов. М., "Мир". 1977. - 207 с,

72. Усов Б.А. Графовые модели в автоматизированном проектировании механизмов. Минск. 1991. - 85 с.

73. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М., "Мир". 1966.- 276 с.

74. Харари Ф. Теория графов. М., "Мир". 1973. - 302 с.

75. Харари Ф., Палмер Э. Перечисление графов. М., "Мир". 1977.- 324 с.

76. Харченко А.П. Конструирование и расчет планетарных передач. Часть 1. Л., Из-во ЛПИ. 1974. - 192 с.

77. Хачатрян М.А. Матрицы на гиперграфах и задача о плотности. Ерев. политехи ин-т. Ереван, 1988. - Деп. В АрмНИИНТИ 08.04.88, №35. Ар88. - 15 с. .

78. Хачатрян М.А. Оценка хроматического числа гиперграфа и некоторых его су графов / /Графы, гиперграфы и дискретные оптимизационные задачи Кишинев, "Штитинца". 1982. - С.179-184.

79. Хачатрян М.А. Оценка хроматического числа гиперграфа и некоторых его суграфов //Графы, гиперграфы и дискретные оптимизационные задачи Кишинев, "Штитинца", 1982.- С.179-184.87 8889