Турунтаев Л.П. Теория принятия решений. Учебное пособие томск 2007 Томский межвузовский центр

• Название: Учебное пособие томск 2007 Томский межвузовский центр
• Анкор: Турунтаев Л.П. Теория принятия решений.pdf
• Дата: 29.12.2017
• Размер: 1.57 Mb.
• Имя файла: Турунтаев Л.П. Теория принятия решений.pdf
• Тип: Учебное пособие; #13417
• страница: 13 из 18

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
− ».