Разработка и оптимизация графовых моделей САПР систем управления
Методы исследований. Методическую основу исследований составила теория характеризационного анализа. Это позволило в каждом из выполняемых преобразований исключить из рассмотрения бесперспективные варианты и тем самым дало возможность избежать их комбинаторного перебора. Кроме того, использовались методы теории множеств и теории графов. Целью работы является исследование разложимости и разработка… Читать ещё >
Содержание
- 1. Состояние вопроса и постановка задачи
- 1. 1. Обзор методов автоматизированного проектирования систем управления
- 1. 2. Преобразование ДСМ в детерминированный автомат
- 1. 3. Задача декомпозиционного синтеза
- 1. 4. Выводы
- 2. Анализ функционирования автоматов по входным векторам
- 2. 1. Структуры автономного функционирования систем логического управления
- 2. 2. Анализ пересекающихся контуров
- 2. 3. Определение номера вершины контура по ее спектру
- 2. 4. Пересекающиеся контуры с прерывистой общей частью
- 2. 5. Преобразование структур графоидов к стандартному виду
- 2. 6. Выводы
- 3. Разработка системы проектирования абстрактной декомпозиции и ее имитационное моделирование
- 3. 1. Выделение контуров автономного функционирования
- 3. 2. Генератор графоидов с заданными параметрами
- 3. 3. Выводы
- 4. Абстрактная декомпозиция систем управления (на примерах системы управления промышленной автоматики и системы управления информационными процессами)
- 4. 1. Построение автомата управления установкой очистки воды
- 4. 2. Построение автомата управления локальной вычислительной сетью
- 4. 3. Выводы
Разработка и оптимизация графовых моделей САПР систем управления (реферат, курсовая, диплом, контрольная)
Современные достижения научно-технического прогресса сопровождаются усложнением задач управления многосвязными технологическими процессами. Это делает невозможным управление без использования средств автоматизации. В свою очередь, время разработки автоматизированной системы управления вручную, на основе только инженерной интуиции, соизмеримо со сроками морального старения проектируемых устройств. Это обусловило необходимость создания систем автоматизации проектирования (САПР) высокой производительности, позволяющих в приемлемые сроки оценивать большое число проектных решений и выбирать наиболее удовлетворительное.
Системы управления представляются конечно-автоматными моделями, дискретно-событийными моделями (ДСМ), как вероятностными, так и детерминированными, пакетами прикладных программ. Идеи конечно-автоматной интерпретации систем управления получили большое развитие в трудах ряда отечественных и зарубежных ученых, таких как Глуш-ков В.А., Гаврилов М. А., Горбатов В. А., Поспелов Д. А., Кобринский Н. Е., Трахтенброт Б. А., Лазарев В. Г., Хафман Д., Ангер С., Мак-Класки И., Полл М., Миллер Р.
С середины 80-х годов большое внимание разработке и анализу ДСМ, состоящим из взаимодействующих модулей дискретных событий, таких как производственные системы и сети связи, системы с непрерывными переменными. Различным аспектам разработки и анализа ДСМ посвящены работы Зиглера Б. П., Цао С. (США), Рамаджа П.Дж., Уонема У. М. (Канада), Коэна Г., Моллера П., Кадра Ж.-П. (Франция), Горбатовой М. В., Захарова В. А., Крицкого С.П.(Россия) и др. ДСМ позволяют достаточно полно учитывать воздействия внешней среды, однако они имеют большое количество физических состояний, что затрудняет обработку сложных технологических систем. Вследствие этого представляется целесообразным подход, реализующий преобразование ДСМ в детерминированный автомат, где все случайные воздействия приводят к заранее известным технологическим состояниям. В результате такого преобразования уменьшается количество переменных, которыми описываются устройства управления.
Очень удобной и эффективной формой представления дискретно-событийных динамических систем (ДСДС), и особенно их наиболее значительного и широко распространенного подкласса — конечных автоматов, являются графовые модели. Графовые модели, служившие многие годы лишь средством иллюстрации тех или иных свойств объектов и явлений, к настоящему времени стали мощным математическим аппаратом, позволяющим решать многие проблемы оптимизации дискретных систем.
Высокая степень формализации и инвариантность относительно предметной области исследований обусловило их широкое распространение, а созданная в трудах Российского ученого Горбатова В. А. ветвь дискретной математики — характеризационный анализ, стал новым импульсом развития прикладной теории графов.
При выполнении оптимизационных преобразований над графами, задающими функционирование проектируемых устройств управления, часто приходится решать задачи комбинаторной сложности, что становится серьезным, иногда непреодолимым, препятствием нахождения оптимальных проектных решений для систем большой сложности.
Из этого следует очевидная актуальность проблемы уменьшения размерности решаемых задач путем построения декомпозиции проектируемых устройств уже на этапе абстрактного синтеза.
В случаях сложных систем представляется целесообразным производить декомпозицию детерминированного автомата на совокупность параллельно функционирующих устройств.
Целью работы является исследование разложимости и разработка методики разложения автоматных операторов, заданных графоидами, в частичное декартово произведение, что позволяет уменьшить размерность задачи до величины практической реализуемости последующих после этапа абстрактного синтеза преобразований в допустимых временных пределах.
Для достижения указанной цели в работе:
— решена задача характеризации разложимости графоидов в терминах автоматов автономного функционирования;
— найдены ограничения на разложимость, накладываемые характером пересечения контуров автономного функционирования;
— проведено имитационное моделирование разработанных процедур предложенного подхода и выработаны рекомендации по целесообразности его применения в зависимости от свойств автоматного оператора.
Методы исследований. Методическую основу исследований составила теория характеризационного анализа. Это позволило в каждом из выполняемых преобразований исключить из рассмотрения бесперспективные варианты и тем самым дало возможность избежать их комбинаторного перебора. Кроме того, использовались методы теории множеств и теории графов.
Научная новизна работы. В результате проведенных исследований:
— для этапа абстрактного синтеза управляющих автоматов предложен метод декомпозиции, основанный на анализе автоматов автономного функционирования;
— разработана структура взаимодействия предложенного метода с ранее известным (основанном на специальной раскраске графа функциональной связности состояний — графа зацепления), что позволило строить декомпозицию графоидов произвольных свойств;
— выявлены запрещенные фигуры разложимости графоидов и предложены процедуры их преобразования к разрешенному виду, а также сформулирована и доказана соответствующая теорема;
— установлено взаимно — однозначное соответствие между номером вершины в контуре и соответствующим ей спектром, обеспечивающее сохранение детерминированности автоматных операторов компонент разложения;
— на основе анализа пересекающихся запрещенных фигур выработаны рекомендации по их оптимальному расщеплению расширением носителя;
— предложены эффективные процедуры преобразования графоидов автономного функционирования к стандартному виду с целью упрощения реализации проектируемого устройства.
Практическая значимость работы состоит:
— в создании методики построения графовых моделей систем управления по заданному описанию управляемого процесса;
— в совмещении двух различных подходов в единой системе абстрактной декомпозиции управляющих автоматов, что дает возможность в зависимости от результатов выполнения некоторой процедуры выбирать следующую в том же или в другом подходе;
— в разработке алгоритмов и программных средств реализации декомпозиции графоидов со сложными структурами.
Реализация результатов работы. Полученные в работе результаты внедрены в практику проектирования устройств управления технологическими процессами металлургического производства на заводе «Электроцинк «, а также в учебный процесс по курсу «САПР систем промышленной электроники», в курсовом и дипломном проектировании.
Апробация работы. Основные положения диссертационной работы доложены и обсуждены на научно-технических конференциях СКГТУ (г.Владикавказ, 1998;1999 г. г.) и Международной конференции «Информационная математика, кибернетика, искусственный интеллект в инфор-мациологии» (г.Москва — г. Владикавказ, 1999 г.).
Публикации. Основные положения диссертации опубликованы в 9 печатных работах.
4.3. Выводы.
На основе предложенного метода спроектирована абстрактная декомпозиция системы управления локальной вычислительной сетью. В результате исходный автоматный графоид состоящий из 26 вершин разложен в произведение двух графоидов с семью и десятью вершинами соответственно.
Спроектирована также абстрактная декомпозиция системы управления промышленной автоматики. Графоид автомата управления системы очистки воды содержит 35 вершин, в результате декомпозиции получили два подавтомата с 5 и 7 состояниями соответственно.
ЗАКЛЮЧЕНИЕ
.
По результатам диссертационной работы сделаны следующие выводы:
1. Предложен метод декомпозиции, основанный на анализе автоматов автономного функционирования.
2. Найдены запрещенные фигуры разложимости автоматов автономного функционирования и предложен способ их оптимального расщепления.
3. Разработано взаимодействие этого метода с известным ранее подходом, основанном на специальной раскраске неориентированной графовой модели функциональной связности состояний по входным векторам.
4. Предложены процедуры преобразования графоидов к структуре цунга и эмпирическим путем установлены количественные характеристики графоидов, позволяющие оценить целесообразность этого преобразования.
5. Созданы математические и программные средства декомпозиции СЛУ на абстрактном этапе синтеза.
6. Предложен комбинированный подход формального описания объектов управления, использующий анкетный язык диалога «проектировщик — заказчик» и временные диаграммы функционирования объекта.
7. Проведено имитационное моделирование системы проектирования декомпозиции и по его результатам осуществлена коррекция взаимодействия двух подходов.
Список литературы
- Цао.С. Сравнительный анализ динамики непрерывных и дискретно-событийных систем // ТИИЭР, т.77, № 1, январь 1989.
- Райтер Р., Вальран Ж. С. Распределенное имитационное моделирование дискретно-событийных систем // ТИИЭР, т.77, № 1, январь 1989.
- Рамадж П.Дж.Г., Уонем У. М. управление дискретно-событийными системами // ТИИЭР, т.77, № 1, январь 1989.
- Зиглер Б.П. Представление динамических систем на основе дискретно-событийных описаний: Интеллектуальное управление на базе событий // ТИИЭР, т.77, № 1, январь 1989.
- Инан К.М., Варайя П. П. Алгебры дискретно-событийных моделей // ТИИЭР, т.77, № 1, январь 1989.
- Коэн Г., Молл ер П., Кадра Ж.-П., Вьо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // ТИИЭР, т.77, № 1, январь 1989.
- Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. у ¦
- Талль А.А. Анкетный язык и абстрактный синтез минимальных последовательностных машин // Автоматика и телемеханика, № 6, т. XXV, 1964.
- Пийль Е.И. Кодирование состояний входа в микропрограммном автомате. Сб. Автоматы и управление. М.: Наука, 1972.
- Горбатов В.А. Схемы управления ЦВМ и графы. М.: Энергия, 1971.
- Hartmanis I. On the state assignment problem for sequential mashines I, IRE Trans. On Electronic Computers, EC-10, N2, 1961.
- Hartmanis I., Stearns R.E. Pair algebra and its application to automata theory / Information and control, I., N7, 1964.
- Yoli M. The cascade decomposition of sequential machines / I. IRE Trans. On Electronic Computers, EC-10, N4, 1961.
- Yoli M., Ginsburg A. On homomorphic images of transition grafs / I. Franklin Inst., 278, N.5, 1964.
- Kohavi Z. Secondary state assignment for sequential machines / I. IRE Trans. On Electronic Computers, EC-13, N.3, 1964.
- Григорян A.K. Метод декомпозиции конечных автоматов // Автоматика и телемеханика, № 5, 1968.
- Григорян А.К. Метод декомпозиции конечных автоматов с выделением выходного и входного автоматов // Автоматика и телемеханика, № 10, 1968.
- Кузнецов О.П. Параллельная декомпозиция автоматов с разделением входов // Автоматика и телемеханика, № 3, 1969.
- Мелихов А.И. Некоторые операции над графами // Изв. АН СССР. Техн. кибернетика, № 6, 1964. I
- Мелихов А.И., Дворянцев Ю. А. Разложение графов и конечных автоматов относительно операции умножения // Кибернетика, № 3, 1965.
- Мелихов А.И., Бернштейн JI.C., Карелин В. А. Разложение графов и конечных автоматов по операции суммирования // Изв. АН СССР. Техн. кибернетика, № 2, 1968.
- Мелихов А.И., Дворянцев Ю. А. Теоретико-множественные и алгебраические операции над конечными автоматами // Изв. АН СССР. Техн. кибернетика, № 3, 1967.
- Мелихов А.И., Бернштейн JI.C., Карелин В. П. О декомпозиции абстрактных автоматов // Кибернетика, № 3, 1969.
- Мелихов А.И. Ориентированные графы и конечные автоматы.- М.: Наука, 1971.
- Горбатов В.А., Дедегкаев А. Г. Метод расщепления запрещенных фигур при построении параллельной декомпозиции систем / Сб. Прикладные вопросы теории систем и системотехнике.- М.: МДНТП, 1973.
- Горбатов В.А., Дедегкаев А. Г. Запрещенные фигуры при параллельной декомпозиции автоматов / В кн.: Оптимизация дискретных систем управления.- ГВЦ Госплана СССР, 1972.
- Горбатов В.А., Макаренков C.B. Запрещенные фигуры при совместной минимизации системы булевых функций в классе решетчатых ДНФ / В кн.: Оптимизация дискретных систем управления. ГВЦ Госплана СССР, 1972.
- Дедегкаев А.Г. Использование зависимой раскраски графов при построении декомпозиции автоматных операторов / В кн. Логическое управление в промышленности.- Ижевск, ИМИ, 1984.
- Горбатов В.А., Кафаров В. В., Павлов П. Г. Логическое управление технологическими процессами.- М.: Энергия, 1978.
- Зарецкий С.А. Технология электрохимических производств.- М.: В.Ш., 1970. '
- Дедегкаев А.Г., Динцис Д. Ю. Особенности функционирования управляющего автомата в случайной среде // Международный конгресс информатизации пам. А. Нобеля. Материалы конгресса.- Ижевск, 1995.
- Дедегкаев А.Г., Динцис Д. Ю. Частный случай детерминирования конечного автомата / Сб. Труды СКГТУ, вып.1, Терек, Владикавказ, 1995.
- Айзерман М.А., Гусев Л. А., Розоноэр Л. И., Талль A.A. Логика. Автоматы. Алгоритмы.- М.: Физматгиз, 1963.
- Отчет о НИР «Разработка параллельных систем логического управления для САПР «Компас-Р"(Заключительный)», Орджоникидзе, 1985.
- Горбатов В.А. Теория частично упорядоченных систем.- М.: Сов. радио, 1976.
- Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике.- М.: В.Ш., 1973.
- Горбатов В.А. Семантическая теория проектирования автоматов.- М.: Энергия, 1979.
- Горбатов В.А., Останков Б. Л., Фролов С. А. Регулярные структуры автоматного управления.- М.: Машиностроение, 1980.
- Автоматизация проектирования сложных логических структур / Горбатов В. А., Демьянов В. Ф., Кулиев Г. Б. и др. Под ред. проф. В. А. Горбатова.- М.: Энергия, 1978.
- Горбатов В.А. Интеллектуальные информационные технологии и стратегии (состояние и перспективы) // Информационные технологии, январь, 1995.
- Харари Ф. Теория графов.- М.: Мир, 1973.
- Горбатов В.А. Информационная математика.- М.: Наука, 1997.
- Горбатов В.А. Основы дискретной математики.- М.: В.Ш., 1986.
- Поспелов Д.А. Логические методы анализа и синтеза схем.-Л.- М.: Энергия, 1964.
- Горбатов В.А., Павлов П. Г., Четвериков В. Н. Логическое управление информационными процессами.- М.: Энергоиздат, 1984.
- Горбатов В.А., Крылов А.В, Федоров Н. В. САПР систем логического управления.- М.: Энергоиздат, 1988.
- Планирование эксперимента в исследовании технологических процессов. Под ред. Э. К. Лецкого.- М.: Мир, 1977.
- Горбатов В.А. Минимизация логических структур при общем подходе к синтезу. Теория дискретных систем.- М.: изд. МЭИ, 1967.
- Горбатов В.А., Смирнов М. И., Хлытчиев И. С. Логическое управление распределенными системами.- М.: Энергоиздат, 1991.
- Горбатов В.А. Синтез микропрограммных автоматов по временным диаграммам их функционирования. Цифровая вычислительная техника и программирование, вып.5- М.: Сов. радио, 1969.
- Лазарев В.Г., Пийль Е. И. Синтез управляющих автоматов.-М.:Энергия, 1970.
- Евреинов Э.В., Прангишвили И. В. Цифровые автоматы с настраиваемой структурой.- М.: Энергия, 1974.
- Закрецкий А.Д. Алгоритмы синтеза дискретных автоматов.- М.: Наука, 1971.
- Рогинский В.Н. Основы дискретной автоматики.- М.: Связь, 1975.
- Минский М.М. Вычисления и автоматы.- М.: Мир, 1971.
- Трахтенброт Б.А. Алгоритмы и вычислительные автоматы.- М.: Сов. радио, 1974.
- Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука. Физматлит, 1999.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.
- Горбатов В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов // Изв. АН СССР. Техническая кибернетика.-1970.-№ 4.
- Горбатова М.В. Теория трасс / Информационные коммуникации, сети, системы и технологии.-М.: МАИ, 1993.
- Зыков А.А. Теория конечных графов.- Новосибирск: Наука, 1969.
- Майника Э. Алгоритмы оптимизации на сетях и графах.- М.: Мир. 1981.
- Поспелов Д.А. Логико лингвистические модели в системах управления.- М.: Энергия, 1981.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир, 1980.
- Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.: Мир, 1984.
- Юзвишин И.И. Инфомациология.- М.: Радио и связь, 1996.
- Дедегкаева Л.М. Технологические процессы как объекты управления / В кн. Электронные приборы и устройства в промышленности. Тезисы докладов юбилейной конференции. — Владикавказ: Терек. — 1994.
- Цаллагов А.Г., Маркман М. Я., Дедегкаева Л. М. Программируемый контроллер технологических процессов / В кн. Электронные приборы иустройства в промышленности. Тезисы докладов юбилейной конференции. Владикавказ: Терек — 1994.
- Дедегкаева Л.М. Использование планирования эксперимента при проектировании АСУТП / Труды СКГТУ, выпуск 5.- Владикавказ: Терек, 1998.
- Дедегкаев А.Г., Рязанов В. П., Дедегкаева Л. М. Применение дискретной модели управления при проектировании металлургических процессов / Сб. Логическое управление организационными структурами. СКГТУ, Владикавказ: Терек, 1998.
- Дедегкаев А.Г., Динцис Д. Ю., Дедегкаева Л. М. ОсобенностиIграфоидов стохастических автоматов, накладывающие ограничения на их разложимость / Сб. Логическое управление организационными структурами. СКГТУ, Владикавказ: Терек, 1998.
- Динцис Д.Ю., Дедегкаева Л. М., Рязанов В. П. О возможности преобразования автоматных графоидов технологических процессов к стандартному виду / Труды СКГТУ, выпуск 5, Владикавказ: Терек, 1998.
- Пагиев К.Х., Дедегкаева Л. М. Некоторые особенности декомпозиции микропрограммных автоматов управления технологическими процессами / Труды СКГТУ, выпуск 6, Владикавказ: Терек, 1999.
- Норенков И.П. Введение в автоматизированное проектирование технических устройств.- М.: В.Ш., 1986.
- Цурков В.И. Декомпозиция в задачах большой размерности.- М.: Наука, 1981.
- Романовский И.В. Алгоритмы решения экстремальных задач.- М.: Наука, 1977.
- Бурков В.Н., Ланда Б. Д., Ловецкий С. Б. Сетевые модели и задачи управления. -М.: Сов. радио, 1967.
- Горбатова М.В. Быстродействующий алгоритм раскраски вершин графа / В кн.: Логическое управление в промышленности.- Ижевск: ИМИ, 1984.
- Шнейдер A.A. Классификация и анализ эвристических алгоритмов раскраски вершин графа // Кибернетика, 1984, № 4.
- Советов Б.Я., Яковлев С. А. Моделирование систем. — М.: Наука, 1987.
- Малина О.В. Сравнительная характеристика множеств запрещенных фигур объектов различной природы // Информационная математика в информациологии.- Сборник трудов, Москва Ижевск, 1997.
- Лашенков A.B. Декомпозиционный подход к раскраске вершин графа // Академический сборник научных трудов. Проблемы характеризационного анализа и логического управления.- М.: 1999. I