Как стать автором
Обновить

Принятие решений. Пример

Время на прочтение 18 мин
Количество просмотров 8.4K

Прочие статьи цикла
Принятие решений
Принятие решений. Пример

Продолжая тему скажу, что посмотрел публикации других авторов Хабра по этой теме. Интерес к проблемам имеется, но в теорию влезать никто не желает. Действуют как пионеры первооткрыватели. Это было бы прекрасно, при получении ими новых результатов, достижений, но к этому никто и не стремится.

А на деле получается хуже, чем уже известно, не учитывается масса факторов, результаты теории применяются там, где она это делать не рекомендует и вообще не очень серьезно все выглядит, хотя Хабр, как надо понимать к этому и не стремится. Читатели не могут и не должны играть роль фильтра.

Исходное множество альтернатив их измерение и оценивание


Известно, что проблемы поиска решения возникают только в многоальтернативных ситуациях выбора. Для рассмотрения ситуации принятия решения, формулирования конкретной задачи принятия решения (ЗПР), выбора метода ее решения необходимо располагать некоторой исходной информацией об альтернативах, отношением предпочтения.

Покажем в подразделе, какие существуют способы ее получения. Альтернативы обладают многими свойствами (признаками), оказывающими влияние на решение. Например, показатели свойств объектов (вес, объем, твердость, температура и др.) могут быть количественными или качественными.

Пусть некоторое свойство множества альтернатив из Ω выражается числом, т. е. существует отображение ψ: Ω → Е1, где Е1 – множество действительных чисел. Тогда такое свойство характеризуют показателем, а число z = ψ(x) называют значением (оценкой) альтернативы по показателю.

Для проведения оценивания альтернатив необходимо произвести измерение показателей.

Определение. Под измерением показателя некоторого свойства понимается приписывание числовых значений отдельным уровням этого показателя в определенных единицах. При этом важным является выбор единицы измерения.

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

С другой стороны, имеются свойства, показатели которых не допускают подобного манипулирования с их значениями. Степень нагрева тел характеризуется температурой и измеряется в градусах. Значение этого показателя +10°С и –15°С не позволяют судить о том, во сколько раз больше нагрето тело, имеющее температуру +10°С, чем тело с температурой –15°С

Из этих примеров можно (и важно) сделать вывод о том, что показатели объем и температура относятся к различным типам свойств, над значениями z = ψ(x) которых допустимы или недопустимы определенные преобразования f(z)=f(ψ(x)).

Именно, множество допустимых преобразований f(z) и принимают за основу определения типа шкалы, в которой выполняется измерение показателя некоторого признака (свойства). Выполняя то или иное измерение показателя признака, который выделен исследователем, мы приходим к задаче определения типа шкалы, в которой измерение должно проводиться.

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

Определение. Шкалой измерений называется принятая по соглашению последовательность значений одноименных величин различного размера.
Рассмотрим подробнее основные типы шкал.



1. Номинальные шкалы. Номинальные шкалы используются тогда, когда исследователь имеет дело с объектами, описываемыми некоторыми признаками. В зависимости от наличия у данного объекта некоторого значения признака или отсутствия такового объект относят к тому или иному классу.

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

Шкала в этом случае образована названиями всех профессий. Очевидно, на этой шкале нуль не обозначен, хотя отсутствие профессии у субъекта допускает его отнесение именно к категории людей без профессии. Названия профессий никак на этой шкале не упорядочены, хотя часто из соображений удобства их располагают при перечислении по алфавиту.

Из этих cоображений такая шкала называется шкалой наименований.
Допустимые преобразования значений в этой шкале — это все взаимно однозначные функции: f(x) ≠ f(y) <=> x ≠ y.

2. Порядковые шкалы. Если изучаемый признак, например, твердость материала, по-разному проявляется у объектов и имеет значения, которые нельзя конкретно измерить, но можно однозначно судить о сравнительной интенсивности его проявления для любых двух объектов, то говорят, что значение признака измеряется в порядковой шкале. Классическим примером такого признака является твердость минералов. Начало отсчета — 0 на шкале не определено.

Значение признака определяется следующим образом. Более твердый минерал рассматриваемой пары оставляет царапину на другом. Все минералы по значениям этого признака могут быть упорядочены так: первый наименее твердый, второй более твердый он оставляет царапину только на первом, третий оставляет царапину на первых двух и т. д.

Отличие порядковой шкалы от номинальной в том, что значения признака удается упорядочить, в то время как значения на номинальной шкале даже упорядочить не удается. Неудобство порядковой шкалы состоит в том, что она не пропорциональная.

Ответить на вопрос насколько или во сколько раз один минерал тверже другого не удается. Допустимые преобразования порядковой шкалы состоят из всех монотонно возрастающих функций, обладающих свойством: x ≥ y => f(x) ≥ f(y).

3. Шкала интервалов (интервальная). отличаются от шкал порядка тем, что для описываемых ими свойств имеют смысл не только соотношения эквивалентности и порядка, но и суммирования интервалов (разностей) между различными количественными проявлениями свойств. Характерный пример — шкала интервалов времени.

Интервалы времени (например, периоды работы, периоды учебы) можно складывать и вычитать, но складывать даты каких-либо событий бессмысленно.

Другой пример, шкала длин (расстояний) — пространственных интервалов определяется путем совмещения нуля линейки с одной точкой, а отсчет делается у другой точки. К этому типу шкал относятся и шкалы температур по Цельсию, Фаренгейту, Реомюру.

В этих шкалах допустимы линейные преобразования, (x — y)/(z -v); x ∓ y; в них применимы процедуры для отыскания математического ожидания, стандартного отклонения, коэффициента асимметрии и смещенных моментов.

4. Шкала разностей(балльная) Шкалы разностей отличаются от шкал порядка тем, что по шкале интервалов можно уже судить не только о том, что размер больше другого, но и на сколько больше в сущности это та же абсолютная шкала, но ее значения сдвинуты на некоторую величину относительно абсолютных значений (x — y) < (z -v); x ∓ y;

5. Шкала отношений. Шкала, для которой множество допустимых преобразований состоит всех преобразований подобия, называется шкалой отношений. На этой шкале фиксируется начало отсчета и для нее допустимо изменение масштаба измерений.

Пусть в этой шкале выполняется измерение длины предмета. При этом можно переходить от измерения в метрах к измерению в сантиметрах, уменьшая единицу измерения в 100 раз. Очевидно, что в этом случае отношение длин L(A) и L(B) двух предметов А и В, измеренных в одинаковых единицах, не изменится при изменении единиц измерения.

Значения показателя признака, измеренные в этой шкале позволяют
отвечать на вопрос во сколько раз интенсивнее признак проявляется у одного предмета, чем у другого. С этой целью необходимо рассмотреть отношение значений L(A)/L(B) = k.

Если отношение больше единицы (k >1), значение показателя признака у первого объекта А в k раз больше чем у В, если k < 1, то значение показателя признака у объекта В в 1/ k раз больше чем у А. Допустимым преобразованием показателя является умножение на целое положительное число и только оно.

6. Абсолютная шкала. Наиболее простой из всех шкал является шкала, допускающая только одно преобразование f(x) = x. Этой ситуации соответствует единственный способ измерения показателя свойства объекта, а именно простой пересчет предметов.

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

Задача принятия решения. Получение матрицы отношений


Перечислим возможные постановки ЗПР, к ним относятся:

  • линейное упорядочение альтернатив (верхняя в цепочке лучшая);
  • выделение лучшей альтернативы;
  • выделение подмножества (неупорядоченного) лучших альтернатив;
  • выделение упорядоченного подмножества лучших альтернатив;
  • частичное упорядочение альтернатив;
  • упорядоченное (частично упорядоченное) разбиение альтернатив;
  • неупорядоченное разбиение альтернатив (классификация).

На основе анализа измерений показателей свойств альтернатив в различных шкалах результаты измерений могут быть представлены различными способами [1, 5].

1. Классификационная таблица. Таблица получается при проведении измерений в номинальных шкалах и представляет собой таблицу, строками которой являются: наименование объекта, а столбцами – наименования классов $X_1, X_2, X_3,$… и т. д. В столбцах класс 1, класс 2 и т. д. ставится 1, если объект принадлежит данному классу и 0 – если нет (табл. Классы объектов).

В таблице классов объекты $x_1 ,x_2 є X_1, x_3 є X_2, x_4 є X_3.$

2. Матрица отношения предпочтений. Получается при проведения измерения в порядковых шкалах. Выявить предпочтения на множестве объектов Ω– значит указать множество всех тех пар объектов (х, у) из этого множества для которых объект х предпочтительнее (например, тверже) объекта у. Матрица отношения предпочтений получается следующим образом. (см.здесь, рис 2.15)

Строится $А_{[n×n]}^p$ квадратная матрица. Ее i-я строка соответствует i-му элементу $x_i$ множества Ω, а j-й столбец – элементу $x_j$. На пересечении i-той строки и j-го столбца ставится единица, если объект $x_i$ предпочтительнее объекта $x_j$, нуль, если объект $x_j$ предпочтительнее объекта $x_i$, 1/2, если объекты $x_i$ и $x_j$ безразличны, и ничего не ставится – если объекты несравнимы $x_i$ и $x_j$ нельзя сравнить.

Пример такого отношения предпочтений представлен матрицей ниже


3. Таблица показателей. Получается при проведении измерения в шкале отношений. Выбираются свойства показателей, которых будут измеряться. Производится измерение показателей этих свойств, и результаты измерений записываются в таблицу.

В столбцах $p_1, p_2, p_3, p_4$ таблицы Отношение предпочтения размещены значения показателей свойств, по которым оцениваются объекты $x_1,x_2,x_3,x_4,x_5,x_6$ и $x_7$.

После получения результатов измерений в данных формах представления, нам необходимо произвести отображение результатов в форму отношений, так как мы будем решать ЗПР, опираясь на хорошо разработанный аппарат теории бинарных отношений.

Отображение таблицы предпочтений в матрицу бинарного отношения осуществляется следующим образом:


Из матрицы отношения предпочтения $А_{[4×4]}^p$ для 4-х альтернатив представленной в табл. Отношения предпочтения получится матрица $А_{[4×4]}^p$, которая выгляди следующим образом:


Отображение матрицы показателей в матрицу отношения предпочтения осуществляется следующим образом: $a_{i,j}=1$, если:
1)число показателей, по которым объект $x_i$ предпочтительнее объекта $x_j$ больше, чем число показателей, по которым объект $x_j$ предпочтительнее объекта $x_i$;

2) для объекта $x_i$ ни один из показателей не принимает наименьшего из возможных значений.

3) из условия 1 следует, что те показатели, по которым объект $x_i$ не хуже объекта $x_j$, составляют большинство среди всех рассматриваемых показателей.

Однако при выполнении этого условия может оказаться, что по тем показателям, по которым объект $x_i$ хуже объекта $x_j$, разница значительна; чтобы уменьшить число таких случаев при отдаче предпочтения в пользу х, вводится условие 2.

Методы решения задачи принятия решения


Пусть после получения исходных данных мы располагаем отношением R на множестве альтернатив $Ω= {(x_1, ...,x_n)}$. И стоит задача принятия решения. Основной метод — линейное упорядочение (ранжирование) альтернатив, т. е. выстраивание альтернатив в цепочку по убыванию их ценности, пригодности, важности и тому подобное, от самой «хорошей» до самой «плохой».

Отношение R может быть:

  1. полным нетранзитивным отношением;
  2. отношением частичного порядка;
  3. линейным порядком.

Только в случае линейности отношения R, структура предпочтений отвечает поставленной задаче. В этом случае ранжирование альтернатив из множества Ω получается непосредственно, путем построения линейной диаграммы упорядоченного множества. На диаграмме альтернатива $x_i$, будет находиться строго выше альтернативы $x_j$, если она более предпочтительна.

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

Ранжирование альтернатив. Пусть отношение [Ω, R] – полное и нетранзитивное. Свойство полноты говорит о том, что все альтернативы $Ω = {(x_1, ...,x_n)}$ из множества сравнимы между собой. Наличие нетранзитивности возможно только в том случае, если граф G[Ω, R] предпочтения содержит контуры.

Необходимо преобразовать структуру графа отношения так, чтобы были устранены логические противоречия в форме контуров. Если предположить что в отношении R имеется контур $x_1, x_2, …,x_k, x_1,$ то при ранжировании альтернатив $x_1$ должна быть расположена выше $x_2, x_3, …,x_k, x_1,$, что приводит к противоречию.
Введем следующее утверждение [1,5].

Пусть В' и В" – два произвольных контура графа вида G[Ω, R], тогда если некоторый элемент $x_i$ є B' доминирует элемент $x_j$ є B'', то и любой элемент $x_1$є B' доминирует любой элемент $x_k$ є B''.

Это предложение предоставляет возможность разбиения множества R на m подмножеств $B_1, B_2, …,B_m$, таких что $B_i ∩ B_j=∅, ∀i,j є [1, m]; UB_i =Ω.$
Итак, задача ранжирования альтернатив множества распадается на два этапа:
1) выделение контуров графа, т.е. разбиение множества Ω на подмножества $B_1, B_2, …,B_m$ и групповое упорядочение этих подмножеств;
2) ранжирование элементов контуров, выделенных на первом этапе.

Алгоритм выделения контуров графа

Для нахождения контуров графа существует простой алгоритм [1]. Пусть $А_{[n×n]}$ – матрица смежности графа G[Ω, R], а $Е_{[n×n]}$–единичная матрица. Образуем $Е_{[n×n]}+ А_{[n×n]}$, $(Е_{[n×n]}+ А_{[n×n]})^2$, $(Е_{[n×n]}+ А_{[n×n]})^3$,… последовательность степеней матриц, элементы которых выражают количество путей длины не более 1, 2, 3… Для некоторого значения m ≤ n получим следующее равенство (установившуюся матрицу):
$(Е_{[n×n]}+ А_{[n×n]})^m=(Е_{[n×n]}+А_{[n×n]})^{m+1}$.

Из теории графов известно [10], что каждой системе всех одинаковых строк «установившейся» матрицы соответствует подмножество вершин графа, лежащих в одном контуре. Группируя соответствующие вершины в классы, получим разбиение исходного множества Ω на подмножества $B_1, B_2, …,B_m$.

Очевидно, что среди этих подмножеств можно найти такое подмножество $B_im$, что элементы этого подмножества не будут доминироваться никакими элементами из других подмножеств. Это подмножество будем считать наилучшим, и оно займет первое место в ранжировке по убыванию предпочтительности.

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

Пусть на множестве Ω задано отношение предпочтения R матрицей $А_{[6×6]}$.


Граф отношения R изображен на рис. Г.


Рис. Г. Граф нетранзитивного отношения R

Для осуществления первого этапа ранжирования элементов множества необходимо выделить контуры графа G[Ω, R]. Это делается возведением матрицы смежности графа в последовательные степени, пока не выполнится совпадение матриц.

Получаем $(Е_{[6×6]}+ А_{[6×6]})$, $(Е_{[6×6]}+ А_{[6×6]})^2$, $(Е_{[6×6]}+ А_{[6×6]})^3$.
Далее последовательно вычисляем возрастающие степени матрицы, суммируя их с единичной матрицей соответствующей размерности до тех пор пока матрица не перестанет изменяться:


Так как $(Е_{[6×6]}+ А_{[6×6]})^2 =(Е_{[6×6]}+ А_{[6×6]})^3$, можно сделать вывод, что $(Е_{[6×6]}+ А_{[6×6]})^2 = (Е_{[6×6]}+ А_{[6×6]})^k$, при k ≥ 2. Из анализа матрицы $(Е_{[6×6]}+ А_{[6×6]})^2$ следует, что строки, соответствующие элементам $x_1,x_4,x_6$ совпадают, это говорит о принадлежности этих элементов одному контуру графа G[Ω, R].

Элементы $x_1,x_4,x_6$ образуют множество $B_1 =(x_1,x_4,x_6)$. Другой контур образован элементами $x_2,x_3,x_5$, которые входят в множество $B_2 =(x_2,x_3,x_5)$.

Таким образом, мы провели разбиение множества на m=2 класса $B_1, B_2$. Проведем групповое упорядочение этих подмножеств. Для этого необходимо найти какой-нибудь элемент $x_i є B_1$, который доминирует элемент $x_j є B_2$.

Это будет означать превосходство подмножества $B_1$ над $B_2$. В нашем примере $x_1 є B_1$ доминирует над $x_2 є B_2$. Следовательно, подмножество $B_1$ доминирует над $B_2$. Графическое представление доминирования в разбиении Ω изображено на рис. КК.


Рис. КК. Ранжирование контуров, выделенных на первом этапе

Алгоритм ранжирования элементов контуров. Возможно, ли упорядочить элементы отношения, лежащие в одном контуре, эквивалентны ли они друг другу или между ними имеют место достаточно тонкие различия, позволяющие их различать? Оказывается такая возможность, как правило, существует [1].

Обозначим через $ B_{h_{[n×n]}}$ матрицу смежности h-го контура. Введем понятие $p^i(k)$-силы порядка k элемента i, значение которой вычисляется как сумма элементов i-й строки в матрице $ B_{h_{[n×n]}}^k$ (1).

Пусть $ b_{h_{[i,j]}}^k$– элемент, стоящий в i-й строке и j-м столбце матрицы, тогда


Под относительной силой k-го порядка элемента i понимают дробь

При неограниченном возрастании k (k → ∞), число $π_i(k)$ стремится к некоторому пределу π, который мы в дальнейшем будем называть силой элемента i. Вектор $П_{[n]} = (π_1,...,π_n)$ называется предельным вектором.

Вследствие теоремы Перрона-Фробениуса [1] предел всегда существует. Собственный нормированный вектор матрицы смежности контура совпадет с ее предельным вектором. Следовательно, вектор $П_{[n]} = (π_1,...,π_n)$ (2)

может быть найден без вычислений интегрированных сил $p^i(k)$, путем решения системы линейных уравнений
$B_{h_{[n×n]}} · П_{[n]} = λП_{[n]}$, (3)
где λ – наибольший неотрицательный действительный корень характеристического уравнения
$det(λЕ_{[n×n]}- B_{h_{[n×n]}}) = 0$ (4)
Необходимо отметить, что нормированный собственный вектор неотрицательной неразложимой матрицы не меняется при умножении матрицы на число s > 0, а также при суммировании ее с матрицей вида sE.

Затем элементы контура упорядочиваются по уменьшению значений соответствующих компонентов вектора $П_{[n]}$, т.е. элемент i доминирует элемент j тогда, когда $π_i >π_j$.

Осуществим ранжировку элементов множества $B_1 =(x_1,x_4,x_6)$. Построим матрицу предпочтений для этого множества


Вектор интегрированных сил 1-го порядка для элементов $(x_1, x_4, x_6)$ выглядит (1,1,2), вектор относительный сил П(k) = (1/4,1/4,2/4).
Ранжирование элементов $(x_1, x_4, x_6)$по силе 1-го порядка представлено на рис. Р.


Рис. Р. Ранжирование элементов

Найдем векторы, характеризующие силы 2-го, 3-го, 4-го и 5-го порядков.


Графическое представление ранжирования изображено на рис. П.



Рис.Ц — Цепь

Осуществив аналогичным образом ранжирование элементов множества В2, получим результаты представленные на рис. П справа.

В результате совмещения ранжировки элементов множества В1 и В2 переходим к окончательному упорядочению элементов множества Ω (рис. Ц).

Линейное доупорядочение строгих частичных порядков


Пусть отношение R (рис. А ниже по тексту), полученное в результате агрегации индивидуальных суждений экспертов является отношением частичного порядка, на множестве Ω. В этом случае Ω– упорядоченное множество. Построение линейного упорядочения альтернатив представляет собой получение глобальных оценок их «возможностей» в порядковой шкале.

В силу каких-либо причин, некоторые эксперты не могут сравнить определенные пары альтернатив по предпочтительности. В этом случае агрегированное отношение R на множестве Ω не будет линейным порядком. Очевидно, это приводит к задаче линейного доупорядочения альтернатив из Ω. Такое доупорядочение часто возможно многими способами.

Наличие нескольких линейных упорядочений для частичного порядка указывает на то, что имеющегося в структуре «внутреннего порядка недостаточно» для единственного линейного упорядочения. Таким образом, возникает необходимость решения задачи линейного доупорядочения частичных порядков. Пусть R – частичный порядок.

Теорема (Шпильрайн [5, 10]). Всякий порядок R на множестве можно продолжить до линейного порядка на этом множестве.

Следствие из теоремы Шпильрайна: всякое линейное доупорядочение подмножества $Ω_i ⊆ Ω$ может быть продолжено до линейного доупорядочения всего упорядоченного множества Ω.

Если X – подмножество в Ω, состоящее из несравнимых альтернатив, то всякое линейное упорядочение X может быть продолжено до линейного упорядочения всего множества Ω. При этом порядок R выражается через линейные порядки $R_i$.

В силу теоремы Шпильрайна, на множестве Ω существует нумерация $x_1, x_2,...,x_n $ элементов этого множества. Нумерация n-элементного упорядоченного множества Ω, с заданным на нем отношением порядка R, есть взаимно-однозначное отображение множества Ω в себя, т.е. в {1, 2, ..., n}, при котором «большему» относительно порядка элементу соответствует больший номер [5]. Далее под ранжированием элементов будем понимать любое линейное доупорядочение этого порядка. Отметим, что нумерация упорядоченного множества представляет собой его измерение.

В общем случае, задача поиска линейных доупорядочений сводится к нахождению всех допустимых нумераций исходного частичного упорядоченного множества. Можно выписать все перестановки элементов, из Ω, которых будет n! и для каждой проверить условие, что «большему» элементу соответствует больший номер. Однако, такой метод отыскания всех доупорядочений очень трудоемкий и не эффективный.

Для упорядоченного множества Ω, с заданным на нем порядком R, элемент х' множества Ω называется максимальным, если не существует строго большего его элемента х, т.е. если x>x' не выполняется ни для какого x є Ω. Элемент x'' называется наибольшим элементом упорядоченного множества [Ω, R], если он больше любого другого элемента х, т.е. для всякого x є Ω, x''>x [5].

Если в упорядоченном множестве имеется наибольший элемент, то он является максимальным элементом. Если в упорядоченном множестве имеется единственный максимальный элемент, то он будет наибольшим элементом. В частично упорядоченном множестве допускается наличие нескольких максимальных элементов.

При всякой нумерации n-элементного множества Ω, номер N приписывается максимальному элементу. Все нумерации множества Ω можно получить, если известны все нумерации всех подмножеств, получающихся из Ω удалением одного из таких максимальных элементов. К каждому подмножеству применим тот же прием [7]. Рассмотрим алгоритм построения всех нумераций упорядоченного множества [Ω, R].

1. Строится вспомогательный граф [β, γR] упорядоченного множества [Ω, R], вершины которого удовлетворяют условиям:

а) являются подмножествами Ω;

б) для любых двух подмножеств X, Y є β верно: (X,Y є γR) тогда, когда
подмножество Y может быть получено из подмножества X удалением одного из его максимальных элементов (рис. А и АА).


2. Для каждого одноэлементного подмножества множества γR выписываем его единственную нумерацию. Для получения всех нумераций подмножества X необходимо перебрать все смежные с ним подмножества и для каждого такого подмножества продолжить все его нумерации. В итоге будут получены все нумерации множества Ω, т.е. все линейные продолжения порядка R.

Задача заключается в нахождении всех линейных доупорядочений частичного порядка, диаграмма которого представлена на рис. A. В этом отношении нет информации, например, о том, доминирует ли альтернатива $x_1 $альтернативу $х_2$ или наоборот, а также аналогично для пар $(х_3, х_6);(х_4, х_5)$. Это и означает, что А частичное упорядочение. Достроить до линейного упорядочения существует много (22) вариантов, которые желательно привести к единственному. Это возможно с привлечением дополнительной информации об альтернативах, получаемой при детальном изучении ситуации.

1. Строим вспомогательный граф [β, γR], начинаем с множества $(x_1, x_2, x_3,x_4, x_5, x_6)$ и снизу. Цифра около дуги графа указывает удалением какого максимального элемента получено подмножество, в которое эта стрелка направлена (рис. AA).

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

3. При составлении нумерации подмножества X, состоящего из k элементов надо переписать все записанные ранее (для предыдущего подмножества) нумерации подмножеств Y є γR(x) и присвоить номер тому элементу, который дополняет Y до X.


В последнем (нижнем) блоке (табл. AAA) находятся все нумерации линейных доупорядочений множества Ω. Графическое представление этих доупорядочений изображено на рис. AAA.


Рис. AAA. Графическое представление доупорядочений

Необходимо отметить, что всего линейных порядков на множестве из 6 элементов 6! или 720, а линейных доупорядочений множества Ω с отношением, заданным графом, изображенным на рис. AA, всего 22. Это также достаточно много для принятия решения.
Существуют ли возможности для сокращения количества таких вариантов? Да существуют.
Для уменьшения числа линейных доупорядочений, необходимо воспользоваться дополнительной информацией.

Дополнительная информация


Пусть [Ω, R] – исходное отношение, тогда дополнительную информацию можно представить в виде отношения δ на множестве Ω, где условие (x,y)є δ, т.е. (x>y) интерпретируется как сообщение о том, что объект х доминирует объект у;
отношение δ можно рассматривать тогда, как множество подобных сообщений информации о доминировании, заданной в виде бинарного отношения δ, возможно два случая при использовании дополнительной информации:

  1. граф отношения R∪δ содержит контуры;
  2. граф отношения R∪δ не содержит контуров.

В первом случае линейное упорядочение множества Ω с заданным на нем отношением R∪δ производится с помощью алгоритма ранжирования,
рассмотренного ранее.

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

Для успешного выхода из этой ситуации необходимо, чтобы дополнительная информация δ и исходное отношение R были заданы в виде диаграмм Хассе, т.е. без явного указания транзитивных связей. Ценность дополнительной информации будет определяться тем, во сколько раз уменьшиться число линейных доупорядочений при ее использовании.

Например, если поступит информация о том, что $x_2$ доминирует $x_4$, т.е. $x_2>x_4$, то число линейных доупорядочений сократиться с 22 до 19, а если поступит информация: $x_1>x_2$, то число линейных доупорядочений сократиться в два раза. Таким образом, возникает вопрос: какая информация будет наиболее ценна, или при добавлении, какого отношения δ число доупорядочений уменьшится в наибольшей степени?

Для решения этой задачи для всех пар элементов $(x_i, x_j)$ множества Ω, которые не входят в отношение R, в нижнем блоке табл. ААА, необходимо вычислить $n_{ij}$ – сколько раз номер элемента $x_i$ больше номера элемента $x_j$, т.е. элемент $x_i$ стоит выше элемента $x_j$ и $n_{ji}$ – сколько раз элемент $x_j$ стоит выше элемента $x_i$.
Степень ценности дополнительной информации об отношении в этой паре, будет тем выше, чем меньше разность $|n_{ij} - n_{ji}|$. Большее из чисел $n_{ij}, n_{ji}$ будет равняться числу доупорядочений множества [Ω, R∩δ]. Для рассматриваемого примера получим сводку характеристик графического представления доупорядочений


Из анализа таблицы следует, что наиболее полезной будет являться
информация об отношении в парах $(x_1, x_2)$ и $(x_4, x_5)$. Получение дополнительной информации об отношении в любой из этих пар приводит к сокращению числа линейных доупорядочений в два раза.

Заключение


Формулирование и решение ЗПР возможно только в ситуации множества альтернатив и выбора лучшей из них. Если выбора нет, то следуй путем на котором оказался.
В основе решений, принимаемых ЛПР, лежит его предпочтение, которое описывается отношением предпочтения. Наличие отношения позволяет построить математическую модель для проведения исследований. Неопределенность в предпочтениях устраняется использованием дополнительной информации, которая не является экспертной.

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

На конкретном числовом примере показано применение алгебраических методов решения ЗПР, без привлечения статистических выборок и эмпирических методов обработки.
В основе метода лежит результат теоремы о возможности продолжения частичного порядка до линейного (совершенного).

Список использованной литературы


1. Берж К. Теория графов и ее применение. – М.: ИЛ, 1962. – 320 с.
2. Ваулин А. Е. Дискретная математика в задачах компьютерной безопасности. Ч. I. СПб.: ВКА имени А. Ф. Можайского, 2015. – 219 с.
3. Ваулин А. Е. Дискретная математика в задачах компьютерной безопасности.Ч. II. СПб.: ВКА имени А. Ф. Можайского, 2017. – 151 с.
4. Ваулин А. Е. Методы исследования информационных вычислительных комплексов. Вып. 2. – Л.: ВИКИ им. А. Ф. Можайского, 1984. – 129 с.
5. Ваулин А. Е. Методология и методы анализа информационных вычислительных комплексов. Вып.1.– Л.: ВИКИ им. А. Ф. Можайского, 1981. – 117 с.
6. Ваулин А. Е. Методы цифровой обработки данных: дискретные ортогональные преобразования. – СПб.: ВИККИ им. А. Ф. Можайского, 1993. – 106 с.
7. Кузьмин В. Б. Построение групповых решений в пространствах четких и нечетких бинарных отношений. – М.: Наука,1982. – 168 с.
8. Макаров И. М. и др.Теория выбора и принятия решений.– М.: Физматлит, 1982. –328 с.52.
9. Розен В.В. Цель – оптимальность – решение.– М.: Радио и связь,1982.–169 с.
10. Szpilraijn E Sur Textension de l'ordre partiel. — Fundam. math.,1930, vol.16,pp.386-389.
Теги:
Хабы:
+6
Комментарии 0
Комментарии Комментировать

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн