Турунтаев Л.П. Теория принятия решений

Подождите немного. Документ загружается.

121

1 0 0.72

0 1 0.2

0.79

72.0)05.375(75.270

=−=

′

2/0)0700(139

−

′

)350497()3505.466(

−

′

= 116.5:147=0.79

3. Рассчитываются весовые коэффициенты

10.36

10.1

−

;

10.36

1 0.395

−

;

123

ααα

0.9

– 0.64

=0;

0.605

– 0.64

=0;

123

1++=

ααα

Решая эту систему уравнений, получаем:

=0.3;

=0.42;

=0.28.

Шаг

1. Определяется решение по глобальному критерию

()

∑

Решая задачу линейного программирования

0.3

500 750

375500

⋅

+0.42

700

⋅

+0.28 →

⋅++

⋅

497

33.1)(5.0

max

при ограничениях на ресурсные параметры:

0.06

x 0.06

0.07

≤

42;

0.04

+0.085

≤

34; (*)

0.035

+0.035

+0.12

≤

42;

ÏÑ

,, 0

xxx

≥

ÏÑ

xxx

— целые.

Получим компромиссное решение

с координатами

=0;

=517;

=156.

2. Вектор критериальных оценок

для решения

122

{

}

ÑÑÑ

123

();();()

yy y

PXXX

= ={117 тыс. руб.; 517 шт.; 466.5 час}.

Шаг

Формируется сообщение ЭВМ для ЛПР

Критерии

Вектор оценок

Вектор

идеальных

решений

∗

375.5 тыс.

руб.

700 шт. 497 час

Вектор

компро-

миссных решений

117 тыс. руб. 517 шт. 466.5 час

Шаг

ЛПР оценивает компромиссное решение по значениям кри-

териев. Если оно считает это решение удовлетворительным, то

процедура поиска на этом заканчивается. Иначе, переходим на

следующий шаг.

Шаг

ЛПР указывает, какой из критериев в векторе

имеет

наименее удовлетворительное значение. Пусть оно указывает на

критерий 1 и устанавливает порог в 300 тыс. руб., то есть дает

сообщение

{1; 300 тыс. руб.}.

Переходим на шаг

Шаг

1. Рассчитывается матрица

Решения

);(

;С

xxx

X =

Критерии

∗

(0;700;0) =

∗

(

279;(1–

)279;268)

(шт.)

700 0

279

(час)

350 497

123

2. Нормируем таблицу

по каждому из критериев, при-

няв

=139 шт.

1 0

′

0 1

3. Рассчитываются весовые коэффициенты

=0.5;

=0.5.

Шаг

1. Определяется решение по глобальному критерию

()

∑

Решаем задачу

0.5

700

⋅

+0.5

ÏÑ

0.5 ( ) 1.33

497

xx x

⋅++⋅

⋅→

max

при ограничениях на ресурсные параметры (*) и на значение

критериальной функции

500

+750

≥

300000.

Получим новое компромиссное решение

с координата-

ми

=365;

=152;

=156.

2. Вектор критериальных оценок

для решения

{

}

ÑÑÑ

123

();();()

yy y

PXXX

= ={300 тыс. руб.; 152 шт.;

466.5 час}.

Шаг

Формируется сообщение для ЛПР

Критерии

Вектор оценок

∗

идеальных решений

375.5 тыс.

руб.

700 шт. 497 час

компромиссных

решений

300 тыс. руб. 152 шт. 466.5 час

124

Шаг

ЛПР оценивает полученное решение. Если оно считает это

решение удовлетворительным, то процедура поиска решения

заканчивается, иначе, повторяются шаги

233 3

,,,,

EAB D

6.2 Метод порогов несравнимости «ЭЛЕКТРА»

В методе «ЭЛЕКТРА» [18] разработана процедура много-

критериального выбора наиболее предпочтительных объектов,

включающая следующие этапы.

1. Для каждого из критериев вводится дискретная шкала

возможных значений этого критерия, весовые коэффициенты

критериев.

2. Для каждого из критериев строится граф, вершинами ко-

торого являются отдельные объекты множества, а дуги указы-

вают на отношение доминирования между объектами в соответ-

ствии с данным критерием.

3. С учетом важности критериев и предпочтительности объ-

ектов вычисляются матрицы значений специальных коэффици-

ентов, называемых индексами согласия и несогласия.

4. Для каждой пары объектов

(, )xy X

∈

считается установ-

ленным отношение превосходства, скажем х над у, если значе-

ние соответствующего индекса согласия больше некоторого по-

рогового значения, а индекс несогласия — меньше соответст-

вующего порогового значения.

5. Строится обобщенный граф превосходства, структура ко-

торого зависит от выбранных пороговых значений.

Рассмотрим следующую задачу. Пусть Х представляет со-

бой множество абитуриентов, принимающих участие в конкурс-

ных экзаменах при поступлении в технический вуз. На основа-

нии проведенных экзаменов необходимо отобрать лучших кан-

дидатов. Состав дисциплин и возможные способы оценки аби-

туриентов по дисциплинам могут варьироваться согласно спе-

цифическим особенностям вуза. Рассмотрим этапы процедуры

«ЭЛЕКТРА».

1. В качестве примера рассмотрим оценки трех абитуриен-

тов по трем дисциплинам в пятибалльной шкале (табл. 6.2).

125

Таблица 6.2 — Оценки вступительных экзаменов

Абитуриенты Дисциплина

Математика Физика Литература

x 5 3 4

y 5 4 3

z 4 5 3

Обозначим:

,,xyz X∈ — множество оцениваемых объектов;

— оценка объекта x по критерию , 1,3;ii=

— весовой коэффициент критерия ;3,1 , =ii

0 1(10,100, ...).

c<<

Пусть

123

5, 3, 2.ccc===

2. Для каждого критерия i строим граф

(,),

GXV=

где

— множество дуг графа

(рис. 6.1). Дуга в графе

из

вершины х в вершину у существует, если

xy≥ Равенство оце-

нок

в графе влечет наличие двух дуг из х в у и из у в х.

(, ) , 1,3.

iii

xy V x y i∈⇔≥ =

Построим объединенный граф

(, ),GXV

где

есть пересечение трех графов с дугами

V (рис. 6.2). В нашем

примере

V = {Ø}, т.к. в трех графах нет дуг, одновременно сов-

Рис. 6.1 — Графы отношений по математике (а),

физике (б) и литературе (в)

126

падающих по направлению. Объединенный граф характеризует

полное согласие превосходства одних объектов над другими.

3. Строим матрицу индексов согласия превосходства объек-

тов и матрицу индексов несогласия с этим превосходством.

Рассмотрим пару объектов

(, ) .xy X

∈

Применительно к ней

множество всех критериев может быть разбито на два «проти-

воположных» класса. К первому классу

(, )Cxy отнесем все

критерии

k , для которых , 1,3,

xyi≥= т.е. критерии, соглас-

но которым в графах

G имеет место дуга (х, у):

{

}

(, ) (, ) , 1,3

Cxy k xy V i=∈=.

В примере

13 1 3 1 2

(, ) { , }; (,) { , }; (,) { , };Cxy k k Cxz k k Cyx k k== =

13 2 23

(,)

{

}

; ( , )

{}

; ( , )

{

}

zkkCzxkCz

kk===

где

k — математика,

k — физика,

k — литература.

Ко второму классу (, )

xy пары объектов (, )xy отнесем

критерии

k , для которых отсутствуют в графах

G дуги ),( yx :

{

}

(, ) (, ) , 1,3

Dxy k xy V i=∉=

В примерах

223

(,){}; (,){}; (,){}; Dxy k Dxz k Dxy k===

2131

(,)

{}

; ( , )

{

}

; ( , )

{}

zkDzxkkDz

k== =

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

(,)

(, ) ,

kCxy

cxy c

∈

∑

где

c — весовой коэффициент критерия

k ;

∑

Рис. 6.2 — Объединенный граф

127

Матрица индексов согласия будет иметь вид

−

5,03,0

7,08,0

7,07,0

Индексы согласия в матрице

),( yxc могут изменяться от 0

до 1 и выражают степень согласия о предпочтении х над у.

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

(,)

åñëè

0, ( , ) ;

(, )

max , ( , ) ,

kDxy

Dxy

dxy

yx Dxy

∈

=∅







−

≠∅





где d — нормирующий коэффициент, равный максимальному

разбросу оценок на всем множестве критериев.

Матрица индексов несогласия будет иметь вид

−

5,05,0

15,0

Индексы несогласия

(, )dxy в матрице могут изменяться от

0 до 1 и выражают степень несогласия, недоверия к превосход-

ству х над у.

Абсолютная уверенность в превосходстве х над у будет при

(, ) 1cxy = и 0),( =yxd . В объединенном графе

G в этом случае

будет дуга (х,у).

4. Вводится отношение превосходства на объектах через

пороговые значения p и q. Значение порога p вводится для ин-

дексов согласия и должно быть ближе к единице, значение по-

рога q вводится для индексов несогласия и должно быть ближе к

нулю. Говорят, что объект х превосходит объект у, если

(, ) è (, ) ,cxy p dxy q≥≤ т.е. выполняются следующие условия:

• совокупность критериев (с учетом их относительной важ-

ности) по которым

xyf достаточна представительна (порог p);

x y z

128

• оценки по остальным критериям не дают достаточных

оснований (порог q) для отказа о превосходстве

, степень

недоверия к этому предположению не выходит за допустимый

предел

5. Объединенный граф превосходства

(1; 0)G при

1 è 0pq== представлен на рис. 6.2. В графе (,)Gpq появится

дополнительная дуга (рис. 6.3), например, если верхний порог

0,8,p = а нижний порог .5,0

q Всегда

(1; 0)G является час-

тичным графом

(,), Gpq

′′

если

1, à 0.pq

′

6.3 Многокритериальная задача о назначениях

В практике организационного управления весьма распро-

странена задача принятия решения о распределении прав, обя-

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

название задачи о назначениях. Приведем несколько примеров

многокритериальных задач [12]. Выпускники военной академии

получают назначения на места службы. Каждый офицер имеет

определенные пожелания (в соответствии со своими возможно-

стями) относительно места службы. В свою очередь, в зависи-

мости от места службы определенные требования предъявляют-

ся к офицеру. Необходимо найти наилучшие (с точки зрения

обеих сторон) назначения.

В студенческом общежитии студенты первого курса рассе-

ляются по комнатам. Возникает необходимость расселить сту-

дентов так, чтобы учесть определенные требования со стороны

студентов к своим соседям (например, предпочитают в комнате

некурящих, занимающихся спортом либо художественной са-

модеятельностью и т.п.) и к расположению комнаты. С другой

Рис. 6.3 — Обобщенный граф G(0,8;0,5)

129

стороны, каждое помещение имеет определенные характеристи-

ки. Необходимо найти такой вариант распределения, при кото-

ром бы был обеспечен нормальный психологический климат в

коллективе.

Выставочный комплекс располагает местами для демонст-

рации экспонатов со своими возможностями. Экспонаты долж-

ны демонстрироваться в определенных условиях (требования к

свету, площади и т.д.). Необходимо разместить наиболее удачно

экспонаты с точки зрения целостного восприятия выставочной

экспозиции.

Во всех приведенных примерах определяются пары наи-

большего соответствия возможностей одних элементов (будем

называть их в дальнейшем субъектами) требованиям других

элементов (будем называть их объектами).

Сделаем содержательную и формальную постановку мно-

гокритериальной задачи о назначениях.

Пусть имеется

n субъектов и n объектов, каждый из кото-

рых характеризуется совокупностью оценок по

m критериям.

Оценка возможностей субъектов по соответствующим критери-

ям и оценка потребностей объектов по этим критериям пусть

производится в пятибалльной шкале измерения. Имеется ЛПР,

ответственное за решение задачи. Необходимо определить

наиболее близких по своим оценкам пар «объект-субъект».

Основная идея подхода к решению задачи схожа с процеду-

рой образования пар в известной телевизионной передаче «Лю-

бовь с первого взгляда», в которой образование пар молодых

людей происходит, если их взгляды и выбор совпадают.

Пусть

(1,)

Ci n= и (1,)On

ν= — множество субъектов и

объектов.

(

)

, , ..., , ...,

Ccc c c= — множество оценок возможностей

субъектов

,1,ii n= ,

где

(

)

, , ..., , ...,

iii i i

ccc c c=

— вектор оценок субъекта

по

критериям

mjj ,1, = ,

c — оценка i -го субъекта по критерию

130

(

)

, , ..., , ...,

Ooo o o

= — множество оценок потребностей

(требований) объектов

n,1, =νν ,

где

(

)

, , ..., , ...,

ooo o o

ννν ν ν

— вектор оценок объекта

по

критериям

mjj ,1, = ,

— оценка

-го субъекта по критерию j .

Далее работу алгоритма решения задачи проследим на при-

мере.

Пусть решается задача распределения курсантов на практи-

ку в воинские подразделения. Оценки по критериям (теоретиче-

ская подготовка, техническая, боевая, строевая) приведены в

табл. 6.3.

Таблица 6.3 — Значения оценок по критериям субъектов и объектов

Критерии Критерии

Субъект

1 2 3 4

Объект

1 2 3 4

4 3 5 1

3 2 5 2

4 3 4 3

4 3 5 2

3 1 4 1

4 3 4 3

На первый объект может быть распределен один из трех

курсантов, при этом приоритет распределения у курсантов будет

зависеть от степени соответствия их оценок оценкам первого

объекта. Аналогично для второго и третьего объектов. Можно

получить информацию

относительно каждого объекта

)3,1( =νν о распределении курсантов )3,1(

ii через индексы

несоответствия возможностей курсантов потребностям воин-

ских подразделений в виде матрицы индексов несоответствия