Разработка и исследование ПДО-алгоритмов для труднорешаемых задач комбинаторной оптимизация тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

V./,. Наш овальна Академ! я Наук Украпш Тнститут Шбернетики |мен| В.М. Глушкова

¡г.;

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

Павлова Людмила 0лександр1Ена УДК 519.8

РОЗРОБКА ТА Д0СЛ1ДЖЕННН ЩП~АЛГ0РИТМ1В ДЛЯ ВАЖКОРОЗВ'ЯЗУВАНЮС ЗАДАЧ К0Ш31НАТ0РН0I 0ПТИМ13АЦ11

от. ьз

■01т05-.64- - теорвтичн1 основи 1нформ1Тики та кибернетики (матэматкчна кЮврнвтика)

Автореферат

диоертац!к на здобуття наукового ступени к£ о ф1зико-математичних наук

ки1в-19Э6

Дисвртац|ею 8 рукопис.

Робота виконана у Нацюнальнаму Теыпчному Ун1верситет1 Укракни

"КШВСЬКИЙ П0Л1Т8ХН1ЧНИЙ шститут".

Науковий кер|вник - доктор фшико-матэматичних наук

член-кореспонденг HAH Укра1ни, доктор ф1зико-математичних наук, професор Шор Наум Зуселевич, с.и.о., кандидат ф!зико-математичких наук Бшцыотй Платон Михайлович

Провдаа установа: Кшеський Ушверситвт imbhi Т. Шэвченко

о годин! на зас!данн1 спец1ал1зовано1 ради Д 01.39.02 при 1нститут1 к 1 (Зерне тики. 1мен! В.М. Глушкова HAH Украгни за адресок»!

252022 Ки1В 22, проспект Академ1ка Глушкова, 40. 3 дисертац|ею мокна ознайомигися в науково-техн1чному apiiBi тституту.

Асельдеров З.М.

0ф|ц1йн1 опоненти:

Автореферат роз 1 слано Вчений секретвр спец!ал1зовано! рада

В.Ф.Синявський

Эагалыш юрактсриотика дисертвц|йшм робота

Актуальжоть тематики 1 отушнь м досл1дтекост1 Анал1з математичних моделей, що використовуються в шформатиц1, доол1 джэнн! операщй, оучасшй теорп управлтня, економ1чн1й кЮернетиц!, приклада 1й ! обчислювальшй математиц!, св1дчить про ванишву роль ванкорозв'язуваних кошЛнаторних задач (ВКЗ) (задач! розп1знавання а класу гл1 та породкуваш ними задач! комб! наторю г оппшзэщ l), а такон ефактивних нвтод1в . tx розв'язання. Прийняття нпотези P^iJP, яке базуаться на iснуючих на сучарному этап! точних алгоритмах розв'язання ВКЗ, та теоретичш властивост! цього класу задач, що випливають з щвI г1пот93и, стрелять перед досл1дником достатньо складну проблему пошуку ноеих, ефективних, точних алгоритМ1в !х розв'язання. ОсновнI в 1 дом! ушверсальн! шдходи розв'язання ВКВ можна

9

класиф!кувати таким чином.

1. 1з доол1джувано( комбтаторнои задач 1 вид!ляють шдклас (визначений обмешннями, що накладавться на параметри щек задач!), для якого будувться пол!ном!альний точний алгоритм. Практична р9ал1зац1Я першого шдходу ютотно обмежена як малою к!льк!стю в1домгос на даному втап! шдкласмв комб!наторних задач, що пол1ном1 ально розв'язуються, так ! суттввою обмэженнютю з точки зору практики их математичних моделей.

г. Точн] метода розв'зання. Ця група метод!в базувться на травилэх В1дс!чень конкуруючих вар1ант!в, що побудован! на [деях Ч9Т0Д1В плок та граничь, в1Д01чэнь, посл!довного конструювання зар!ант!В, динам1чного програмування та ix модиф1кац1й. Головний 19дол! к Ц181 груш М9Т0Д1В при розв'язанш ВКЗ загального вигляду цостатньо велико! розмфност1 — статистично-значимо реалъний

обсяг обчислювань визначааться экспонентальним алгоритмом.

Э. Наближен] та еврисигчн! алгоритм». Створвння нвОлиженк або евриотичних алгоритм1в, що дають моклив 1 сть розв'язуват] задач! велико! розм1рност1. 1х практична ефектившст: перев!ря8ться на задачах меншо! розм!рност1 (шляхом статистичноп пор1вня1шя з точшм ршенням) 1 як юно обгрунтовувтьс: прийнятшстго закладених у них евристик. Ц! .эвристики породкуютьс; самою математичною моделлю та особливостями розв'язувано практично! задач!. Запропонований шдеид буде придатним лишэ тому ВИПЗДКУ, КОЛИ отршання ТОЧНОГО Р1Ш8ННЯ не в ПРИНЦИПОВ' необх!дним. Достатньо, у певному розушшп, "розумного" ршення В даному випадку, головне — цэ можливють його отримання дл задач велико I розм!рност!.

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

Мета роботи. Створвння нового шдходу до розробки точни алгоритма для важкорозв'язуваних комб1наторних задач досл1дж0ння його ефективност!.

Метода Д0СЛ1ДЖ8ННЯ базуються на поняттях 1 результата теорп алгоритм!в, теорп граф!е, теорп розклад1Е та метод! дискретно 1 оптим1 зац и.

Наукова новизна.

Введения поняття ГЩО-алгоритму для важкорозв'язуванс задач1 комб!наторно! оптим!зац!1.

Введения нового критерю оцижи ефективност! точнр алгоритмт для важкорозв'язуваних задач комбтаторно! оптишзац] Розробка та доел1дження ефективност! ЦЦС-алгоритму да

задач! "Максимальна незалежна множина" (МШ).

Розробка та досл!дтання ЦЦО-алгоритму для задач! "MiHiMtaautH сумарного звакенога моменту зшинчення роб!т, якщо в 1 дношвння порядку задано ор|ентованим ациклiчнлм графом" у сам!й загальшй постанови! (ваги можуть бути недодатшми числами).

Теоретична та практична щнщсть роботи

Розроблен! ПДО-алгоритми дозволяють статистично вагомо розв'язувати задач! "Максимальна незалежна множина" (МНМ), "Вершинне покриття" (ВП), "Хроматичне число" (ХЧ), "Эд!йсне;нн!сть" (ЗД), "Максимальна кл!ка" (Ж), "Розбиття на о1ки" (PK), "Гам!льтон№ цикл" (ГЦ), "Гамиьтошв шлях" (ГШ), "Шн 1м1збц1 я" сумарного ЗЕаженого моменту зак!нчення роб!т, якщо в!дношення порядку задана ор18нтованим ацикл1чним графом" (МВМ) цля випадку, коли параметри задач! МВМ модвлюються випадковим чином.

Публ!кац1» та апробацп роботи

Основн! результата по тем! дисертац!i опубл!коваш в одн!й лонографи, у 10-ти друкованих роботах i допов!дались на таких ганференщях: 3-я м!жреслу0л!канська конференщя молодих вчених га студент 1в, Украина, Кит, 1989 p.; International conference on system science, Wroclaw, Poland, 1992; III М!жнародна иуково-техщчна конференщя, Украша, Харюв, 1Э93 р.; 1-ша ^кракнська конференщя по автоматичному упраЕЛ!нню 1 автоматиц1, гкраина, Ки!в, 1994 р.

Структура та обсяг роботи

Дисертащя складааться з вступу, 3-х раздшв, висновк!в, ¡писку використанно I л!тератури (84- назви) та. додатку. Основну ;астину викладено на 145 сторишах машинописного тексту i 10

малюнках.

Зшст робота

У встуш обгрунтовано актуальнють розглянутих у дисертац! питань, коротко викладено змют роботи.

Розд1л I. ЦЦО-алгоритми для вазтарозв'язуваних комб шаторнгос задач, оонови к^одологи их побудови.

У цьому розд1л( визначено основн! теоретичн! властивост важкорозв'язуваних комбшаторних задач та метод1в кх розв'язання Коротко викладено теоретичн! результата, яю випливають прийняття гшотези 1УНР, 1, на IX основ 1, критичний огляд в1доми п1дход1в до розроОки точних алгоритм!в розв'язання ВКЗ.

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

Пол1нон1альний шдалгоритм Еизначавться сл 1 дуючт властивостями — якщо в проц9С1 розв'язання дов!льнс 1ндив1 дуально! задач! виконуються достутл для перев1рки 1 строго г.изнач9н1 лопко-анал!тичн1 умови, то дана довиы !ндав!дуальна задача мае точне ршення, визначене щ шдалгоритмом (складають шдалгоритму е ф1ксованим пол1номом в| розм!рност! дов1льноI !ндив1дуально! задач1).

Експоненц1альний шдалгоритм включав доступш перев1рщ 1 строго визначеш лог 1 ко-анал 1 тичн 1 умови, при виконанн! яких процес1 розв'язання дов1льна |ндив!дуальна задача стро1 декомпозуаться на шдзадач1 меншо! розм1рност!.

Ощнкою. ефектиЕност I розглянутого ЩС-алгоритму в Й01 статистична значимЮть, тоОто те, що при масовому модэлюваш

випадковим чином 1ндав!дуальних задач данои важкорозв'язуванок комбшаторно! задач I, отатиотично-значимо вони належать до мнакини полташальна розв'язувених шдивидуальних задач, яка вианачэна гошношально» складово» и ТЩО-влгоритму.

Розд1Л а, ВДС-алгоритм задач) "Максимальна незалеада

мноюша" (МНМ).

Множила верши?' графу С»(У,Е) називавться невалежною, якщо н!як 1 дв 1 вершини а Ц181 множили на а сумикнида. Тобто, якщо 5=У незалежнэ у гаф| 0, то породиений нею шдграф О(Я) а порожнш. Треба знайти незалежну множяну V', яка мае найбиыяу потуга(сть сзред усIX н&залежних мнозвдн графа в.

У цьому роздш роаглядаютьоя властивост! задач! "Максимальна незалежна множила" та залропановано алгоритм !I розв'язання, що в1дпов!даа вимогам ДЦС-алгоритму. Введемо так! визначення.

Виеначвния I. Поточною незалежною множиною - Ут1с в : на 1-й 1тераЦ11 алгоритму — побудована допустима незалежна множила; на к-Й |терацп алгоритму — поточна иеаалекна множила, одержана на к-1-Л (тераци алгоритму.

Визначення 2. Набрана нвзалекна множила на к-й !Т8радп ~ ?н1<;, цв дов1льна П!дмножина вершин, як! не вв1Йшли до допустимо! юзалекно! множили, та ЯК! попарно не ав'язан! в граф! в ребрам ик собою.

— це шдмножина вершин з 7тк, кожна з ягсих зв'язана

>еброМ в граф! О з вершиною а{.

Ствврдяйння I. Нехай ^ - це п!дграф графа в, побудований на 01х вершинах множинй У\(аи+1,...,аг). Тод! у'мк+м в ршенням

I-6-К(, 7

задач! ШШ для графа в*.

Ствердження 2. Нехай для дов1льно! шдмнокини вертя {и ,...,и } з множини {и.,...,1»7 ,а) виконуеться УткПУтк=0

га 1 1к-1 к и^ и{

• Тод1 множина Си, не а полтшуючою.

Я* ^ 1 Щ

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

с Уки{ак), V = 7тк такого, що (7тки7')\и' - незалежна множил та IV |—1С* |>0, е:

I. V" - набрана незалехна множина, д£"=0» 2. V гкс 7 '

V ^ у„

-(е 7", (Uj.a^Jji Е, де 7"=У'\{ок}.

v,

Визначення 3. Вершина с^ мае покриття на k-й трацп, якщ

!снуе множила VHkcF\{ak,ak+1.....ar>, для яког А^=0 та для v и%

7^ виконуеться: v^ t не юнув вершини з 7Hk, зв'язано! у

граф! О ребром з с^, тобто с t для v t>{«=7Hk (ut»aKX Е

рУПк _ У ^ уТк_

Ствердаення 3. Нехай при виконенш bcix вимог теореми !снув покриття V для вершини а^., та в така шдмножина 7" с у що для кожнок и вершини и, в mhosmhi 7£k\7Tk юнуе хоч одн

I с с^

вершина, яка зв'язана з ut ребром, та б!льше не зв'язана в гра$ 5 Hl з одн!ею з Еершин мноиини V'XiUj}. Назвемо п 1зольованок Тод! множина 7'\7" s також покриттям верши а^.

Визначення 4. Множина S&Vk називаеться зачкненою, яга: VleVgk, з IteS, iteS, u/v: (и, t (V,l)<=E.

Визначення 5. Замкнута множина S називаеться максималънс замкненою множиною, якщо не юнуе такои замкненои множини S' S'С v s с ч», що Э под1л S' на S та Р такий, що S U F=S', 7gk 7|k=0.

Сгвердження 5. Нехай з , що виконуеться

Л {и} = 0. Тод1 вершина с^ не мае покриття.

Висновок. Вершдаа а,, не мае покриття I в тому випадку, коли э

П {и} = {и}, але (и.,и)«Е.' VJ }

Ствердаення 6. Нэхай для вершини и{еУк виконуаться тана

рмова: з и^и^"^-. У*к Л {и1)={и1}, п 1 для *

такок, що У*к П {и2} = Ыг) виконувтьоя Тод)

зершина не налагать до нокриття а^

Висновок I. Нэхай виконувтьоя умова стверджання б та для V . 1 (иг,и В цьому випадку вершина а^. на мае

юкриття.

Висновок 2. Нехай вершина у{1 задовольняе визначенюо ¡те^рдження б та юнуа р вершин t=гTp, таких, що (и^.и^еЕ, ;=Т7р. та

!) для V ии Iснуз вершина Ц^У^, така, що (ои,иг)^Е;

2) для v tt?^Jt, (и^,иг)=Е, виконуеться (vit^VJt)^sЯ^

'од! покриття для вершшш с^ на (снув.

Ствердаення 12. Нахай на деякому крощ побудована замкнена

гаожина З'^З, тана, що 5 — це ранние побудована

к к

амююна множила. Тод1 продовження процедур алгоритму приведе до ойудови максимальная замкнених множин {5"}, кошна з яких бов'язково в складовою элемент!в мноюши де У'®1к —

аксималып замкнен! множит, як1 вмщують 3.

Теорема 2. Якщо на к-й 1 терац! г юнуе шшпшуюча множила для

ноши Ук 1 У111, то така множила юнуе також 1 для пари ^ДЯа^},

тк, дв мнохкни Ук та Утк утворекн! июля проввдення

екв1 валентно! замIни в мноюшах та Утк.

На баз! вшца розглянутих полокень розроблено ПДО-алгори1 розв'язання задач1 МНМ, якиЯ Мае теку структуру: побудов допустимо! нвзалекно! множини, упорядкування залишку верши вIдпов 1 дно ¡х зв'язноотч з побудованою допустимою незалежнс мнокиною, !терац!йна процедура побудови покриття для вершивд а^ додано! до 7 на розглянут!й !терацп. Суть роботи алгоритму в конн1й 1терад!1 полягае у перев!рц1 теоретично! можливовд включения на данн1й !терац|! вершини, яку розглядаемо, I поточно! дону стаю! н83вл8жн0! множини. У випадку п03итивн01 результату виконуеться корекц1я допустимо! незалежно! множили I як насл1док, II потужшсть абиыпувтьоя на одшдщю. Утг -поточив незвлежна множила, що одержана на осташлй (тераци I рнпенням задач 1 "Максимальна незалекна множина".

Алгоритм побудови покриття вершини с^ складаеться сл!дуючих процедур: пол!ном1альних процедур визначення вершш як1 напевно входять чи не входять в покриття вершини с^ — гш алгоритму В1-ВЗ, В42-В44; побудоЕй масив|в зв'язност1 Евршин множин Уяк, У7* 1 Ук — плка В1; находкення масив!в м1н!мальнс доезяши — плка В41 та сукупност! вершин, як! додаються до V1 на кожному кроц! — г!лка В4Б; процедур! побудови замкнених ч ес 1х максимальних замкнених шокин -- плки В5 I В6; процедур пошуку покриття для кокно! максимально! замкнвно! множили ас визначення факту його в)дсутност! — плка В7. Теоретич! оОгрунтування лог1ко-анал1тичних умов полшом1альнс алгоритм1чн01 процедура побудови максимальних замкнених мною (приведених та обгрунтованих в дисерташйнШ робот!) - умови 1-та ствердження 13 для В5; В61, умови 10-12 для В6; знаходкеш

псжриття (або встановлення факту його в!дсутност!) для кожноI максимально! замкнено* множили ~ умови 13-15. Теоретична ОбГруНТУЕЭННЯ логiко-анзл 1 тичшя углов пол!ном1е.!ьно[ склэдоео! ПДС-алгоритму задач! МНМ 1 точно г декомпозицп виидног задач! на шдзадач! мэншо! розм1рносп в стверджэння 14 та умови 16,17.

Розроблено методику доол!джвння статиотично! ефективност1 запролонованого ПДС-алгоритму (як усередненот характеристики його ефективноси) для важкорозв'язуввних задач комб1наторно! оптимоацп "Максимальна нэзалежна множила", "Вершинне покриття", "Хроматичне число", "Вд|йсненн1сть", "Максимальна кл!ка", "Розбиття на юлки", 'Там!льтон!в цикл", "ГаМ!льтон1в шлях".

Як наел!док проведеного статистичного моделювання встановлено, що запропонований ЛДС-алгоритм в статистично ефективним для задач МНМ, ВП, ЗД, ХЧ, РК, МК, ГЦ, ГШ, як1 моделюються Еипадковим чином. Цей висновок стэе насл|дком анал1зу результатов проведэного статистичного досл!дження.

1) Пол1ном!альна складова ЩО-алгоритму задач 1 МНМ статистично-значимо точно виршуе дов!льну !ндив!дуальну задачу МНМ, н9ор!знтований граф яког мае тану характеристику середньоарифметична стушнь верппш графа знаходится у межах 0-8% або 35-100% в!д ступен! графа; !ндив!дуальна задача МНМ з середньоарифметичшм ступеней вершин графа у допазош 1755-25% статистично-значимо вирппувться експоненц!альною складовою ПДС-алгоритму задач! МНМ.

2) Для задач 1 ВП' характеристики ефективност! повнютю епшпадають з поданим) в п.1), а задач! МК ц! характеристики виконуються для додаткового графа.

3) Задач! ХЧ, РК, ГЦ, ГШ при зведэнн! !х до задач! МНМ

статистично-значшо знаходяться у межах 0-1 ОХ; шдклас шдав!дуалышх задач "ЗД", зведених до задач) МШ у межах середаьоарифыатичноI ступен! вершин 0-10%, не в виродкеним.

Необх!дно в1дзначити, що при розв'язанш ГЩС-алгоритмом будьяко! дов1льно1 1ндив1дуально! задач! з наведених клао!в, заввди в1домо, чи а одержана ршення точним, чи Н1.

Розд1Л 3. ДЦС-алгоритм задач! "М!НШ!звц!я сумарного зваженого ыошнту закютення роб!т, якщо в!дношення порядку задано ор1ентованим ацшшчним графом" для випадау, коли параметри задач! №М моделюються Еипадковим чином

У цьому розд1л1 подано алгоритм виршення задач! МВМ, який задовольняе вимогам ЦЦС-алгоритму, для випадку, коли параметри задач! ЫВМ моделюються випадковим чином.

Частково упорядкована множила J={Ji,Jг,...,Jn) завдань, як! почипаючи а моменту чаоу <3=0 обслуговуються одним приладом. Завдання обслуговуються баз припинення, не б1льш н!ж одна одночасно. Необхюто знайти таку посл!довн1оть обслуговування завдань, для якои сумарний зважений момент завершения Еиконання завдань 8 м!н1мальним:

л

Р = V щ. о. -> т1п (3.1)

'ск]

де ш, — Д1йсн1 числа, с, — момент завершения виконання ' ^ [к]

завдання, яке ааймав у допустимому розклад1 к-у позиц1ю, I к }

с. = У г, (3.2)

Ск] а= 1 [1°

-I - в!дношення порядку, запис означав, що робота } займав

у розкладi g-ту П03ИЦ1Ю.

Стверджэння 1. (Отримано С1дневм Дж.Б.). Пехай на множин! перестановок Р задано функцюнал

Т(П)=У V. с, .

" fiel Jrkl

'[k] J[k] k=1

Тод! для дов1льних перестановок Я'=(П(1>,Л<а\л(Ь,,Я(г)),

я"=(я(1),я(ь),л(а),я(г>>, (3'3)

як) належать Р, юнуэ функцюнал /(/7), який задовольняе таким властивостям! з умови /{Л(а)) > /(Псъ3> випливаэ F(ff') < ?(Я"), а з умови /(П(а))= /(iï(b)) — piBHicTb Р(Л') = Р(Л").

Р(Л) = ^¡Г wjy/ ]Г прюритвт перестановки Я.

./е(Я)

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

а) першою виконуеться шдмножина с J, (J — множила вcix завданнь), яка мае максимально можливий прюритет, тобто

P(S, ) > Р(У), VU с j/s^;

б) шдмножина Sj вмицув максимально можливу юлькють завданнь, при умовî виконання нер)вност1 пункту а);

в) другою виконуеться шдмножина S2>- яка задовольняе вимогам а), б) на множинi завданнь J/S^ i т.д.

Теорема 1. Оптимальний розклад в Р-впорядкованим (теорема отримана С1дневм Дк.Б.).

Теорема 2. Як ¡до вдаошення порядку задаеться посл|довно-парэлельним графом, Р-впорядкований розклад . е

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

Ствердаевня 2. Яйцо в допустим iй посл!довност| о для

незалежних ланцюгш завдань сИ/(г3.....A«]'' ^^[вГ-'-'Ля'®

де fir, виконуатьоя P(a(J[g]))) та справедлив! сл|дуюч!

умови: якщо J£t)]H P(J[f]), то ^ РфЦ я^0

[U]

J

[М

тод! у прюритетло-впорядкованому розклад! ланцюг завдань P(J[f]) мае виконуватися ранюе, шж ланцюг завдань

Ствардвення Б. Нахай посл!довшсть, яка вмицув п!доосл1довнють о1 U в р-впорядкованою. При виконанн!

умовя í(a(Jtel))>P(p(J[í.])) в прюритвтно-впорядкованому розклад! поаиц11 М1ж ланцюгами завдань P(JlfJ) та <*(./1в]) можуть займати т 1льки ланцюги завдань zU[g]). г>q>f, для якйх справедливо

де Оа(/ ) = J>(J) t Ia(J. .) = Е Ш) .

Стверддеяня 6. Нахай s Шдпосл!довн1сть а та сукупнють п1дпосл1довностей G(a1,...»cijj.) (сц,...,^ — не зв'язан! по графу шдпосшдовност! poOlT). Тод! об'вднання п!дпосл!довноотей до яких належ!Ть а, що мають мвксимальний прюритет, визначааться сл1дуючим правилом.

Будуемо посл1довнють роб!т 01:

СГ <a(,)'a(2)'"-'a(k))s р<а<п> Р(а(г)) >... Р(а(к ,), - P(aÍJ}) > Pía), J » Т7Б. 4cLj « О/С,, P(aj) < Р(а).

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

a(J) 3 Р(а + £ a(J)), t=T^T (3.5)

1 J=1

р+1

а(Л) < Р(а+ V а(Л). J=1 7=1

Ha основI викладених вшцв результата та додаткових

теоретичних досл!джень, приведение у дисертатйшй робот!,

побудовано орипнальшй шшном1альний 1тэрац!йний алгоритм

розв'язання задач! МВМ для в|дношення порядку, звданого

посл!довно-парал9льнш графам, який декомпозуз граф на множили

максималъних прюритет!в та буду а оптимальний розклад для кожно!

тако! множили. Введено поняття просто! та складно! конструкцШ,

як1 в узагальнвними р-ЕПорядкоЕЗНими структурами мнокин

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

На основ 1 даного алгоритму побудогано та обгрунтовано

ДЦО-алгоритм розв'язання задач1 МВМ для дов1льно визначених

параметра задач 1. В алгоритм! введено розширене поняття просто!

та складно! конструнц»й для дов!льного графа ! використовувться

процедура отримання оптимального розкладу для задач! з мэншою

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

У дисертац1йн!й робот! запропоновано I обгрунтовано

лог!ко-анал!тичн! умови, виконання яких на кожн1м k-м крощ

роботй ГЩС-алгоритму реал!зув його пол!ном!альну складову.

Розбиття початкового розкладу на множит максималъних прюритет1в

рэал1зув декомпозиц1йну плку ДДС-алгоритму. Все ж необх!дно

заувакити," що, як показали таоретичн! досл!дження t результата

статистичних эксперимент!в, пол!номlaльна складова ЦЦО-алгоритму

Р(а +

задач! МВЫ а статистично-значимою лише для масового дов!льного моделювання графа часткавого впорядкування, ваг I тривалостей завданнь.

У висновках викладено основн! результата, як1 отриман! в дисэртац!йн1й poöoTi:

- Введено визначення ПДС-сигорилиу — алгоритму точного роав'язання важкорозв'язуваних комбшвторних задач.

- Введено ноеий критер!й ощнки ефективност! точних алгоритм1в для ваккорозв'язувених комбшаторних задач.

- Досл!даано властивост! NP-складаок задач! "Уанаилал ьна неасиежня лножиха". Знайдено та теоретично обгрунтовано умови, яким задовольняа п оптимальне р|шення.

- ПоОудовано 1 теоретично обгрунтовано ПДС-алгоритл розв'язання задач I НИМ.

- Роароблено методику досл1дження статистичног ефективност! аапропонованого ЦЦС-алгоритму (як усереднено! характеристики його ефективноот!) для важкорозв'язуввних задач комб!наторно! оптим1заци "Максимальна незалежна множина", "Вершинне понриття", "Хроматичне число", "Зд!йсненн1сть", "Максимальна кл|кая, "Розбиття на кл!ки", "Гам!Льтон!в цикл", 'ТамиьтоШЕ шлях". Визначено його статистичну вфективнють для цих задач.

- Розглянуто КР-складну задачу "М1н1м1зац!я сумарного зваженого моменту зак!нчення роб1т" у сам1й загальн1й постанови!. Досл!джено теоретичн! властивост! як само! задач1, так t и оптимального ршення.

ч Побудовано та теоретично обгрунтовано ПДС-алгоритл розв'язання задач! МВЫ, який в статистично ефективним, коли параметри задач! МВМ моделшоться випадковим чином.

За темой дисертацп опубл!ковано наступи! робота:

1. Конструктивные полиномиальнне алгоритмы решения индивидуальных задач из класса №. / А.А.Павлов, А.Б.Литеин, Е.Б.Мисюра, Л.А.Павлова, В. И.Родионов. - К., Техника, 1993. -126 о.

2. А.А.Павлов, Л.А.Павлова. Принцип суперпозиции эталонных алгоритмов. -К.,1994, Дэп.в УкрНШГГИ 01.10.94, N430 - Ук 93.

3. Павлова Л.А. Алгоритм решения задачи "Максимальное независимое множество". — К., 1993.— 58сi — . Деп. в УкрНИИНТИ 29.06.93, N — 1277 — Ук.ЭЗ.

4. Универсальный алгоритм решения задачи "Минимизация взвешенного момента окончания работ при отношении порядка, заданном ориентированным ациклическим графом" / Л.А.Павлова, Е.Б.Мисюра и др. - К., 1992, 58с. - Деп. в УкрНШГГИ

05.05.90, N 569, Ук.92.

5. Эффективные алгоритма полиномиального сведения задач распознавания из класса NF к эталонным задачам / А.Б.Литвин, Л.А.Павлова и др. - К., 1991, 54с. - Деп. в УкрНИИНТИ

04.07.91, N 9S4, УК.91.

6. Эффективные частные алгоритмы сведения сведения индивидуальных комбинаторных задач из класса NP к эталонной задаче / А.Б.Литвин, Л.А.Павлова и др. - К., 1992,19с. - Деп. в УкрНШШТИ 14.02.92, и 169, Ук.92.

7. А.А.Павлов, Л. А.Павлова. Нахождение дополнительных условий полиномиальной разрешимости задачи "Минимизация суммарного взвешенного момента окончания работ при отношении порядка, заданном ацикличным ориентированным графом". III Международная научно-техническая конференция. Метода

представления и обработки случайных сигналов и полей. Тезисы докладов, стр. 121, Харьков, 1993 г.

8. А.А.Павлов, Л.А.Павлова. Принцип суперпозиции эталонных алгоритмов. 1-я украинская конференция по автоматическому управлению, автоматике — 94, Киев 1994 г. Тезисы докладов, часть 1, стр. 210.

9. А.А.Павлов, Л.А.Павлова."Основы методологии проектирования ЦЦС-агоритыов для труднорешаемых комбинаторных задач"—Кизе, 1995 г, Проблемы информэтшш.и управления, No 4, ст. 135-141.

IQ. A.A. Pavlov, A.B. bitvin, Ь.А. Pavlova."Efficient reduction of different intractable problems to the "Heference ргоЫетз" — Sequencing jobs to minimize the total weighted completion time Bubjeot to preceding constraints". International conference on eyetems eoienoe, abstracts of papers, p.119-120, Wroolaw, Poland, 1992.

Павлова Людмила Александровна "Разработка и исследование цца-алгоритмов. для труднорешаемых задач комбинаторной оптимизации". Работой является рукопись на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические осноеы информатики и кибернетики (математическая кибернетика).

Защита состоится " "" " 1996 г. в часов на

заседвнии специализированного совета Д 01.39.02 при Институте кибернетики имени В.М. Глушкова HAH Украины по адресу г. 252022, г. Киев 22, проспект Академика Глушкова, 40.

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

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

Pavlova Ludmila Alexandrovna "Development and study of PDC-algorithms for Intractable problems of combinatorial optimisation". This scientific work is a manuscript to submit thesis for candidate of physics and mathematics sciences in speciality 01.05.01 - theoretical bases of informatics and cybernetics (mathematical cybernetics).

This manuscript deals with creation of exact algorithms for Intractable combinatorial problems. These algorithms are baaed on the ideas of extraction of polynomial and decomposiotional

components (PDC-algorithms). Author presents two PDO-algorlthms

>

for "Independent Set" problem and "Sequencing jobs to minimise total weighted completion time subject to preceding constraints" problem and results of the study of their • statistical effectiveness. .

Ютов! слова: . важкорозв'язувана задача комбшаторно! оптим1заци, ДЦО-алгоритм, ствтистична значим!сть, максимальна незалзжна множина, покриттй, замкнена множила, м1н1м!зац!я сумарного зЕаженого моменту закипания роб!т, р-впорядаованють, поелtдоЕНо-паралельний граф, конструкщя.

4г