Дипломна работа на Пламена Димитрова Чонгова F18015 на тема програмна система за многокритериален анализ mka 2

Нов Български Университет

Бакалавърски факултет

Научен ръководител: ст.н.с. I ст. д-р Васил Василев

Задачите за вземане на решение при много критерии могат да бъдат разделени на два отделни класа в зависимост от тяхната формална постановка. При първия клас задачи краен брой алтернативи са зададени явно в таблична форма. Тези задачи се наричат многокритериални задачи за вземане на решение с дискретни алтернативи или задачи на многокритериалния анализ. При втория клас задачи краен брой от явно зададени ограничения във вид на функции определят безкраен брой допустими алтернативи. Тези задачи се наричат задачи за вземане на решение с безкраен брой алтернативи или задачи на многокритериалната оптимизация.

В дипломната работа се разглеждат проблеми, свързани с решаването на задачи на многокритериалния анализ. При тях няколко на брой критерии се оптимизират едновременно в множествотото от допустимите алтернативи. В общия случай не съществува алтернатива, която е оптимална за всички критерии. Но съществува множество от алтернативи, характеризиращи се със следното свойство: всяко подобрение в стойността на един от критериите води до влошаване в стойността поне на един от другите критерии. Това множество от алтернативи е наречено множество на недоминираните Паретооптимални алтернативи (решения). Всяка алтернатива от множеството на Парето може да бъде решение на многокритериалната задача. За да бъде избрана една алтернатива е необходима допълнителна информация, която се определя от т.нар. “лице вземащо решение” (ЛВР). Информацията, предоставена от ЛВР е отражение на неговите глобални предпочитания с оглед на качествата на търсената алтернатива.

За решаването на задачи на многокритериалния анализ са създадени различни подходи и методи. Голяма част от методите, разработени до сега могат да бъдат групирани в три отделни класа (Vincke (1992)): методи на теорията за полезност, аутранкиращи методи и интерактивни методи. Всеки от тези класове методи има своите предимства и недостатъци, свързани главно с начините за извличане на информация от ЛВР по отношение на неговите локални и глобални предпочитания. Тъй като тези начини се отличават значително един от друг, разработените досега софтуерни системи за подпомагане решаването на задачи на многокритериалния анализ реализират методи от една от трите групи.

В дипломната работа са описани основни елементи на софтуерната система с общо предназначение MKA-2, разработена за решаване на широк клас задачи на многокритериалния анализ. Реализирани са четири метода – един тегловен метод, два аутранкиращи и един интерактивен. Системата MKA-2 работи с четири типа критерии – количествени, качествени, тегловни и ранжиращи.

Във всяка програмна система за вземане на решения много важно е реализирането на адекватни методи за вземане на решения, с оглед на задачите, които ще бъдат решавани и квалификацията на ЛВР. Поради това е дадено описание на методите, програмирани в MKA-2. Особено внимание е отделено на аутранкиращите методи от типа ELECTRE. Тези методи са анализирани и за включване в системата MKA-2 е избран метода ELECTRE ІІІ. Методът е програмиран и детайлно тестиран. Разработката на методите и изследователската проблемно-ориентирана програмна система MKA-2 е осъществено в Института по информационни технологии при БАН.

Дипломната работа се състои от увод, три глави, заключение, списък на използваната литература и приложение. В първа глава е извършен анализ на състоянието на методите и софтуерните системи за решаване на задачи на многокритериалния анализ. Във втора глава е дадено описание на методите, реализирани в разработената софтуерната система MKA-2 за моделиране и решаване на задачи многокритериалния анализ. Детайлно е описан методът ELECTRE ІІІ. В трета глава е дадено общото описание на системата MKA-2, ръководството за потребителя и тестови примери, решени по метода ELECTRE ІІІ. В заключението е представен приноса на дипломната работа. Като приложение е даден програмния код на софтуерната система.
Глава 1.

Многокритериален анализ – методи, системи, задачи
1.1 Обзор на съвременните методи и системи за решаване на задачи за многокритериален анализ
Съществуват множество методи, за решаване на задачи на многокритериалното вземане на решения. Една класификация е спрямо типа на данните, които ползват – делят се на детерминистични, стохастични и размити (Chen и Hwang, 1992). Друга класификация е в зависимост от броя на участващите в процеса на вземане на решения лица. Една от най-често прилаганите класификации е спрямо типа на изискваната от ЛВР информация – делят се на тегловни, аутранкиращи и интерактивни(Vincke (1992)). Според нея методите, разработени до сега могат да бъдат групирани в три класа:

• 
  Методи на теорията за многоатрибутна полезност, тегловни методи;
  
• 
  Аутранкиращи методи;
  
• 
  Интерактивни методи.
  

Вторият клас методи са наречени аутранкиращи методи (методи ELECTRE (Roy (1996)), методи PROMETHEE (Brans и Mareschal (1994)); алгоритъм TACTIC (Vansnick (1986)) и др.) и са базирани на предположението, че съществува ограничена сравнимост между алтернативите. При тези методи първоначално се построява една (или няколко) аутранкираща(и) релация(и), която да отрази глобалните предпочитания на ЛВР. След това тази аутранкираща релация се използва, за да подпомогне ЛВР при решаването на задачата за вземане на решение на многокритериалния анализ. При сравняването на две алтернативи се използват четири бинарни релации: на неразличимост I (рефлексивна и симетрична), на слабо предпочитание Q (нерефлексивна и асиметрична), на силно предпочитание P (нерефлексивна и асиметрична) и на несравнимост R (нерефлексивна и асиметрична). Аутранкиращата релация покрива тези четири релации. При повечето от аутранкиращите методи се приема, че ЛВР често не е способен или няма желание да направи явно разграничение между четирите релации, следователно ЛВР определя предпочитанията си като задава интер- и интракритериална информация. Интеркритериалната информация се изразява под формата на тегла, а в някои методи и чрез вето-прагове, а интракритериалната – под формата на прагове на неразличимост и предпочитание.

Интерактивните методи (алгоритъм VIMDA, алгоритъм на аспирационните нива, алгоритъм InterQuad, алгоритъм LBS, алгоритъм CBIM и др.) обособяват методите от третата група. Те са “оптимизационно мотивирани” и са ориентирани към решаването на задачи на многокритериалния анализ, когато са зададени голям брой алтернативи и малък брой критерии. Първият и вторият алгоритъм използват първия тип модел на задаване на предпочитанията, при които ЛВР трябва да дефинира на всяка итерация желаните или допустимите стойности на критериите. Четвъртият и петият алгоритъм използват модел на предпочитание, при който ЛВР трябва да зададе не само желаните или допустимите стойности на критериите, но и интер- и интракритериална информация на всяка итерация.

Разработените системи, подпомагащи решаването на задачи на многокритериалния анализ, могат да бъдат класифицирани в три групи:

• 
  комерсиални;
  
• 
  изследователски ;
  
• 
  обучаващи и експериментални (за тестване на нови методи).
  

От гледна точка на предназначението софтуерните системи, подпомагащи решаването на задачи на многокритериалния анализ, могат да бъдат разделени на два класа:

• 
  софтуерни системи с общо предназначение;
  
• 
  проблемно-ориентирани софтуерни системи.
  

• 
  В методите от различните групи се използват различни по тип процедури за извличане на информация от ЛВР, което води до значителни трудности при реализирането на подходящ потребителски интерфейс в софтуерните системи.
  
• 
  Разработчиците на софтуерните системи обикновено имат интерес към реализирането на собствения си метод (методи) или имат определени предпочитания към методи от една и съща група.
  

Проблемно-ориентираните софтуерни системи за многокритериален анализ най-често са включени в други информационно-управляващи системи и служат за подпомагане на решаването на един или няколко типа специфични задачи на многокритериалния анализ. В тази връзка обикновено в тях е реализиран проблемно-ориентиран потребителски интерфейс и в някои от тези системи са включени методи от различни групи на многокритериалния анализ. Някои представители на проблемно-ориентираните софтуерни системи са системата FINCLAS – за финансови задачи (Zopounidis и Doumpos (1998)), Agland Decision system – за аграрни дейности (Parsons (2002)), системата DESYRE – за възстановяване на замърсени местности (Carlon (2004)), системата MultCSync –за планиране на опазването на околната среда (Moffett (2004)).

Задачите за вземане на решения са неформализирани или слабо формализирани задачи, за решаването на които е необходимо участието на така нареченото лице, вземащо решение (ЛВР). Получаваните решения са до голяма степен субективни и зависят от предпочитанията на лицето, вземащо решение. Задачите за вземане на решения се разделят на три основни класа: задачи за вземане на решения при много критерии (многокритериални задачи); задачи за вземане на решения в условия на риск и задачи за вземане на решения в условия на неопределеност. От своя страна задачите за вземане на решения при много критерии се разделят на два класа (Vincke (1992)): задачи на многокритериалната оптимизация и задачи на многокритериалния анализ. При задачите на многокритериалната оптимизация краен брой аналитично зададени ограничения във вид на функции определят безкраен брой алтернативи. При задачите на многокритериалния анализ явно се задават краен брой алтернативи в таблична форма.

Задачата на многокритериалния анализ (ЗМКА) може да бъде описана чрез матрицата на алтернативите А (n x k), която може да бъде зададена по два начина:

Таблица. 1

или

Таблица. 2

където:

a_i - означава алтернатива с индекс i, i=1,…,n;

k_j (.) или f_j(.) – означава критерий с индекс j, j=1,…,k.

Множеството от индексите на алтернативите се означава с I, а индексното множество на критериите - с J.

Оценката на i-тата алтернатива по отношение на всички критерии се задава с вектора-ред или .

Оценката на всички алтернативи по отношение на j-тия критерий се задава с вектора-стълб или .

Избор на най-добра алтернатива от ЛВР в съответствие с неговите предпочитания (задача за многокритериален избор).

Подреждане на всички алтернативи в низходящ или възходящ ред (задача за многокритериална наредба, рейтингиране, ранкиране и др.).

Разделяне на алтернативите на групи (задача за многокритериална класификация или многокритериално сортиране).

Допустимата алтернатива с индекс i^’ се нарича недоминирана алтернатива, ако не съществува друга алтернатива с индекс i, за която да е изпълнено условието:

и поне за един индекс j=s да бъде изпълнено условието:

Допустимата алтернатива с индекс i се нарича удовлетворителна алтернатива, ако е изпълнено условието:

където е аспирационното ниво на критерия с индекс j, j= 1,…,k

Алтернативата с индекс се нарича идеална алтернатива, ако е изпълнено условието:

В общия случай идеалната алтернатива не съществува.

Недоминираната алтернатива се нарича най-предпочитана алтернатива, ако тя най-добре отразява предпочитанията на ЛВР.

Критерият е най-общ термин. Той се проявява като целева функция, когато е възможна пълна формализация и като атрибут, когато такава формализация не е възможна.

Допустимата алтернатива с индекс i^’ се нарича недоминирана алтернатива, ако не съществува друга алтернатива с индекс i, за която да е изпълнено условието:

и поне за един индекс j=s да бъде изпълнено условието:

Допустимата алтернатива с индекс i се нарича удовлетворителна алтернатива, ако е изпълнено условието:

където е аспирационното ниво на критерия с индекс j, j= 1,…,k.

Алтернативата с индекс се нарича идеална алтернатива, ако е изпълнено условието:

В общия случай идеалната алтернатива не съществува.

При некомпенсаторния модел лошата стойност по един критерий в дадена алтернатива не може да бъде преодоляна за сметка на стойностите на тази алтернатива по другите критерии.

При компенсаторния модел малки промени по един критерий могат да бъдат извършени за сметка на промени по други критерии. При компенсаторните модели на всяка многомерна характеризация на алтернативите може да съответства едно число (числова характеризация). На основата на подхода за определяне на тази числова характеризация, компенсаторните модели се делят на три групи:

• 
  резултативен модел – определя алтернативата, която има най-голям резултат (най-голяма стойност на функцията за полезност). Проблемът при тези модели е как да се построи функцията на полезност.
  
• 
  компромисен модел – определя алтернативата, която е най-близо до идеалната алтернатива. При този модел алтернативите се разглеждат като точки в критериалното пространство.
  
• 
  модел на съгласието – определя множество от отношения, които най-добре удовлетворяват съответна мярка за съгласие.
  

При моделиране и решаване на задачите на многокритериалния анализ възникват следните проблеми:

• 
  как да изследваме даден количествен атрибут;
  
• 
  как да сравняваме количествени и качествени атрибути;
  
• 
  как да сравняваме повече от два количествени атрибута.
  

При ординарната скала измерваните величини се поставят на определено място в една възходяща или низходяща наредба. При тази наредба не се говори за разстоянието между величините, а само за мястото по важност, което заемат.

При интервалната скала отделните стойности са на еднакво разстояние една от друга. Величината на тази стойност се измерва до произволно избрано начало.

При пропорционалната скала отделните стойности са също на еднакво разстояние една от друга, като величината на стойността показва разстоянието до естественото начало. За тази скала са валидни всички аритметични операции.

Вторият проблем се решава като качествените атрибути се превръщат в количествени чрез използване на интервална скала. Един от най-известните начини за такава трансформация е използването на т.нар. биполярна скала. Взема се, например, десет точкова скала.Десет точки се дават на максималната стойност на атрибута. Средният брой точки (пет) се дават за отделяне на добрите от лошите стойности на атрибута.

За решаване на третия проблем се извършва трансформация на количествените атрибути, така че те да станат безразмерни и стойностите им да се изменят в един и същ интервал.

По-подробно ще бъде разгледана групата от методи ELECTRE, в която решаването на задачите за многокритериален анализ е базирано на аутранкиращия подход.
Глава 2

Методи за оценяване при много критерии в софтуерната система за подпомагане вземането на решения MKA-2
2.1. Методи AHP, PROMETHEE, CBIM – общо описание
Разработената софтуерна система MKA-2 трябва да отговаря на две основни изисквания.

Първото изискване е с нея да се решават задачи за многокритериален избор и задачи за многокритериална наредба.

Второто изискване е свързано с това, че в системата трябва да бъдат включени представители на трите групи методи за решаване на задачи на многокритериалния анализ. Трудностите, свързани с изпълнението на второто изискване, произтичат от това, че в методите от трите групи по различен начин се извлича различен тип информация за предпочитанията на лицето, вземащо решение. Това обяснява и факта, че в досега реализираните софтуерни системи е включен само по един метод. В софтуерната система MKA-2 са включени методи от трите групи, а именно:

• 
  AHP-метод на Saaty (тегловен);
  
• 
  метод PROMETHEE (аутранкиращ);
  
• 
  метод ELECTRE (аутранкиращ);
  
• 
  метод CBIM (интерактивен).
  

Таблица 1.

Стойности за не се знаят и не са установени. ЛВР дава тази оценка, която може да не бъде толкова точна, за да задоволи напълно . Във всяка матрица малките отклонения в коефициентите ще доведат до отклонения в стойностите на собствения вектор. Ако дефинираме матрицата , съответстваща на М, и на w, тогава ще получим следния израз: = , където е най-голямата стойност на собствения вектор на .са изменени тегла и се получават чрез решаването на система линейни уравнения.

Параметрите S_i , които представляват претеглени суми на стойностите на критериите за всяка алтернатива: , където , j=1,…,k е теглото на всеки критерий, а a_ij , i=1,…,n; j=1,…,k е стойността на този критерий в алтернативата a_i, определят важността на всяка алтернатива за ЛВР. Колкото е по-голяма стойността на този параметър, толкова алтернативата с индекс i е по-добра.

Стойността a_ij може да бъде интерпретирана аналогично както , като важност на алтернативата а_i за критерия к_j, т.е. a_ij може да бъде интерпретирано като тегло на а_i за критерия к_j.

Ако използваме трансформацията (векторна нормализация) , , то тогава е възможно критериите и алтернативите да се разглеждат като нива на един йерархичен процес за вземане на решение.

Методът на Saaty реализира описаната по-горе идея.

В този метод, наричан още аналитичен йерархичен процес (AHP), ЗМКА се свежда до задачата за намиране на теглата на елементите на всяко ниво по отношение на всеки елемент от по-горното ниво.

В началото се построява йерархичната структура. Първото ниво съдържа един елемент, т.е. главната цел. Второто ниво съдържа целите, на които се разбива главната цел и които в общия случай покриват главната цел. Възможно е някои от тези цели да бъдат разделени на подцели. Последното ниво съдържа алтернативите като цели. Основните идеи на този йерархичен процес са две:

1. Разбиване на целите на подцели, които са по-разбираеми за ЛВР и той може чрез сравнение по двойки да изрази своите предпочитания при определяне на техните приоритети.

2. Целите и алтернативите да бъдат третирани еднакво от математическа гледна точка.

Ниво 1

Обектът на търсене е недоминирана алтернатива, която задоволява ЛВР в максимална степен от гледна точка на едновременното оценяване по всички критерии.