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

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

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

Решение вопросов синтеза и анализа структур сложных систем нажло отражение в работах кал отечественных: В. А. Горбатов, С. В. Жак, В. И. Нечипоренко, А. И. Половинкин, А. Д. Цвиркун, Д. Б. Юдин и да., — так и зарубежных ученых: Л. Берталанфи, Дж. Касти, М. Месарович, М. Пешель, Я. Такахара, Ф. Харари, Р. Г. Эткин и да. Проблемы синтеза информационных измерительных систем (ИИС) и измерительно-вычислительных комплексов (ИВК) изучались советскими исследователями: Г. И.КавалероЕым, С. М. Мандельштамом, Г. С. Певзнером, Э. И. Цветковым и да. Однако решение указанной задачи ещё далеко от завершения.

Постановки задач проектирования структур, предлагаемые различными авторами, в основном, кал правило, могут быть сформулированы в виде задач целочисленного программирования [ 1,6,30,48,60,85,91]. Но получившая развитие в последнее десятилетие теория NP — полноты [22] оставляет слишком мало надежд на принципиальную возможность существования алгоритмов решения этих задач за приемлемое (полиномиальное) Еремя при достаточно большой их размерности (число переменных больше 10). Поэтому в [91] указывается на актуальность классификации конкретных задач проектирования и разработки частных методов решения специальных классов дискретных задач, специфика которых позволяет получить приемлемые по трудоемкости точные или приближенные алгоритмы.

Следствием сложности проблемы Еыбора структуры является не только признание достаточности приближенных результатов решения, но и большое разнообразие подходов к ней. Подход, предлагаемый е настоящей работе, базируется на опыте, накопленном в области теории выбора структур, и наиболее близок к работам В. А. Горбатова [16], С.В.ЗгСака [30] и Дж. Касти [38] .

Актуальность проблемы подтверждается тем, что она включена в тематику рабочей группы «Математические методы САПР» секции по общесистемным вопросам «Программы САПР» Минвуза РСФСР, а работы по созданию автоматизированного поверочного комплекса выполнены в соответствии с планом государственной стандартизации Госстандарта на 1980;1985 гг. по проблеме «Создание государственных и рабочих эталонов» (код задания 8.3.2.08.12).

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

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

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

2. Разработка и анализ математической модели задачи выбора структуры АПК, постановка частных задач выбора структуры е терминах: разработанной модели, анализ существующих алгоритмов решения этих задач, разработка и исследование новых алгоритмов.

3. Реализация на ЭВМ и экспериментальные исследования разработанных алгоритмов решения частных задач Еыбора структуры.

4. Выбор архитектуры АПК на базе предложенной модели и разработанных алгоритмов, реализация и проверка выбранной архитектуры в условиях эксплуатации АПК.

5. Повышение эффективности применения микро-ЭВМ в АПК путем разработки алгоритмов прецизионных измерений физических величин.

В результате решения перечисленных задач получены следующие новые результаты;

1. Для решения частных задэ. ч выбора структуры АПК предложена математическая модель в Еиде двудольного графа, которая позволяет ставить и решать частные задачи в терминах покрывающих, доминирующих и независимых множеств двудольного графа, причем, доя многих из этих задач существуют полиномиальные алгоритмы.

2. На основе предложенной модели сформулировано 15 частных формализуемых задач, входящих в последовательность синтеза структуры АПК, и указаны пути их решения.

3. Предложен общий алгоритм выбора структуры и архитектуры АПК.

4. Теоретически обоснованы, разработаны, реализованы на ЭВМ и проанализированы два экономных эвристических алгоритма решения задачи о покрытии множествами с единичными весами, один из которых основан на вероятностных оценках элементов-кандидатов в наименьшее покрытие, .другой — существенно использует свойства орграфа, построенного из исходного двудольного графа по определенному правилу.

5. Теоретически обоснован, разработан, реализован на ЭВМ и проанализирован точный алгоритм решения задачи о покрытии множествами с произвольными весами. Алгоритм основан на приндипе лексикографического упорядочения и позволяет находить кал точное, так и приближенное (за более короткое время) решение задачи.

6. На основании предложенных модели и алгоритмов выбора структуры решены вопросы выбора архитектуры АПК: обоснована необходимость децентрализации управления в АПК и сформулированы рекомендации по выбору спецификации интерфейса измерительного подкомплекса.

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

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

Диссертационная работа состоит из пяти глав.

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

Во второй глазе для решения частных задач выбора структуры АПК предложена математическая модель в виде двудольного графа, где X и Y — конечные множества элементов, являющихся исходными .для частной задачи, Е — множество ребер, отображающее бинарное отношение ДсХхУ Сформирован список из девяти задач о покрывающих, доминирующих и независимых множествах в двудольном графе, в который вошли следующие задачи: I. Минимальное покрытие множествами- 2. Минимальное вершинное покрытие- 3. Минимальное реберное покрытие- 4, Максимальное независимое множество вершин;

5. Максимальное независимое множество ребер (паросочетание);

6. Минимальное доминирующее множество вершин- 7. Минимальное доминирующее множество ребер- 8. Минимальное независимое доминирующее множество вершин- 9. Минимальное независимое доминирующее множество ребер. По признаку существования для указанных задач полиномиальных алгоритмов решения каждая задача отнесена к одной из двух груш. В I группу вышли задачи 2−5, для которых существуют полиномиальные алгоритмы (если гра$ двудольный), ео П группу включены задачи I, 6−9, которые таких алгоритмов не имеют, и, По-Евдимому, иметь не могут (в соответствии с теорией NP — полноты).

Рассмотрены взаимосвязи между задачами в каждой группе и между двумя группами. Указало, что для решения задач I группы универсальным является метод паросочетаний [22,43], а .для П группы и задач всего списка общим методом является метод решения задачи о покрытии множествами (ЗИМ). Далее в этой главе формируются 15 частных задач структурного синтеза АПК в терминах покрывающих, доминирующих и независимых множеств и предлагается общий алгоритм проектирования структуры АПК, Еключающий в себя решение этих задач.

В третьей главе в связи с тем, что для П группы задач возможность существования полиномиального алгоритма весьма призрачна, предлагаются алгоритмы приближенного решения ЗПМ. Эта задача состоит в нахождении покрытия Есех элементов из множества X двудольного графа G (X, Y) или наименьшим числом элементов из множества Y, если веса элементов из Y равны Iили элементами из Y с наименьшим суммарным весом, если их веса — произвольные.

ПерЕые два алгоритмаPR0BEST и C0STARпредназначены для приближенного решения ЗПМ с единичными весами. Для обоснования алгоритма PR0BEST используются вероятностные оценки Еершин из Y — кандидатов в наименьшее покрытие. Оценка его трудоемкости — 0(m2 + mn), где tn = IYI .n-IXI. Доказательство правомерности алгоритма COSTAR основано на выявленных свойствах орграфа, полученного из исходного.

1Z двудольного графа по предложенному рекуррентному правилу.

Трудоемкость этого алгоритма ограничена величиной гдеУ^сУ множество кандидатов в наименьшее покрытие.

Третий алгоритм — SELEX — предназначен для точного решения ЗПМ с произвольными весами и позволяет сократить перебор с помощью порождения частных решений, в лексикографическом порядке. Доказаны корректность и конечность алгоритма. Оценка его трудоемкости не приводится, так как он относится к классу алгоритмов с неявным перебором. Указывается на возможность сокращения времени решения путем введения априорной погрешности? в текущее решение,.

В конце главы рассматривается программная реализация предложенных алгоритмов на языке АЛГ0Л-60 (ЭВМ М-222) и анализируются результаты численного эксперимента.

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

В пятой глаЕе рассмотрены вопросы организации измерительного процесса в автоматизированном поверочном комплексе на примере АПК «Кедр-1» :описаны принципы поверки цифровых вольтметров, измерительных усилителей и делителейпредложены быстродействующие алгоритмы прецизионного измерения напряжения и их реализация на языке США$ 1Сдля ЭВМ «Электрояика-бОМ» .

Основные результаты и выводы диссертационной работы заключаются е следующем:

1. На. осноЕе анализа существующих методов решения задачи выбора структур сложных систем выявлены поддающиеся полной или частичной формализации частные задачи Еыбора. структуры АПК.

2. Для решения частных задач Еыбора. структуры АПК предложена. математическая модель в виде двудольного графа, позволяющая ставить и решать частные задачи в терминах покрывающих, доминирующих и независимых множеств двудольного графа, причем, для многих из этих задач существуют полиномиальные алгоритмы. Предложенная модель способствует решению Есех сформулированных е работе частных задач Еыбора. структуры АПК.

3. Предложен общий алгоритм выбора, структуры и архитектуры АПК, включающий в себя 15 формализуемых задач, поставленных е терминах предложенной модели. Указаны пути решения этих задач.

4. Теоретически обосновали, разработаны, реализованы на ЭВМ и проанализированы два экономных эвристических алгоритма решения задачи о покрытии множествами (ЗПМ) с единичными весами. Один из них основан на. Еероятностных оценках элементовкандидатов в наименьшее покрытие и тлеет квадратичную оценку трудоемкости решения. Другой — использует выявленные свойства орграфа, построенного из исходного двудольного графа по предложенному рекуррентному правилу. Оценка трудоемкости этого алгоритма е среднем меньше, чем квадратичная.

5. Теоретически обоснован, разработан, реализован на. ЭВМ и проанализирован точный алгоритм решения ЗПМ с произвольными весами. Алгоритм основан на принципе лексикографического упорядочения и позволяет находить как точное, тал и приближенное за более короткое время, решение задачи путем введения априорной погрешности в частичное решение.

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

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

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

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

ЗАКЛЮЧЕНИЕ

.