автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Основы комбинаторной теории многоуровневой декомпозиции и её приложения в территориальной АСУ

Томские ордене Октябрьской Революции и ордена Трудового Красного Знамена политехнический институт им. С.М.Кирова

На правах рукописи

Кацмая Валерий Евельевич

основа КОМБИНАТОРНОЙ ТЕОРИИ МНОГОУРОВНЕВОЙ ДЕКОМПОЗИЦИИ И ЕЕ ПРИЛОЖЕНИЯ В ТЕРРИТОРИАЛЬНОЙ АСУ

Специальности 05.13.01 - Управление в технических системах

05.13.06 - Автоматизированные системы управления

Автореферат диссертации на соискание ученой степени докторе технических явук

ТОМСК - 1991

Работа выполнена ь Оренбургском политехническом институте.

Официальные оппоненты: д.т.н..профессор Буймов А.Г.

д.в.н..профессор'Пирмухамедов А.Н. д.т.н..профессор Тарасенко Ф.П.

Ведущая организация: Научно-иоследовательски! институт

информационных технологий (Г.Москва)

Защита состоится " " /Мсец 1991 г. в 15 часов на заседа специализированного совета Д 063.80.03 по ваците диссертаций на со квнив ученой степени доктора технических наук при Томском политехи чэском институте.

634004, Томск, пр.Ленина, 30, политехнический институт.

С диссертацией можно ознакомиться в библиотека Томского полит нического института (634004,Томск, ул.Белинского,б4). "

Автореферат разослан " 2 УлирбАй 1991 г.

' ' -Ч /! '

Ученый'секретарь • _ ¿у с/уН/с*''•' Чудинов И.Л. .

специализированного совета ^и

ОБЩАЯ ХАРАОТЕРИСТЩЦ РАБОТЫ

АКТУАЛЬНОСТЬ ПРОБЛЕЩ. Процесс парэстройка в сфере управления экономикой неразрывно связен с широким внедрением современной вычислительной тваншш (ВТ),экономшсо-математическнх методов (ЭММ) и автоматизированных систем управления (АСУ) различных уровней.Государственная программа повышения эффективности ВТ и АСУ предусматривает, в частности, ссздвшэ в развитие территориальных АСУ(ТАСУ) автономных республик, краев а областей.

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

Ос ^бвнно слезными, но в то же время наиболее эффективными задачами ТАСУ являются оптимивациг-й^э задаче территориального планирования в управления. Дня решения этих задач,имеидщ высокую размерность, за средвих в больший; ЭВМ итользуптся модвлй в метода математического арограширования (линейные в целочисленные) в ашарат теории графов.

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

Да композит- "онныи методам решения сливных задач посвящено большое шшо исследований. Основное внимание в этих работах уделяется декон-воввшговннм методам в алгоритмам решения частных задач. Сами хе процедуры разбиения множества параметров модели исходной задачи, на шд--зоданожества параметров моделей подзадач не исследованы. Кроме того, ' в большинстве работ рассматривается лишь двухуровневая^декомпозиция задач.иощая теория многоуровневых разбиений множества параметров задачи в процессе декомпозиции отсутствует,хотя при решении все более ус-пожшшцпхся задач планирования в управления требуется проведение указанных многоуровневых разбиений. Выбор варианта декомпозиции задачи ■ известными методами осуществляется за основе интуиции разработчиков зистемн, что приводит к недопустимо большой погрешности решения.

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

zz ii ccc-zzzzzz^z ЕС—Л^^П, rr.z2z~zrp

ks2 спггез саллч езсог.о2 рзз^рцззш.

líacizzzzzzzz cpotoaa рсеалиаъ в ps^Cü^z z-ijszxzzzzrizсг:з£ FÍ--CJ И"-Т 0.£0.С2,агдспзз И.05.ПЕЗ ЛСос^гь п E33CS2 С пзрзуз счзрсгь 1CJ ОргнЗургскоС ^зтз рсЗзщ !

пслплл-зь Ез Гссда?згпэы:з::у EEazj сзсг^лплзлзго п сс;;1;;лгзгз рл; Е=5Е2 FC-:G? £19 Г. E3Sr¡:££0SS3Z£3 C333I2 i^33tp33 ГС13? ¡

23 сзллрл IS23 г. £230) п Госудь-.стес^вд Е- ск^Г-'з ссдсп

ирсгрзса{¡Г^зг^лзз'х 3 г. еззтезэз^ссзз Ссигз Г;-.т;згрзз с; 2 с::тлбпл IS37 г. - 410}.

1СЛЬ FiECHi. есзголцзГ; рзСога ллллзтсл czz;,zz:z

не;: тзорил лз- i:l;: ссл.ли i

c^rc, ¡^срлт^хЗс::гго п Ерагргзг—ого слпг.гзга p—-.—i с: дзч тэррзторзз^гзго п упра&юглз» :

урсолалниз: EZJ, рзз?£.Лоп:а ез croa оспозз сэдззсгг;; 2¿CST какого с; кзлзхлш и EZ цр^знззгз.

Ллд ГчОсппс^лл уу-зззгллй цолл в слзезртлцлз СЕ^ачз:

- рззрзбэтшз с гзтемлглчзелеэ оСзслозлплз с:^; :: хгроцзос? ьгегоурез^ззго сгргггроззлгя плрл::зтрзз егдзч рс

- рззрзЛстиз ZZ:.Z:zzozziz:Z^ZJZ. uozizzZ и нэто^зз сзхг^з: цлолип ездгч па езглх с грз£зз п спзцпсльах аадзч hzízZzztq npci-pc глроЕаая из озпзлз грзцздф ь^эгоурагЕзвого ьгрзпфоз^гия;

- рзорзЗзтз 01£1:э1-з21дпас:зас праацзиз срос-кифЗЕлнлл л алгерл изо ^уесцлз^з^зззл^л коьэго х'ласса дпеплзоз с лслользсззнлсы ¡.глэгзур елового код^резлзгл слсязпх гре^зчзезп: езьегтоз;

- ьзтоцзкздзеззззоа хгроолтироЕазхо и.црс^гцчзсгля рЗЗСЗЗЗчЛД Е ' 0233 ПЭБУ пол зле те:.: ТЛСУ, содзрла^пх задаст шсокаЗ рззизрлэсхл.

Тызлл сЗрззси.в слссорт&цлп развзноэтея иэзаэ езтчпзз недрззхзз - коиЗшхпторнзл тсорзл шагоурОЕлэЕаП дзко.'позлщл: и козлздхтсл ез-прзздапля прл::гл7ос::зго использования цродлогзпзей тсорзл длл рззазг exorna опдлч террзтераздъпзго плзнзрозгшия и упрзвлзЕзл.

1ЕТ0Лз КОСЛЗаЗЕЛГЛ. В качзствз иатеыатнчзасого г.ттппраха в рз2э исаользована ксиЗзнзтйрас:, тзэрли кзогзегз н 530|пл розэто^.

Дз::сьлюзлцпзнзыэ kzzszz зэдзч тэррзторлвльнзго шшнзреззз^я и ¿иравл езл разрзботззз: m сз^озз теорх! грзСоз е 1:зхг::з,г~ч2С1гого црогрз^зф

БЗЗ^Я.

НАУЧИМ НСЕИЗНД в:лтолношш: исследований заключается п слэдугн

!дзм.

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

2. Разработана теория схом разбиения, пклггаающая ire определения л свойства. Рассмотрены спэцаальниэ классы схем разбиения. Для оценки числа схем разбиения, соотвотствуЕзого числу вариантов мисго-урошэЕоЯ декомпозиции задачи, ввздэпо повоо комбинаторное число К, яаг тг,зеся обоецэниеп числа С-пфлппга S и числа Белла В. Разработаны мэтодц п алгоритмы генерирования и сиптоза его:« разбизиия.

3. Проведаны оценки вычислительной слогзтостя и погрешности резания задач мзтодом гаогоуровневоЗ дскстлозяцпд. Сформулированы условия допустимости полу эемого рзеонпя и пппелптельней гф1эктпЕности его

д0стп2эшм.

4. Разработана мотоладса ююгоуровнзвоЗ доксстозпцна задач на сетях п графах. Конструктивно доказана взаимно однозначная связь кзеду схемами разбиения множеств верни п ребор графа. Построена матеиатп-чзскр" по; ~лъ формирования оптимальной cxeioi разбнзкпи мпоггэства верен!. Прздаогзтш три мзтода рэсонпя поставленной задачи.

5. Разработали дзкс'зюзг^.сшгю методы рзгзппя задач ТЛСУ боль-сой размерности, сеодщгеся к задачам Еоиивоягзра, построения 1грат-чамого остова г~"гфэ, расчета параметров сетевых графиков. Сформировали теорэтгтгеекп обосновашяю условия оптимальности и 8ф5зктшяюстл рзпзппа этих задач, получаемчх . .¿ко;яозкцкопвест мэтодва.

G. Прэдлоззш декемпозиционкао м.одоял и гсэтосх рэаэнзл ряда задач территориального планкрованимя .1 управления, сводетися к спзциальсмч задачам линейного прогр&':мпровэтткя высокой размерпостп: поставок кост-пых строительных материалов,закупок сельскохозяйственной продукции, развития гмлшцно-коммупального хозяйства и "иллпзюго строительства, перераспределения ресурсов.

7. Разработаны декомпозлцзонныо методы синтеза слокпнх графических объектов, вклвчапци- схемотехнические принципы и алгоритмы функционирования пового класса дисплеев,' заяптщчшшо 15 авторским свидэ-тол! "твамл на изобретения.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. Результат работа в цело« язллг/гсд теоретической основой автоматизированного проектирования программного обеспечения для решения декомпозиционными метода?« задач высокой

мерности. Разработана библиотека типовых программных средств, ша щья 5 пакетов прикладных программ (ГОШ), предназначенных для быи реализации на ЭВМ декомпозиционных методов:

1)базошй комплекс декомпозиции задач;

2)инструментальную систему перевода программ на персональные

3)систему формирования полутоновых изображения на экране дис

4)пакет прикладных программ решения задач линейного прогршг. на база микроэвм;

Б)пакьт прикладных программ для решения задач на сетях и грг

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

- в САПР вычислительных устройств (декомпозиционные модели t тоды решения задач на графах);

- в АСУП (оптимизация производственной программы прадприятш система сетевого планирования и управления производством);

- в человеко-машинных системах различного назначения (форми] вание сложных графических объектов);

- в приложениях теории вероятностей, статистики и комбинато] (обобщения чисел Стирлинга и Белла, алгоритмы генерирования схем биения множеств).

РЕАЛИЗАЦИЯ РАБОТЫ. IIa основе предложенного декомпозиционной хода в составе АСУ хозяйством Оренбургской области решены следуй задачи:

- оптимизированы схемы перевозок местных строительных матер:

- оптимизирована программа жилищного строительства;

- разработан оптимальный план государственных закупок сельс! зяйственной продукции по районам области;

- внедрены автоматизированные системы обмена ресурсами ropoj (жилыми помещениями, местами в дошкольных учреждениях);

- внедрена автоматизированная система сетевого планирования управления производством в/ч I38I4;

- введены диалоговые режимы с формированием сложных графычес объектов в система обработки плановой информации ГлавПЭУ OpeHöypi облисполкома и автоматизированной системе учета и анализа Оренбу| го троллейбусного управления.

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

на порлдоз;, что позволяло рзолпзовать их на персональных зш.. Фактическая годоеой окопог-пгческпа Еф$экт от внэдрвния разработок в состав? пэрзоЗ очерэдя АСУ ховяЗотвом Орэпбургской области составил более I млп. рублой. Некоторые подсистемы, вклачакщяэ перечисленные задачи, . передали з Вряпскув, Псковскую к Читинскую области.

'Гссрзттгеэсюгз материалы диссертации и пакеты прикладных нрогрянм иссольооваки в учобнсп процессе Оренбургского политехнического плот1 тута d лзкцпопных курсах л практических занятая!.

ЛПГСЗЖ'Л РАБОТЫ. Сыновние полозэшш ц результате днссзртсш-.п -nrriT'wrjo^ и обсуздакясь па слэдукста itoi?ioponnwnx и сомшйрах: г: Г";сс:'г:::с:\ ссг.знс.'пл "ПроЗл::"? -лсгапцг.зшюго сбора,передачи з ели-,zc" их а sirlop'sivioh^az систзмаг (Кпов,БГОРЭС т2?.Л.О.Поповп, 1077); 1,0 п IV rccco2;:.4JZ ксп^эрэкцглЕ. •'Управлзшш большзд городок (.Чсгаз, ¡ШО АСУ "I'оз^-а", IC3I,IP25, 23); D Госнублпкшсхом совоцзшм "Иробле'-'а создзнгч •"АСУ-Росска"(Носхса.Гссплаи PC"CP,I£S3); ЗсосокмьЯ кск'эрзышя "Соиэрзопствовштэ с-таппзощюшшх структур и методов управляли п1лппао-ко1.?лупальшд .».озяЛотес:! и ситовым обслугзшапиом насе-лзипл з условиях йгккцво»„.ровшшя АСУ-ЯСС и АСУ-БЫТ(Уфа,НТО коммунального хозяйства и батоБог». обслуппвшпя, IS84); Всесоюзном сегагарэ "Пр:г,;с;го:г'з СЕМ для аптсмптпзпровзпного учета и обработки отчетности п ггададо-кк51упольпоп хозйстпэ и бытовом обслуживании(Красноярск,НТО капупальпого хозяйства и битного 03сяуг21вмп1я,1585); Всесоюзной коя-фзрзяцп:: "Проблем п метода ускорения научно-технического прогресса но ос ого ирпмзпонпя гачиг стольной гехншси п автоматизированных систем (!йс:сез,ЕШП310У,хС05); III Всероссийском семинаре "Разработка и внедрение прогрг-i'за средств для автоматизированных систем управления (Нос-1 юза.ШГО АСУ "Москва",1936); совместном заседании Советского национал! .ого комитета мэпдунаро'шой ассоциация по математическому п jташнзпоглу моделированию п Центрально-Поволжской территориальной группы Сово"з;сого национального ко^тета по участив в деятельности международной jccomiauan по математическому п машинному моделирования (Ку2б!сзв,1083); 17 Всесосзном семинаре "Разрабо~<а и применение программных средств SEM в учебном процессе" (Симферополь,КПИ АН СССР, 1983); I Всесоюзной конференции "Практическое применение современных технологий рограммирования,пакетов прикладных программ в вычислительных системах и сетях ЗВМи(Днепроп8трозск,Нгашри0ор,1,Э83); Всесоюзной конференции "Проблемы создания 'автоматизированных рабочих мест и уч-рэадончеаснх сет Л в'городском озяЯстве" (Москва, ШО АСУ "Москва", . 1988).

За разработку ютодов рзкзяия слонах задач первой очврэда .АС.: хозяйством Оренбургской области автор награздон серебряной иедальы ИЩИ СССР.

ПУБЛИКАЦИИ. По тема дассортащш опубликованы ЕО научных труде: в той числа з монографии и 16 авторыщх свидетельств па изобретена ОСНОВНЫЕ ПОЛСШШШ ДИССЕРТАЦИИ,ЕШЮСИШЕ НА [ЗАЩИТУ:

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

- теория схем разбиения (многоуровневых разбиений) шшетва параметров задач высокой размерности;

- методы оценки вычислительной сложности п погрешности шюго-уровневой дзкомпозиции;

- модели и штодц построения схем разбиения шозэств Бэрпзш и рэбер графа}

- декомпозиционные ыодалп п метода рзшошя задач высокой размерности на сетях и графах;

- декомпозиционные ыодэлн и штода ранения ряда задач герратс реального планирования и управления высокой размерности;

- декомпозиционные ыотоды форгларовшгая слоаных гргфшеклх объектов.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, шв разделов и заключения, излогвнных на 250 страницах, списка литера! из 230 наименований, содержит 41 рисунок, 12 таблиц и 7 црилогзрй

СОДЕШНИЕ РАБОТЫ

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

В первая разделе проводон анализ проблем территориального ущ ления, определены структура и функции территориальной АСУ в совре; них условиях. В состав ТАОУ, как показано на примере АСУ хозяйств! Оренбургской области, долины входить порядка двадцати порвоочарвд межотраслевых, отраслевых и территориальных систем. Из всего ынов ва задач, составляющих указанные подсистемы, в данной работе расс риваются наиболее сложные оптимизационные задачи, а именно задачи представленные моделями математического программирования, а также долями ва сетях и графах.

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

Проведенный анализ показал, что многие задачи ТАСУ, представленные в виде общих и специальных моделей линейного программирования(ЛП), содержат большое число переменных,что не позволяет решать их известными методами на средних,м^лых и персональных ЭВМ. К таким сложным задачам, требующим больших вычислительных ресурсов ЭВМ. относятся задачи планирования развития различных отраслей хозяйства области по всем ее административно-территориальном единицам (ATE) - городам и районам.

Как показано в диссертационной работе» каждая задача рассматриваемого класса может быть решена декомпозиционным методом путем сведения к последовательнсчтьи более простых подзадач. На первом уровне декомпозиции решается координирующая подзадача ЛП. В результате находятся значения агрегированных перемь^яых, задающих оптимальное распределение ресурсов между АТВ облас.л. На втором уровне решаются локальные подзадачи ЛП для определения £..;ачений исходных переменных, соответствующих каждой ATE,

На основе анализа соотава подсистем ТАСУ выявлен класс оптимизационных задач, направленных н° рациональное использование трудовых, -финансовых, материальных я других видов ресурсов, которые формализуйся как модели на графах вида G=«<V,E>. В задачах рассматриваемого класса множества 7 в Б вершин и ребер имеют высокую размерность, поэтому реализация большинства методов решения этих задач на ЭВМ огра- . ниченной производительности практически невозможна.

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

Таким образом, задачи ТАСУ рассматриваемого класса о точки зрения применения декомпозиционного подхода можно исследовать в зависимости от метода представления множества входных параметров. Каждое из множеств вход их параметров может содержать элементы определенной математической категории.

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

тва I на й блоков, удовлетворявши условиям: ь

U Х.=Х, Х.ПХ.=0 для Hi<J&. 1=1 ' * J

Декомпозиция задач на сетях и графах осуществляется путем пс 01шя разбиения fí=f7J,...,y ) множества вершин V или разбиения S i. ства ребер Е исходного графа, где S=fE}.....Е^).

При организации диалогового ропыа работы пользователя поде»: ТАОУ с ЭШ вашое аначениэ шаот отображение на экране дисплея дс точно большого объЭма графической информации. Однако, известные i леи ГОШ не были способны к формировании сложных полутоновых изо. брагоний. Предложенный декомпозиционный подход, защищенный авторе свидетельствами на пзобретенпя.основан на том, что для ьаюсоства . Г изображения строится разбиение R={T1t...,Tb) на блохи, соотвзте пдю некоторые базпснш.1 олсмонтсм.

Сложное пзобрагепао, закодированное в задшюа базиса, тробу значительно иэнызаго сбъОиа оперативной ы ehsühsü памяти но срава с' исходным представлением.

В процессе развитая задач ТАСУ в ш ыыештнчогащй задали тр втея добавлять всо Солхеоо число параметров. Рад указавших задач сокой раз?4орЕоотп нзвоглядо рс-злть па совроглошшх П2Ш дги.з црд пользовании двухуровневой схеш декомпозиции еадати, основанной к одноуровневом разбиотш шохгэства пар&атрои.

Принцип многоуровневой декомпозиции згшзч&этея в юа, что с чала на порвем уровкэ. строится оОачноэ разбиение шо^осгва парада исходной задачи. Наздый блок полученного разбиения вновь нодаорга аналопгшоиу разбжэншв на блош! второго уровня п т.д. Шпэдзму бло разбиения соответствует сеоя задача. Причем рзезшю задача некою, уровня й (Ogisn-D входит в исходные данные для ресэшш соответст ' цях задач уровня к+1. Совокупность реиений задач на послодаеы уро. д принимается-за решение исходной задачи. ■

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

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

Определение I. О-уровневой схемой разбиения а0 множества X. ¡а ляется само множество 2.

Определенна 2. Пусть R - нэкотороэ разбиение кнокэства X. Тогда I-уровпэвая схема разбиэнпя шгоноства X, которуи обозначим как a1-<R>, совпадает с обнчннм разбиением мнотаства X.

Определение 3. Пусть задано некоторое конечное множество X п я разбиений Л,.....R этого мнозэства (т>1). Кортек а=<Д.R > назы-

i Я J W .

вается п-уровневой схемой разбиения ынокэства X, если вшолняется условие где < - отношение измельчения»

Обозначим через Dn(X) семейство всех m-уровневых схем разбиения ).шоЕ9ства X.Свойства схе • разбиения представлены в следувдих теоремах.

Теорет 4. Вырагэппя аАр и сг?р, полученные из схем разбиения atDm(X) и fizDm(X) по слэдущим вырагениям

0АР=<Д|ЛВ,.....Rn*em>. c'P=d?fVS,.....RnVSn>,

где л и v - нижняя и верхняя граница для соответствующих одноуровневых разбиений, являются п-уровневымн схемами разбиения многэства X.

Теорела 5. Для любого и&1 семейство схем разбиения шогест-ва X, у. лрядочэшио отношением измельчения образует решетку, в которой нижняя граница любых эле энтов аир определяется как одр, a верхняя граница этих эле? нтов равна а?р.

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

В решетке n-уровневых схрм разбиения множества Х=(х1.....хп)

имеются наименьший элемент оп, который соответствует'й-уровневой схеме рр-биения <{(х.),...,(х }),...,Их.),...,Сх ))>, и наибольший элемент

I J П

im, соответствуй ¿Й т-уровневой схеме разбиения <(Х)(Х)>.

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

' . Использован"введенных пгчтий позволило провести класси^гкацип различных вариантов декомпозиции задач в зависимости от типов соот-

^етствупда схем разбиения множества параметров. Формализовано i понятие типа схемы разбиения и исследованы его свойства.

Важной проблемой является оценка числа схем разбиения аадш множества. Такие оценки известны для одноуровневых разбиений мне Например, число Отирлинга второго рода 3(п,Н) определяется как ч разбиений n-элемэнтвого множества на к блоков, а число Белла В (г, число всех равбиений втого множества« В работе введено К(п,т), к определено как число и-уровневых схем равбиения n-елементного ма ва. В следующей теореме сформулированы основные свойства втого ч где положено К(п,0)=1 для г&О и I(0,т)*1 для п&1.

Теорема 6. Для любых п,№»0 число К(п,т) Начисляется tlo фор*

*£

K(n,m)= Е S(n,t) s s (I л E5ftgit,j, (i)

K(n,m)= ZS(n,i)K(i,$i-D, (3)

(=0

K(n,m)= E a(n,t)R(l,m+1), (3) '

("T^Äft,m)K(n-i). (4)

Из выражения (I) следует, что числа Стерлинга и Белла S и В ляются частными случаями введенного числа К, поскольку при т=1 пс

Е S(n,l)=B(n).

1-0

Далее приведены аналитические оценка числа I' (п,п) охем разб. без повторений, где положено К' (п,0)=1 для то, К' (п,п)=0.

Теорела 7. Для любых nzO, CKn^i-1 представление числа (n,m ределяется формулами:

<ш-Г V

K'(n,n)* £S(n,im) Е S(t ,1 Sft2,l,J, (Б)

№ W—I I

n n.-t J+eM

K'(n,m)= E S(n,t) E (-1) K'(iJ), (в)

i=m+1 JiO

Г fn,m;="s SCn.lW (i,m-1). (7)

t=m

Получены также оценки числа K(n,m,1) ш-уровневых Z-регулярных схем разбиения n-злемантного множества параметров.

Теореха В. Число K(n,m,l) определяется по формуле

K(n.m.l)=S(n.n(l-l')-H)U

гдз п>1 ,г&1

Разработаны два алгоритма генерирования схем разбивши. В порвем

по заданной (п-и-уровпевой схеме разбиения а=<Я(,...,Лг1_;> мнохветва-строятся вез п-уроЕНЗЕые схег.'ы разбиешш Р=<Я(,.. .Йп>, где (.

Другая процедур3 построения схем разбиения заключается в генерл-ровг'.'пп! по заданной п-уревновой схеме разбиения а=<Л ,...,/? > (п~1 )-злемоятпого «иогэстза А' таких п-урознзвых схем разбиения т=<Т,.... ,Т > гтгггзстза Ш(хп), что а получается путем удаления из 7 элемента л? .

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

.ТгЗэй взрпяит дэкс:510з::ц>ы исходной задачи, соответствующий некоторому ргзбие-г.» И мнсггэства параметров, моузю оценить значением функция гогрссностп /(И). Доказана следукцая теорема, которая позволяет * проводи""-! синтез "оенх схем разбиешш с меньшей погрешность:), чем исходные схемы разбиения.

Тгсрзга Э. Пусть /-монотонная функция погрепности разбиения. Тогда (1;ун:;цня Р погрэглсста ,.<-уровнэвой схе?ы разбиения удовлетворяет условиям :

аср Г(а)<Р(р;, РГадр^СаЛ

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

ПрИННИЛ СрЭг'НПТ9Л1 "ОЙ ОЦЭЮ'З! ЕНЧИСЛИТвЛЬЕОЙ эффективности г-уро-внэвого деко:-лоз1ВД!сшюго подхода проиллюстрирован на примере 1-регу-лярннх схем разбиения гс-элемзнт"ого множества параметров исходной за-' дачи а зависимости от времешюй слояюсти алгоритмов для следущкх. случаев.

1. Временная слояюспь формирования и решения задач п.сзеп порядок пол ;о.щ ахепеки р, где р'?1. Доказано, что для р=1, т.е. для относительно простых задач, декомпозиция но целесообразна, а при р>1 г.

декомпозиция эффективна.

2. Вре.генная слогисспь фор.*иро6ания и реиянш задач цгвеп порядок экспонент с основание* к, где 1&г. Показано, что в этем случае дакемпозицк.. целесообразна.

3. Ереяетая слохносяъ формирования задан шеея порядок эиспо-'«еьта, а врежиная слохноукъ рг^онил задач - порядок помнава. Тогда

Л4

при Щ и р> ■ использование схемы r-уровневой декомпозиции i фективно, а в противном случае декомпозиция не целесообразна.

Предложенный декомпозиционный подход предусматривает следупвд основные этапы решения задачи высокой размерности:

- построение схем разбиения множества параметров задачи указв ного класса с оценкой возможного числа вариантов многоуровневой да композиции соответствуиадш числе»« Ж;

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

' - формирование моделей подзадач, соответствующих каждому блон разбиения;

- последовательное решение подзадач каждого уровня разбиения аналогичным методом.

Изложенная методология применяется в следувдн. разделах для р шения сложных задач территориального планирования и управления.

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

Тесгрела 10. Для заданного графа С=<Т,Е> существует взаимно ода злачное соответствие между схемами разбиения верпин в ребер.

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

Разработана модель формирования схемы разбиения а=<7,.....7Jt

...,УГ> множества вершин 7 любого связного графа С=<7,Е>, представ щая собой задачу линейного программирования с булевыми переменными точное решение которой представляет сложную вычислительную проблем; Построенная модель полезна для нахождения точного решения с примеи пнем средней или большой ЭВМ и для теоретического обоснования разл шх приближенных алгоритмов, требущих меньших вычислительных ре сур Разработаны и теоретически обоснованы два приближенных метода: дна. говнй графический метод и метод последовательного формирования подграфов. Приведены практические рекомендации по выбору наиболее под дяцего метода разбиения множества верешн графа для различных класс« задач.

Расстлотрэпц слэдугцпо прзкери использования многоуровневой до-кошоззсн при рэ29ЕШ1 ряда прикладных задач высокой размерности на сатях н графах. '

1. ¿^юд решения ваОсчи о /фсгачш&эл остова срефа осклеэтся в слэдусцеи. Сначала о покоцьз диалогового графического алгоритма форзпрузтсл блост Еэрппш В^ (1=1,...,г, ¿=1,..., ка всзх г уровнях разбиения гр~1э. Затом последовательно па каццом уроплэ рззблзпня рзпавтся задачи построэппя кратчайших остовов иэболь-лсЗ рлз.^зрпсстн, состазля-тлзх остов исходного графа. Доказана сходя-мзсть разработанного !.:этода и пнведзно условно сптсиальности полученного рзгггпя. Показано, что для регулярен схем разбиения- шосоства лор: лп грв.:з доксглюзицпсшшй "зтод сффзктпгзн по сравнении с пзшзст-пп злгор::т:.:с:! Пргг'з при двух л трзх уровнях разбпзпля.

2. а гсг.об л сад очи 1:ог.-Л1Лог~ера состоит- в тем, что сначала аналогично предыдущему гэтоду формируется блоки пэр-

тн гр"4 . Затем 1__> кагдем уровне разбиэния последовательно решавтея

задачи пострознпя 1фатча2гпх гг'^гьтояовчх цепей небольшой размерпос-тя, которое образует* резеде исходной задачи. Для обоснования продло-гзппого !.:этодз гзэдзно понятче "докемгогнцпонного разлогэпил* (1^,..., 1г) взрппш и{е7, гдэ Ц-псмер блока разбиения 1-го уровня, в который еходг" еэр лл!3 vi, 1=1,...,г. С цельэ координации рзшзннЗ на всех уровнях разбпзпля каздая задача построения кратчайшей га'яльтсяовй2 . цзпп сзодптся к задачо Zг построения кратчайшей гшлкьтопоеой цепи с от?'г?чошллд1 Еэрляна'гл. Теоретически доказана а практически проверена сходимость продл-ценного метода.

3. ДгтглозициаипЛ гзг.од остевого п-'лиировсшия и управления позволлзт организовать управленкз слошся проектам взаимосвязанных работ с использование» пэрсональпнх ЗЕУ. 1£ногоуровневая декомпозпцйя выполняется на осн^еэ построен^.! р-уровневой схегы разбиения а=<Г?,.. ...,Гг> тяюгоства событий 7, гд° каздое разбиение Г,=ГУи.....7|ь )

уровня I о'тоделяется слэдущпм образом:

й<

7{рП 7|ч= 0 для и 7(р=7 для 1=1.....г; для К1<7«г.

Введено понятие правильной нумерации блоков схема разбиения а многества с-">ытнй 7, которая, как доказано, обеспечивает корректность расчета параметров сетевой модели: ранних и поздних сроков свершения блоков событий, резервов времени работ, пахоздения критического пути. Получены расчетш. .формулы опре-^лоиия указанных параметров.

Исследован вапный класс "комплексных" сетевых юдолей, опь'сш вдсс циклически повторяющиеся последовательностп работ (комплексы; некоторого производственного или организационного процесса. Напри: сотовой моделью указанного вида могио описывать взаимосвязанные а; ремонтных или сборочно-монташшх работ на различных сложных одноп них агрегатах, строительство типовых гпышх' домов или сооружение д объектов, которые требуют'использования обдих расурсов (трудовых, финансовых, материальных и т.д.).Реальные сетевые комплексные гр^ могут содержать несколько тысяч работ, позтсму их обработка на Г££ иовостпшш катодами невозможна. Предложены дэксмпозЕцаэццце процоя обработки комплексных сетевых графжов, основание;) на построении с разбиошш множества события, возводящие оперативно в диалоговом р мз решать задачи сетевого плашфовннпя и управления.

Предложенный декомпозиционный подход реализовал при создали:: базе ПЗЕ.М системы оперативного сетевого планирования и упр^влокия изводством в/ч 13814, которая учитывает около 7000 работ на 12 сОг тах, представленных комплексным сетевым графиком.

В четвертом разделе исследована многоуровневая дэкозаозкцдя за территориального планирования и управления. Для пллвстрацип дэког.ш циошого подхода выбраны наиболее вапшэ звенья ЧАСУ: автоматпзпро пая система плановых расчетов (АГОР) и комплекс АСУ городским хоая вом. Рассмотрены слэдухщие оптимизационно задачи АСПР, ропавшо на нова предложенного подхода.

1. Планирование распреОеления хястих аярошелъта ятзрцам>8 Сущностью втой задачи является поиск вариантов оптимального прлкре; лония потребителей строительных материалов (строек области) к поставщикам на основе решения транспортной задачи. РеЕвняе задачи неп] , влено на внсвобовдента Езлезнодоро^ного п автомобильного транспорт! уменьшение общих транспортных расходов,устранение встречных серево: Для решения па ЭШ классическими методами описанной транспорт! задачи, с большим числом потребителей, требуется чрезвычайно болыс объем оперативной памяти н значительное врем вычислений. В традиад ной форме поставленную задачу практически невозможно ранить иа изщ и шши-ЭВМ и весьма затруднительно решить дате на средних ЭШ.

Декомпозиционный подход к ресению поставленной задачи заключае в предварительном построении схем разбиения вида fi(QJ=<Л},...,Rц> I гоства потребителей 5. Каздой схеме разбиения соответствует свой в£ ант декомпозиции исходной задач:!. Например, каждый вариант двухури воя декомпозиции транспортной задача представлен следующей ыодэлы)

ордцпзрупцзй подзадачи:

п г

• Д jIVpj - а1п' (8) •

Е Хп.=а ,р=1.....т. (9)

j=i pj р

Z z ,=з., j=u...,r, (Ю)

р~i PJ J

p=i,...,n, j=i.....г. • di)

Псслз р:поштл ноорднпирувдей задачи (Q)-(II), кнэгцей небольшую тхоялогаш нахождения значений XpJ РЗПШПТСЯ Г IGGTHUS. т^тиггпрггнх задач небольшой размерности:

Е №.....г. (13)

Je/'^V Q=k>.....nJ' (I4>

peRj, q=tej,...,rij, J=I,...,r. (15)

Доказано, что для любой заданной схег: разбиения множества потребителей исходной транспортной задачи оптимальные величшш C*pJ .в коор-дишфугдей транспортной задаче (8)-(П), минпмизируадкэ погрешность дэксмпсзицпи, определяются как средне арифметические значения расстояний cp¡j в соответствующих блоках разбиения.

Другим путем минимизации погрешности декомпозиции является рацио-пзлъекй ем бор числа блоков разбиения (степени агрегирования). Проведены расчеты на ЭВМ для класса эталонных задач большой размерности (от 1000 до 10000 потребителей,агрерпрованных по схемам разбиения), которое показали, что при увеличении степени агрегирования до 15 блоков относительная погрешность резко уменьшается. При дал1...зЯшем увеличении стапзни агрегирования до 40 блоков погрешость уменьшается незначительно, а затем почта не меняется, т.е. дальнейшая декомпозиция нецелесообразна.

По разработанной программе на. ПЭЕ!1 "Искра-ЮЗО" выполнаш расчета планов распределения 24 видов местных строительных материалов. р частности, при распределении кирпича декомпозиционным методом россам •транспортная задача для 17 поставщиков и примерно 1000 потребителей, которые на первом этапе агрегированы в 32 блока в коордншфущг-Л: задача. Требуемый объем оперативной памяти ЭВМ сократился на порядок,

а полученное субоптимальноа рэшзине всего на 5S отличается от опта-«.ХЪЕЮГО рЭГСЗНИЯ ПрИ погрепности ЕОХОДННХ ДЯЯТЕТТ не мзнзэ IOS.

í>. Планирование раасз^эншг aoc¡¡Qapcz£smejz cœynox сглъохсхо-элЛл&гпнай продукции по районам области.

Цэльв решения этой задачи является вкопогхля годовых щшзеэдсг-ь'звшх затрат за счет планирования закупок видов продуияи в poissai kï наиболее целесообразного производства.

Рассматриваемся задача ©эриализоваза в впдэ мздзлп лппвЕлого программирования специального вада, которая путем замени пор-з^знних сводена к '¿^анспортной задаче с большнл числом "поставщиков" (ендоз продукции ). Декошозиционпый подход к рз-ошги постав-тойной задачи заключается в первоначальном построении схем рззбпзппп вндз c.KP)=<S¡,.. ...,Su> множества поставщшсов Р. Двухуровневая дзг.с:.:нззнц-:онн£л подо; строятся аналогично модели (8)-(15). Координируемая задача смеет вгд:

S S О х ta-nln, (16)

{ = J <j=J 14

£X. =Á., 1=1,...,8, (17)

q -=1 14 1

£ X q=I,...,n, (IB)

1=1 4 q ntn laax

Xtq • 1=1.....o. g=I,...,rc, (19)

После решения транспортной задачи (16)—(19), слэшей соболь уя разморность, п нахождения величин Ilq рз^автея а локалыах тралсяорт-ннх задач, такте имепцих небольшую размерность:

Г'1 п

Е ЬрЛ? - nln' (Z0)

р=£>{ q~ 1

^ЛЛ P=et...-.nt. (2D

r.t

s* .г nos

Xpq ^Pq^PQ ' P^t....."i* t23)

Цинимизация HoipsnniocTH решения, полученного по иодзлг (16)-(23), проводится аналогично ранее рассмотренному случав Разработатшнй voie реализован но микроЭВЯ "Искра-226" в составе тадснстеиа "Сельское хозяйство" Awiff Оренбургской области, проведен расчет плана на I9S0 год

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

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

Иода дарование ыесотрасленых пропорций моано выполнить с исполь-гсзанкем двух вариантов декомпозиционных моделей: агрегированной межотраслевой модели (1121), межотраслевой межрайонной модели (МММ). Эти подели формализованы в вида задач линейного программирования больше рззяэрзости с бяочно-даагональной структурой матрица основных огра-Егтензй.

Варианты дакскшзшда в рассмотренных моделях соответагву»? различным разбиениям стогества Р районов и городов области. Прячем, ¿Г! соотсзтствует единичному разбиении I,(области ч целом), а МММ- 0-раз-Схешт о} по всем городам и районсы. Аналогично могут быть построены издаст для других случаев разбиения множества Р. Например: П=СГ).Р2) задав» разбиэнгэ множества Р на блоки Р( городов и Рг сьльских райо-онов областа.Разбгвниэ S=fíIJ,...,QГ^ соответствует зональному делении области. Например, для Оренбургской области г=8.

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

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

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

Рассматриваемая задача формализована в виде модели на орграфе 0=<2,Е>, где 2= (г 1 .Ноюхество Еерпшн (заказов), а каждая дуга (г^гр

2О

соответствует случаю, когда заказ z} удовлетворяет требованиям заказ z {. Задача оптимального подбора вариантов обмана по критерии удовлетворения максимального числа заказов представлена как задача цэдзчпз-лошюго линейного щюграммирования большой размерности (болзз ICQO переменных). Для резэшш этой задачи докошозицкошш.? ¡.:зтодз;.: ekejcs-зована трехуровневая схема разбиения y=<f1tTg,T3> кноеэствз загсоззз Z, гдз -разбиение но типа:,? "город-город", Т2-разбххокпз по тхзгс:-. сЗ меннваеких расурсов, Г -разбиение на взаимосвязанные блоха.

В результате использования декомпозиционного подхода удалось значительно уменьшить вычислительную сложность алгоритмов, что позволило реализовать их на средних и персональных ЗЕ". В работе приведены сравнительные оцешш вычислительной слолностн рззлхг~"-:х алгоритмов поиска. На основа предложенного подхода разрзбэтстхз автоматизированная система обмена р зурсамл, в которой елсгллз б страт реализован поле-' слохашх вариантов обмена. Система вххздрэиа городах Оренбурге и Брянске.

В пятя разделе описаны декомпозиционные прододури синтеза грз фичесхсих объектов, применяемые в диалоговых процедурах рз~знххл зедзч территориального планирования и управления. Рассматриваемой подход пепован lía построении трехуровневой схемы разбиения нзобрзл-зннл с.= -■<R1tR2,R3>, где разбиение соответствует представления езобрзлзнл совокупностью Фрагментов, формируемых в пределах одного вкраххл, Я, -разбионие на "окна", Я -разбиение на базисные элементы.

' Наиболее слошшми являются процедуры выбора и формирования базх: пых еломзнтов. Научный приоритет автора в этом направлении подтЕзрлд ló авторскими свидетельствами на изобретения в которых ои;--акп средс ва отображения различных базисных элементов типа полутоновых прлмэуг лхлмков, кругов, треугольников, эллипсов и их эломоптов, енпуклнх it гоугольников и т.д.

Для оценки сравнительной аЗДективности формирования пзобрзганпл некотором базисе <|) по от меняю к другому базису О введена следувци; характеристики:

1) коэффициент сжатия информации

2) коьЭДициэнг сокращения времени развертки ЯГ=!Гф/Хп,,

где Уф,У5,-объем памяти ЭВМ для представления изобретения в базисах Ф и 0 соитнитствошю;

Гс. ^.¡мя развертки изображения, закодированного в в тих базиса;

- Еьздонные характеристики вычисляются по .следующим формулам:

• б,]]. (24)

где N - число базисных элементов, составляющих изображение, п4- объем памяти, необходимый для хранения одной точки, и - число параметров, определяющих размеры элемента,

0. - число уровней квантования /-го параметра размера элемента;

5 и N 8

V ~5 д' . (25) .

где а - время выборки из памяти одного параметра базисного элемента, t{- время перемещения луча в начальную точку развертки элемента, 5 - площадь пзобрааения в дискретах экрана, и - скорость перемещения луча на экране ЭЛТ.

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

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

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

Коды каждого базисного елемента, составляющего изображение, передаются из ГОШ в буферное запоминающее устройство (Ь^У), Код J яркости поступает из БЗУ в модулятор яркости ЭЛТ. Коды х0,у0 начальг^й точки развертки луча изображения подаются через блоки БР-Х и БР-У развертки по координатам X и У на отклоняющие системы ЭЛТ и устанавливают луч на экране в начальную точку базисного 'элемента. Затем по сигналам блока' управления (БУ) блоками БР-Х и БР-У производится формирование очеж ;д-ного базисного элемента по кодам его размеров, поступающим из БЗУ.

от ЭВМ

Б37

БР-Х

ЯГ

БР-Y

x=u(t)

элт

V=v(t)

Рис.1. Схема функционального генератора Оазисных элементов изображения

Конкретная охема функционального гензрзтора, реализующего некоторый базис, определяется структурой блока управления г блоков развертки по координатам X и У, моделирующих соответствующие временные зависит,¡ости я-и(t),y=v{t).

Сферой применения рассмотренных декомпозиционных методов формирования изобр некий в ТАСУ является построение полутоновых диаграмм, наглядно представляющих техн" со-экономические и плановые показатели, отображение текущих ситуаций на объектах управления, схем компановка и размещения объектов, планировки территории и т.д.

В шестом разОеле рассмотрены вопросы автоматизации проектирования АСУ на основе декомпозиции и типовых проойтНых решений.

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

Таким образом, унив ^.-сальность декомпозиционного подхода для . рошения разнообразных классов задач является основой создания и ис-пользов<'-..(ин типового прогрвмного обеспечения,реализущег алгоритмы многоуровневой декомпозиции.

Особошю г;ф^кт1шно приманешю методики деком.ззиции дат решапя .уь^плещя на базе персональных ЭВМ, когда многоуровневая деком-«оз;;ц!Г г,ит. .отся единственным средством решения сложных Задач.

Симулированы следующие принципы програмной реализации дэкомпози-з;:цисч;шх мотодоь.

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

2. Реализацию алгоритмов декомпозиции необходимо осуществлять ка основе разработки пакетов прикладных програш (ППП), обеспг1,шввщих универсальность решения различных задач.

3.Декомпозиционные программы долхны обеспечивать эффективное пение задач о точки зрения затрат вычислптвлы_я ресурсов ЭЕМ по кря--тория:! использования |дшималыгаго объема оператишой памяти и «ашш

ПОГО ВрЭМЗНИ.

4. Програшоэ обзспэчепие необходимо ориентировать па оргышсгчи», диалогового рэгз.та работы пользователя с ЭЕМ при решении задач деком-поапцпошшзш методами.

Б. Должна достигаться совместимость различных пакетов пршсладных. прогргг-з.рэалпзуггях декогшозпционшю алгоритм.

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

Библиотека прогрогсдих сродств многоуровневой дексшопацп;!,разработанная в соответствии с перэчкслоцпмми 'прпнцшюги, шсличиет пдть пакетов программ: БАЗА, ПАКТ, ТОП, М-НИШ, СЕТЬ.

Разработанная библиотека программ за счот реализации доодшоашш отпппс ??этодоп ориентирована на решение задач высокой размерности ля базе персонально! ЗЕ?! !'с::рп-226, Лскра-1020 и ПЗЕ'1 типа Ш! 1С.

ПрограгппЯ котласа БАЗА предназначен для анализа различии ы-рчантов докслозгате задачи,шборз наиболее рзцпспад итого варианта да» котшезззднн и форяровенпя подзадач для их последующего решения. Гаси«-трлваенгй програмиий комплекс является базовым,поскольку входное и него програмгжш срэдства используется во всех осталышх перэчислен-пнх ПШ. В этом программном ко?.шлексэ рэалпзоваш двкошюзкщгоняпэ методы, изложенные во втором п тротьем разделах диссертационной работ. Программный комплекс БАЗА позволяет проводить генерирование вариантов схем разбиения и оценку их возможного числа для различных сл: юев, определять декомпозиционные координата любого элемэпта, реализует диалоговый и последовательный методы разбиения графов.

Инсаруяеталъная сиспет ПАКТ предназначена для быстрой подготовки типового программного обеспечения персональных ЭВМ -путем евтома...-зированного перевода пакетов прикладных программ со средних и больших ЭВМ Единой системы на современные ПЭВМ. Система ПАКТ реализована на языке ПЛ/1 в операционной среде ОС ЕС. Уровень автоматизации при использовании системы ПАКТ достигает 971, преобразование средней 1фОг-

раммы выполняется на ЭВМ £0-1022 примерно ва I мин.

Одним из практических приложений системы ПАКТ является автоматизация подготовки программ решения задач декомпозиционными методами. Другое важное направление использования етой системы заключается в быстром проектировании ППП для решения разнообразных аналитически?, прогнозных в оптимизационных вадач ТАСУ на базе ПЭВМ. О помощью системы ПАКТ выполнен, в частности, перевод на язык БЕЙОИК пакета научных программ на ФОРТРАНе, содержащего около 200 подпрограмм, и пакета сетевой оптимизации.

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

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

С помощью системы ТОН введены режимы отображения графической ин-<Тормации в автоматизированную систему управления Горелектоо транспортом и автоматизированную систему обработки Плановой информации. На основе подпрограмм системы ТОН реализовано многоуровневое разбиение графов диалоговым методом в программном комплекс" ВАЗА.

Пакет прикладных програлл ЛП-ЮКРО содержит программы, реализующие на ПЭВМ различные методы решения задач линейного программирования и объединенные на основе декомпозиционного подхода. В зависимости от характеристик решаемой задачи (необходимость плотной валиси матрица ограничений, вида задачи, заполненности матрицы ограничышй, возможности поиска приближенного решения) управляющая программа DEC0UP выбирает "аиболее подходящую для ее решения программу пакета. .Ш JL-ИИКРО использован для решения задач территориального планирования и управления, рассмотренных в четвертом разделе. '

Пакет прикладных программ СЕТЬ включает программы построения крзг'айаего остова графа, решения задачи коммивояжера и комплекс прог-

рвмм сетевого планирования и управления, в которых па ПЭВМ реализсва щ декошозпцнонние метода, рассмотренные з третье» разделе. Пакет программ разработал по технологии автоматизированного проектирование программного обеспечения с использованием инструментальных средств БАЗА,ПЛ<Т,ТОВ.- -

По мэре растрясшейся ручной п автоматизированной подготовки ПШ для современных CEU становится актуальной проблема рационального формирования Спблиоте1ш программ. О одной стороны, необходимо полностьа удсадзтворить фушсцисяальше требования пользователя автоматизирован-пего рабочего места. О другой стороны, следуот осуществлять эти требования о гглгпмзлыпгд затратами ресурсов.

Gадача оптимального комплектования библиотеки прикладных программ ьшет-Снть формализована следующим образом. Необходимо минимизировать фуякцзш

Е 2 11,,*,. (26)

Jai 1 J t=IJ=» ,J J ;

где Tj - трудоемкость разработки или адаптации J-й программы о учетом éosmüshoctii автоматизированного перэвода) (/=!,...,п); t(J - трудоемкость решения í-й задачи с помощью /-й программы {1=1, ...,п, J=1,...,n)¡

если J-n программа включена в библиотеку,

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

1=1,..., а, (27)

если задача { решается по программе J,

и "fj"

где а,,=\

в противном случае.

Модель (26), (27) представляет собой задачу о м "шмальнем покрытии большой разг.?9рности, которая решается декомпозиционным методом, рассмотренным в диссертационной работе.

Все рассмотренные пакеты прикладных программ, разработанные при непосредственном участии автора, прошла экспертизу на ноачзну и внедрены в ГосФАП СССР, а такта используются при проектировании подсистем АСУ хозяйством Оренбургской области и в учебном процессе в Оренбургском политехнически! институте. ■

ЗЛЮШЧЕ1ШЕ

D диссертационной работе представлены результаты создашш и применения комйшаторной теории многоуровневой декомпозиции. Совокупной разработанных теоретических полоаеяий является новым крупным достш:э-нпом в развитии перспективного научного направлештя в области теории пиитики проектирования автоматизированных систем управления. При э:? ¡)!';{;г-не р-эион комплекс следующих теоретических и прикладшх задач.

I. Разработан понятийный аппарат теор:ш гаогоурэьаммй дзтлю-сштпя, обвс:..ч;гоюэдК общоо прэдетавлзшю докомкозпгкопшх мо,цол2:1 Сомл'.и систем. В píjr¿5cax лредложзшой теории ros:?:, т.- л исг-.одокзг.» упорядоченное лространсг о вариантов докомлоз::;. ;; с.-".--™ г:.;, роггк:.: схем разбиошгя ¡.шокэстаа параметров. Даш оцо;-::п Есс-.гчгаго числа вариантов, шчислителыюй сло:люсти и «огромности эелзвэл де-

композиции сода i для различных классов схем рззбцоюи. -РезраЗотат ьлгорктш генерирования и сшиеза схем разбиения. Доказана возможность значительного (на порядок) уменьшения вычислительной слоазюст^ рс-поштя задач за счет использования методологии многоуровневой допем-позиции.

Z. На ocituBO предложенной теорш! разработана методика гл-гагоурзс-нзвой декомпозиции задач на сигях и графах, кшвчаздая модели, кэто-дч и алгоритм- построения схем разбиения множеств вгр:;пи и pr"¡ap rp'Tjcn. ГЬ отой методике решены задачи коммивояжера, построения кратчайшего остова графа, сетевого планирования и управления.

3. С использованием методологии многоуровневой дэкомп^иции рал-ра^оташ модели .. методы решения ряда оптимизационных задач территориального планирования и управления: поставок местных строительных m.tj.íриалов, закупок сельскохоз.Лствониой продукции развития хзупедо-коммунального хозяйства и зкилицного строительства, перераспределения ресурсов.

4. На основе декомпозиционного подхода продло::ош метода, алгоритма и г емотехнические решения для формирования слоили тра£пчзских объектов на экране дисплея, защищенные авторскими свидетельствами.

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

6. Использование разработаншх декомпозиционных моделей, методов, я "''оритмов и схемотехнических решений для решения задач в сос-

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

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ ОПУБЛИКОВАЛО В СЛЕДУЮЩИХ РАБОТАХ

1. Абдрашитов Р.Т., Кацман В.Е., Манковский Э.И. Программные средства головного комплекса АСУ Оренбургской области//Разработка л внадрэниз прогршгашх средств для автоматизированных систем управления: Тез.докл. на 3-м Всероссийском семинаре/НПО АСУ "Цосква"-М., 1Ш6.-С.47-49.

2. Абдрашитов Р.Т., Манковский Э.И., !Сацман В.Е. Ошт создания головного комплекса АСУ сбласти//Проблемы и методы ускорения науч-по-тэхнзческого прогресса на основе при?,«нения вычислит* .ьной техника н автоматизированных саотем: Тез. докл. Всесоюз. конф. 4.2/ ВНИШОУ.-U. ,1986.-0.53-ББ.

3. A.c. Б85510 СССР, Ш1 0 06 К 15/20. Устройство дл' отображения ипфордации на вкране электроннолучевой трубки/В.Е.Кацман, В.И. Заболотских, Н.И.Калядан (СССР).-З с.

4. A.c. 616642 СССР, ШШ 0 Об К 15/20. Устройство для формирования изображения на экрана электроннолучевой трубки/ В.Е.Кацман, В.И.Заболотских, Н.И.Налядин (СССР).-4 с.

5. A.c. 647712 СССР, МКИ G Об К 15/20. Устройство для формирования изображения на экране электороннолучевой трубки/ В.Е.Кацман, В.И.8аболотских, Н.И.Калядан (СССР).-4 с.

6. A.c. 682924 СССР, ШШ G 06 К 15/20, Устройство для отображения графической информации на вкране электроннолучевой трубки/ В.Е.Ка-цаан, В.И.Заболотских, Н.И.Калядан (СССР).-4 с.:ил.

7. A.c. 691898 СССР, ШШ G Об К 15/20. Устройство для С рмирова-пзя изображения на экране электроннолучевой трубки / В.Е.Кацман, В.И.Заболотских, Н.И.Калядан (СССР).-4 о.:ил.

8. A.c. 705485 СССР, ЫКИ в 06 К 15/20. Устройство для формирования изображения на экране электроннолучевой трубки / В.Е.Кацман,

.В.И.Заболотских, Н.И.Калядан (СССР).-4 с.:ил.

9. A.c. 7II60I СССР, МКИ С 06 К 15/20. Устройство для формирования окружностей на экране электороннолучевой трубки. / В.Е.Кацман, В.И.Заболотских, Н.И.Калядан (СССР).-З с.:илл.

10. A.c. 720430 СССР, ШШ G OS E 15/20. Устройство для фэржров пня изображения на экрана электроннолучевой трубки / В.Е.Кацман,

B.1Î.Заболотских, И.И.Калядац (СССР).-5 с,:илл. t

11. A.c. 734664 СССР, mai 0 Об Д 15/20. Устройство для отсбпо::: шя графической информации на экрана электроннолучевой трубки /В.Е.Г iwau,В.И.Заболотских, Н.И.Налядин (СССР).-5 с.:плл.

12. A.c. 739595 СССР, ШШ G Об К 15/20. Устройство для отобрав шш графической информации на акраио электроннолучевой тру Леи /В.Е.1 цмая,В.И.Заболотских,Н.И.Каллдин (СССР).-Б о,:нлл.

13. А.ь. 744670 СССР, Ш! О 05 Я 15/20. Устройство j:m отобрав ш;л информации на экране электроннолучевой трубки /В, 3. о ль ci сяП,

' В.Е.Кацман (СССР).-4 с.г'лл.

14. A.c. 841028 СССР, ШИ G 09 О 1/CQ. Устройство для форг.арог! ния изображения на экране елэкт^шолучэвой трубкп /В.Е.Кацман (ССо; -3 с.:илл.

15. A.c. 959140, ШМ G 09 О 1/Q5. Устройство для отобрагэшхп с формации на экране электроннолучевой трубки /В.Е.Кацман (ОССР).-З с

16. A.c. 1027758 СССР, ШШ G Об G 1/06. Устройство для фор:."тро нля изображения на s:фане электроннолучевой трубки /В.Е.Кацман (CGC -5 с.гилл.

17. A.c. 1226495 СССР, Л G Об G 7/43. Устройство для ыодзлгр ваши задач дленного программирования /В.Е.Кацман, В.А.Волков, Г.В Бажова ХСССР).-3 с.гилл.

18. A.c. 1372350 СССР, ЫНИ G 09 G 1/06. Устройство для отобраг г:ш информации ыа экране электроннолучевой трубки /В.Е.Кацман,А.В.С талкин (СССР). - : с.гилл.

19. Калядаш Н.И.,Кацман В.Е. О разбиения растрового изображали/ ыа минимальное число прямоуг шшх элэцэнтов//Авто:.ттЕчоскце ycipoi ства учета и контроля.--Ижевск, 1077.-С.23-28.

20. Кацман В.Е. .Заболотских В.И.,Калядин H.H. Использование 31 f.ölP-2 для визуального вьяода полутоновых пзобрагэ1Ей//Прпборы н те; ка эксг. римант а. -1979. -Ш. -С. 90-92.

21. Кацман В.Е. Повышение эффективности обработки : формации i решении задач большой размерности в АСУ обменом Еплпл01дади//Управл! большим Т'ородом:Тез.докл.1 Всесовз.конф.ЛШО АСУ ..!осква'\-Р Д93Т

C.I09-II0.

L2. Кацман В.Е. Применение алгоритмов оптимизации в сфере икф маццокшх услуг по обмену ресурсами горосан//Совершенствовшшэ орг 11нзг"".юн1ых структур ц методов управления ищгпцю-коммукальшм хоз

crr-;i n (ffi-nrnn cSosjrznsqnsa пгсэлгии n услоезяг Стнпцющровгшя

а.пз-зэ,

_ПЗ. Г'"Т"-"t D.D. O.A. СОЕЗрЕЭГСТВОЕВНИа

'"-rrrr'T'i сЗслустппзл ейсэлзнкя о примененном автоматизм-

ртзпгггсЗ: c~c7"zi плггогж рзгчзтов//СоЕзразнствован2э организационных п матсдзз упрЕзлзпяя гяЕпгцю-ко:.™^уиальннга гозгДством п быта-га изсэлзпнл в условиях Стшсщгоннровйсш АСУ-ЕНХ и АСУ -

FC2CP.-U. ,1934.-С,81.

21. Б.П., Ропязр Д.Г., Бдина IUI. Пп::з? прикладных прог-

"--J л"Л p:r:rrr! сзтг:™2ЦИПП1Ц2 задач па сзтяг п графах (СЕТЬ): [1-:::? xrçcrp:.:,?V .Çssijprc^îî полтох. пп-т.-Кпз.Я 50900000578,' ГосФАП с.

ГЗ. В.2. .Цзкегтаггздпснпгй алгоритм рзггзпия транспортной

зггзтз птл пл-ггрззггги распрэдэлзиил местных строительных каторкалог:

плтрзвапгл n рзспублпке,' УАССР, краях к областях mcP/CZIZ^Ï.IT-r ¿СУ при ГСОТЛПЯЭ P02CP,-t!.,I985.-C.57-65.

ГЗ. D.D. 1'этодц дзкклгазкцзп задач большой размерности в

спсгзмзх планирования п управления // Убавление "э::::—I гсрэ-см:Тсз.г,":'л.Есзсо::з.г.сгГ)./П110 АСУ "Москва".-П.,1985.-3.23-25.

27. Кшг'-Л D.E. Пскэ? программ для декошозпщп задач большой ^гзрнсстп (EISA): ïïoro? прогрз:,:.!/ Орзнбургсшй политех, пн-т.-ПСГС0ССС57Э, гсо^лп CCCP.-Ü.-ISSO.-25 с.

23. Ксцт^д D.D. ,!'алп:эз Б.Г. Пакет линейного програьодфовашы ^ча ПЗ'ЕЛ "Пг:ф2-223//РззЕИ,п:э функциональных подсистем АСПР Госплана ГС1СР /ICE"!,ЕС! АСУ np:i Госплане РСГСР.-М. ,1987гО.35-102.

20. И2!с?пл В.Е. Созрзмзшпгэ мэтодц-п опит создания автоматизиро-сгстогл управления гозл2стеом области.-Чэлябптгч:Ш.-Урал.га. гзд-ео,1530.-207 с.

20. Кпцмга В.Е. Кпструкэпталышя система подготовки паке оз при-•.лздчйх программ для А1Г!//Проблзмы создания азтсязтизировашшх рабочих :зст л учр-эздзнчэсхих сотой в городском хозяйство:Тез.докл.Есосоьз. :oh3./ŒO АСУ Москва".-ÎJ.,IS33.-C.79-80.

31. Itojiaa D.E. Пакет прикладных прогри-i для формирования пол,,-гаиошх изображений на экране кшфоЭШ/ЛТрактпчвсков применение сов-ззмэншх технологий программирования,пакетов прикладных программ б гычислительшх системах п сетях ЗК1:Тез.докл.1 Всесога.конф./ВДорм-фИбср.-и.,1963,-С.25-97.

32. Кацман в.Б. Автоматизация подготовки программ для ГОШ // Разработка и применение программных средств ПЭВМ в учебном процесса: Тез.докл.17 Всесоюз.свминера/ШИАН.-Ы.,1888.-С.98-В9,

33. Кацман В.Б. Автоматизация управления регионом.Учебное пособие.-Куйбышев:КуАМ, 1988. -88о.

34. Кацман В.Е. Декомпозиционные процедура принятия ращений в автоматизированных систем обмена ресурсами горо$ан//Ыатоды ййтомагазации процессов принятия решений в управлении городом/НПО АСУ "Москва", -41..1988.-С.31-Э7.

35. Каман В.Е. Формирование полутоновых изображений на экране ¡дисплея методом декомпозиции//Изв.вузов.Приборостроение.-1688. -W6.-'С ,34-39.

36. Кацман В.Е..Саталкин А.В. Система визуального вывода полутоновых изображений на базе микроэвм "Иснра-226и//Ышфапроце ссорные средства и сис1^мы.-1988.-УБ.-0.34.

37. Кацман B.B. Теория схем разбиения //Пав.АН СССР.Техн.кибар-нет.-1990.-КЗ.-G.28-37.

38. Кацман В.Е. Пакеты прикладных программ для решения сдрцнда задач управления городе»! на базе персональных ЭВМ//Управление бойьшиы юродом.Тез.докл.4 Всесоюз.конф.-М.,1989.-С.122-123.

39. Кацман В.Е. .Малинов Ъ.Г. Оптимизация капитальных вложений в жилищное строиveльство//Математическое моделирование.-J989.-Itt2.-C.82--88.

40. Кацман В.Е.,Габидулин U.B. Декомпозиционный метод решения задачи размещения государственных закупок сельскохозяйственной про-дукции//Планироьание на ЭВЫ в новых условиях хозяйствования/ЦЭНЙИ,ШИ АСУ при Госплане РОФСР.,-M.,I989.-C.87-93.

" . 41. Кацман В.Е. Использоьание микро ЭВЫ для пинтеаа полутоновых изображений//Изв .вузов. Приборостроение. -1989. -ff5. -С.82-В6.

42. Кацман В.Е. Комплекс задач учета,анализа и отображения движения троллейбусов на базе микроэвм "Искра-226" : Экспресс-информация. Серия "Г родской электротранспорт". Отечественный производственный опыт/Центр.бюро науч.-техн.ивф.Ыинжилкомхоза РОФСР,-M.,Ibd9.-ini(17). -6 с.

43. Кацман В.Е. .Коновал Я.Ы. Пакет автоматического кодирования текстов ФОРТРАН-БЕЙСИК//Алгоритмы 2 программы:Инф.бюлл.ГосФАП СССР.--.'i7.-C.il.

44. Кацман В.Е.,Саталкин А.В. Формирование сложных изображений на экране дасплэя//Алгоритмы и программы:Инф.бшл.ГосФАП СССР.-1989.-

-17.-0.13.

45. Нацыан В.Е.,Малинов В.Г. Решение задач линейного програики--рования//АлГоритмн я програмвсИвф.бпдя.ГосФШ СССР.-1969.-Ш.-С.12.

46. Кациан В.Е. Основы теории многоуровневой декомпозиции и ее прлкшенвя.-Саратов :Ивд-во Сарат.ун-та,1990.-192 с.

47. Кациаа В.Е. Передача программ в 4СУ городским хозяйством,''/ Автоматизация передач! данных в городском хозяйстве/НПО АСУ "Москва", -II..1969.

48. Кациаа В.В.,Коновал Я.К. Автоматизация подготовки программ ддя персональных ЭВМ//1йакропроц9ссорные средства и системы.-1989.-У6,

49. Кацман в.В. Оптимизационные модели подсистемы "Хюотшо-коы-мунальяов хозяйство" АСПР местных плановых органов/Л1лаввроватае на ЭВМ в новых условиях хозяйствования/ШНИИ,НИИ АСУ при Госплане РСФСР,

ш.лэвэ.-с.тб-ев.

60. Кащввн В.В. Методы в средства автоматизации процессов организационного управления хозяйством области/Оренбург.политех.ия-т.-Оренбург. 1968.-225 с. Деп. в ВИНИТИ 30.04.86, Л2948-В88.