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

ХЛРКГВСЬКИИ ДЕРЖАВНИК ТЕХН1ЧШИ УН1ВЕРСИТЕТ РАД10ЕЛЕКТР0Н1КИ

-t—n.......................-----.....—

* Ч от юпА " '

' J., 'i Ha правах рукопису

УДК 519. 95*62-503. 55*601. 142

СОПБЛЬННКОВА ОЛЕНА В0Л0ДИЯКР1ВНА

АВПЖАТЯЭОВАвЕ ПРОВИУЕИПЯ ЗВ'КЗфНЧМХ REPES

05.13.12 - снстеми автоиатизая»i проектування

<пр0кисл0в1сть)

Автореферат дисерталк на здобггтя вчевого швевя кандидата техшчннх вале

XapKlB - 199«

Робота виконана в Харк1вськону державному педагогичному ушверситет! 1м. Г. с. сковороди

НаУков1 кер!вники: доктор техн1чних наук. проФесор Вайнер В. Г.;

кандидат Ф1эико-натенатичяих наук, проФесор Б1лоусова Л I. .

ОФ1н1йн1 опоненти: доктор теян1чних наук. проФесор Олександров £. е.; доктор ♦1эико-матенатичних наук. проФесор Яковлев С. В.

Вёдуче п1дприснство - Науково-досл1дний та проектно-конструктор-ський 1нститут автонатизованих систем управл!ння транспорта газу (НДПIАСУтрансгаз) 10 "Укргазпром" Державного ком1тету УкраТни по наФт! 1 газу, н.харк!в

Захист в1йбудеться_££." 1994 року о годинI

на зас!данн1 спеаГал1эовано1 ради К 068.37.03 у Харк1вському . державному текн1чнону ун1верситет! рад!оедектрон1ки за адресов: 310059. Харк1в. пр. Лен1на. 14.

3 дисертая1ею можна ознайомитися у б1бл!отеи1 Харк1вського державного техн1чного ун1верситету рад1оелектрон1ки.

Автореферат розIслано"

___ 1994року

Вчений секрета? спеп1ал1эовано? ради, кандидат техн!чних наук, допеит /1 Сукесов Е. А

ЗАГЛЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

АктуадьнЮть робота. Техн1эоване середовише проживания людини являе собою численн1 приклади об'ект1в, шо з'-едная1 зв'язками в един! систени. ш систенк зв'язк1в утворюють зв'язуюч! нерех1. Такими € електронн1. телефонн!. шляхов! нерех!. канал1эап1йн1 систени, наб!р ланпюИв. то з'еднюють елементи друкованих плат в слиний електронний лрилад та багато 1нших. Прискорений.розвиток науки 1 техн!ки створюс все б!льш 1 б1лыо с клади! систени об'скПв. як! з'еднан! мережею : !нФормап!йн!. конп'ютерн!. ситуад1йнГ мере*!, с хеки розвитку пронислових комплекс!в. V зв'яэку з аим актуальна практична потреба розробки систени■матенатичних моделей. .засоб!в 1 алгоритм!в р(шення задач побудови них мере*. Хр!н того, у зв'яэку з! с клади 1 стю б Слыло с т! нерех. для 1х синтезу винагасться застосування систен автонатизо-ваного проектування (. САПР ). тобто залучення засоб!в сучасних БОН . |

Мережа призначена для того, тоб переносите деяний продукт (речовину. пот!к. 1нФориад1ю ! т. п.).. Продукт, який проходить по мерех1. утворюс пот1к. шо по данону ребру переносить, певну к1льк!сть продукту в одииипю часу. Тому необх!дно потурбуватися про.те. тоб синтезувати нерех! з такою пропускное спорножн1сп> ребер, шо ногла ои забезпечити необх1дний пот1к. Проблема синтезу нерех постала в 60-1 роки, коли була опубл!кована робота Форда. 1 ♦алкерсона " Потоки в. мережах де вони вир!шили проблену розпод!лу-оптимальних поток1в у вхе спроектован!й иерех! з ребрами обмехено! пропускно! спроможност!. Нин же завданням присвячен! численн1 робота, особливий !нтерес з них являють робота Срнольева. евдок1мова 1. Тевяшева; КаФарова. Нешалк1на. в яких одержан 1 ефективн! алгоритми оптин1эаШ1 для розв' язування задач потокорозпод! лу.. розгляду нетрадиШйних задач, зворотних задачам анал!зу - синтезу нерех. коли потоки. як1 проходять .по ребрам, задан! ! иеобх1ано спроектувати саму мережу - присвячеко значно менш р061т. огляд. яких. призведений в . робот! :Вайнера . !з сп1вавторами ." - Автоматизад] я, проектування зв' язуючих нерех ". Задач! синтезу вахч1 н1ж задач! анал!эу мере* !. неньш вивчен). Оя аисерталМша \ робота лехить у.русл!.' зазначеного наукового напрям-ку. II особлив!стю е подалыпий розвиток шдходу. викладеного в роботах Зайцева,. Вайнера. Кхрхнера. який пов' яэанийз рпрадаван-

.-■Щт

яяи нового класу задач дискретно! оптюазалП на мерехах -побтаовою зв'язуючих нерех • во роэвиваються . Справд1. до остан-нього часу розглядалися с.тапЮнарн! мереж 1, тобто нерех). тополоПя яких ве залетать в1д част. Проте. для вс1Х нерех Юнуютъ так! природнич» поняття. як час експлуатаяп нерех! 1 час П- хяття. шо. в свою черту, виэначас етапи побудови систеки комун1кад1& Актуальн) сть Р1иення даних проблем викликана там, по систеки ве В1чн1. вони +1зично спрадьовуються. зак1нчуеться терн!в IX використання тоао. Шкавин 1 практично вахливин додат-кои теорП -побгдови нерех . то роэвиваються. с утворенвя ситуап1йних нерех. як1 використовуються в - ход! управления рятувадьнини та 1ншимн нев1дкладними роботами (Р1НР) уход! л!кв1дая11 наел!дк1в азар!й ва х1М1чвс-небезпечних виробнидтвах : загальне управд1ння Р1Н-роботами; виэначення найкоротшия иарорупв доставки рятувальних п1дроэд1я)в в ход1 аварп. во розвивасться; ггворенвя нерех. во роэвиваються. для поетапно! п1сляавар1йно! в1дбудови виробашгге тояю.

Наведен1 н1ркуваиня роблять актуальною проблену створения единого п1дходу для утворенвя моделей. засоб1в. алгоритн1в 1 програнншс систен автонатизованого проектування зв'язуючих нерех. якии прнсвячеиа дисертад!йна робота.

Кетою робот« с теоретичне обгрунтування 1 досл1дхення натенатичних моделей. эасоб1в 1 алгоритм¡в Р1иення задач авто на-.тизованого проектування тополоШй стадЮварних зв'язуючих нерех 1 зв'язуючих нерех. во роэвиваються.

Для досягнення поставлено! нети необх!дно вириогги наступн1 задач» :

1. Опраш>вания катекатичних моделей. засоб1в I алгоритн1в побудовн стадюнарних зв'язуючих нерех.

г. Теоретичне досл1дхення класу задаче получения зв'язуючя-ни мере хами, во роэвиваються.

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

4. Одерхадня о01 нок оптимум*. в задачи автонатизоваяог© проектування зв'язуючихнерех.

5. Одралювання комплексно! -моаел! автоматнэованогр проектування опткнадьних зв'язуючих нерех.

6. Практична р«ад1эац1я резудьтат1в вир1веиня конкретних

задач.

Налоова новхзяа результат! в дисертад! I подягас в

- 5 - '.......

епрадюванн! комплексного комб!новая6го П1дяоду роэв'язання задач сполучёння зв'язуючини мережами, який ноже бути використаний для автоматизованог© проектування багатоФУнквЮнальних зв'язуючих мерех ^Кр1м того, в робот! в1дом1 засоби 1 алгорйтни вир1шення задач синтезу мереж були доповнея1 1 конкретизован!.

Науков! результата полягають т тому, то :

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

£. Запропонований. 1 досл!джений нетрадиШйний клас задач побудови мереж, шо розвиваються. Розроблений загальний виглял п1яьового функпюнала. спеа!ал!заи!я якого дозволяе будувати р!зноман1тн1 зв'язуюч! мереж1. Оск1льки задач"! дього класу належать до НР - повних, то на баз1 одержании властивостей оптимальних р!шень розроблений точний алгоритм для задач малого розн1ру ( зас!б в! ток 1 меж ). наближеж-й алгоритм, оснований на заздалепдь одержан1й б!бл!отед! оптинальних 1 субоптимальних (базисних) р1шень та евристичн! алгоритни р!шення динам1чних задач.

3. Поставлен! ! вир!шен! задач! побудови зв'язуючих мереж, во розвиваються. в тону числ! аналоги задач Прина-Краскала 1 Итейнера.

4. Наведен1 ошнки типу середиього значения для п!льового функпюнала в задачах побудови зв'язуючих нереж , шо розвиваються. в р!зноман1тних постановках. На 5х основ! р!шення, то одержують по наближенин 1 евристичним алгоритмам, иожуть бути оШненк

5. Розроблена комплексна . комб!кована обчислювальна схема автоматизованого проектування оптимальних зв'язуючих нереж на основ! кластерного анал!зу.

6. розроблено математичне забезпечення для реал! залп комплексно! комб1новано! обчислювально! схеми як Штегровано!

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

Нетоди досл1джения ! обгрунтованють наукових результат!в.

Науков! результати. шо н!стяться в дисертапИ. базуються на сучасних засобах дискретно* оптим1зацп 1 теорП граф 1 в. Теоретичн! результата мають точний математичний доказ. Евристичн1 алгоритми оптим1зап!1 перев!рен! на реальних об'ектах. наближен!

- в -

алгоритмы оШнен! э точки эору наближення отриманих Р1тень до оптимуму. Натематичне эабезпечення для вирШення задач автомати-эованого проектування засновано на коректном застосуванн! теорП 1нФормаШйних систем, включаючи структурне 1 нодульне програиУ-еання. 1нструментар1й програмування на ПЕОН. Кр!м того, 61рог1дн1сТь наукових положень робота Шдтверджуеться апробацию результате. 1к практичним застосуванням I впровадженням.

Практична Шнн1сть результат! в робота полягае в тому, що вони £ теоретичною, методичною ! практичною основою для комплексного Шдходу до рШення проблеми сполучення оптимальниш зв'язуючими мережами, яка ноже Формулюватися в р1зноман!тних постановках : стаШонарн! 1 динам1чн! задач!; !з р!зноман!тнини тополог1ям1 : задач! Штейнера ! Прима-Краскала: э урахуванням ! "без урахування потоков. Реал!зац1я комб!новано'£ модел! синтез у нереж зд!йснено у ,вигляд1 математичного эабезпечення Штегровано"! системи, яку можна використати : в САПР ( ионтажно-технолог!чне проектування, проектування генеральных план!в ! 1нженерних комУн!каа!й ); для управл!яня Р1НР в ход! л!кв!дац.!1 насл!дк1в авар!й ( для проведения найкоротших маршрут!в доставки рятуваль-ьих Формувань до м!саь виникнення авар!!, коли тимчасов! парамет-ри зв'язуючо! мереж! визначаються моделлю прогнозу розвитку -зар1яка використовуеться у вигляд! вих!дних даних ); для "правл!ння поетапною в!дбудовою п!дприемства п!сля авар1 "1. а також у вигляд1 навчаючо! системи з дискретно! оптим!запП (окрем1 алгоритки 1 модул1 викликають 1нтерес як 1яюстраШ5 ориПнальних нетрадШ!йних засоб!в р!шення оптгоизаШйих задач ).

Науков! положения, висновки, рекомекдапП I црактичй! результата, висловлен! в дисертаи!ян!я робот!, статтях 1 навчаль-ному пос!бнику. використан! в навчальному пропес! Харк!вського державного педагог!чного ун!верситету !м. Г. С. сковороди в межах читання спецкурс1в " основи наукрвих доел!джень " 1 " Модел! еколог!чних систем "

Реал1заи!я ! впровадження результат!в робота. ДисертаШя , виконана в межах госпдоговор!в 1990 - 1993гг : з опраиювання програмного эабезпечення задач моделювання, прогнозування 1 оптим1заои х1м!ко-технолоПчних систем ( замовник - Харк1вське НПО " Карбонат " ); з опрашовання автоматизовано! системи моделювання авар!й, прогнозування п1сляавар!йних обставин ! управл!ння д!кв1дад!ею насл!дк!в авар(й ( зановник - Северодонеаьке виробни-. че об'еднання " Азот " ) 1 з утворения автоматизовано! системи

- т -

йрийняття р1шень у випадках авар1й на пронислових п!дприенствах облает! ( зановник - штаб дивмьно! оборони Луганськ1й облает! ).

АпробаиГя робота. Натер!али дисертап!йно! робота допов!далися. обговорювалися ! були схвален! на Н!хнародн!й робоч1й нарад! Шжнародно! Федерал II з автоматичного управл1ння (1РАС ) з питань взаемояП пропес!в проектування 1 управл!ння «Лондон. Англ!я. 1992 ); н1жнародн!й науково-практичШй конференпи " Б!знес 1 наука " ( Феодос1я, 1993 >; нарад! н!жнародно1 школи-сем1нару " Проектування автоматизованих систем вонтролю 1 управл!ння складними об'ситами" ( Туапсе. 1992 ); Шждержавнону науково-Техн!чнону сем!нар! " Над!йн1сть. в!дказост!йк!сть 1 продуктивн1сть 1нФормап!йних систем " (Туапсе, ■1993 ); всеукра!нсько! науково-техн!чно1 конФерени!I " пожежна безпека." ( Харк1в, 1993 >.

ПУбл!калИ. основн! науков! положения опубл!кован! в 9-ти лрукованих роботах» в тому числ1: у двох розд!лах навчального пос1бника. в 3-х статях ( 2 - у з61рп1 прадь наради 1РАС. 1 - в эб1рд! прадь ВсеукраТнсько! конферендп -по проблемам пожежно! безпеки ), у 4-х тезах допов1дей. Прийнят1 дв1 статт! до опубликования в журнал! Нап1онально1 АкадемП. Укра1ни " Проблени. нашинобудування ".

структура I обе яг дисертадП. Дисертад1я складаеться э вступу. чотирьох р03д1л1в. висн0вк1 в. списка використано! л1тератури 1 додатк!в. Ос но вний текст дисертадП викладений на 144 стор1нках.

& роод-Ш 1 виклааена теор!я 1 засоби побудови стац1онарних зв'язуючих нереж з урахуванням 1 без урахування поток!в.

V ро$А1л1 2 поставлен!. досл1джен1 1 вир1шен! ориг!нальними алгоритмами оптим1зап1йн1 задач! синтезу оптимальяих зв'язуючих мереж, шо розвиваються

$ Р04&1Л1 3 наведен! ошнки оптимальних р1шень задач яобгдови зв'язуючих мереж, то розвиваються.

Я ро^д-1л1 4 описана комплексна комб!нованй схема побудови багатофункцгональних мереж.

Основй! положения I результата, во виносяться на захист.

1. Теоретичне^ обгрунтування, засоби ! алгоритми р1шеяь задач синтезу нереж з зФдЙуваниям поток1в в р1знонан1тних постановках 1 для р!зноман1тних шльових функп!й :

- задач! Гонор1-ХУ;

- задач! синтезу многополюсно! мереж! 1з и1и1м1заоНю II

- » -

довжияж

- задач! синтезу нногопояюснв! мереж!. враховуючи варт1сть транспортировки насопоток! в;

- задач! Итейнера з урахуваннян поток!в.

г. ДосШдження кяасу дискретних моделей побудови оптиналь-икх зв'яэуючих мереж, то розвиваоться. включаючи :

- визначення властивостей оптинальних р!шень;

- доказ НР -повноти найпрост!пшх задач нього класу;

- здобуття властивостей оптимайьних Р1шень для побудови точних 1 наближених алгоритм! в.

3. Алгоритаи р!шенняприкладних задач побудови оптинальних эв'язуючих мереж, то розвиваються:

- задач! Прима-Краскала < побудова. иереж без впровадженкя сром!жних вершин >.-

- задач! Штейнера ( побудова нереж! !з пром!Жними вузлами ).-

- задач! Штейнера з. задании числом пром!жних вершин.

4. Одержання оШнок типу середнього значения Шльового фуншцонала для ршення задач в стаШонарн1й ! динам!чн1й постановках.:

- задач! Штейнера < дискретно! ! непреривно! );

- задач! Прима-Крас кала.

5. комб!нована обчислювальна модель синтезу эв'яэуючих иереж. яка використовус пропедури кластерного анал!зу.

6. натематичне забезпечення !нтегровано? системи. шо реал!зус роэроблен! алгоритми синтезу багатоФуйкпЮнальних мереж.

ОСНОВНИИ ЗШСТ РОБОТИ -

Я обгрунтована актуальн!<;ть теми, сформульована мета

! задач! аосл!дження. наведен! основн1 положения, то виносяться. на эахист. показана наукова новизна 1 практичне значения проведе-них досл!Джень.

9 первощ роз&1л1 побудована математична модель задач! з'сднання дов1льною зв'язуючо» мережею Н 1 визнаЧений вид , ц1льового функШонала, шо виражае. витрати на буд!внийтво мереж!

р ( х» 6. г. ч,р )-- с< (1. с. г, ч ) о ( х.у ). < 1.1 )

1. Нножина хмх^... .х,) - наб!р .точок п-н!рного простору* е*

(п=г.3). координата яких описують роэнтення вия1дниа об'скт1в мереж! к.

г. Ннохина ..?„,} - наб1р точок з еГ то описують

роэншеняя пр0н1жяих вузл1в мереж1 н.

3. Нереж! н ставиться у bíдпов1дн1сть абстрактний граф 6 так, тоб кота! й точп! 1 нереж! н в!днов1 дала вершина 1 графа G i кохн1й пар! точок 1. i nepexl S. с получения дугою. в1дпов1дало ребро (i. J ) графа G. Граф G визначае тополопю нереж!.

Жожнону елементу xte х ( ГГк ) э!ставино нев!д'емне число tt, шо 1нтерпрету£ться як час початку фунюнювання об'екту z в мереж! Н, тобто час його включения в загальюг систему. Такин чинок ннйжин! X з!ставляеться вектор Т= (tt,..., tK!. такиа, то 1, <tt<, <tK i. На час ^веривши x.t повинн1 бути включен! в

Hépexy Н. яка hí стать прон1жн! вершини. а також ви*1дн! вертаини, во мають б!льш п1зн1 часи включения. Посл!довн1сть час!в включения породжус посл!довн!сть нереж ht...., н*.

5. 3 мережею н нов'язакий деякий поток ч. який задаеться

вектором ч-(ч4..... чв), де ч -величина потоку в вих!дн1й вершин!

1 ( 1-ГГк ). вектор ч i граф 6 характеризуюсь величину потоку ч в будь-який дуэ! (1,4).

С. Для будь-яко! пари точок и.уеЕ* функшя p(ü.V) визначае нетргасу простору Е. тобто задас найкоротшу в1дстань н!х точками О i v. звичайно розглядають «вклХдову метрику

pi U'V , (Ki-f , ?

i пряиокутну

7. BaPTiCTb одинид! довжини дуги cíe.H) залехить в!д струк-тури графа G, а, отхе. в1д t ■ i потоку ч

с( е.Н ) =с( ( 1, J >. G, t. ч ).

СформУльована оптим1зап1йна задача побудови оптимально!

зв'язуючо! нереж! для заданик киохин вйх!дних вершин ! потоку ч

* • *

складаеться з в!дтуканйя структури G i полохення вузл1в y, таких, тоб

F ( X. Y?0>! t. q. <p ) -- min F ( X. Y. G. t. q.<J>>. < 1.2 )

Виходячи 3 виду Шльового функционала (1.1). дана класи-Ф!кад!я натенатичних иоделей задач синтезу зв'язутэчих мереж:

- якшо в функшонал! <1. 1) в!дсутня залежн1сть в1д q. то сФормульована задача про знахождення найкоротшо! зв'язуючо! мерёж1 без урахування потоку;

- якшо f<q > - опукла по q функшя ( наприклад. f(q) псбудова нереж! трубопровод!в: f(q) = <Ья*Ь - побудова мереж! аьтомоб!льних дор!г. коли ширина проЧжджо! частини залежить л!н1йно в!д пропускно! спроножност!; f( q ) = const - проектування. л1н1й електропередач ). то виникае задача транспортування иасопоток!в;

- якшо с( е.н » =то пе багатополюсна задача синтезу нереж. коли варт!сть д!льнип! нереж! залежить в!д довжини;

- якшо с(е, Н ) = 1. то виникае задача Гонор1-Ху:

- якшо нножина X лежить в плошин! 1 <U. v> - «вклХдова в!д-стань, то пе задача Штейнера ;

- якшо заборонено введения пром!жних вершин, тобто в мереж! немас точок галуження 1 нножина V в1дсутня. то маемо аналог в!домоТ задач! Прима-Краскала;

- якшо в функшонал! (1.1) в!дсутня залежн!сть в!д часу, то ми насмо задач! побудови стап!онарних, зв'язУючих мереж.

Одержан! алгоритми синтезу оптимальних тополог!й стадюнарних зв'язуючих нереж без урахування поток!в в Постанов! задач Прима-Краскала ( без введения пром!жних вузл!в; складн!сть алгоритму 0(n')> 1 Штейнера < з введениям додаткових вузл1в; складн!сть алгоритму 0<ns>>. Для находження оптимального положения пром!жних вузл1в в задач! Штейнера запропонована процедура груповоТ покоординатно! релаксап!! <складн!сть пропедури 0(п5>).

Розроблен! 1 теоретично обгрунтован1 алгоритми синтезу стапЮнарних зв'язуючих мереж з розпод1лом заданих поток!в. Вир1шен! задач! синтезу мереж без урахування пром!жних вузл1в (задач! Гомор1-Ху ) для наступних тльових функшй :

F. (' Н ) = ^ с ( е. ). е.еЕ

F.( Н ) е- »1 ( е- ).

е^Е

де с( е. >-пропускна спроможн!сть ребра е. ; 1( е-) -довжина ребра е,

- 11 -

Складн!сть алгоритме 0< п5>.

Запропонован1 засоби зн^ходження оптимальних положень прон1жних вузл1в при задан!й топологи в задач! Штейиера з наступними н!льовини Функциями :

N ) = е. Я ( е- ).

ее£

з

К1 н > с( е.) >1< е;), {( с) опукла.

ееЕ

Складн1сть алгоритм!в 0< п5).

Був запропонований евристичний алгоритм р!шення задач! синтезу стап!онарно! нереж! з урахуванням транспортировки касопоток1в в раз! наявност1 п-1 джерела ! 1 стоку. Доведена, його коректн!сть для опуклих Функп!й. Складн!сть алгоритму 0( п1).

У дрцеощ ро$д1л1 розглядаеться клас задач сполучення нерогами, шо розвиваються. коли заданий порядок часу п1 дключення вершин до мереж!. 0птин1зап!йна задача вир!шувалася з наступним Шльовим функшоналом :

е= Я4.....,т ) 0.41-. [¿т^рц^.. ( г. 1 )

де К = ( Н^..... - нережа. яка синтезусться.. то описусться поел! довним впровадженням в стр1й 1' i Фрагмент! в'; Т - час функц!онування вс 1 с I системи-.^-Т- ^ -час експлуатацП фрагменту нереж! який добудовусться при п!дключенн! об'екту х^до нереж! Н-гсконструйовано! на момент часу X для одержання мереж!

: " сумарна довжина ребер множини Ь^; 6^= уза-

гальнена вартить аобудовування мереж! при переход! в!д мереж! Н; до мереж! коеФ1д1«нти"с/- 1 в!дбивають р!зноман!тн! типи ви-трат. Вивчен1 Функп!I лШйноТ залежност1 експлуатап!йио* вартос-т1 фрагменту мереж! в!д його довжини.

Показано! то нав!ть в найПР0ст!Ш0МУ випадку. (динан!чний аналог задач! Прима-Краскала ) синтез мереж1. що розвиваеться. -НР-повна задача. Установлен! властивост1 оптимальних р!шень, наближен!сть функп!й на трасктор!як. доведено твердження шодо певно! упорядкованост1 в проведенн! оптимальних траектор!й. шо дозволяе використовувати для р!шення нових задач в!дом! оптимальн! траскторП.

При посл!довному добудуванн1 мереж! на етап1 переходу В1д фрагменту мереж! к до Н . вийикас трудя1сть у вибор! оптинального альтру!стачного шляху сполучения двох фрагнент1в. Довдено, то довхина ребер дього шляху повинна бути кеньша. н!ж найкоротша в1деталь н1ж фрагментами, то з'сднуються. Пя властив1сть використана в эасоб! в!ток 1 меж 1 еврнстичних алгоритмах синтезу зв'язуючих мереж, шо роэвиваються.

У Вревымц ро$&1л1 продовжен! робота в. Г. Вайнера. I. Д. Зайцева з в1дшуку ошнок оптииум1в Шльових Функпюнал1в для НР-повних задач. 1дея побудови таких отнок належить в. Г.В1э1нгу. шо запропонував оц1нювати оптимум at льового функдюнала в задач! ком1вояжера кр!зь середне значения вс1х припустимих РЮень. Иого робота продовжили В. Н. К1ржнер 1 В. 1. рубл1недкий. як! удосконалили од!нку оптимума. вирахувавши квадратичне в1дхилення вс!х припустимих значень д!льово* ФункдП шодо середньогс\ 0д1нки типу сегг zHboro одержан! для динан1чно! задач1 Прима-Краскала i стадюнарно! задач! штейнера в дискретному 1 непреривнонг видад-ках. Обчислена дисперс!я вс1ляких значень д1 льового функдюнала для дискретно! задач! Штейнера. шо дозволяс визначити верхню нежу оптимума. Одержан1 ошнки використовуються у виг ляд! початкових 1 пром1жниу оа!нок значень д!льового функШонала в засоб! bItok 1 меж при синтез1 мереж, шо роэвиваються. а також для оШнки pi тень, то одержують евристичнини алгоритмами.

ЗГ ъев&ер&нщ poq&lAi розглянутий декомпоз1а1йний зас!б побудови зв'яэуючих мереж, шо роэвиваються. за допомогою процедур кластерного анал!зу.

Головною трудн1стю в побудов1 иереж, то роэвиваються. с то® Факт, шо одержання точного р1шення кожна зд!йснити лише для задач иевелйкого розм!ру (п<10 ). Тому при р!шенн! задач реально! розн!рност! виникае необх!дн!сть щукати засоби, шо дозволять знизити розм!рн!сть вих!дно! задач1. Сане з Шею нетою розробле-ний комб!новаяий зас!б. оснований на застосУванн1 процедур кластерного анал! зу.

Натенатична постановка задач 1 кластер!задП для редУкип розн1рно;т1 складаеться э розбиття вектора t^ ,..., tn нанепере-тинн! кластери Smct> обеягами п^...., и >

таким чином, шоб елеиенти кожно! групи лежали один в!д одного на в1детая! нент!й. н1ж в!дстань м!ж еленентани. узятими з р!зних груп. П1сля того, ях розбиття Sa (t>.. .., Sm(t> збудовано. црирод-но збудовано розбиття S4(X)..... Sm(X) для кожного класа вих!дних

точок X по часу включения в нережу, прояедури кластеР1заШ! до-эволяють вид1ляти групи вершин з близьким часом шдключення до мереж! 1 дають можлив!сть вирШувати стапюнарн1 задач! синтезу для кожного з кластер!в. а п1сля пього об'еднувати збудоваи! фрагмента в сдину динам1чну нережу при допомоз! розробленого уза-гальненого алгоритму пошуку альтруТстичного шляху, або будь-якин 1ншин алгоритмом, то п! дхояить. При такому п!дход( загальна задача побудови мереж!. то розвиваеться. розпадаеться на три етапи :

1. Застосування процедур кластерного анал1зу ( паралельних 1 поел!довних - в залежност! в1д розм!рност! вия!дио'£ завдач! > для зниження розм!рност!,

г. Р!шення задач!, синтезу оптимально! стап!онарно! зв'язуючо! мереж! всередин! кожного кластера :

- побудова мереж1 без введения додаткових вершин - алгоритм Прима-Краскала (складн!сть алгоритму 0<п3));

- побудова мереж1 з введениям додаткових вершин -.узагаль-нений алгоритм Прима-Краскала (складн!сть алгоритму 0(п*));

- синтез мереж! з урахуванням поток1в ( складн!сть алгоритму О(п3)>;

3. Р!шення задач! синтезу, оптимально! динам!чно! зв'язуючо! мереж! на р!вн! кластер!в ( об'еднання в сдину мережу, то розвиваеться стаяюнарких фрагмент1в ) : побудова мереж! без введения додаткових вершин

1 число кластер!в т : т<10 - точния алгоритм засобом в!ток ! меж, шо використовуе ои!нки оптимума (складн!сть алгоритму 0( п4)):

- число кластер!в т : 10<т<100 - наближений алгоритм, то використовуе б!бл!отеку базисних р1шень 1 оа!нки оптимума (складн!сть алгоритму 0( п >>; або використання узагальненого алгоритму пошуку альтру!стичного шляху за до по ногою процедур кластерного анал1зу ( складн!сть алгоритму 0( п3));

- число кластер1в т : т>>100 - точний алгоритм Прима-Краскала. п!дключення кластер!в в порядку зростання часу включения в мережу <складн!сть алгоритму 0< п.3»>; або використання узагальненого алгоритму пошуку альтру!стичного шляху за допо-могою процедур кластерного анал!зу (складн!сть алгоритму 0(п* >>г

побудова мереж1 з введениям прон!жних вершин :

число кластер!в т : т<10 - алгоритм Вайнера - Зайцева -Л1втица для об'еднання кластер!в (складн!сть алгоритму 0< п5));

- число кластер!в т : ю>100- точний моди<И кований алгоритм Прина-Краскала ( порядок Формування мере*! диктуеться тимчасовин порядком п!дключення вершин в нережу; пе е параметром, то визна-чить алгоритм; (складн!сть алгоритму 0( п+>); або використання узагальненого алгоритма пошуку альтру!стачного шляху за допомогою процедур кластерного анал1эу <складн!сть алгоритму 0( п5));

Частики наведено! конб1новано! схени стакуються одна з одною по простору вх!д-вик!д, при дьому обов'язковими параметрами € : вид метрики, координата вершин, величини поток!в в вершинах, час !х включения в мережу, загальний час експлуатааП мереж!, види Шльових Функционал!в.

В комб!нован!й обчислювальн!й схем! використовуються паралельн1 1 посл!довн! кластер-пропедури в задежност1 в!д розм!рност1 вих!дноТ задач!. Паралельн! пропедури призначен1 для р!шення задач при к!лькост! об'ект!в. то э'еднаються, п<100. Вони реал1зуються за допомогою 1тераа!йнних алгоритм!в. на кожному крои! яких одночасно ( паралельно ) використовуються вс! 1снуюч1 точки. Складн!сть розроблених алгоритн!в 0( п*)>. Посл1довн! про-цедури призначен1 для р.!шення задач б!льшо? розм1рност!. Вони реал1зуються за допомогою 1терац1йник алгоритма (складн1сть адгоритм1 в О <па)>. на кожному крон! яких використовуеться часта-на вих!дних точок, а також результат розбиття на попередньому

крои!.

Складн1сть комб!нованого засобу побудови з'язуючоТ мереж1, то розвиваеться. поягае в тому, то п!сля того, як збудован! м1н!мальн1 по довжин! стаШонарн1 зв'язуюч! нереж! для кожного кластера вершин, об'еднаних за принципом близькост! часу а!дклсчення в нережу, виникае безл1ч альтру!стичних пшяхГв об'еднання цих фрагмент!в в сдину мережу, шо розвиваеться. Викодячи з виду фуюшЮнала (£. 1). в якому узагальнена варпсть ребра, визначаеться добутком його довжини на' час Функд1ювання в мереж! £ н Т-г ) ], а також враховуючи необх1дн1сть Шдключення ' вершини х не п1зн!ше моменту t , роэроблений евристачний узагаль-нений алгоритм пошуку альтру!стачного шляху за допомогою кластерного анал!зу для зв'язку стадюнарних Фрагмент1в в мережу, то розвиваеться. Складн!сть алгоритму СМ п*>.

У висновку розд!лу роэглянуто застосування комб1новано! обчислювально! схени синтезу багатофунмиональних з'язуючих мереж в нежах САПР х!н!чних виробнидтв, автонатизованих систем управл!ння ( АСУ ) л!кв!дад!ею насл!дк!в авар!й на х!м!чних

п!дпригмствах 1 навчаючо! системи по курсу дискретной оптим1зааП.

ВИСНОВКЙ

Сукупн1сть результат!в, одержаних в дисертап$йн1й робот! яляс собою теоретичне обгрунтування математичних моделей, роэроб-ку засоб!в 1 алгоритм!в р!шення задач макропроектування •багатофункп!ональних зв'язуючих мереж, як! використовуються для аванпроектування х!м!чния виробниптв, проведения Р1Н-роб!.т ! спешальнох реконструюлI в проиес! АСУ л!кв!даШсю насл!дк!в авар!й на х1М!чних п!дприемствах.

Основн! результата дисертапП так! :

1. Побудован! матенатичн! модел! 1 розроблений комплекс алгоритм!в р!шення задач побудови сташонарних з'язуючия мереж:

- наведена математична модель ! класи<Нкад1Я задач синтезу з'язуючия мереж;

- вир!шен! задач! синтезу мереж без урахування потоков;

- вир!иен! задач! синтезу нереж з урахуванням поток!в.

2. Поставлен! 1 теоретично яосл1джен! задач! сполучення мережами, то розвиваються, визначен! властивост! оптималышх р!шень.

3. Роэроблен! матенатичн! засоби ! класиф!кован! алгоритми вир!шення задач сполучення мережами, шо розвиваються :

- динан!чного аналога Прима-Краскала;

- динам! чного аналога Штейнера.

4. Наведен! оц!нки оптимумов п!льових функа!онал1В в терм!нах середнього 1 дисперс!1 для задач-сполучення з'язуючими мережами в р!знокан!тних постановках;

5. Розроблена комплексна обчислювальна комб!нована схема синтезу багатофункц!ональних з'язуючих мереж на основ! кластерного анализу :

- поставлена математична проблема декомпозипи задач реального масштабу для зниження П роэм!рност1 ;

. - описан! проиедури кластер! запП вектора часу исключения вершин до мереж!.

6. описано математичке забезпечення ! застосування комбновано"! ¡нтегровано! системи, яка реал1зу€ роэроблен! алгоритми синтезу багатофункд!ональних мереж.

Освоений ЗН1СТ дисертадН опгбл!кований в наступив* роботах

t. V. G. vainer, Е. v. SopelniKova Design and Control of Chemically-Hazardous Plants //IFAC VorKshop on interactions between Process Design and Process Control. Imperial College of Science, Technology, and Hedecine, London. U.K., September 6-8'th, 1992, P. 26-29.

2. V. G. Vainer, E. V. SopelniKova, Computer-Aided Optimal Dynamic NetwirK Design// ifac worKshop on interactions between Process Design and Process control, imperial College of Science. Technology, and Hedecine, London. U.K., September 6-eth. 1993, p. 41-46.

3. Вайнер В. Г., Сопельиикова Е. В. Иетоды решения задач оптимального синтеза связывающих сетей: Тез. докл. Неждународ. науч. -практ. конФ. - г. Феодосия, 1992. -Харьков : Инженерная Академия Украины-Харьковский политехнический ин-т. 1992.-с. 25-26.

4. Вайнер В. Г., Аннопольский Д. В., Сопельиикова Е. В. Применение нетодов исследования операций для управления процессом ликвидации последствий аварий на химических производствах: Тез. докл. Международ, науч. -практ. конФ. - г. Феодосия, 1992. -Харьков .•Инжнерная Академия Украины-Харьковский политехнический институт,

1992. -С. 26-28.

5. Вайнер В. Г., сопельиикова Е. в. разработка и исследование нетодов оптимального управления спасательными и восстановительными работами: Тез. докл. Неждунар. школы-семинара, Туапсе: 1992. -Краснодар: Российская Акдемия Налс-Министерство обороны Российской Федерации. 1992.-С. 25-26.

в. Вайнер В. Г., Сопельиикова Е. в. Применение теории построения оптимальных связывающих сетей для планирования спасательных работ: Тез. докл. Всеукр. науч. -техн. конФ., г. Харьков.

1993. Харьков: Нин. образования Украины, НВД Украины. 1993г. -С. 35.

Т. Вайнер В. Г. , Сопелькикова Е. В. Применение теории построения оптимальных связывающих сетей для планирования спасательных работ// Проблемы пожарной безопасности: Сб. трудов / Под ред. В. Г. Памоха. Харьков. : Нин. образования Украины, НВД Украины, 1993. -С. 261-263.

8. Вайнер В. г., Сопельникова Е. В. Комбинированный метол построения кваэиоптимальной топлогии информационной системы: Тез:

докл. Межгосударственного шкоды-семинара, Харьков-Туапсе, 1993. -С. 9-Ю.

9. Костенко Ю. т., Сопельникова Е. В., Зайиев А. И. // Новые информационные технологии для инженеров: Хиния и прон. экология: Учеб. пособие / под ред. Костенко ю. т.. Вайнера В. Г. -Киев: Учеб. метод, конбинат но Украины. 1993. -Разделы 5.6 -с. 136-183.

РЕЗОНЕ

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

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

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

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

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

- решены задачи синтеза сетей без учета потоков;

- решены задачи синтеза сетей с учетон потоков.

2. Поставлены и теоретически исследованы задачи соединения развивающимися сетями, определены свойства оптимальных решений.

3. Разработаны математические методы и классифицированы алгоритмы решения задач соединения развивающимися сетями:

- динамического аналога Прима-Краскала ;

- динамического аналога Жтеянера.

- 1в -

4. Приведены опенки оптикуновпелевых функционалов в терминах среднего и дисперсии для'Задач соединения связывающими сетями в различных постановках,- ..... >■ -

5. Разработана комплексная комбинированная вычислительная схема синтеза многофункциональных связывающих сетей н основе -кластерного анализа: '

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

6. Описано математическое обеспечение и применение комбинированной интегрированной систены. реализующей разработанные алгоритмы синтеза многофункциональных сетей.

[1! д писан о до друку а& /994р. Обсяг I сеч. л. Уч. -друк. л. 0. 75 Форнат папери 60x84 Безплато Тира* 4о екз. Зак N¿¡/4 -----:-}-

Ротапринт НД10ЩИБ. 310180 м. Харк1в> вул. Ото кара Яроша. 13