автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Разработка методов анализа и управления в обобщенных сетевых моделях

ВВВДЕНЙЕ.

РАЗДЕЛ I. АЛГЕБРАИЧЕСКИЕ МЕТОДУКТУРНО

ФУНКЦИОНАЛЬНОГО АНАЛИЗА СЕТЕВЫХ МОДЕЛЕЙ

1.1. Алгебро-топологические характеристики сетевых моделей. Обще положения

1.2. Структура отношения.

1.3. Структурный анализ семейств отношений.

1.4. Динамика систем и управление

1.4.1. Динамика детерминированных систем.

1.4.2. Динамика и управление стохастических систем.

1.5. Й -полукольца и оптимизационные задачи в сетях.

1.5.1. Струкоурно-упорядоченнйге., полукольца.

1.6. Матрицы в Й -полукольцах.

В условиях развитого социализма наша страна достигла такого уровня развития экономики, когда особую актуальность приобретает дальнейшее улучшение управления народным хозяйством. "Задача состоит в том, чтобы поднять уровень планирования, привести их в соответствие с требованиями нынешнего этапа - этапа развитого социализма." [2].

Совершенствование планового руководства - сложная, многогранная проблема. В "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года" ХХУ1 съезд КПСС указал на необходимость: "осуществлять комплексный подход к планированию развития взаимосвязанных отраслей народного хозяйства и экономических районов страны" и "обеспечить в планировании правильное определение первоочередных задач, выбор наиболее эффективных путей достижения высоких народнохозяйственных результатов" III.

Совершенствование и внедрение АСУ в гражданской авиации призвано содействовать улучшению использования авиационного оборудования, повышению безопасности полетов, организации более эффективного взаимодействия различных служб ГА. В приказе Министра ГА & 75 от 5 мая 1977 года говорится: "Считать главным нацравлением работ по созданию АСУ в Гражданской авиации . автоматизацию планирования и управления транспортной деятельностью всех уровней на базе поэтапного развития информационно-вычислительной сети и повышения эффективности внедрения таких систем".

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

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

В.Н.^уркова, А.Н.Гарина, Д.И.Гсленко, С.И.Зуховицкого, В.И.Дудо-рина, А.М.Кривцова, Н.Б.Мироносецкого, Г.С.Поспелова, В.Е.Ха-зацкого, а также зарубежных исследователей Х.Ахьвджа, В.Коппера, Э.Майника, X.Мюллера, К.Неймана, А.Притскера, С.Элмаграби и многих других только сетевой язык дает возможность достаточной формализации процесса разработки и построения математической модели сложной системы. Это объясняется тем, что при управлении разработкой сложного проекта построение адекватной математической модели невозможно без представления его в виде сети, структура которой отображает как конструктивно-технологическое деление проекта, так и логическую схему сложного комплекса работ по его выполнению, определяет целесообразную последовательность выполнения отдельных этапов работ от начальных стадий выполнения проекта до его завершения, установления связи.работ внутри комплекса и взаимосвязи его с другими комплексами.

Практическое использование сетевых моделей началось в середине пятидесятых годов в США после разработки метода критического пути (СРМ) и метода анализа и оценки программ (PERT).

Начиная с первой половины шестидесятых годов в СССР действует система сетевого планирования и управления (СПУ), являющаяся дальнейшим развитием системы PERT. Применение сетевых моделей для управления конструктивно-технологическими разработками и подготовкой производства может на 25-30 % сократить сроки создания и запуска в производство новой техники, снизить затраты труда и материальных ресурсов. В частности, по данным Архангельского В.А., применение целевой системы управления на основе сетевых моделей при создании крупного межотраслевого комплекса для координации деятельности 150 организаций-исполнителей позволило сократить срок пуска объекта на 3 месяца по сравнению с планом, что дало экономию около I млн.рублей [7].

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

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

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

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

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

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

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

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

Впервые понятие стохастической сетевой модели комплекса операций упоминается в работах Эйснера [116] и Элмаграби 1118], где исследуется возможность использования сетевых моделей типа РШ для анализа проектов, в которых работы и события не носят фиксированного характера и содержат логические отношения весьма сложной природы, иначе говоря, сама структура сети становится стохастической.

Поспелов Г.С. и Баришполец В.А. развивают классификацию элементов чисто стохастической сетевой модели 1821. Для составления сетевых моделей со стохастической структурой ими предлагаются несколько типов событий с различными логическими возможностями. Этими авторами разработаны также процедуры анализа стохастической сетевой модели, которые позволяют получать вероятностные характеристики параметров процесса.

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

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

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

Целью настоящей работы является разработка методов и алгоритмов анализа и оптимального управления работами и ресурсами в обобщенных сетевых моделях.

Содержание диссертации отражено в четырех разделах, заключении по каждому разделу и основных результатах.

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

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

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

В разделе 1У рассматриваются воцросы практического применения разработанных методов и алгоритмов. Даются отдельные примеры описания проектов и определения ряда характеристик с помощью предложенных методов и алгоритмов.

По результатам диссертационной работы опубликовано 7 печатных работ.

Результаты работы внедрены в Московском институте инженеров гражданской авиации, производственном объединении "Электромеханика" и Главном техническом управлении.

Акт и справки о внедрении результатов диссертационной работы приведены в Приложении.

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

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

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

3. Разработанные элементы структурно-функционального анализа позволяют рассматривать сложную систему как целостное образование, а также выявлять степени связи и влияние ее отдельных подсистем.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В соответствии с Координационным планом работ по решению научно-технической проблемы 0.80.09, утвержденной Государственным Комитетом Совета Министров СССР по науке и технике (задание 05.02.03), а также приказом Министра ГА № 75 от 5 мая 1977 г. "О дальнейшей разработке, внедрении и совершенствовании АСУ в о м . сэ гражданской авиации" и в связи с созданием автоматизированной системы управления авторемонтными предприятиями (АСУ 4) и информационно-вычислительной сети (ИВС) ГА вопросы разработки адекватных моделей систем, методы их анализа и управления являются одной из важнейших проблем создания и совершенствования АСУ ГА. Актуальность данной проблемы побудила к разработке обобщенной сетевой модели, методов анализа и управления работами и ресурсами в сложных системах.

При решении указанной проблемы лично автором получены следующие наиболее важные результаты:

1. Предложено два подхода алгебраического анализа абстрактных сетевых моделей.

2. Разработан универсальный алгоритм решения различных оптимизационных задач на сетевых моделях.

3. Разработана обобщенная сетевая модель, позволяющая адекватно описывать реальные процессы.

4. Разработан аналитический метод анализа обобщенной сетевой модели.

5. Разработаны методы и алгоритмы преобразования сети к виду, удобному для анализа.

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

7. Разработаны методы оптимизации общих затрат на управление цроектом с использованием метода градиента.

Основные положения диссертационной работы и ее результаты докладывались и обсуждались:

- на Всесоюзной научно-технической конференции "Совершенствование системы управления эффективностью производства в гражданской авиации с применением. АСУ и вычислительной техники" (Москва, МИИГА, март 1981 г.);

- на научно-технической конференции "Эффективность и оптимизация систем и процессов в гражданской авиации" (Москва, МИИГА, февраль 1982 г.);

- на Всесоюзной научно-технической конференции "Проектирование и эксплуатация информационно-вычислительных комплексов" (г.Пенза, ЦЦНТП, сентябрь 1983 г.).

Результаты исследований позволяют сделать следующие выводы:

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

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

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

4. На основании предложенной ОСМ-затрат многокритериальная задача оптимизации сводится к однокритериальной, что позволяет свести задачу оптимизации к задаче управления и решать ее с помощью известного метода градиента.

Результаты настоящей диссертационной работы внедрены:

- в работах, проводимых МИИГА, по созданию автоматизированной системы обучения техническим и программным средствам АСУ (по заданию МГА);

- в производственном объединении "Электромеханика" при решении задач оперативного уцравления производством с экономическим эффектом 24 тыс.руб. в год;

- в Главном техническом управлении при выполнении ОКР "Разработка и внедрение автоматизированной системы оперативного контроля научно-исследовательских и опытно-конструкторских работ отрасли".

ЗАКЛЮЧЕНИЕ

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

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

1. КПСС. Съезд 26-й, Москва, 1981. Материалы ХХУ1 съезда КПСС. - М.: Политиздат, 1981. - 233с.

2. Постановление ЦК КПСС и Совета Шнистров СССР от 12 июля 1979 года. М.: Политиздат, 1979, с. 7.

3. Абрамов С.А. Математические построения и программирование. -М.: Наука, 1979. 192с.

4. Адельсон-Вельский Г.М. О некоторых вопросах сетевого планирования. В кн.: Исследования по дискретной математике. -М.: Наука, 1973, с. 105-134.

5. Андреев В.А., Пепкин Г.П. Автоматизирование системы управления предприятием. М.: Финансы и статистика, 1981. - 248с.

6. Аоки М. Введение в методы оптимизации. М.: Наука, 1972. -343с.

7. Архангельский В.Н. Вопросы комплексного управления научными исследованиями. В кн.: Планирование, управление и оценка эффективности научных исследований и разработок. - М.: ЦЭМИ, 1972.

8. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536с.

9. Ахыэджа X. Сетевые методы управления в проектировании и производстве. М.: Мир, 1979. - 638с.

10. Багриновский К.А., Бусыгин В.П. Математика плановых решений.-М.: Наука, 1980. 224с.

11. Берж К. Теория графов и ее применение. М.: Иностранная литература, 1962.

12. Еигель Дж. Управление производством. Количественный подход.-М.: Мир, 1973. 304с.

13. Болтянский В.Г., Ефремович В.А. Начальная топология. -М.: Наука, 1982. 160с.

14. Брегман В.И. Графы в задачах управления производством. -М.: Статистика, 1974. 144с.

15. Брехов A.M. Автоматизированная система управления производством судостроительных предприятий. I.: Судостроение,1978. 28Ос.

16. Е!уйко В.П. и др. Автоматизированная система управления ремонтным производством (система "Резерв"). М.: Экономика, 1970. - 127с.

17. Дурков В.Н., Кондратьев В.В. Механизмы функционирования организационных систем. М.: Наука, 1981. - 384с.

18. Бурков В.Н., Ланда Б.Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления. М.: Советское радио, 1967.

19. Вайнберг М.М. Функциональный анализ. М.: Просвещение,1979. 128с.

20. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980. - 208с.

21. Вентцель E.G., Овчаров Л.А. Прикладные задачи теории вероятностей. М.: Радио и связь, 1983. - 416с.

22. Владимиров B.C. Уравнения математической физики. М.: Наука, 1981. - 512с.

23. Буш Г. Теория систем. М.: Советское радио, 1980. - 288с.

24. Гарин А.Н. Модели текущего планирования производства. -М.: Статистика, 1978. 85с.

25. Гафт M.Г. Принятие решений при многих критериях. М.: Знание, 1979. - 64с.

26. Гнеденко Б.В., Хинчин А.Я. Элементарное.введение в теорию вероятностей. М.: Наука, 1982. - 160с.

27. Голенко Д.И. Статистические методы сетевого планирования и управления. М. : Наука, 1968. - 400с.

28. Голубков Е.П. Использование системного анализа в принятии плановых решений. М.: Экономика, 1982. - 160с.

29. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. - 366с.

30. Дудорин В.И. Моделирование в задачах управления производством. М.: Статистика, 1980. - 231с.32. «Пудорин В.И., Лыкова I.H., Сиротин A.B. Моделирование структур АСУ на ЭВМ. М.: Финансы и статистика, 1982. -168с.

31. Захаров В.К., Севастьянов Б.А., Чистяков В.П. Теория вероят-г ностей. М.: Наука, 1983. - 160с.

32. Захаров В.Н., Поспелов Д.А., Хазацкий В.Е. Системы управления. М.: Энергия, 1977. - 423с.

33. Зимин И.Н., Иванилов Ю.И. Решение задач сетевого планирования сведением их к задачам оптимального управления. Журнал вычислительной математики и математической физики, 1971,т. II, № 3, с. 633-641.

34. Зимин И.Н. Алгоритмы расчета сетей при переменных интенсив-ностях выполнения ограничений. Изв.АН СССР, техническая кибернетика, 1973, J6 6, с. 17-23.

35. Луховицкий С.И., Радчик И.А. Математические методы сетевого планирования. М.: Наука, 1965. - 296с.

36. Истюнин C.B. Математическое обеспечение информационно-вычислительной сети гражданской. авиации (МО ИВС ГА). Пенза: ПМТЦНТИиП, 1982, $ 28-82, 4 с.

37. Истюнин C.B. Система межмашинной интерактивной связи. -Пенза: ПМЩНШиП, 1982, № 294-82, 4 с.

38. Истюнин C.B. Представление производственных систем методом структурного синтеза. В кн.: Информационно-вычислительные сети гражданской авиации. - М.: МИИГА, 1982, с. 84-90.

39. Истюнин C.B. Супервизор канала связи информационно-вычислительной сети гразданской авиации (ИВС ГА). Пенза: ПМТЦНТИиП, 1982, J* 257-82, 2 с.

40. Калман Р., Фалб П., Арбиб М. Очерки по математической теории систем. М. : Мир, 1971. - 400с.

41. Кальфа В., Овчинников В.В., Рякин О.М. и др. Основы автоматизации управления производственными процессами. М.: Советское радио, 1980. - 360с.

42. Касти Дж. Большие системы. Связность, сложность, катастрофы. М. : Мир, 1982. - 216с.

43. Клейн Дж. Статистические методы в имитационном моделировании. В 2-х вып. - М.: Статистика, 1978, вып.1. - 221с. Вып.2. - 335с.

44. Колмогоров А.Н., Журбенко И.Г., Прохоров A.B. Введение в теорию вероятностей. М.: Наука, 1982. - 160е.

45. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1976. - 544с.49,50,51