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

М1Н1СТЕРСТВ0 осени УКРЛ1НИ КШВСЬКИЙ ШВЕРСИТЕТ 1М. Т.ШЕВЧЕНКА

6 0/1

На правах рукопису ГНАИеНКО ГригорШ Миколайович

УДК 519.62

АЛТОРИТМИ ОВРОБКИ ЖСПЕРТН01 ШФОРМАЦП В ЗАДАЧАХ РАНЖУВАННЯ ТА IX ЗАСТ0СУВА1МЯ

05.13» 16 - застосування обчислювалыю! техШки, математичного моделювання I математмчних метод! в у. ийукових досмидженнях

АВТОРЕФЕРАТ - дисертащ ! на эдобугтя вченого ступени кандидата тешчних наук

К;пв 1994

Роботу виконано на кафедр! теор!I автоматизованих систем факультету кЮернетики Кшвського ушверситету 1М. ТАРАСА ШЕВЧЕШ

Науковий кер1вшпс:

- доктор техн!чних наук,

професор ВОЛ МИШ О.Ф.

ОфШйн! опоненги:

— доктор ф! зико-математичних наук, професор мшлевич м.в.

- доктор техшчних наук С1Ш 1-Х.

Пров!дна оргайзашя: - КБ "Шторм" при Кшвському

шш техш чкому 1нстатут1

годим на заспданн! спзш ал1зовано! ради К 063.18.10 'в Кшвському ун'верснтет! !м. Тараса Шсвченка зэ адресов:

252!27 Кшв 127. проспект Академ!ка Глуикова, 6, факультет кЮернетики, ауд.42.

1з дасертатею коша, ознайомитися в науков!й ОЮлЮтеЩ Кшвсысого ушверситету 1м.Тараса Шевченка (вул. Володи-мирська, 58). •

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

Вчений секретар спе щ ал!зевано! ради, доктор гели чних наук

ЭЛГЛЛЬНД ХАРАКТВЙЮПША РОВОТИ

AxïyajibHlcTb теин. Дисврташйяа робота црисвячена питаниям роз~ робки алгоритм! чного та проррэмного забезпзчешм деяких задач прий-няття Р1.иень та ксделювашхя конкретних прщ<ладних задач. Основу математшшого апарату, лкий застосовувався пш робот! над дисертаЩ-ею, склаяають так1 науков! напрядай.

В силу теяденаП до optetrrantï проградеюго забозпечення на Бикористашя екскзртам 1нФормац1! зростае роль фах!вця в процес! автсматизованого розв'язання задач. Проблема ефективного залучешш е'ксперта в процес розв'язання задач! е актуальною,осшльки нзобхшю використсвувати евристику для адекватного мод-эдювакня процес!в, ао автоматизувться. Тому, питаниям одеряанкя та анал!зу експертно1 1нфо-purautï в роботах М.А.Дйзермана, О.И'.Лар1ч«ва, Б.Г.Литвака, Б.Г.М1Р-к!яа, М.ВЛЛхалевета.В.I.IkHtотто, Т,4.Сазт1, ЮЛ.Саснко, Н.В.Хова-нова та lKimx автор! в придЬчлеться pejsma увага.

В останн! д<зсяткр1ччя активно розробляеться t добре зарекокен-дував себе б ptsHiw областях дауки та народяого господарства багьто-критер! альний п!дх!д, цо дозволяе засюсовувата мат'еизтичшй апарат з шкористаяням евристики. Тут доречяо визначити роботи Ю.Б.ГермвЯ-ера, В.Л.Волховича. В.1.1р1Кова, В,С.Шхалев(па, В.В.Под!новськогс, М.е.Сулуквадгзо то 1н.

В задачах з великою обчиелввалько». склада сде> уешзно застосо-вуаться схеж поел!доеного aitajttзу вар!зн?!в, ззгальнпй форматзм яког запропонований В. С. Ut хале алчем га И.З.Шором t розроблешй В,Л.Водксгичш, О.Ф.Волоншюм, АЛ.Куксо», В.В.Шдурбою та !н.

Побудоаа моделей, катод'в, алгоритме та преграмного забезпе-чечня конкретшх прикладах задач прийзшття р1к<зння з викориотанням вкззаного натематичного апарату, мое вяжляве шродногосподарське гнатеаня I сз!д<и:гь ïîpo актуальн! сть wmk доолЕетзнь.

Мзта роботи. Розроска та согр/нтувачни моделей та об'шелаваль-ннх м-зтед!в розз'яйзкня ^адзч рг'нжуванкч сб'ектмз та «Зрсбкд експер-iuc>i tнформаш I,сгворекия выдов! диого алгоритм! чного та програчного забззнечения.

йатода досл1/г;0:-п'я, Тесрзтиэисп основою достджэи:. по те?« дк-сврташЯно! рсЗоти стяла праш rcpoeîsrax. вггчкэкшиг. та заруб!яяих вчвних в cctaüovi KPto.ii в ¿згатскрнтер! ялгоо t оптимзаШ ï, теорП виСору а ' ияйЬдагя рпвеиъ, пен поел; дог,наго «над!зу вар!ант!в, катемаиинорс програмува;-.:!.;, суч-ч-лвы jtnfctWHt flma тохнолог1й.

Науксс» новязпа. R.n«"í¡rtt кпШ л '.fan'-î, >m ¡а^П'.туеться в pcefoït,

i-i-.ЗМГ.Ь.-»:'.;!. if!4

- г -

включае метрики, критер! i, форми представления даних для запропоно-вано! модел! та постановки задач, як1 найчасЛше використовуються в тзори крийняття pimeiib I зустр!чаиться в рхзних роботах, але вперше наводяться в систематизованому вигляд!.

Алгоритм розв'язакня iioBoi задач1 знаходження результуючого (кош;рс;,',1 сксго) раижуваппя об'ект!в в багатокритер!альшй'постанови! корнд з алгоритмами розв'язаиня в1домя. постановок задач знахсдаення межаня Кемегп-Снелла та кезз!порядку, найбликчого до заданого цикл!чного в1дношення переваги, побудоващ з внкористанням розробле-нмх автором процедур анал!зу структур;! сшарних в1дношень, осиованих на схемах посл1довного шал! зу eapt aim в. : •. - .

ЗапропоиоваШ алгоритш непрямого задания !нтервал!В зм1ни сагових коеФ1ц1ент1 fj об'ешв та стабШзацП переваг .експерта, ор?.ентоваш на неповпу метризовану матрицю парних пор1внянь, можуть слугувати.шроя компетентност! _ ексшрта або вистуггати точною апрок-снмашею пареваг експерта в простор! вагових коеф1ц1ент!в.

1грсвз модель оптимального спостерекення за трупов об'ект!в од. ним пе-росл1 дувачем в Оагатокритер1альн1й постанови! дозволила побу-дуватн тренакерний програмгшй комплекс для допомога особ!, ио прий-мае piеоння,переел! дувати групу гравщв в складн!й 1гров!й ситуацП.

Практична ц1нл1сть робота полягае в створенн! математичних моделей, алгоритм!члих та програмких засо01в для розв'язаиня конкре-тних практичних задач:'

1. Програмлого забезпечення задач обробки експертно! 1нформацП в склад! ыодуд!в знаходження результуючого ранхування об'екпв, задания переваг на множил! об'ект1в та визначення кошетентност! екс-'церт! в в середовищ! ОС реального часу СМ ЕОМ та-в сереловищ! MS DOS

ibh.pc.' . ; . :

2.' Д1 а логово i системи КОРСАР,-яка викорнстовуеться як тренажер для Ш1'ац11 продеру оптимального спостерекення за групою-об'ект!е та 'навчання користувача прийвяттю складного ршення в режим! реального часу. . ,

о. Комплекса 1 нструшнтальних ззеоб]в синтезу д!адогових систем з базових функщоиалышх модул! в на баз! СМ .ЕОМ в середовищ! ОС реального часу. '

Дисерташйна робота виконувалася в рамках загалыюсо'юзйо! нау-ково-техк1чао1 прогреми 0.26(1986-1990 pp.) "Обчислювальна техшка", завдання 0.80.03, "Створити нов! га розвивати д1юч! САПР та АС1Щ в народному господарств! (АвтоыэтизаЦ!я доел!джень)" ■ (Додаток №73 до

- з -

Постанови ДК СРСР з науки та тешки та АН СРСР в1 к 10.11.1985 р. ■£537/137) за держбюдазтними науково-досуц дат темами кафедр моделю-вання складних систем та теорП автоматизованих систем факультету кЮернетики Шнвського университету 1м.Т.1Пэвчен1«а, а тзкож за рядом госпдогов!рних тем. .

АпробацХя результат1в робота. ОсновШ положения й результата робота допов!далися й обговорювалися на:

Проблемному сем!нар! Шституту г!дроакустики < Пущин, 1987-1988 ): Науково-техн!чному сем!нар! Центрального науково-досл!дного (петиту-ту 1м. Крилова (Санкт-Петербург,1988,1389); Науково-техн!чному сем!~ нар! В1йськово-1нженерного 1петитуту 1 м. МотаЯського (Санкт-Петербург, 1989,1990);Республ1канському сем!нар1 Кауково! Ради з проблемы "К! беряетика" Ки!вського УН1 верситету "Молелюзання та олтим! заш я складних.систем" (1987-1993); Науковому сем!нар1 кафедри теор!1 автоматизованих систем факультету кибернетики Кш'вського ун!верситету (1990-1993); Республ!канськ!й конфзрент! "Бпровадаення САПР шлях вдосконалення Игаенершн прац! та якост! розробок" (В!нниця 20.062.07.1987); 8-й Всёсоюзн!й конференц!I "Проблеми теоретично! к1бер-нетгаот" (Волгоград, 19Э0), М1)тародшй конЗеренШ I ■ "Интеллектуальные •системы поддержки принятия решений и многокритериальная оптимизация -'НЕБ'92" (КацавелЬ 1992).

Публ1кац11. По тем! дисертацП опубл1ковано 19 роб!т. Структура та об'ей робота. ДисертаШя склалзеться з вступу, чотирьох розд!л!в, висновк! в, списку л1тератури та додатку.

3>ЛСТ РОБОТИ

. I вступ! обгрунтовуеться актуалън! сть теми яисерташ I, виклада-еться короткий зм!ст роботи та наводиться аиспаЩ г оеновши результат! в. .

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

В §1-1 наводиться модельна ситу-'¡ц! я та основш поняття в задачах прийняття р/шення, •

Задано множинУ-З п об'ект1в (вар!ант! в,альтернатив,план!в тощо)

' аг * д. :> « (1.....¡О-!!. (1)

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

ау=(а^,....а£) « А, V « и, (2) ••

яе aj[, veH, цсм={1,...,ш}, - значения параметр!ß v-r-o об'екта,

Для кожного параметра можуть бути в!дом1 ( &бо визначатись ) вагов! коеф1Шенти ix вШгосно! важливост! -

Pi.-..Р^ ' (3).

а також задан! . напрями оггоаИзацП параметру. Мнокини !ндокс!в параметр!в, що максим! зуються та тнх.що м!нШ зуються,' позначимо BiijiDBlÄHO через Mt та К2, М,!-'Мг=М. . '

Група. що складаеться з к експерт1в (ос!б,що приймавть Р1шения, внборщв года) • в межах одн&ковж для вс!х обмекень - (напршшад, вказ!Бки про KiJibKlcvb oö'eKTiB, ко мають бути вибраш, про cnöctö ранвування oö'cktIb, вэтляд вих1дшй 1 вформат i тошо) задае (ошкюс ) 61 норн! в!лкоь'ешш на мяокшн об'ект!В Онколи кажуть, во В1 дношгшя роаглядаються у- заздаяоп дь Ф1 кссваному кдас!; для простота ц! Шлношення та BiÄltobtMl 1м матриш гозначаемо однаксвими символами) $ iel={l,...,k).. (4)

Можуть' оутй 'такой задан! кос-ФШенти компетентност! експерт!в Сьэгя", квалШкаШЬ .felßHöctof ерудованост!,'важлйвоот! експерив, ефективност! мстод!ь нар!Шй(на «0Чкт1в. рейтингу турит в i тлн.)

.....(5)

Сл1д в!азтШШ, ¡80 I й (?.), f-i) Mose буги як объективною

(результата вим1Ш1аш»на1Рвй1аД) .так 1 одержано» ыд ексиерт!в. 1нформаи!я (ЗМ&). йк йр'звмо» was еврасмчний характер,

Наводяться гакох основа! вгш Шал емрюзалня, як! винористо-вуоться в задачах прийняття püsemmS способа ПорГеняння об'ект!в: види пегетворень значень параметр!В . об'ект!в до безрозшриого внгляду: м1рн йпизькост! ш» сб'ёХТаМЯ (1) та вШюиегаями (4). Вводиться пспяття ефектиЕного оО'скта.

В SliS ■ наводятьоя основа! способа агрегуванвя тформаЦП та на!5б!льа поширен! прдашти оптшальносп об'шчв. Розглядаються також plsuL аспекта поняття УЗгодхеност!,

В §1.3 пропонуетьея клэсиф!кашя SäAai у постанови! (1)-(5) за и!лями, ко стоять пер?д дослщшком, та за взглядом bxIjhoi та вих! дноi шформаиП. ' '

В gl -4 розглядавтьс'я мокливосй людитог в задачах екгпертного оцтгвання.

Роздал Z присвяченкй omiCQBl . використання схем поел!данного ангзл! з.7 вар1ант1в та методолог} i Оагатокритемально'! оптимьззЩ] в задачах ранку ваши сО'екИв.

Задач) рэикуьашш (упорядкування множили oö'cktib зз степеням

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

Практичне . застос.ування задач ранжування дуке р! зноман! тне. Так1 задач! виникають.наприклад, при розв'язанн! проблемы визначення поел!довност! завантакення та розвантаження транспортного косм1чного корабля; виявлення поел!довност! усунення несправностей деяко! сис-теми; комплексному анал!з! якост! продукт!; анал!з! характеристик продукт I га вид!ленн! головяих показник!в якост!; виявлення вузьких М!сць в деяк!й складнШ систем!, яка мае так! властивост1 як ст!й-к!сть (наприклад, кивуч!сть), керованЮть, самооргаШзац!я; проекту-ваиня канал!в зв'язку ы!ж вузлами в Iнформац!йно-обчислювальних мережах; експертного ошнювання р1зномаштних проект!в розвитку деяких галузей чи наукових досл!джень; планування забудови житлових район! в тоню.

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

Нехай маемо модельну ситуац!ю у постанови! (1)-(5).

Елементи матрчць Р1 найчаст1ше внзначаються таким чином 1, якщо а,,} а^,

О, якщо ' н^," а^ або ^=11, (6)

-I, якщо а„( ■ "

Рщ+ РщпО, V г.,Т1=1.....п, т^г}, К,

де "I", """ - символи Б!дпошень в1дпов!дно переваги та Р1 вноц!шюст1 м!ж оО'ектами.'

Для вим!рювання в!дстан1 м!к в!дношенням Р. що задане експертом та вшюшеняям Н.що в!ДПов!дае результуючому ранжувашж.будемо вико-ристовувати найШльш поширену в цьому клас!: задач метрику Хешнга

- Ч(Р.И)4 Д ' V'

де р^. г^- елементи матриць в!дпов!Лно Р та-Я.

/Ооилькй-матриц! вщношень Р та и кососиметричн1, ¡х можна записати у Тзигляд! вектор1в. С та К з компонентами

... ,:.Гругг х гпг

)у/2. К V < т) $ п.

2-э<1моплешгя 188

: '' ' .'■■~б* ' ■. ;." ;■. ..:

Тод! в1дстань Ml ж в1дноаеннямк Р та Н запишеться у вигляд!

N .

d(P,E)= I I c.¡- х-,1 . - де Н=п(п-1)/2.

В1домо, що нестрогим ранжуванням 1 т1льки ¡м в[дпов1дають авдкл!чн1 ,в1дноиення на множшп А. ,

.Означения 2.1./Ашжл!%™ в1 ¿ношениям, на А називаеться повне б1нарне вютошення R, уякого строга компонента R(s) не мае цикл!в: не 1снуе посл1довност1 об'ект!в а1,аг',...,аТ1тако11що ■ atR^s'at+j;

'.-•-!.....Т-1 та a^R^'aj. ,■'.."..■

Зауважевня 2.1. У випадку, що розглядэеться.в силу шастгвостей матриць з, елементами вигляду (6), вимога -в1дсутност1 цикл1в екв!валентна вим031 в1дсутност1 1шкл1в довкшш 3 (?-3).

Позначимо через J=(l,...,N> мнокину ¡ндекс!в елементГв вектор!в О - " ■ н

вигляду (7); X -;множин.у вс!х можливих вектор1 в вигляду (7), ID1=3

D1 - множину вектор!в вигляду (7),як! в1дпов1лають ацикл!чним в! дно-

ао * 1 ' "

пгевдям D СХ ; c¿-j _ j-y компоненту вектора, побудованого за матрицею

Р , задано» 1-м.експертом.. ■

В §2.1 розглядаються процедури посл1 довного,акал!зу вар!ант1в,

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

необх!дн! означения та. твердкення. -■■.'.. ■

Розглянемо, ланшожок об'ект!в а; ,а,- ,а,- • з заданими стволами

, 1i Ja J3

в!дношень х={ {, ~ } м!ж ними ....

• '-а,- * a.- it а. ij.,ia.i3 « ti ,...,n>.

J-j хз

Означения 2.2. Базисним тявар! антом, який породжуеться тр!йкою об'ект!в ( ач ,'а« ) , назвемо елементи вектора вигляду (7) •

i-l 4-а J-з

• л c-t .с,- ,с, ), 1 í jt< ¡3 « n. (8) .. ' J i Ja va

як! в!дпов!дають в!дношенням вигляду

( а., п а,- -,. a.- it ¿i,- , а,- .« а,- ).

. . . -i-i -J-a Аз . Li

Базисний Шдвар!ант може як в!дпов!дати ацикл!чном.у вютошенню на множин! трьох об'ект!в С ai .а^.а.^ > , так í не в!дп6в!дати. Не мШмальна Шдмножинэ об'екпв з множили А. на як1й можна виявити цикл. Елементи вектора С, ао утворюють . базисний п1двар1ант (7 У, назвемо спряженими Ml ¡к собою. ■

Означения 2.3.Допустимым базисним ,шдвэр1антом назвемо базисний п1двар!.ант, то породжуеться тр1йкою об'екпв. в1днош,ення М1ж якими задовольняють умов1 здакл! чност1. - . .

•.. Означения 2.4. Повним вар!антом (ваР!антом довжини К) лазвемо вектор, шо в!дпов1дае повному б!нарному в!дно[пенню irá множит об'ект!в А.-

Означения 2.5.: Допустим™ варшггом назвемо повний вар!ант. що в1дпов1дае ацишчному вгдношенню на множин! вс!х об'ект!в.

Означения 2.6. Базисним шдвар!антом йксованого вар!анта

називаеться тргйжа 1 « ;к< 32< Лз^ N .

ТоОто для кожного конкретного вар!анта 1снуе )*(Н-2)/б

Кого базисних пг двар!ант1в. Вс! 1ншг можлив! тр1йки,складен! з трьох елемент!в вектора х1^, як1 не задовольняють умов! 1 < ,Ь< Зз^ N. не е'базисними■П1двар! антами Повного вар!анта хф.

Твердження 2.1. НеоОх!дною 1 достатньою умовою допустимост! вар!анта (7) е допустим: стьвах можливих його базисних шдвар1ант1в на множин1, об'ект1в, за в1дношеннями м!ж якими складений вектор вигляду (7).

Твердження 2.2. Умовою допустимост! базисного шдвар1анта (8) е Р1вн1сть його (0,0,0) ,або нэявн!сть у ньому одночаско компонент!в -1 та 1. ' •

. Будемо називати множину Х°,е=1,2..... скороченою (в1дносно

початковоХ'мноюши Х°). ■ ..

Твердження-2.3. На множин! можливих базисних-шдвар!ант1 в, що утво'рюються елементами скорочених множин X^ , X ^ , X ^ , завжди

1снуе допустимий Оазисний П1двар!ант, якщо тзх_1 Х^ I =3., де Г-1 -

- . " , . : ■ - 1 ■■■•'-.'- ■'.- . , п ■ . потуясшсть, множили.' . _

'Твердження 2:4. Якщо 1>1,на множин! можливих базисних

; 4=1,3 "Ч - -

шдвар1аит1в, що утворюються елементами множин Х^ , Xе) , X? , завжди

о 1 ия «3

!снуе допу.стимий. базисный и!двар!ант.

Означения 2.7.' Цикл!чним елементом множини Х^., Л=1,...,

, називаеться. такий елемент х^ « ' , який не утворйе »одного

допустимого,базисного шдвар!анта з! спрякёними з ним елементами.'

: - " Йа: основ! введених означень та доведених тверджень будуеться

N

процедура Ф скорочення множини допустимих розв'язк!в X ^¿П^-за умовою ацдал! чност!. б!дношення, що. В!ДП0В!Дае розв'язку задач!. зна-ходження.результуючого ранжування оО'ект!в множини;(1).. Р1зн! постановки таких задач формулюються :в параграфах цього розд!лу.

Наводиться розройлена автором'процедура л пошуку та в! дсгювшшя щшчних едемент!в множин'Х^,3=1, ....И. /

- В. !)2.2 розглядаеться однокритер! альна'задача визначення' резуль-туючого ранжування о0'ект1в. ' . ;

' На сьогоднг найчастние використовуеться 1 е, найб!льш обгрунто-

ваною результуюче ранжування ,що д! стало назву мед! анн Кемен! -Снелла:

R*e Arg rain ÍPj E iKR.P1)}, (9)

■ • . tteSí 1 iel ,

де Ж - множина матриць, що в1 дповиают'ь нестрогим ранжуванням п об'ект!в (ранжувашя та матриц! ,що im в!ддов! дають, будемо позначати однаковими символами), cKR.P1) - вистань м!к R та р\

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

них моделей .

Г (х)= Z Их )= Е Е Iс-гmin. (10)

jeJ JfiJ iel J

Xf Xj={-l,0,l), JeJ = Cl.....N), (11)

' xeDAcX°, X°= П Xi. (12)

Наводиться алгоритм посл!довного анал1зу вар!ант!в, який вико-ристовуе в1дому процедуру W та розроблен! автором процедуры Ф та Л.

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

Незважаючи на те, що серед задач знаходження результуючого ранжування найШльш поимренз задача знаходження мед!ани Кемет-Снелла, i'i не завждн мокна вважати найб1льш придат!шм розв'язком,оск!лыш не ранжування швелюе думки експерт!в, згллджуе "аномальн!" думки, на як! теж сл!д звертати увзгу. Для шбору ранжування, яке б б)льшою м1 рою враховувало думки bcix член!в колективу • експерт!в, моша запропонувати багатокритер!альну постановку задач!:

(Р.КН.Р1)}— min, 1*1. (13)

1 ¡...-.К

де Р^-задай! чи обчнслен! коеф!ц!енти комнетецтност! експерт1в (пай-

част! ше нормован1 ,тобто так! ,що задоволышч-ъ умов'ам Е f'i=l, PjsO);

cKR.P1) - в!дстань м!ж в!Дношеннями R та Р : R - ,bi дношення,' що В1д-.пов!дае нестрогому ранжуванню об'ект!в; К.- юкжина вс!х можливкх нестрогих ранжувань задано! к!лькост! об'ект!в.

В1Д0М0, що прщщипова особлив!сть задач багатокритер!алыю! оптим1зацП полягае в тому, що не кожпу пару розв'язк!в. \в нашому випадку - результуючих.ранжувань) коша пор1Вняти за мнохиною крите-р! альних ФункЩй (в нашому ■ випадку - в!дотаней до заданих.експертами матриць Р1), тобто для двох ранжувань з множили .-9J но -зависли моша' сказати, яке з них крата одночасно за ecimq криторшш. Розв'язок задач! (13) "сл!д шукати на множит «Фэктиышх рандаонь .? -St.

Означения 2.8. Ранжування об'.ект!в R° називаеться ефективним, якщо на множит ра/жувань Si не 1снуе такого ранжування И^.для якого б вик'онувалися нер1вноег1 _ .

í díR0,?1)• для .

1 хоча б одна з нер1вностей була d строгою.

Розв'язком задач1 (13) (компром!сним ранжуванням) е

R*= arg min max PidíR.P1).

ROÍ iel x

•У випадку, коли розв'язок (14) не единий, тобто

е Arñ min max Р^Ш.Р1),,

E Re:R i<äI '

на множил! , 'Ji екв! валентних за цими критер1ями ранжувань шукаеться

мед1ана вигляду (9).

Задача знаходжегаи Компром!сного ранжування об'ект!в в наведе-н1й постанови! формальзуеться в клас! <5агатокритер!алышх комб!нато-рннх моделей: .'■•'.

f,-(x)= £ fi(Xs)-- Е Ix-í-Cj .-i— min, 1«I, (14)

. J ¿«J 3 J

. x^Xj={-l,0.1), J«J, (15)

x«D4xú. X°= Л (16)

Гозв'язок задач! <14)—(16) може бути одержаний методом W з застосуванням розроблених автором процедур Ф та A¡.

$'¿•4 присвячений описанию алгоритму розв'язання задач! визначен-ня кваз[порядку. найближчого до заданого цикл!чного в!дношення.

Необх!дно знайти лшйний кваз1порядок об'ект1в з множили А в якомусь розумшш найближчий до вишошення вигляду (4).Взагал1 побу-дова л!н!Иного кваз!порядку вимагае внесения досить-великих зм!н в задану структуру переваг (4). Тому на сьогодн1 1снуе багато моделей, иго якимсь.чином апроксимують задан! гтереваги л!Шйними кваз!порядками.

Липйний кваз! порядок,найближчий до заданого в1дношення вигляду (4), ^находиться як ■ .

R*= arg min <1(P,R),' , -

je Ж - множила матриць. як1 в1дпов!дають лШйним кваз! порядкам п об'ект!в. Задача знаходження кваз!порядку е складною комбтаторною задачею. Тому для побудови л1н1Йного квёзторядку R* часто викорис-товуються алгоритм» локально! оптим1заш1. евристичн! алгоритми. або аягоритми, то Оазуються на метод! г!лок та меж* На сьогодн!. метода

поел!довного аналхзу до цього класу задач не застосовувалися, хоча

1х використання у ц1й облает! е перспективном.

Задача знаходження л1н!йного квазгпорядку, найближчого до зада-

ного на множил (Г) в1дношення переваги (4), Формал!зуеться у кдаС1

однокритер! алышх комб! наторних моделей .■.■''■'.

N

Е I Сд-- Х0-1 т1л1. ' • н (17)

х=(х1.....хн) е Х°, Х°= П Х^={-1,0.1>, . (18)

Х-ФаСХ°. ; <19)

Описуеться 1теращйна процедура одержання розв'язку задач! (17)-(19), що базуеться на поел!довному анал131 вар1ан«в.

В йй.5 проводиться дослишкення ¡алгоритмов поел!довного анал!зу . вар1ант!в для задач1 знаходження результуючого ранжування,Наводиться результата обчислювального експерименту,, який було проведено для по-Р1 вняння багатокрйтер1ально1 постановки 'задач! знаходження результуючого ранжування об'ект1в з результатами в!домих в теорП голосувань' правил вибору та для виявлення розм1рностей задач, як! МоЛа розв'.я-зувати запропонованим алгоритмом. .';■-*•",. •

Розд,1л 3 присвячений описанию Задач визначення ваГових коефЩ!-енив (ваги об'екмв, важливост! параметров, компетентное« експер-т!в) та класиф1катя цих. задач за виглядом вх!дно! Iнформащ г. та процедурами задания переваг експертом. -. '• : . , ■ ' ' \

Серед поширених способ! в задания ф!ксованих значень- коеф!щен-т!в сл1д.в1дзначнти так!: , ' ' .-'

— дов1льн! д1йсн! числа Р}ей, , де И — мнокина д!йсних чисел;

— д! йен! числа-з врахуванням обмежень (односторонн!х' чи двосторон-•Н1х), наприклад Р^О, 1^1; -5 ^ Р^ Б, 1«1; • 0Ф1<1, 1^1;

-- з врахуванням умови центрованост1:

. ■ ¡»-т 1 1 .

— з врахуванням умови нормованост!. ■." -

Е Р^Ь Р4>О, 1*1. ■ - (20)

На вагов! коеФШЕНТИ можуть бути ■ накладен! пши^ обмеження, наприклад, в !ерарх1чних моделях враховуються обмеження

£ Р®+г= Р| » Е Е Е

•о Я

де 8=0,1,2,...,''- р!вень 1ерарх11 п1дсистеми, I/5- мнокина 1ндекс!в шдсистем з-го Р!вня , 1ц -множила- 1ндекс!в гадсистем (вгП-го р!вня, зв'язаних з 1-ю шдсистемою.з-го р!вня.1 ,т.!н.

Поширеною е .. також !нтервальна форма задания вагових коеф!ц!ент!в .При цьому сл!д завважити, що да вс! пперпара-лелетпеди . К можливих знэчень коеф1ц1ент1в (конуси переваг ~ КП) з пперкуба [0,1) е допустимими:

' к= п ( р?; р?1 . о < р?< 1. 1^1. (21)

„ в , - , >х 1 1 1 ......

де в1дпо'в1дно йижня.та верхня меж! зм!ни.елемент1в вектор!в,

1*1. • ■,' . ;; \ " ' Означения 3.1. Надлишковими значениями . КП називаються так1 значения його'компонент- Р^., для яких не юнуе Р0-, в

конус! (21), иоб виконувалися сл1вв!дношення нормованост!. (20).

, В §3.1 оггасуеться процедура в!дс!ювання надлишковйх значень конуса переваг,яка £ модиф!кашею в!домого метода посл!довного анал!зу вар1ант1в для задач л1н!йиого програмування велико! розм1рност1.Сут-н1Сть цього методу полягае в звуженш 1нтервал!в зм1ни. коеф!Шент!В , р" , '"-Г. -.■.;..■-•

В $3.2 описуеться розроблений автором метод непрямого визначен-ня конуса переваг за неповною метризовэною.матрицею парнпх пор!внянь На першому етэпь цього метода по матриш вигляду (4) Оудуеться прямокутна матриця розм1ру '!п*п(п-1 )/2) з элементами.'. .

П=(тс.,), 1=1,....п*(п-1)/2, КГ, (22)

^ ' в '

1, якщо 1=(2~п)+ г (п-и, 3=1,...,п-1, 4 = 1

Л" , *i¿

Р-н, якщо J-S+-1 для 1=1,...,п-1,

1<1 к

j=s+l- Е (n-t) для ' або sS2. ■ t=i,

О - у вс!х 1нших вшшках, ; - ,

3 матриц! (22) по черз! вибираються вс1 можлив! комб!нац!1 з (п-1)-го рядка 1 доповнготься рядком довжини п, що складаються з одшшчних елемент!в. Одержана матриця позначаеться через G 1 складаеться система лШйних р!внянь . - '

- GP = е,

(23) .

. Рр О, 1^1,

1 - ф

де е - вектор довжини п з ел змеятами (О,...,0,1) t т — знак транспонування. .

На останньому кроц! алгоритму визначаються мШмальне та макси-мальне значения елемент!в вектора розв'язк!в систем вигляду (23)

Р% min р\, Р?= гпах pi, 1*1, - -

1 IsL 1 1 1«L • де L - множила !ндекс!в систем вигляду (23), для яких матриця G не-вироджена, рг=(Р*,1«Т)-розв*язок 1-1 сум!оно! система вигляду (23). .

' Тверджекня 3.1. Розв'язки -систем вигляду (23) не порушують

в1дношення переваги, задан! експертами на множит об'ект!в.:-Юбто у

випадку, коли на думку експерта. 1-й об'ект переважае 3-й, в!дпо-

В1ДН1 компонента вектора вагових коеФШент!в знаходяться у сшв-

в1дно1иенн! РрР^-. ИЗ, ие1, 1 навпаки.

В ¿ЗЛЗ. наводиться узагалъвдння методу стабШзацП переваг на

випадок неповних метризование матриць парних пор!внянь.

На першому крощ (з=0) методом рядкових сум визначаються величини ,

Ч? = Е Р-м. ГИсля цього визначаються початков! значения вагових

1 ¿--I :'.'■'

коефщ1ент1в об'ект!в (з=0)..

р! = Ч? / С Чч.' (24) •

На наступному. крот для уточнения коеф!Щент!в скористаемося формулами

• ^ '(Р1Р7 + РД.1 (Р^)7. 1-1.

де. ,»>={¿1: Р1д-1>. р1>5'-П,1е1; а.рл - параметры.вар1.ашI. яких

використовуються при ОПТИМ13ЭШ 1' КП. який визначаеться. Щсля цього коефгшенти визначаються формулою (24) для 1 т.д. Наводиться

критерП 'зупинки процедуры (умоеи стабшзащ!).

Пропонуеться модиф!кашя методу: на виладок неповних матриць парних пор!внянь. . -''.'■

В §3.4 опйсуються запрононоваш автором процедури визначення компетентност! експерт!в.

В •5 наводяться приклада розв'язання задач визначення вагових косфшшшв.

Е2ММ 4 присвячений описанию багатокритер!алыю! нолем, опт-мального спостере^ення за групою гравщ в одним переел! дувачем.

'.В §4.1 пропонуеться багатйкритер!альна постановка тако! задач1 б !гров!й 1 нтернротац! 1, 1\ математична модель", метод розв'язання, оснований на використаши апарату Сагатокритер1 ально! опадпзацП, комплекс програм синтезу д!алогових систем з базових ФУнкцюналышх модул1в,що слугуе системним программы забезпеченням для тренакерао! д!алогово1 системи КОРСАР шдтримки прийняття ^ршенна у вказан!й задач! супроводження групи об'ект!в. ■

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

деяк! законом!рност! маневрування тоао). Сл1д завпмснти, ¡до значения вказащи параметра кожуть бути як об'ектнвними (В!М1ряними), так 1 евристичгшш (гадашаи, ou! не ними е штертами аво вивелетьт на основ! яакопичених емШричних даних).' Через . заданий час (такт приЛняття Р1шення) характеристики гравшв зм1нюються.Будемо вважати, що стратеги îXHboï поведпки нев!дсн! (з 1грових задачах ввакаеть-ся, ио вх!дн! дай "е управл! нням, яке шбирае противник).

Задача супроводаення полягае в тому.щоб протягом вказаного терм!ну,враховуючи техн!чн! кокливост! перг.сл! дувача (порвметря зоня вшпшост!, яка являе собс» деяку багатозв'язну область, кон$!гургц!я яко1 уточнюеться при адаптацП до конкретних умов, шзидхють ходу, меневрування курсом,ыетддк!сть занурення чи шд'йому (трала - в рибо-ловецькШ ¡нтерпретацГ!) тогцо) гз зовнивню обстановку, преймзги pi-шення на.маневрування шресл! гувача таким чином, иоб утрнмувати вс!х гравщ в на оптиМальШй в1 легаш з врахуванням ixHboï "вакливост! ".

В §4.2 пропонуеться задачу супроводаення групп сб'ект!в у вик-ладеН1й постанови! будемо формал1 зувата. у клас! игекретгаа моделей бэгатокритер! ально!. оптшзан! i.

На множил! допусти«« розв'язК1в (вяр1ант!в мзкеврування перес-л!дувача) .. ■

D = D(x), X = (xj.x2.x3), (25)

знайти розэ'язок, "кокпром! сзшй" по сукушгост! кратер! íb

! /2

í=|fj(x,Q)=mln I dji(Q)- Д <ia¿ - хп1-Ф1)2| j— mln.Ktj. (26) leL

•до x = (х1.х2,хз) - вектор просторзвих координат пегесл1дувача: ,п=1,2.3,-екстрапольовон! на момент замнчення поточного такту прийняття'.ривеиня з зрахуваяням ппотези про пгямолшйшя PtmioMtp-ний рух координата 1-го гравия;. Ф^у^ sin С, у^-шидмсть 1-го гравия; ç>0 - допустимий кут маиеврування грзвтв ; ûji<q). - дискретнозначнэ Функц1я. iuo. золекять б!д вектора пзреметр!в Q, для .j-i облает! зв'язност! зони видимость яка мае pmict перевамто! аальносМ для сН облает! па 1-й дискрет! яопряму; М, Ь. I - множили iндвкс! в в! лпоь!дно областей пв'ядазст!, даскрзт напгякт руху та гравшв (критер!¡в зздачП. Параметры Ci харпктеризуоть модель зсвШшнкн обстановки: природа! умовн (рельеф грунту. глибишмнтсн-сиен!сть хвиль на поверш тощо), ширину зони koctICsoI вйдимост! (точя! сть апроксамац! i mm i i матемапгшов моделли), модель руху

переикод (ctopohhix о<5'ект1в,як1 не приймавть участ! в rpi) 1 'тЛв.: fiíx.Q). l«i, - даскротгюзначш Функц! f, як! в!дображують В1дстан1 гравтв е1д переважно1 для переел!дувача дальности t - довяина такту прийняття Р1шення на рух пересл1дувача.-

Кожен крок (такт) супрошджекня (переел!дування) розд!ляеться на два етапи - прийняття р!вення на рух пэресл!дувэча та прийнягтя р! пення на розворот з врахуванням глибшш занурення (напршшад, трала) в обох випадках. . - • ■'

У в! дпов) дност! до методолог! i. багатокритер! альноi оптишззШЬ провалиться перетверенвя значень крктер!альних функшй íj^x.Q), , до 0езрозм1рного вигляду wt(x,Q)=w1(fi(x,Q))=íi(xtQ)/f?,leI. де rf, - Haftripiul на поточнок^у такт! прийняття Р1щевдня значения-критерПв. - '"■"■•','

Шелл врахування нормованих вагових коеф! Ш eirri в в1дно'сно1 вакливост; областей зв'язност! • для прийняття ршення r-j. 'г^>0, зважеш безрозм!рн! значения критерНв р!вн! wJjíx.Q) = rjWj(x.Q) . Í«M, 1«1, для облает! зв'язност!, в як!й знаходиться 1-й гравець та w^(x,Q)=0, яшо 1-го гравая в 3-й област1 немае. Розв'язок задач! (25),(26) мае вигляд

х°= arg rain wax p.-w^U.Q), (27)

leí 1 ч ¿"íí

де P1>0, M, - нормован! BaroBl коеф1ШЕНТИ в!дносно! важливост! критер1альних . функшй (26), як! передбачаеться обчислювати як Pi=4i/Pi. leI; -"важлив!сть" 1-го гравця з.точки зору , переел!-дувача в К-бальн!й шкал!: 0<qi<N, 1=1; И - деяке натуральне число; Pi" ймоырн!сть BlpHoi класиф!кац1i 1-го травця_ пересл!дувачем: 0<рА<1, 1®1; Ц, Й>0, - Д1йсне число, яке задае стешнь переваги м!ж параметрами <1} та Pj.

Якао розв'язок задач! (25), (26) вигляду (27) неединий, застосо-совуеться узагальнений критер!й вигляду Е P^wi" .(x.Q) --. min , ,

íeM 1 XeJ)n .

де Dg, D0sD, - мжшша екв! валентна за критерием. (27) розв.'язк!в.

В $4.3 описуеться даэлогова система КОРСАР спостереження за групою об'ект!в, яка функШонуе в середовилЦ- ОС реального часу СМ ЕОМ. . . . '

В §4.4 описуеться комплекс игструментальних эасоб1в створення д1алогових систем на баз! СМ E0Í«.

ОСНОВШ РЕЗУЛЬТЛТЙ РОБСГИ

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

Основш теоретичш й практичн! результата, представлен! в дасертащ к

• 1. Запропоновано нову постановку задач! ранжування, осноезну на багатокритер1 альному п!яход!, розв'язск яко! краще узгоджуетьоя з задааики експэртами ыдиоыэннями переваги, н!ж розв'язки юнувчих постановок задач; Розроблено процедуру посл1 довного анал!зу та в!д-с1ву недопустима вар1ан?1в розв'язшв задач! ранжування за умовою ацишчносп розв'язку та наведено п обгрунтування. На основ! процедур поел!довного анализу запропоновано алгоритма розв'язання задач знаходташя компром!сно1 ранжировки, медгага Кемен! -Снелла та кваз!-порядку. найближчого до задакого петранзитявного б!паркого вгдновен-ня. Створено в!дпов1дне програмне забезпечеиня.

2. Введено означения надлишкоБих значень паралслетпеда можливих нормованих -знэчень коефшетчв В1дисснс1 бааизюост! об'ект!в та запропоновано процедура, основан! на метод! поел»довного анал!зу та в1дс!ювашш несуттевих обмеженЬ в задач1 л! Шйного програмування.

3. Запропоновано метод визначення конуса' переваг по неповшй метризован! й'матриц! парних тдовнянь, який точно апроксимуе мномшу тонок, йо в!дпав!дае задан!й матриц! парных пор!Е!Шнь.

4. Запропоновано узагальнення метода' стаб!л!зашг переваг для неповно! матриц!1 парник пор!шянь. Введено критерП точност! апрок-симацп вх1дно! матриц! карних пор!внянь конусом переваг. Проведено обчислювальний эксперимент,що показав позитивн! сторони розробленого методу., . ;

5. Запропоновано блгатокритер! альну модель супроводження групи гравшв одним переел!дувачем та алгоритма ¡1 розв'язання. Розроблено алгоритм! чне,программе га 1 нформаш йне забезпечення задач! супровод-ження групи грявщв у вигляд! гренажерао! д!алогово! системи КОРСАР, яка викорастовуеться для навчання особи, що приймае р!ше1шя, знаход-кеншо комаром! сного вар!анту маневра перед« дувача в склада! й !гро-в!й сагуацП.

'6."Розроблено комплекс.! нструментальнид. засоб!в синтезу д!ало-гових систем з Оазових функшоналышх модул!в на баз!. СМ ЕОМ, який е системним. програмшш яаЗюпеченням для програмних продукт!в, пред-ставленях в, дисертацп, а токож вихористовуеться р!зними, авторами

для стЕорьния программа комплекс!в, то функцюнують в режим! реального часу в pishkx проблемних областях.

1. Волоаян Л.Ф., Гнатк-зкко Г.И. Диалоговая система поддержки принятия решшзШ на базе СМ ЭВМ// Исследование операций И - АСУ,-19э1; • вцп.35. - с.100 - 109.

2. Волошин А.Ф.. Гн^тиенко Г.Н. -Многокритериальный подход к задаче сопровождения 'группы обьектоь в игровой постановке // Автоматика.-' 1991. - И> Ь - C.S5 - 93, '

3.' Волошин А.Ф., Гнатионко ,Г.Н. Построение . компромиссной ранжировки в задача группового выбора // Проблемы .теоретической кибернетики: Тез. 8-fi Всесоюз. ч,2. - Волгоград, 1.S90. С.44-46.

4. Волошин^ А.Ф., Гнатиенко Г.Я,, Требин С.Л. Диалоговая састема многокритериальной и системной оптимизации на базе СМ ЭВМ //Тез.докл.Республ.ксиФ. "Внедрение с,утр - путь соверыенствоеения . юшгнеркого труда и качества разработок" // В1нщ«щ, 30 червня -

г даШгЯ 1Э87 Г, - В!швдя: 1937. - С. 18.

6. Волошин О.Ф., Рнат1е!Гко P.M. Програшпй комплекс п!дтримки узшдашш р1вепь у двор1внев!й 1ерарх!чн1й модел1 вибору режиму . футцЮнУБагаш.систекй засо0!.в зв"язку// В!сн. КиТв. ун-ту,- 19Э2-Виц.4 - С.19-24.

. б.ГнаПенко P.M. Клзсиф: каш я задач одн!е! модел! анал!зу данах//. Кшб. ун-т.- Кит, 1992.-S9 с. - Б1бл1огр.: 105 назв.- Укр. - Деп. В'УкрНДИШ 18.06.92, Л 911 - Ук92.

7. Гиатианкс Г.Н. Задание предпочтений На множестве критери-алышх фушоцй ь задачах многокритериальной оптюизаиии // Вести.

' Ккав.у!£-та. Моделирование и оптимизация ело«.систем.1990.- Вип.9 -С.8? - -92. ' ' - ''

8." Гнгш^ако Г-Н,, Косматый Д.Ю. Обобщегше катода стабилизации предпочтений на случай неполных метризованных матриц napimx сраЬнэгай //Ки!в;ун-т. Ка!в, 1992 . - 22 с. - ЕЮлЮгр.: 6 назв -Рос. - Лен.' в УкрНДШП S.0G.92, А'347 - Ук92. - -

9. Гиатаенко Г.Н. Метод косвенного задания интервалов относительной вакности кригеризлызй Функций в задачах многокритериальной оагхглгзащш// пИХБ. УИ-1'. - КИ!Б, 1902. - Не,- Б10Л1ОГР.: 9

. назв - -Рос. - Лай. в УкрКЕШН 8.05.92, КШ ' УкЭ2.

10. Гпатикко Г.М., Косматей. ».Д. Апроксимвщя м&тризоважй матриц! кгрнвх пор!вняпь конусом переваг//В1сн,-Хи1в. ун-ту ,',Ф1зико-иатемаиян! науки,- 1994- Вип.4 (У ДР......

0CH0BHI 1ГОЛШЩ11 ПО 'ГЕЯ ДКСЕРТАЦИ: