Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

MULTI-ATTRIBUTIVE DECISION MAKING BASED ON THE QUALITATIVE INFORMATION

Stupina A.A. 1 Ezhemanskaya S.N. 1 Kuzmich R.I. 2 Vayngauz A.M. 3 Korpacheva L.N. 1 Fedorova A.V. 1
1 Siberian Federal University
2 Siberian state aerospace university n.a. M.F. Reshetnev
3 Kuzbass state university n.a. T.F. Gorbachev
The approach for solving variant search problems of the module structures of N-variant program systems where a portion or the whole accessible information could be as qualitative as well as incomplete is presented. The paper considers the method of multi-attributive decision making that involves only qualitative information, i.e. due to the attributes of alternatives, only the qualitative information type is accessible. Originated from this information the given alternative is preferable or rejected. Having used only qualitative data the problem statement can be presented as a modified formulation problem 0-1 of the integer programming that uses the notion of the variable deviation from the goal programming. Though primordially this method was developed for solving variant sampling problem of the module structures of N-variant program systems, nevertheless this method can be used in some other sampling problems.
multi-attributive method
N-variant program systems
qualitative information
alternative
Введение

Как правило, люди используют качественно-вероятностное  исчисление при рассуждениях об окружающем мире, и, поступая подобным образом, они генерируют огромное количество качественной информации, которая, в свою очередь, становится доступной в качестве входных данных в процессе субъективного (человеческого) решения [2]. Оптимизационные методы как средства решения полагаются главным образом на количественные данные (дискретные или непрерывные). Однако решение многоатрибутивной задачи, полученное таким образом, не может быть оптимальным.

При соответствующих условиях целесообразно расширить методы оптимизации до методов многоатрибутивного качественного анализа. В случае анализа данных по атрибутам альтернатив возможно следующее отображение: {более предпочитаемая (>), равно предпочитаемая (=), менее предпочитаемая (<)}. Более строгий вид отображения: {выбрано (1), не выбрано (0)}. Последнее отображение фактически является основой 0-1 целочисленного программирования [5]. Остановимся на определении соответствующего отображения для задачи выбора варианта модульных структур N-вариантных программных систем.

Материал и методы

Рассмотрим постановку задачи выбора, в которой доступны n вариантов построения модульных структур N-вариантных программных систем или n альтернатив: Y1, Y2,..., Yn. Лицо, принимающее решение, (ЛПР) может выбрать одну или несколько альтернатив, исходя из оценки m атрибутов, где Yi обладает атрибутами Xi1, Xi2,..., Xim  [3]. Информация по атрибутам альтернатив представлена в качественной форме. То есть, основываясь на данном атрибуте, ЛПР может предпочесть одну альтернативу другим. После сравнения по другому атрибуту порядок предпочтения может измениться. Однако ЛПР не имеет количественной информации по атрибутам, а качественная информация, которой он обладает, может быть неполной, и тогда не все альтернативы будут сравнимы по всем атрибутам.

Качественная  информация по атрибутам может быть сформулирована в следующем виде:

Xik> Xjk,   XikXjk,   Xik= Xjk,,  (1)

где, исходя из значения атрибута k, альтернатива i может быть соответственно сильно, слабо или равно предпочитаемой, по отношению к альтернативе j. Кроме того, альтернативе может не хватать одного или более желаемого атрибута. Такой случай можно сформулировать как: Xik=0.

Даже если атрибуты альтернативы, в основном, имеют количественные данные, для ЛПР важно, выбрана данная альтернатива или нет. Если i-я альтернатива выбрана, то Yi приобретает значение 1, в противном случае - 0. Можно интерпретировать выбор i-й альтернативы, как предпочтение каждого из ее атрибутов атрибутам конкурентов. Такая интерпретация позволяет нам установить Xik, (k=1, 2,...,m), равным 1 для выбранных альтернатив и 0 для невыбранных.

Тогда (1) можно записать как: Xik-Xjk+Pa--Pa+=0, k=1, 2,...,m.

Если Xik предпочтительнее, чем Xjk, то тогда ЛПР может пожелать максимизировать Pa+ и минимизировать Pa- (или максимизировать -Pa-). Преобразование истинно, если предпочтения Xik  и Xjk меняются.

Однако различные атрибуты альтернатив имеют разную важность. Степень важности атрибутов может быть отображена в виде относительных весов (или относительных приоритетов), которые ЛПР (или эксперт-консультант) назначает атрибутам.

Таким образом, можно решить эту задачу выбора методом «качественного программирования»:

max Z = waPa - w'aP'a - w"aLa   (2)

при ограничениях:

Xik-Xjk+Pa--Pa+=0 для всех сравниваемых атрибутов и a=1, 2,...    (3)

mYi-( Xik)=0 для всех i,  (4)

Yi=C,   (5)

Xir-La=0,   (6)

для всех отсутствующих r атрибутов альтернативы i, всех i альтернатив с отсутствующими атрибутами и a=1, 2,...

Pa++Pa- 1  для всех a=1, 2,...  (7)

Xik, Yi, Pa+, Pa- и La равны 0 или 1, для всех i, k и a,  (8)

где Р и Р' имеют противоположные знаки в надстрочных индексах.

В формулах (2)-(8), когда Xik предпочтительнее чем Xjk, то Pa+, имеющая постоянный тип (3.3), входит в целевую функцию с положительным знаком и своим коэффициентом wa, и Pa- с отрицательным знаком и коэффициентом w'a. И наоборот, если Xik менее предпочтительнее, чем Xjk, то тогда Pa- входит в целевую функцию с положительным знаком, и Pa+ - с отрицательным. В случае равенства предпочтений ни одна, ни другая переменная не входит в целевую функцию.

Хотя wa и w'a равны в большинстве случаев, возможно, также назначить и различные веса. Такое назначение различных весов может быть полезным, когда все альтернативы сравниваются с базовой. Положительное предпочтение над базовой (или контрольной) альтернативой может иметь вес, отличный от веса отрицательного предпочтения. Например, если решение выбора касается замены одной из версии модуля N-вариантной программного продукта, который уже используется, то атрибуты этой версии могут служить контрольной точкой. Для того чтобы данная альтернатива была, по крайней мере, равно предпочитаема базовой по данному атрибуту, отказ версии модуля может получить больший вес, чем превосходство. В этом случае w' будет иметь большее значение, чем w для того же атрибута.

Конечно, может существовать такое оптимальное решение, где альтернатива j предпочтена альтернативе i, несмотря на то, что ЛПР альтернативу i предпочел альтернативе j по некоторым атрибутам. Объединение P+ и P- в ограничении (3) служит предотвращению невозможных ситуаций, которые могут появиться из-за противоречивого сравнительного упорядочения предпочтения различных атрибутов альтернативы при сравнении с другими альтернативами.

Ограничение (4) гарантирует, что выбор альтернативы i (т.е. Yi=1) означает предпочтение всех ее атрибутов атрибутам других альтернатив (т.е. Xik=1 для всех k атрибутов). И наоборот, если альтернатива отклонена (Yi=0), тогда все ее атрибуты также отклонены (Xik=1, k=1, 2,..., m).

Значение C в ограничении (5) представляет собой количество (или портфель) альтернатив, которые нужно выбрать из n доступных вариантов. Следовательно, С - целое число, большее или равное единице. Решая задачу несколько раз, изменяя значение С от 1 до 2, 3,..., m-1, можно найти неявный ранговый порядок m альтернатив как дополнительный эффект, от попарного сравнения их атрибутов. Следовательно, данный подход будет полезен и для выбора более чем одной альтернативы, и для упорядочения предпочтения альтернатив.

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

Ограничение (6) существенно для тех атрибутов, которые отсутствуют или такого низкого качества, что ЛПР может отклонить альтернативу, если оценивать ее только по этим атрибутам. Следовательно, может априори существовать такое решение, что Xir=0. Например, если какой-то текстовый редактор не имеет выходных символов стандартного размера (как в случае с некоторыми научными редакторами), то ЛПР может отказаться от него априори, судя только по этому атрибуту.

Впрочем, в дальнейшем решение может измениться. То есть, когда вся доступная для анализа информация рассмотрена, альтернатива i может быть выбрана, несмотря на отсутствие атрибута r. Например, при решении о выборе версии модуля, задача которой - обработка цепочки символов, программный модуль может иметь специальные возможности обработки символов и набор шрифтов (два других важных атрибута), что может привести к выбору этой версии модуля, несмотря на отсутствие атрибута стандартного размера выходных символов.

В этом случае ограничение (4) вынуждает Xir принять значение 1. La, в ограничениях типа (6) объединены в рамках целевой функции с отрицательным знаком, чтобы принять во внимание отклонение априори Xir. Следовательно, любое изменение в априорном отклонении атрибута включит в целевую функцию штраф, равный w"aLa. Еще раз отметим, что w"a для атрибута не обязательно должен быть таким же, как и w'a или wa. ЛПР может не накладывать больший (или меньший) штраф на отсутствие (или отклонение априори) атрибута, чем тот, который он мог бы наложить сравнительным предпочтением одной альтернативы над другой (w) или отказом от одной альтернативы, ради сохранения соответствия основной линии атрибута (w'). Это различие в назначении весов (wa, w'a, w"a) данному атрибуту допускает нелинейности  функции полезности лица, принимающего решения. Переменная L имеет ту же природу, что и P-, т.е. отклонение предпочтения; она штрафует альтернативу в абсолютных терминах, так как альтернативе не хватает существенного атрибута, что делает ее априори неприемлемой.

Ограничение (7) устанавливает верхнюю границу для P- и P+. Когда различие предпочтения между атрибутом двух альтернатив - это или их выбор (со значением 1), или их отклонение (со значением 0), тогда переменные отклонения не могут иметь значение более 1. То же справедливо и для La.

Формулы (2)-(8) приводят к нулю или одному значению для предпочтения переменных отклонения (L, P - и P+), которое дает возможность решить задачу методами 0-1 целочисленного программирования. Однако модификация формул (2)-(8) в дальнейшем предоставляет возможность объединения качественной и количественной информации, что может привести к нецелому значению предпочтения переменных отклонения и, следовательно, к смешанному целочисленному программированию как методу решения.

Другая отличительная черта этого подхода - это его гибкость к объему информации. Т.е. нет необходимости в полном наборе данных перед началом решения задачи. Более того, можно попытаться измерить возможное влияние новой информации, предшествующей любым инвестициям на ее приобретение, выполняя анализ чувствительности и оптимальности после изменений.

Результаты

Следующий пример иллюстрирует предлагаемый подход. Решение включает одну из трех доступных альтернатив, основываясь на 2-х атрибутах, один из которых в два раза важнее другого. Кроме того, нехватка атрибута облагается штрафом в 1,5 раза как относительный вес этого атрибута. Вся доступная информация имеет качественный вид, что отображено в таблицах 1 и 2. Заметим, что для каждой пары (Xik, Xjk) достаточно одного отображения, чтобы показать предпочтения. Например, если X11 предпочтительнее, чем X21, тогда X21 не предпочтительнее X11. Следовательно, это можно не отображать в отдельных ячейках таблицы.

Таблица 1. Попарное сравнение альтернатив по первому атрибуту

Атрибут

X11

X21

X31

X11

равнозначны

(=)

предпочтительнее (>)

предпочтительнее

(>)

X21

не предпочтительнее (<)

равнозначны

(=)

не предпочтительнее (<)

X31

не предпочтительнее (<)

предпочтительнее (>)

равнозначны

(=)

Таблица 2. Попарное сравнение альтернатив по второму атрибуту

Атрибут

X12

X22

X32

X12

недостача

(0)

не предпочтительнее (<)

не предпочтительнее

(<)

X22

предпочтительнее

(>)

равнозначны

(=)

нет данных

X32

предпочтительнее

(>)

нет данных

равнозначны

(=)

Эту задачу можно сформулировать следующим образом:

max Z=2(P+1+P+2+P-3)-2(P-1+P-2+P+3)+(P-4+P-5)-(P+4+P+5)-1.5L1  (9)

при ограничениях:

X11-X21+P1--P1+=0;    (10)

X11-X31+P2--P2+=0;    (11)

X21-X31+P3--P3+=0;    (12)

X12-X22+P4--P4+=0;    (13)

X12-X32+P5--P5+=0;  (14)

2Y1-(X11+X12)=0; (15)

2Y2-(X21+X22)=0;  (16)

2Y3-(X31+X32)=0; (17)

Y1+Y2+Y3=1; (18)

  X12-L1=0;  (19)

P1++P1-≤1;  (20)

P2++P2-≤1;  (21)

P3++P3-≤1; (22)

P4++P4-≤1; (23)

P5++P5-≤1; (24)

Xik, Yi, Pj+, Pj-, L1 = 0 или 1.

Оптимальное решение задачи: Y3=1,  X31=1,  X32=1,  P2-=1,  P3-=1,  P5-=1,  Z=1.

Остальные  переменные равны нулю. Лучший выбор для этой задачи - альтернатива 3.

Чтобы исследовать, изменится ли решение при получении новой (дополнительной) информации, отсутствующей в таблице 2, можно проанализировать возможные последствия сбора такой информации. Если дополнительные данные указывают на предпочтение X32 перед X22, то это может  усилить выбор альтернативы 3. Однако, если X22 предпочтительнее, чем X32 , то оптимальное решение изменится: Y1=1X11=1X12=1P1+=1P2+=1, P4+=1, P5+=1, L1=1, Z=0.5.

Заметим, что хотя дополнительные данные сравнивают альтернативы 2 и 3, результатом может оказаться выбор альтернативы 1. Данное решение показывает, что дополнительная информация может радикально изменить начальный выбор.

И, наконец, можно ранжировать 3 альтернативы в этой задаче, решая (9)-(24), но в этот раз при С=2, что несколько изменит ограничение (18): Y1+Y2+Y3=2.

Оптимальное решение - это выбор альтернатив 1 и 3. Таким образом, можно заключить, что альтернатива 3 предпочтительнее альтернатив 1 и 2 (исходя из первого оптимального решения) и альтернативы 1 и 3 предпочтительнее любых других комбинаций двух альтернатив. Данный порядок предпочтения основывается на значении Z, и можно заключить, что: альтернатива 3 > альтернатива 1 > альтернатива 2, где «>» можно заменить словами «предпочтительнее чем».

Выводы

В данной работе представлен подход, позволяющий включить качественную информацию в процесс формальной оптимизации при  решении задач многоатрибутивного выбора. Предлагаемый подход использует уже существующие оптимизационные методы решения задач выбора, где качественная информация, часто только формально, представлена количественно. Хотя изначально этот метод разработан для решения задачи выбора варианта модульных структур N-вариантных программных систем, тем не менее, этот метод может использоваться и в других задачах выбора [1, 4].

Работа выполнена в рамках реализации ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы.

Рецензенты:

  • Антамошкин Александр Николаевич, д-р техн. наук, профессор, профессор кафедры системного анализа и исследования операций СибГАУ, г. Красноярск.
  • Кирко Владимир Игоревич, д-р физ.-мат. наук, профессор, профессор, зав. кафедрой менеджмента производственных и социальных технологий СФУ, г. Красноярск.