Содержание к диссертации
Введение
Глава I. Формализуемые задачи проектирования структур автоматизированных поверочных комплексов и методы их решения 15
1.1. Основные понятия 15
1.2. Анализ множества альтернатив 19
1.3. Анализ множества требований 25
1.4. Анализ целей 28
1.5. Рациональная декомпозиция структуры 33
1.6. Построение рациональной структуры 34
1.7. Выбор рационального набора модулей 37
1.8. Проектирование метрологического обеспечения АПК 39
Выводы 39
Глава 2. Двудольные графы и задачи проектирования структуры АПК 41
2.1. Двудольные графы как язык описания задач проектирования структур 41
2.1.1. Бинарные отношения 41
2.1.2. Интерпретации двудольных графов. 42
2.1.3. Двудольные графы в качестве модели для выбора структур 45
2.2. Постановки задач проектирования структур в терминах
покрывающих и независимых множеств 46
2.2.1. Покрывающие, доминирующие и независимые множества в графе 46
2.2.2. Взаимосвязь и сводимость задач о покрывающих и независимых множествах 51
2.2.3. Постановки задач проектирования структур АПК 54
2.3. Общий алгоритм построения структуры АПК 62
Выводы 64
Глава 3. Алгоритм решения задачи о наименьшем покрытии множествами 66
3.1. Краткая историческая справка 66
3.2. Алгоритм решения ЗПМ с единичными весами PR0BEST 69
3.3. Алгоритм решения ЗПМ с единичными весами C0STAR 77
3.4. Алгоритм точного решения ЗШ с произвольными весами SELEX 87
3.5. Реализация предложенных алгоритмов решения ЗШ на ЭВМ и результаты численного эксперимента 94
Выводы 103
Глава 4. Архитектура комплекса для автоматизированных метрологических исследований 104
4.1. Архитектурные характеристики АПК 104
4.2. Обоснование необходимости децентрализации управления в АПК 107
4.3. Выбор спецификации интерфейса измерительного полкомплекса 111
4.4. Реализация промежуточного интерфейса и блока программирования в АПК "КВДР-І" 125
Выводы 136
Глава 5. Организация измерительного процесса в АПК 137
5.1. Автоматизированная поверка средств измерений 157
5.2. Алгоритмы прецизионных измерений напряжения 141
5.3. Программная реализация алгоритмов точных измерений напряжения 151
Выводы 15"4
Заключение 156
Литература 158
Приложение I. Тексты программ предложенных алгоритмов Решения ЗШ. .168
Приложение 2. Акты о внедрении результатов диссертационной работы 174
- Проектирование метрологического обеспечения АПК
- Двудольные графы как язык описания задач проектирования структур
- Алгоритм решения ЗПМ с единичными весами PR0BEST
- Обоснование необходимости децентрализации управления в АПК
- Автоматизированная поверка средств измерений
Введение к работе
Благодаря необходимости внедрения в сферу народного хозяйства, связанную с разработкой, производством и эксплуатацией промышленных изделий, интенсивных форм организации труда, все большую актуальность приобретает проблема автоматизации различных технологических и исследовательских процессов и, в частности, - метрологических исследований. Наиболее эффективно решить эту проблему позволяют автоматизированные поверочные комплексы (АПК), построенные на базе современных мини- и микро-ЭВМ. При этом повышаются производительность, точность, количество, качество и единообразие таких видов метрологических исследований, как аттестация, поверка, прецизионные измерения физических величин и т.д. Но наибольшую пользу автоматизация метрологических исследований может принести, если её начинать с процесса проектирования (синтеза) самих АПК.
Задача формализованного проектирования сложных систем, подобных АПК, является сейчас объектом пристального внимания исследователей, поскольку до последнего времени эта проблема оставалась мало изученной, а особенно один из радних и важнейших этапов её решения - выбор структуры. Такое положение обусловлено объективной трудностью задачи выбора структур, которая принципиально до конца не формализуема. Тем не менее, существует рдц поддающихся полной или частичной формализации частных задач выбора структур, для которых можно предложить алгоритмы, позволяющие получать приемлемые решения за. конечное время.
Решение вопросов синтеза, и анализа структур сложных сие- тем нашло отражение в работах кал отечественных: БД.Горбатов, С.В.Жак, В.И.Нечипоренко, А.И.Половинкин, А.Д.Цвиркун, Д.Б.Юдин и да., - так и зарубежных ученых: Л.Бертэланфи, Дж.Касти, М.Месарович, М.Пешель, Я.Такахара, Ф.Харари, Р.Г.Эткин и да. Проблемы синтеза информационных измерительных систем (ИИС) и измерительно-вычислительных комплексов (ИВК) изучались советскими исследователями: Г.И.Кавалеровым, С.М.Мандельштамом, Г.С.Певзнером, Э.И,Цветковым и да. Однако решение указанной задачи ещё далеко от завершения.
Постановки задач проектирования структур, предлагаемые различными авторами, в основном, кал правило, могут быть сформулированы в виде задач целочисленного программирования [ 1,6,30,48,60,85,91] . Но получившая развитие в последнее десятилетие теория NP - полноты [22] оставляет слишком мало надежд на принципиальную возможность существования алгоритмов решения этих задач за приемлемое (полиномиальное) Еремя при достаточно большой их размерности (число переменных больше 10). Поэтому в [91] указывается на актуальность классификации конкретных задач проектирования и разработки частных методов решения специальных классов дискретных задач, специфика которых позволяет получить приемлемые по трудоемкости точные или приближенные алгоритмы.
Следствием сложности проблемы выбора структуры является не только признание достаточности приближенных результатов решения, но и большое разнообразие подходов к ней. Подход, предлагаемый в настоящей работе, базируется на опыте, накопленном в области теории выбора структур, и наиболее близок к работам В.А.Горбатова [16] , С.В.Жака [30] и Дж.Касти [38.] .
Актуальность проблемы подтверждается тем, что она включена в тематику рабочей группы "Математические методы САПР" секции по общесистемным вопросам "Программы САПР" Минвуза РСФСР, а работы по созданию автоматизированного поверочного комплекса выполнены е соотеєтстеии с планом государственной стандартизации Госстандарта на 1980-1985 гг. по проблеме "Создание государственных и рабочих эталонов" (код задания 8.3.2.08.12).
Целью данной работы является разработка, и исследование математической модели и эффективных эвристических (приближенных) алгоритмов решения частных задач выбора структуры и архитектуры автоматизированных комплексов для метрологических исследований и получение на их основе некоторых практических рекомендаций для оказания помощи проектировщику при создании аппаратурного и программного обеспечения АПК.
Основными задачами, решаемыми в диссертационной работе в связи с поставленной целью, являются следующие:
Анализ существующих методов решения задачи выбора структур сложных систем и выявление поддающихся формализации частных задач выбора структуры АПК.
Разработка и анализ математической модели задачи выбора структуры АПК, постановка частных задач выбора структуры е терминах: разработанной модели, анализ существующих алгоритмов решения этих задач, разработка и исследование новых алгоритмов.
Реализация на ЭВМ и экспериментальные исследования разработанных алгоритмов решения частных задач выбора структуры.
Выбор архитектуры АПК на базе предложенной модели и разработанных алгоритмов, реализация и проверка выбранной архитектуры в условиях эксплуатации АПК.
5. Повышение эффективности применения микро-ЭВМ в АПК путем разработки алгоритмов прецизионных измерений физических
ЕЄЛИЧИН.
В результате решения перечисленных задач получены следующие новые результаты;
Для решения частных задач выбора структуры АПК предложена математическая модель в виде двудольного графа, которая позволяет сталить и решать частные задачи в терминах покрывающих, доминирующих и независимых множеств двудольного графа, причем, для многих из этих задач существуют полиномиальные алгоритмы.
Па. основе предложенной модели сформулировано 15 частных формализуемых задач, входящих в последовательность синтеза структуры АПК, и указаны пути их решения.
Предложен общий алгоритм выбора структуры и архитектуры АПК.
Теоретически обоснованы, разработаны, реализованы на ЭВМ и проанализированы два экономных эвристических алгоритма решения задачи о покрытии множествами с единичными Бесами, один из которых основал на вероятностных оценках элементов-кандидагоЕ в наименьшее покрытие, .другой - существенно использует свойства орграфа, построенного из исходного двудольного графа по определенному правилу.
Теоретически обоснован, разработан, реализован на ЭВМ и проанализирован точный алгоритм решения задачи о покрытии множествами с произвольными весами. Алгоритм основан на прин- ципе лексикографического упорядочения и позволяет находить кал точное, так и приближенное (за более короткое время) решение задачи.
На основании предложенных модели и алгоритмов выбора структуры решены вопросы выбора архитектуры АПК: обоснована необходимость децентрализации управления в АПК и сформулированы рекомендации по выбору спецификации интерфейса измерительного подкомплекса.
Разработаны и реализованы два быстродействующих алгоритма прецизионного измерения напряжения, способствующих повышению эффективности использования микро-ЭВМ в АПК.
Практическая ценность полученных в работе результатов заключается не только в том, что они могут оказать помощь проектировщику автоматизированных поверочных комплексов. Проведенные исследования будут полезны при оптимизации .других звеньев системы метрологического обеспечения: метрологических лабораторий, передвижных поверочных лабораторий, служб проката измерительной аппаратуры, метрологических служб области, региона и т.д. Некоторые из полученных результатов могут быть распростралены на проектирование ИИС и ИВК практически любого назначения. Предложенные в работе алгоритмы решения задачи о покрытии множествами имеют самостоятельное прикладное значение и, кроме выбора структур, могут быть использованы для решения задач информационного поиска, минимизадии дизъюнктивных нормальных форм, составления оптимальных маршрутов и расписаний., а также могут способствовать решению ряда задач о доминирующих, покрывающих и независимых множествах.
Диссертационная работа состоит из пяти глав.
В первой главе сформирован список из семи частных задач структурного синтеза АПК, поддающихся полной или частичной формализации, и для каддой задачи из этого списка рассмотрены наиболее распространенные методы её решения. В результате проведенного анализа сделал вывод о том, что в качестве математического алпарата при выборе структур наиболее удобно пользоваться теорией графов, а также выяснена необходимость разработки математической модели выбора структур АПК, позволяющей с точки зрения единого формализма описывать ортогональные свойства объектов проектирования, то есть решать по возможности все частные задачи выбора структур. Кроме того, эта модель должна давать возможность использовать (или создавать) эффективные алгоритмы решения задач большой размерности.
Во второй главе .для решения частных задач выбора структуры АПК предложена математическая модель в виде двудольного графа G(X,Y,E) , где л и Y - конечные множества элементов, являющихся исходными для частной задачи, с - множество ребер, отображающее бинарное отношение ЛслМ Сформировал список из девяти задач о покрьшающих, доминирующих и независимых множествах в двудольном графе, в который вошли следующие задачи: I. Минимальное покрытие множествами; 2. Минимальное вершинное покрытие; 3. Минимальное реберное покрытие; 4, Максимальное независимое множество вершин;
Максимальное независимое множество ребер (паросочетание);
Минимальное доминирующее множество вершин; 7. Минимальное доминирующее множество ребер; 8. Минимальное независимое доминирующее множество вершин; 9. Минимальное независимое доминирующее множество ребер. По признаку существования для указанных задач полиномиальных алгоритмов решения каждая задача отнесена к одной из двух групп. В I группу вышли задачи 2-5, .для которых существуют полиномиальные алгоритмы (если граф) двудольный), во П группу включены задачи I, 6-9, которые таких алгоритмов не имеют, и, по-ЕИдимому, иметь не могут (в соответствии с теорией NP - полноты).
Рассмотрены взаимосвязи между задачами в каждой группе и между двумя группами. Указало, что для решения задач I группы универсальным является метод паросочетаний [22,43] , а для П группы и задач всего списка общим методом является метод решения задачи о покрытии множествами (ЗПМ). Далее в этой главе формируются 15 частных задач структурного синтеза АПК в терминах покрывающих, доминирующих и независимых множеств и предлагается общий алгоритм проектирования структуры АПК, включающий в себя решение этих задач.
В третьей главе в сеязи с тем, что .для П группы задач возможность существования полиномиального алгоритма весьма призрачна, предлагаются алгоритмы приближенного решения ЗПМ. Эта задача состоит в нахождении покрытия есєх элементов из множества. Л двудольного графа G(X,Y) или наименьшим числом элементов из множества. Y , если веса элементов из Y равны I; или элементами из Y с наименьшим суммарным весом, если их веса - произвольные.
Первые два. алгоритма — PR0BEST и C0STAR- предназначены для приближенного решения ЗПМ с единичными весами. Для обоснования алгоритма. PR0BEST используются вероятностные оценки Еершин из Y - кадцидатов в наименьшее покрытие. Оценка его трудоемкости - 0(tti2 + mn) , где т = IYl ,n = |X| . Доказательство правомерности алгоритма COSTAR осногано на выявленных свойствах орграфа, полученного из исходного двудольного графа по предложенному рекуррентному правилу. Трудоемкость этого алгоритма, ограничена величиной (ДтлПУ+Т]), гдеї^сі _ множество кандидатов в наименьшее покрытие.
Третий алгоритм - SELEX ~ предназначен для точного решения ЗПМ с произвольными весами и позволяет сократить перебор с помощью порождения частных решений, в лексикографическом порядке. Доказаны корректность и конечность алгоритма. Оценка его трудоемкости не приводится, так как он относится к классу алгоритмов с неявным перебором. Указывается на возможность сокращения Бремени решения путем введения априорной погрешности в текущее решение,
В конце главы рассматривается программная реализация предложенных алгоритмов на языке АЛГОЛ-60 (ЭВМ М-222) и анализируются результаты численного эксперимента.
В четвертой главе продемонстрировано применение предложенных в предыдущих главах постановок задач и алгоритмов выбора структур к выбору архитектуры АПК: на основе моделей в виде .двудольного графа синтезирована спецификация интерфейса измерительного подкомплекса, обоснована необходимость децентрализации управления измерительными модулями. Предложена конкретная реализация децентрализованного принципа управления и интерфейса и рассмотрены связанные с нею особенности прикладного программного обеспечения АПК.
В пятой глале рассмотрены вопросы организации измерительного процесса в автоматизированном поверочном комплексе на примере АПК "Кедр-1":описаны принципы поверки цифровых вольтметров, измерительных усилителей и делителей; предложены быстродействующие алгоритмы прецизионного измерения напряжения и их реализация на языке QUAS1C для ЭВМ "Электрояика-60М".
Проектирование метрологического обеспечения АПК
Эта задача является специфической для измерительных комплексов, к которым относятся АПК, и заключается в определении необходимого состава метрологической аппаратуры для поверки АПК и в определении методик исследования метрологических характеристик АПК,
Реализация решения этой задачи может заключаться либо в создании некоего "надкомплекса" (не обязательно автоматизированного) для поверки поверочного комплекса, либо в организации режима самопроверки АПК при наличии встроенных образцовых средств. Второй путь представляется более перспективным, благодаря его экономичности Гі8,І9] . Основу этого пути создает факт наличия в комплексе ЭВМ, которая обеспечивает проведение коррекции погрешностей измерений, управление выработкой тестовых сигналов и т.д., и программоуправляемых образцовых мер.
Двудольные графы как язык описания задач проектирования структур
Пусть система в каком-либо конкретном своем проявлении описывается двумя конечными множествами: л и Y . Декартовым произведением множеств - X х Y - называется множество всех упорадоченных пар ( х , у ), где х Х , у є X .
Пример: пусть X - множество поверяемых параметров, Y - множество измерительных модулей. Отношение А существует между j и у тогда и только тогда, когда І -й модуль участвует в поверке j -го параметра.
Алгоритм решения ЗПМ с единичными весами PR0BEST
Любая задача принятия решений несет в себе элемент случайности. Поэтому вероятностные оценки могут адекватно отражать структуру такой задачи [90] . Представим себе, что надо выбрать из множества элементов - кандидатов в минимальное покрытие - те, которые действительно образуют минимальное покрытие. Как оценить вероятность вхождения того или иного элемента в минимальное покрывающее множество? Ответить на этот вопрос поможет следующее утверждение.
Теорема I. Пусть G(X,Y) - двудольный граф (1Х1=П, lY)sm) и II"Mi 11 - (m n) матрица отношений Т . Тогда наиболее вероятным кандидатом в наименьшее покрытие мощностиїявляется вершина у с минимальной оценкой R\ = S S" , вычисленной для каждой вершины из Y , при 1 [ р-].
Доказательство. Пусть - выбранные произ вольным образом покрывающие множества; Во - событие, состоящее в том, что выбранное множество Со мощности 1 о= I Col покрывает все элементы множества X ; В1 - аналогичное событие, но при t,BC, le. Очевидно, что 0о влечет событие Bj , то есть В0СВ1 . Вероятности таких событий связаны известным соотношением Г13] :
Обоснование необходимости децентрализации управления в АПК
Пусть с помощью предложенных во 2-ой и 3-ей главах методов или .директивно задана структура аппаратного обеспечения АПК, Для простоты, но без ограничения общности рассуждений, будем рассматривать структуру разработанного на кафедре радиотехники Томского политехнического института АПК "Кедр-1" С72, 86] :
а) измерительный под комплекс - генератор-калибратор программируемый ГП-3, делитель индуктивный программируемый ДШІ-2, усилитель высоковольтный УВ-7, указатель дифференциальный программируемый ДУ-ІЗ, коммутатор;
б) вычислительный подкомплекс - ЭВМ "Электроника-бОМ" со стандартной периферией (фотосчитьшатель FS -1501, электро фицировалная пишущая машинка "Консул-260.1", дисплей РИН-609).
Назначение комплекса - автоматизированная поверка, аттестация и исследование метрологических характеристик цифровых вольтметров, измерительных преобразователей и усилителей, делителем напряжения - на переменном токе. "Кедр-I" позволяет также осуществлять точные измерения переменных напряжений, нестабильности источников налряжений и т.д.
Все множество измерительных модулей и ОМИ можно разбить на два подмножества: источники и приемники информации (см.разд. 2.2.3), - которые можно описать двудольным графом G(X,Y), где X - множество источников информации, і - множество приемников информации, а ребро соответствует возможности обмена информацией между элементами Xj и Ці .
На рис.4.2., а приведен граф (X,Y) для случая централизованного управления, когда источником управляющих данных может быть только ЭВМ. Решим для этого rpa a задачу 15(9) "Определение наихудшего режима обмена информацией". Решение тривиально: наименьшим независимым доминирующим множеством ребер графа могут являться пары ребер "ЭВМ-ГП (или ИД, ДУ и т.д.)" и "ЭВМ - ДУ (или вычислительные модули, ОМИІ, 0МИ2)". Таким образом, централизованное управление имеет наихудший из возможных режим обмена, тал как в каждый момент времени разрешен обмен только между двумя модулями, одним из которых всегда является ЭВМ.
Автоматизированная поверка средств измерений
Не ограничивая общности рассуждений, будем рассматривать состав АПК "Кедр-Г (см.разд.4.2 и рис.4.4).
Схема соединения модулей измерительного полкомплекса для организации измерений с целью поверки цифровых вольтметров (ЦВ) приведена на рис.5.1. Схема и программа, поверки ЦВ соответствуют стандартной "Методике по Еерки цифровых вольтметров, аналого-цифровых преобразователей напряжения и комбинированных (универсальных) цифровых приборов постоянного и переменного тока" МИ 118-77. ЦВ поверяются методом измерения напряжения, воспроизводимого многозначной мерой (ГП-3 и ДИП-2). ЕП, хранящий приборные команды (Ж), соответствующие поверяемым точкам конкретного типа ЦВ, выдает их по тактовым импульсам ЭВМ на ГП-3, ДИП-2 и коммутатор К . ГП-3 выдает сигнал с частотой, соответствующей Ж, и уровнем 10В. ДИП-2 ослабляет этот сигнал в заданное приборной командой число раз. На вход ЦВ, таким образом, поступает сигнал заданного уровня и частоты. Усилитель УВ-7 служит для расширения динамического диапазона до 300 В. Измерительный под комплекс АПК "Кедр-Г позволяет поверять цифровые вольтметры в диапазоне напряжений 10 мкВ...ЗОО В и диапазоне частот 20 Гц...200 кГц с погрешностью до 0,03%.
Приборные команды из HI и результаты измерений из ЦВ через промежуточный интерфейс и адаптер поступает в ЭВМ, где вычисляется действительная погрешность ЦВ в заданной поверяемой точке. Полученное значение сравнивается с допускаемой погрешностью. . Коэффициенты двучленной формулы , выражающей предел относительной допускаемой основной погрешности поверяемого ЦВ, и их изменение в частотном и динамическом диапазонах перед началом поверки вводятся Е ЭВМ из Ш,
