Введение к работе
АКТУАЛЬНОСТЬ ПРОБЛЕЩ. Процесс перестройка в сфере управления экономикой неразрывно связав о Ширакам внедрением современной вычислительной твхншад (ВТ),экономика-математических методов (ЭММ) и автоматизированных систем управления (АСУ) различав! уровней.Государсгвевная программа повышения эффективности ВТ и АСУ предусматривает, в частности, создание в развитие территориальных АСУ(ТАОУ) автономных республик, краев я областей.
Существенные затруднения при реализации этого ванного направле-ви.: научно-технического прогресса вызывает необходимость переработки большого объема информация в процессах принятия плановых и управленческих решении. Особенно актуальной становится ата проблема в настоящее время в связи с широким распространением персональных ЭВМ (ШВЫ).'
Ос ^банво слсгннмя, но в то кэ время наиболее эффективными задачами ТАСУ являются оптвмивацдг-ъле задачи территориального планирования в управления, для ранения этих задач,имещих высокую размерность, аа средних в больший; ЭВМ используйся модели в методе математического [программирования (линейные в целочисленные) и аппарат творив графов.
Кар^ шальным направлением решения задач высокой размерности яв-(шляется использование да композиционного подхода, который заключается в том, что всходвая сложная задача сводится к последовательности более ладстых подзадач .каядая из которых может быть решена на имеющейся ЭВМ.
Декомпозиг "онныи методам решения сливных задач посвящено большое исло исследований. Основное внимание в втих работах уделяется деком-довицвишшм методам а алгоритма решения частных задач. Сами же процедуры разбиения множества параметров модели исходной задачи, на под—' подмножества параметров моделей подзадач не исследованы. Кроме того,' в большинстве работ рассматривается лишь двухуровневая декомпозиция задач.изщая теория многоуровневых разбиений множества параметров задати в процессе декомпозиции отсутствует,хотя при решении все более ус-пожяящпхся задач планирования и управления требуется проведение указанных многоуровневых разбиений. Выбор варианта декомпозиции задача їзвєствнми методами осуществляется ва основе интуиции разработчиков зистемы, что приводит к недопустимо большой погрешности решения.
Следовательно, возникает необходимость создания теории, много-іфоввевой декомпозиции, которая позволила бы формально описать пространство возможных вариантов декомпозиции задач, установить взаииосвя- .
- a2Touaii:a;rpc~ir2G0 црослтароваилз Е.црі::т5Чзсгл.і рзй^с:.ихл е ' Оазз ПЭБИ подзеотє:.: ТАСУ, содзрсьЕДХ задачи шсокаЗ ргзизрлосіл.
Тьійгл сбразсм.в д^ссортацял развзнаэтся езеоэ езтчпзэ ЕаоразлзЕ - комбЕнаторгал тсзрлл ідюгоурОЕлзЕсд дзкомзззедеіі с есзлздзхтсл ез-празлзпзя прз::їЕіос:-.зго использования цродлоїзпЕсй тсорхі для рзезее сходна ссгач террЕТсрлздьЕзго планирования п управлзЕЕл.
ІЕТОЛз КОСЛЩ^ЕіІГЛ. В качзствз штематнчзсісого сппарата в рабо ссаользована кэтодз ксиблЕаторака, тоорлп каогасїз и ізорзд ро-зі02. Дз::сь2озлщ:ан~і:з і^дзле; задач тэррзторгальЕэго плшефсесеея и управе
ЕЕЛ PS3P260TZj ЕЛ ССЕ023 ТйОрХІ ГрзСОВ Е ЕЗТе^ЗТЕЧЗСЕОГО ПрСГрС^Лф
НіУЧІШІ ІГСЕИЗНД в:лгалношш: исследований зислзчаатся п сладу!>-
ПЗМ.
-
Іїредлогюпз мзтодолопш комбинаторного подхода к проблеме многоуровневой деш.чюзпцил задач, заклшащаяся в построзшш няо-гоуровнэвнл разбиения мнсгзства параметров, анализе и синтезе вариантов декомпозиция слоила скотом.
-
Разработана теория схом разбиения, пкллчающзя ire определения л свойства. Рассмотрены специальные классы схем разбиогаїя. Для оцаїпга тлела схем разбиения, соотвотствусггого числу вариантов иісго-уроЕНЭЕоЯ дзкогшозицпи задачи, ввздэпо повоо комбинаторное число К, лвл"ісгіЗося обобщение!,; числа С-итрлилга S и числа Бэллз В. Разработаны методы п алгоритмы генерирования п енптоза схем разбиения.
-
Провэдэны оцзнкн вычислительной слогпюстл и погрешности резания задач мэтодом гт-огоуровневоЗ дстетлозгпдтл. Сформулированы условия
ДОПУСТИМОСТИ ПОЛУ ЗЄМОГО рЗСОИПЯ II ГЧЧПСЛЛТВЛЬЕСЛ єфізитпвности его Д0СТП28НКЯ.
-
Разработана мотодика иногоуровнзЕоЗ декомпозиции задач из сетях п графах. Конструктивно доказана взаимно однозначная связь кзеду схемами разбиения множеств верни п рзбэр графа. Построена матемзта-чзскр" г.!о; ~ль формирования оптимальной схемы разбнэиил мсоггэствэ версии. Прэдлогзнп три катода рэсонпя поставленной задачи.
-
Разработали дзкс!.зіозпь_.ош!і:о методы ратания задач ТЛСУ боль-сой розмэрностп, сводящихся к задачам кеммчивоягзрз, построения крат-чамого остова г-гфэ, расчета параметров сетевых гр2п:ов. Сформ^ли-роваш теоретически обосноваяниэ условия оптимальности и эффективности рзезппл этих задач, получаемых . экошозициоппеги методами.
G. Предложены декемпозицноншо модели и методи рэпенил ряда задач территориального планированпмя .і управления, сводетися к спзциальемм задачам линейного проіграммпроваіткя высокой размерности: поставок костных строительных материалов,закупок сельскохозяйственной продукции, развития гмлЕцно-коммупального хозяйства и "плппзгаго строительства, перераспределения ресурсов.
7. Разработаны декомпозиционные методі синтеза слокпнх графических объектов, вклвчащи- схемотехнические принципы и алгоритмы функционировать пового класса дисплеев,' заяптщчппыо 15 авторскими евндэ-толі твамл на изобретения.
ІІРАКТИЛЕСКАЯ ЦЕННОСТЬ РАБОТЫ. Результати работы в целой явллг/тсл теоретической основой автоматизированного проектировапия программного обеспечения для решения декомпозиционными методами задач высокой р*э-
'6
мерности. Разработана библиотека типовых программных средств, bkj
щья 5 пакетов прикладных программ (ГОШ), предназначенных для басі
реализации на ЭВМ декомпозиционных методов: исазовыи комплекс декомпозиции задач; 2)инструментальную систему перевода программ на персональные 3) систему формирования полутоновых изображения на экране дне 4)пакет прикладных программ решения задач линейного програй.
на база микроэвм;
Б)пакот прикладных программ для решения задач на сетях и грг Комбинаторная теория многоуровневой декомпозиции, а тшшэ рг
ботанше на еЭ основе типовые модели, метода, алгоритмы и програї
решения задач высокой размерности могут быть использованы п в да
областях кибернетики:
- в САПР вычислительных устройств (декомпозиционные модели I
тоды решения задач на графах);
- в АСУП (оптимизация производственной программы прадпрлятш система сетевого планирования и управления производством);
в человеко-машинных системах различного назначения (форми] вание сложных графических объектов);
в приложениях теории вероятностей, статистики и комбинато] (обобщения чисел Стирлинга и Белла, алгоритмы генерирования схем биения множеств).
РЕАЛИЗАЦИЯ РАБОТЫ. На основе предложенного декомпозиционной хода в составе АСУ хозяйством Оренбургской области решены оледуп задачи:
оптимизированы схемы перевозок местных строительных матер:
оптимизирована программа жилищного строительства;
разработан оптимальный план государственных закупок сельи зяйственной продукции по районам области;
внедрены автоматизированные системы обмена ресурсами ropoj (жилыми помещениями, местами в дошкольных учреждениях);
внедрена автоматизированная система сетевого планирования управления производством в/ч I38I4;
введены диалоговые режимы с формированием сложных графичес объектов в система обработки плановой информации ГлавГОУ Оренбурі облисполкома и автоматизированной системе учета и анализа Оренбуї го троллейбусного управления.
В результате использования декомпозиционных процедур времеш сложность алгоритмов решения перечисленных задач уменьшилась приі
на порядок, что позволило рзализовать их на персональних ЗШ.. Факта-чесіпя годоеой экопогпгчвскпа еффэкт от внедрения разработок в состава парной очереди АСУ хозяйством Оренбургской области составил более I млн. рублой. Некоторое подсистемы, вклвчакщиэ перзчислевнне задачи, . передает з Врянскуз, Псковскую к Читинскую области.
Тссрзтлчэскпз материалы диссертации н пакеты пршиїадшіх прогрянм псполъооваин в утзСнсм процессе Оренбургского политехнического писі11 тута в лекционных курсах л прсктнческпх занятиях.
ЛЛГСЗЛГГГЛ РАБОТЫ. Сносные положении ц результати днссзртсш'.п ...,,....,,,..,.-..,.,.,,^ ,л обсу:.:лэ^;сь на слэдупгдх конференциях и семинарах: 2 Гзсс:'г::іс:\ саг:::с:;;~і "Проб.'::!"і дпсгаіпіпзгиюго сбора,передачи з ели-'J;;:,.::11:'! ::::''і::: a п:7ор:'з:;;юі-і^ііх спстэмах (Ійов.НТОгЗС им.л.С.Попова, 1077): І,а п IV Всзсо^зіліх їїСиГ'Зрзшцілх ''Упрагшзяло Сольгііїм городом (.Чссппз, НПО АСУ ";,зз.;;::а"!ІГЗІ,І?25,іГ23); L'j Госпубл:н;анс:сом совоцзшм "Проблема создзнгч '"ЛСУ-Россіїя'ЧЇЬскга.Гссплаи РС"СР,І33); Всоссїї.зпс:і ксяТзрзьигп "Совзр-енствовашіз гтаїизаїлюїшні структур и методов управления :.тк'пгно-ко:.г.мупальнш,і .«.озядзїесм :і битовым обслуживанием насо-лзптіл з условиях Фупкцпо1....ровагшя ДСУ-ЖХ и АСУ-БЫТ (Уфа,ІІГО г.омзіунадь-пого хезлдства и битового обслу;дпзапля,І984); Всесоюзном семинара "Пр::мспо:гго СЕМ для автоматизированного учета н обработки отчетности в ггилп^о-ккімуппльїюп хозяйстве н битовом обслуїииванпи (Красноярск,НТО коммунального хсзлЛстеэ и битного обсдуг2івзиця,І985); Всесоюзной коя-фзрзицпл "Проблемі п методы ускорения паучно-тохничэского прогресса на ос ore применения гмчнг -лтольпоа гехншсн п автоматизированных систем (!.:ос:свз,ЕІи^ІїОУ,іС05); ПІ Всероссийском семинаре "Разработка и внедрение прогрій:'зк средств для сз7"матнзїфоЕзнннх систем управленім (Hoc-' іпза.ІПГО АСУ "Москва",1936); совместном засодаяші Советского национал! .ого комитета мзпдупаротной ассоциации по математическому п і:2322210^ моделированию п Цвптрально-Поволткской территориальной груп-ш Соье-зісого национального неістота по участив в деятельности неяду-пародпой лсссциацпи по математическому п машинному моделированию (Кудб>с;зв,ІС80); 17 ВС8С0ЕЗН0М семинаре "Разрабо~<а и применение про-граммных средств ЗВУ в учебном процессе" (Симферополь,ИЛИ АН СССР, I960); I Всесоюзной конференции "Практическое применение современных технологий рограммирования,пакетов прикладных программ в Еычислитель-пых системах п сетях ЭШ"(ДЕегп»П8трозск,Мишгрибор,ГэвЗ); Всесоюзной конференции "Проблемы "создания 'автоматизированных рабочих мест и уч-рэадонческнх сет ,ї в'городском озялстве"(Москва, НПО АСУ "МоскЕа", . 1983).
. 8
За разработку ютодов рзкзаші слоізаїх подач первой очереди ДС2 хозяйством Оренбургской области автор награздоп сорзбряной иодалъы ИЩИ СССР.
ИУБЛЖЩШ. По тема диссертации опубликованы EQ научішх труда в той числе 3 мовографт и 16 авторских свидэтольста па изобретена основные положения дасстшш.шосишЕ НА ВАЩИТУ:
методология комбинаторного подхода к проблеме шогоурошэво: декомпозиции задач высокой размерности;
теория схем разбиения (многоуровневых разбиений) шшства параметров задач высокой размерности;
МаТОДЫ ОЦ9ШШ ВЫЧНйЩТ8ЛЬН02 СЛОЖНОСТИ П ПОГрОШЮСТИ ШІОГО-
уровневоа декомпозиции;
модели и мотодц построения схэм разбиения шозэотв вершин и рэбер графа}
декомюзиционные модели п метода рэшошя задач высокой раз-церности на сетях и графах;
дэкошозицноннаэ модели н шгода ранения ряда задач террдтс риального планирования и управления высокой размерности;
декошозпцноншв катоды форгларования слоэных графических объектов.
СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, шв разделов и заюшеная, изложенных на 250 страницах, списка литераї из 230 наименований, содержит 41 рисунок, 12 таблиц и 7 црялогзпй
