Турунтаев Л.П. Теория принятия решений. Учебное пособие томск 2007 Томский межвузовский центр
![]()
|
z у х z у х z у х а б в Рис. 6.1 — Графы отношений по математике (а), физике (б) и литературе (в) 126 падающих по направлению. Объединенный граф характеризует полное согласие превосходства одних объектов над другими. 3. Строим матрицу индексов согласия превосходства объек- тов и матрицу индексов несогласия с этим превосходством. Рассмотрим пару объектов ( , ) x y X ∈ Применительно к ней множество всех критериев может быть разбито на два «проти- воположных» класса. К первому классу ( , ) C x y отнесем все критерии i k , для которых , 1,3, i i x y i ≥ = т.е. критерии, соглас- но которым в графах i G имеет место дуга (х, у): { } ( , ) ( , ) , 1,3 i i C x y k x y V i = ∈ = В примере 1 3 1 3 1 2 ( , ) { , }; ( , ) { , }; ( , ) { , }; C x y k k C x z k k C y x k k = = = 1 3 2 2 3 ( , ) { , }; ( , ) { }; ( , ) { , }, C y z k k C z x k C z y k k = = = где 1 k — математика, 2 k — физика, 3 k — литература. Ко второму классу ( , ) D x y пары объектов ( , ) x y отнесем критерии i k , для которых отсутствуют в графах i G дуги ) , ( y x : { } ( , ) ( , ) , 1,3 i i D x y k x y V i = ∉ = В примерах 2 2 3 ( , ) { }; ( , ) { }; ( , ) { }; D x y k D x z k D x y k = = = 2 1 3 1 ( , ) { }; ( , ) { , }; ( , ) { }. D y z k D z x k k D z y k = = = Рассчитываем матрицу для индексов согласия по формуле ( , ) 1 ( , ) , i i k C x y c x y c c ∈ = ∑ где i c — весовой коэффициент критерия i k ; 3 1 i i c c = = ∑ z у х Рис. 6.2 — Объединенный граф 127 Матрица индексов согласия будет иметь вид − − − 5 , 0 3 , 0 7 , 0 8 , 0 7 , 0 7 , 0 z y x Индексы согласия в матрице ) , ( y x c могут изменяться от 0 до 1 и выражают степень согласия о предпочтении х над у. Рассчитываем матрицу для индексов несогласия по формуле ( , ) åñëè åñëè 0, ( , ) ; ( , ) 1 max , ( , ) , i i i k D x y D x y d x y y x D x y d ∈ = ∅ = − ≠ ∅ где d — нормирующий коэффициент, равный максимальному разбросу оценок на всем множестве критериев. Матрица индексов несогласия будет иметь вид − − − 5 , 0 5 , 0 5 , 0 5 , 0 1 5 , 0 z y x Индексы несогласия ( , ) d x y в матрице могут изменяться от 0 до 1 и выражают степень несогласия, недоверия к превосход- ству х над у. Абсолютная уверенность в превосходстве х над у будет при ( , ) 1 c x y = и 0 ) , ( = y x d . В объединенном графе 0 G в этом случае будет дуга (х,у). 4. Вводится отношение превосходства на объектах через пороговые значения p и q. Значение порога p вводится для ин- дексов согласия и должно быть ближе к единице, значение по- рога q вводится для индексов несогласия и должно быть ближе к нулю. Говорят, что объект х превосходит объект у, если ( , ) è ( , ) , c x y p d x y q ≥ ≤ т.е. выполняются следующие условия: • совокупность критериев (с учетом их относительной важ- ности) по которым x y f достаточна представительна (порог p); x y z x y z 128 • оценки по остальным критериям не дают достаточных оснований (порог q) для отказа о превосходстве x y f , степень недоверия к этому предположению не выходит за допустимый предел i q 5. Объединенный граф превосходства 0 (1;0) G при 1 è 0 p q = = представлен на рис. 6.2. В графе ( , ) G p q появится дополнительная дуга (рис. 6.3), например, если верхний порог 0,8, p = а нижний порог 5 , 0 = q Всегда 0 (1; 0) G является час- тичным графом ( , ), G p q ′ ′ если 1, à 0. p q ′ ′ < > 6.3 Многокритериальная задача о назначениях В практике организационного управления весьма распро- странена задача принятия решения о распределении прав, обя- занностей, работ, благ между членами коллектива, получившая название задачи о назначениях. Приведем несколько примеров многокритериальных задач [12]. Выпускники военной академии получают назначения на места службы. Каждый офицер имеет определенные пожелания (в соответствии со своими возможно- стями) относительно места службы. В свою очередь, в зависи- мости от места службы определенные требования предъявляют- ся к офицеру. Необходимо найти наилучшие (с точки зрения обеих сторон) назначения. В студенческом общежитии студенты первого курса рассе- ляются по комнатам. Возникает необходимость расселить сту- дентов так, чтобы учесть определенные требования со стороны студентов к своим соседям (например, предпочитают в комнате некурящих, занимающихся спортом либо художественной са- модеятельностью и т.п.) и к расположению комнаты. С другой z у х Рис. 6.3 — Обобщенный граф G(0,8;0,5) 129 стороны, каждое помещение имеет определенные характеристи- ки. Необходимо найти такой вариант распределения, при кото- ром бы был обеспечен нормальный психологический климат в коллективе. Выставочный комплекс располагает местами для демонст- рации экспонатов со своими возможностями. Экспонаты долж- ны демонстрироваться в определенных условиях (требования к свету, площади и т.д.). Необходимо разместить наиболее удачно экспонаты с точки зрения целостного восприятия выставочной экспозиции. Во всех приведенных примерах определяются пары наи- большего соответствия возможностей одних элементов (будем называть их в дальнейшем субъектами) требованиям других элементов (будем называть их объектами). Сделаем содержательную и формальную постановку мно- гокритериальной задачи о назначениях. Пусть имеется n субъектов и n объектов, каждый из кото- рых характеризуется совокупностью оценок по m критериям. Оценка возможностей субъектов по соответствующим критери- ям и оценка потребностей объектов по этим критериям пусть производится в пятибалльной шкале измерения. Имеется ЛПР, ответственное за решение задачи. Необходимо определить n наиболее близких по своим оценкам пар «объект-субъект». Основная идея подхода к решению задачи схожа с процеду- рой образования пар в известной телевизионной передаче «Лю- бовь с первого взгляда», в которой образование пар молодых людей происходит, если их взгляды и выбор совпадают. Пусть ( 1, ) i C i n = и ( 1, ) O n ν ν = — множество субъектов и объектов. ( ) 1 2 , , ..., , ..., i n C c c c c = — множество оценок возможностей субъектов , 1, i i n = , где ( ) 1 2 , , ..., , ..., j m i i i i i c c c c c = — вектор оценок субъекта i по критериям m j j , 1 , = , j i c — оценка i -го субъекта по критерию j . 130 ( ) 1 2 , , ..., , ..., n O o o o o ν = — множество оценок потребностей (требований) объектов n , 1 , = ν ν , где ( ) 1 2 , , ..., , ..., j m o o o o o ν ν ν ν ν = — вектор оценок объекта ν по критериям m j j , 1 , = , j o ν — оценка ν -го субъекта по критерию j . Далее работу алгоритма решения задачи проследим на при- мере. Пусть решается задача распределения курсантов на практи- ку в воинские подразделения. Оценки по критериям (теоретиче- ская подготовка, техническая, боевая, строевая) приведены в табл. 6.3. Таблица 6.3 — Значения оценок по критериям субъектов и объектов Критерии Критерии Субъект 1 2 3 4 Объект 1 2 3 4 1 c 4 3 5 1 1 o 3 2 5 2 2 c 4 3 4 3 2 o 4 3 5 2 3 c 3 1 4 1 3 o 4 3 4 3 На первый объект может быть распределен один из трех курсантов, при этом приоритет распределения у курсантов будет зависеть от степени соответствия их оценок оценкам первого объекта. Аналогично для второго и третьего объектов. Можно получить информацию T ν относительно каждого объекта ) 3 , 1 ( = ν ν о распределении курсантов ) 3 , 1 ( = i i через индексы несоответствия возможностей курсантов потребностям воин- ских подразделений в виде матрицы индексов несоответствия i c ν 131 1 o 2 o 3 o 1 c 11 c 12 c 13 c 2 c 21 c 22 c 23 c 3 c 31 c 32 c 33 c 1 T ↑ 2 T ↑ 3 T ↑ ( ) 1 , ..., , ..., j m i i i i c c c c ν ν ν ν = — вектор несоответствия возмож- ностей субъекта i требованиям объекта ν , где j i c ν — индекс несоответствия пары ) ( ν i по критерию j . åñëè èí à÷å 0, 0 , j j i j i j j i c o c o c ν ν ν − ≥ = − Тогда на основании информации 1 2 3 : , , T c c c ν ν ν ν можно ус- тановить бинарные отношения между субъектами 1 2 3 , , c c c в предположении, что они будут распределяться на объект ν o : • отношение строгого предпочтения (Парето) P — ( ) ( ) { } k p k i j p j i p i c c j k n j c c c P c ν ν ν ν ν ν < ≠ ∃ ∧ = ≤ ⇔ , , 1 , ; • отношение эквивалентности I — { } , 1, j j i p i p c I c c c j n ν ν ν ν ⇔ = = ; • отношение несравнимости N — ( ) ( ) { } 1, , , , j j k k i p i p i p c N c j n c c k j c c ν ν ν ν ν ν ⇔ ∃ = < ∧ ∃ ≠ > Определим вектора ν i c и покажем отношения между субъ- ектами по каждому объекту графически (рис. 6.4). (возможность выше потребности); (возможность ниже потребности). 132 ( ) 1 ; 0 ; 0 ; 0 11 = c ( ) 1 ; 0 ; 0 ; 0 12 = c ( ) 2 ; 0 ; 0 ; 0 13 = c ( ) 0 ; 1 ; 0 ; 0 21 = c ( ) 0 ; 1 ; 0 ; 0 22 = c ( ) 0 ; 0 ; 0 ; 0 23 = c ( ) 1 ; 1 ; 1 ; 0 31 = c ( ) 1 ; 1 ; 2 ; 1 32 = c ( ) 2 ; 0 ; 2 ; 1 33 = c Рассмотрим распределение курсантов с другой позиции. Определенный курсант может быть распределен на один из трех объектов, при этом предпочтение будет отдаваться тому объек- ту, у которого степень соответствия требований возможностям курсанта будет выше относительно других объектов. Информацию i S относительно каждого курсанта ( 1,3) i i = о приоритетном предоставлении мест практики можно получить через матрицу индексов соответствия требований воинских подразделений возможностям курсанта i o ν 1 c 2 c 3 c 1 o 11 o 12 o 13 o 2 o 21 o 22 o 23 o 3 o 31 o 32 o 33 o 1 S ↑ 2 S ↑ 3 S ↑ 3 c 1 c 2 c : 1 T 3 c 1 c 2 c : 2 T 3 c 1 c 2 c : 3 T а б в Рис. 6.4 — Графы отношений 3 2 1 , , T T T между субъектами относительно объектов 1 o (а), 2 o (б) и 3 o (в) 133 ( ) 1 , ..., , ..., j m i i i i o o o o ν ν ν ν = — вектор соответствия требований ν -го объекта возможностям i -го субъекта, где j i o ν — индекс соответствия пары ) ( i ν по критерию j . Определим j j i i o c ν ν = − как j -ю компоненту вектора i o ν , ха- рактеризующего соответствие между характеристиками ν -го объекта и i -го субъекта. На основании информации 1 2 3 : , , i i i i S o o o можно устано- вить бинарные отношения между объектами 1 2 3 , , o o o относи- тельно субъекта i c в предположении, что они наиболее полно позволят реализовать на практике его возможности: • отношение строгого предпочтения P — ( ) ( ) { } , 1, , j j k k i ti i ti i ti o P o o o j n k j o o ν ν ν ⇔ ≥ = ∧ ∃ ≠ > ; • отношение эквивалентности I — { } , 1, j j i ti i ti o I o o o j n ν ν ⇔ = = ; • отношение несравнимости N — ( ) ( ) { } 1, , , , ν ν ν ⇔ ∃ = > ∧ ∃ ≠ < j j k k i ti i ti i ti o N o j n o o k j o o Определим вектора i o ν для нашего примера и покажем от- ношения между объектами по каждому субъекту графически (рис. 6.5). 134 ( ) 1 ; 0 ; 0 ; 0 11 − = o ( ) 0 ; 1 ; 0 ; 0 12 − = o ( ) 1 ; 1 ; 1 ; 0 13 − − − = o ( ) 1 ; 0 ; 0 ; 0 21 − = o ( ) 0 ; 1 ; 0 ; 0 22 − = o ( ) 1 ; 1 ; 2 ; 1 23 − − − − = o ( ) 2 ; 0 ; 0 ; 0 31 − = o ( ) 0 ; 0 ; 0 ; 0 32 = o ( ) 2 ; 0 ; 2 ; 1 33 − − − = o Для определения пар «объект-субъект» проанализируем графы отношений субъектов T ν и объектов i S . В графах будем послойно выделять вершины, над которыми нет доминирующих вершин (в эти вершины не входят однонаправленные дуги). В каждый слой будут входить вершины с отношениями либо эк- вивалентности, либо несравнимости. Вершины первого слоя бу- дут доминировать над вершинами второго слоя, второго — над вершинами третьего и т.д. Несравнимым вершинам первого слоя присваивают индекс 1 N , эквивалентности — 1 I , для второ- го слоя соответственно присваивают индексы 2 2 , N I и т.д. 1 o … ν o … n o 1 c … 1 N i c … 1 N 2 N 2 N i S n c 2 I ν T 3 o 1 o 2 o : 1 S : 2 S 3 o 1 o 2 o : 3 S а б в Рис. 6.5 — Графы отношений 3 2 1 , , S S S между объектами относительно субъектов 1 c (а), 2 c (б) и 3 c (в) 3 o 1 o 2 o Рис. 6.6 — Матрица сходства Всю информацию, по- лученную при послойном выделении вершин, зане- сем в таблицу сходства (рис. 6.6). Строкам матри- цы сходства соответствуют субъекты, столбцам — объекты. 135 В каждой клетке матрицы сходства проставляются индек- сы: в верхней ее части — из графа несоответствия T ν , в нижней ее части — из графа соответствия i S . Очевидному индексу соответствует клетка матрицы сходст- ва с индексами 1 I \ 1 I . В случае если имеются такие клетки, де- лается идеальное назначение и понижается размерность задачи. После понижения размерности задачи необходимо вернуть- ся к графам T ν и i S и опять составить матрицу сходства. Если в матрице сходства нет клеток « 1 I \ 1 I », то для назначения необхо- димо обратиться к ЛПР за дополнительной информацией [12]. Для наших графов отношений матрица сходства будет иметь вид 1 o 2 o 3 o 1 c 1 N 1 I 1 N 1 I 2 I 2 I 2 c 1 N 2 I 1 N 2 I 1 I 1 I 3 c 2 I 1 N 2 I 2 I 3 I 1 N Идеальное назначение « 2 3 c o − », понижаем размерность за- дачи (не учитываем далее субъект второй и объект третий) и 3 c 1 c : 1 T 3 c 1 c : 2 T 1 o 2 o : 1 S 1 o 2 o : 3 S Рис. 6.7 — Графы отношений между субъектами и объектами 136 обращаемся к графам отношений, не учитывая в них 2 c и 3 o . Получим новые графы отношений (рис. 6.7). Строим матрицу сходства: 1 o 2 o 1 c 1 I 1 I 1 I 1 I 3 c 2 I 1 I 2 I 2 I Идеальное назначение либо « 1 1 c o − », а далее назначение « 3 2 c o − », либо назначения « 1 2 c o − » и « 3 1 c o − ». Таким образом, возможны варианты решения задачи: 1) « 2 3 c o − », « 1 1 c o − », « 3 2 c o − »; 2) « 2 3 c o − », « 1 2 c o − », « 3 1 c o − ». |