Файл: Методические указания по выполнению лабораторной ра боты ЮгоЗап гос унт сост. В. В. Апальков, Р. А. Томакова.pdf

УДК 519.816
Составители: В.В. Апальков, Р.А. Томакова
Рецензент
Кандидат технических наук, доцент Е. И. Аникина
Многокритериальный выбор. Метод последовательных
уступок: методические указания по выполнению лабораторной ра- боты / Юго-Зап. гос. ун-т; сост.: В.В. Апальков, Р.А. Томакова. –
Курск: ЮЗГУ, 2017. – 12 с. Библиогр.: с. 12.
Излагается цель лабораторной работы, в теоретической части рассмат- риваются многокритериальная модель задачи принятия решений в услови- ях определенности, проблемы решения многокритериальных задач, метод последовательных уступок. В практической части приводятся пример выпол- нения задания на лабораторную работу и вопросы для самопроверки.
Методические указания соответствуют требованиям рабочей програм- мы по направлению подготовки бакалавров 09.03.04 «Программная инжене- рия».
Предназначены для студентов всех форм обучения направления подго- товки бакалавров 09.03.04 «Программная инженерия».
Текст печатается в авторской редакции
Подписано в печать
Формат 60 84 1/16.
Усл. печ. л. . Уч.- изд. л.
. Тираж 25 экз. Заказ. Бесплатно.
Юго-Западный государственный университет.
305040, г. Курск, ул. 50 лет Октября, 94.

Цель работы: изучить метод решения многокритериальных задач принятия решений (ЗПР) в условиях определенности – метод последовательных уступок.
Теоретическая часть
Многокритериальная модель задачи принятия решений в ус- ловиях определенности может быть представлена в виде:
, , ,
, , ,
t A K X f P r
, (1) где t – постановка задачи;
A – множество допустимых альтернативных решений;
K – множество критериев;
X
– множество шкал критериев;
f – отображение множества допустимых решений в множество векторных оценок;
P – система предпочтений ЛПР;
r
– решающее правило.
Структурная схема процесса построения и выбора оптимального решения для многокритериальной задачи принятия решений представ- лена на рисунке 1.
В реальных задачах, возникающих на практике, оценивание аль- тернативных решений осуществляется с помощью векторного крите- рия, компоненты которого являются не скалярами, а векторами.
В зависимости от содержания условия в постановке задачи могут возникать требования определения, например, наиболее предпочтительного решения, либо полностью упорядоченного множества допустимых решений, либо выделения множества не- доминируемых решений и т.д.
Множество A представляет собой совокупность альтернатив- ных решений, в каждой задаче удовлетворяющих определенным ограничениям и рассматриваемых как возможные способы дости- жения поставленной цели. Элементы множества A называются также допустимыми решениями, альтернативами, вариантами вы-
бора.
Множество допустимых альтернативных решений либо зада- ется, либо формируется в процессе исследования.
Рассматриваемые варианты выбора могут характеризоваться различными признаками, которые выражаются критериями из мно- жества K .

Рисунок 1 – Схема процесса выбора оптимального решения в мно- гокритериальной задаче принятия решений
Тогда каждому решению
i
A
ставится в соответствие n-мерная векторная оценка
1
,
,
(
)
i
i
in
x
х
х , где
ij
x
– оценка характеристики варианта
i
A
по шкале
j
X
критерия
j
K
,
1,...,
j
n
Совокупность векторных оценок свойств вариантов по шка-
Полученное упорядочивание соответствует поставленной за- даче?
Разработка оценочных шкал критериев
Формирование множе- ства допустимых ре- шений
Оценка допустимых решений по шкалам критериев
Получение информа- ции о предпочтениях
Построение решающе- го правила
Упорядочивание до- пустимых решений
Анализ результатов упорядочивания
Постановка задачи
Начало
?
Конец
Д
а нет да

лам критериев из множества X и образует множество допусти-
мых решений.
Качество варианта
i
A
при наличии многих критериев пред- ставляется векторной функцией
1
( ) (
)
,
,
i
i
i
im
y
f x
y
y
, где
( )
ik
k
i
y
f x
R
– оценка варианта
i
A
по частному критерию
k
f ,
1,...,
k
m
;
1
( ,...,
)
m
f
f
f
Совокупность векторных оценок вариантов образует множе-
ство оценок качества решения, или множество достижимых це-
лей.
В теории принятия решений предполагается, что каждое
ЛПР имеет некоторую свою систему предпочтений P , из которой он исходит при рациональных действиях.
Под системой предпочтений ЛПР будем понимать совокуп- ность обычно неструктурированных его представлений, связанных с достоинствами и недостатками сравниваемых решений.
В многокритериальной модели система предпочтений описы- вается совокупностью P некоторых множеств с соотношениями предпочтения (например, наборов критериев, интервалов между оценками допустимых решений определенного вида и т.п.).
Решающее правило (метод принятия решения)
r
представляет собой принцип сравнения векторных оценок и вынесения сужде- ний о предпочтительности одних из них по отношению к другим.
Оно может быть задано в виде аналитического выражения, алго-
ритма или словесной формулировки.
Например, из двух векторных оценок предпочтительнее та, которая имеет хотя бы одну максимальную компоненту и ни одной минимальной.
Решающее правило должно приводить к такому упорядоче- нию множества допустимых решений, которое соответствует со- держательной постановке задачи и согласуется с принятыми в мо- дели допущениями и системой предпочтений ЛПР. К принимаемым допущениям относятся допущения о полноте множества решений и набора критериев, о соответствии множества шкал множеству кри- териев и т.п. В зависимости от принятых допущений, а также от це- лей и предпочтений ЛПР, могут быть построены различные ре- шающие правила.

Проблемы, связанные с решением многокритериальных
задач принятия решений
При решении многокритериальных ЗПР возникает ряд специ- фических проблем, носящих не формальный (т. е. не вычислитель- ный), а концептуальный характер. Главная из них – рациональный выбор принципа оптимальности, определяющего свойства опти- мального решения и дающего ответ на вопрос – в каком смысле оп- тимальное решение лучше всех других решений (превосходит дру- гие решения).
Принципиальное отличие многокритериальных задач приня- тия решений от однокритериальных детерминированных задач за- ключается в том, что для них имеется множество различных прин- ципов компромисса и соответствующих им принципов оптималь- ности, которые приводят к выбору различных оптимальных реше- ний. Это предъявляет серьезные требования к выбору принципа оп- тимальности.
Рассмотрим основные проблемы, связанные с решением мно- гокритериальных задач принятия решений.
Проблема 1 – выделение области компромисса. В многокрите- риальных задачах принятия решений имеются противоречия между некоторыми частными критериями, составляющими векторный критерий. Однако эти противоречия обычно является нестрогими, так как иначе задача становится конфликтной антагонистической. В силу этого множество допустимых решений
A
D
распадается на две непересекающиеся части: область согласия
C
A
D
и область компро- мисса
K
A
D
. В области согласия
C
A
D
противоречий между частными критериями не возникает и качество решения может и должно быть улучшено одновременно по всем частным критериям или, во всяком случае, без снижения значений любого из них. В области компромисса
K
A
D
противоречия между некоторыми частными кри- териями имеются, при этом улучшение качества решения по одним частным критериям приводит к ухудшению качества решения по другим частным критериям.
Все это дает основание утверждать, что оптимальное ре-
шение может принадлежать только области компромисса, т. е.
*
K
A
A
D

В связи с этим утверждением, поиск оптимального решения надо ограничить только областью компромисса
K
A
D
. Отсюда воз- никает проблема 1 – выделение области компромисса
K
A
D
из мно- жества допустимых решений
A
D
. Выделение области компромисса
K
A
D
обычно является первым этапом при решении многокритери- альных задач принятия решений. При этом следует отметить важ- ный практический результат – сужение области альтернативных вариантов решений, что уже само по себе улучшает качество при- нимаемых решений. В отдельных случаях поиск оптимальных ре- шений с приемлемой для практики точностью можно ограничить выделением области компромисса.
Проблема 2 – выбор схемы компромисса и соответствующего
ей принципа оптимальности. Поиск оптимальных решений в об- ласти компромисса может быть осуществлен только на основе не- которой выбранной схемы компромисса. Число возможных схем компромисса достаточно велико, поэтому обоснование и рацио- нальный выбор схемы компромисса представляет собой сложную концептуальную проблему.
Рациональный выбор схемы компромисса соответствует рас- крытию смысла оператора оптимизации:
*
(
)
( )
A
f A
opt f A
A D
, (2) где
*
A
– оптимальный вариант выбора,
A
D
– множество допусти- мых решений, f – отображение множества допустимых решений в множество векторных оценок.
Проблема 3 – нормализация критериев. Эта проблема возни- кает в тех задачах, в которых частные критерии имеют различные единицы измерения. Для осуществления возможности оперирова- ния с векторными критериями необходимо нормализовать значения частных критериев, т. е. привести их к единому, безразмерному, масштабу измерения. К настоящему времени разработано большое число различных схем нормализации.
Проблема 4 – учет приоритета критериев. Частные крите- рии, составляющие векторный критерий, имеют различную важ- ность и значимость, что является основанием и позволяет упорядо- чить критерии. В связи с этим эта проблема сводится к рациональ- ному выбору схемы компромисса.

Перечисленные проблемы являются наиболее важными и час- то встречающимися, но они не охватывают всего множества про- блем, связанных с решением многокритериальных задач принятия решений. Следует отметить, что рассмотренные проблемы 2 - 4 но- сят концептуальный характер, и при их реализации следует при- менять различные эвристические процедуры, основанные на науч- ной аргументации, в которых существенная роль принадлежит экс- пертам и консультантам.
Перейдем от множества допустимых решений
A
D
к множест- ву
F
D
допустимых векторных оценок
1
( ,...,
)
m
f
f
f
, задаваемых частными критериями
k
f ,
1,...,
k
m
Рассмотрим возможный принцип компромисса – принцип по- следовательных уступок.
Метод последовательных уступок
В основу метода последовательных уступок положено требо- вание расположения частных критериев по значимости. Предпола- гается, что все частные критерии, составляющие векторный крите- рий упорядочены по убыванию важности:
1
,...,
m
f
f
. Будем также считать, что каждый из них нужно максимизировать.
Процедура построения компромиссного решения сводится к следующему.
Сначала находится решение, обращающее в максимум наибо- лее значимый частный критерий
1
f .
Затем назначается, исходя из практических соображений и точности определения исходных данных, величина некоторой «ус- тупки»
1
f , которую ЛПР согласен сделать для того, чтобы обра- тить в максимум второй частный критерий
2
f .
Налагаем на значение частного критерия
1
f ограничение, чтобы это значение было не меньше, чем
1 1
max –
f
f , и при этом ограничении находим решение, обращающее в максимум частный критерий
2
f .
Аналогично назначается «уступка» для частного критерия
2
f , ценой которой можно максимизировать частный критерий
3
f
, и так далее.

Достоинство такого способа построения компромиссного ре- шения заключается в том, что известна цена «уступки» в одном по- казателе для приобретения выигрыша в другом. При этом важно отметить, что свобода выбора решения, приобретаемая ценой даже незначительных «уступок», может оказаться существенной, так как в районе максимума обычно эффективность решения меняется очень слабо.
Практическая часть
Рассмотрим применение метода последовательных уступок на примере двухкритериальной задачи принятия решений:
1 1
2
( ) 3
max
f x
x
x
,
2 1
2
( )
7
max
f
x
x
x
, где
1 2
( ,
)
x
x x .
Множество допустимых решений
A
D
задается неравенствами:
1 2
2 4
x
x
,
1 2
10
x
x
,
1 2
,
0
x x
Пусть частные критерии, составляющие векторный критерий упорядочены по убыванию важности:
1 2
,
f f
. Находим решение, об- ращающее в максимум наиболее значимый частный критерий
1
f .
Первая задача имеет вид:
1 1
2
( ) 3
max
f x
x
x
,
при ограничениях
1 2
2 4
x
x
,
1 2
10
x
x
,
1 2
,
0
x x
Найдем решение этой задачи геометрическим методом (рису- нок 2).
Уравнение линии уровня функции
1
( )
f x
имеет следующий вид:

1 2
3x
x
c
, где
c
– const.
Градиент функции
1
( )
f x
– вектор
1
( ) (3; 1)
f x
, показываю- щий направление наибольшего возрастания функции в точке
x
Максимум частного критерия
1
f достигается в вершине мно- гоугольника допустимых решений
*
(10;0)
x
. При этом
*
1
(
) 30
f x
,
*
2
( ) 10
f x
Рисунок 2 – Графическое решение первой задачи
Назначим «уступку»
1 6
f
(20% от максимального значения критерия
1
f ) и решим вторую задачу:
2 1
2
( )
7
max
f
x
x
x
, при ограничениях
1 2
2 4
x
x
,
1 2
10
x
x
,
1 2
3 24
x
x
,
1 2
,
0
x x

Аналогично, геометрическим методом получим решение этой задачи (рисунок 3).
Уравнение линии уровня функции
2
( )
f
x
имеет следующий вид:
1 2
7
x
x
c
, где
c
– const.
Градиент функции
2
( )
f
x
– вектор
2
( ) (1;7)
f
x
Максимум частного критерия
2
f достигается в вершине мно- гоугольника допустимых решений
**
(8,5;1,5)
x
. При этом
**
2
(
) 19
f x
,
**
1
(
) 24
f x
Рисунок 3 – Графическое решение второй задачи
Отметим, что оптимальное решение последней задачи
**
(8,5;1,5)
x
принадлежит множеству Парето (
точки отрезка, со- единяющего две вершины многоугольника допустимых решений первой задачи с координатами (0;10) и (10;0) ).

Вопросы для самопроверки
1. Многокритериальная модель ЗПР в условиях определен- ности.
2. Множество допустимых решений.
3. Множество достижимых целей.
4. Система предпочтений ЛПР.
5. Решающее правило.
6. Проблемы, связанные с решением многокритериальных
ЗПР.
7. Область согласия.
8. Область компромисса.
9. Принцип последовательных уступок.
Литература
1.
Лотов, В.А. Многокритериальные задачи принятия ре- шений [Текст]: учебное пособие / В.А. Лотов, И.И. Поспелова. – М:
МАКС Пресс, 2008. – 197 с.
2.
Ногин, В.Д. Принятие решений в многокритериальной среде. Количественный подход / В.Д. Ногин. – 2-е изд., испр. и доп.
– М.: ФИЗМАТЛИТ, 2005. –176 с.
3. Петровский, А. Б. Теория принятия решений [Текст]: учеб- ник / А. Б. Петровский. – М.: Академия, 2009. – 400 с.
4. Томакова, Р. А. Методы и алгоритмы теории принятия ре- шений [Текст]: учебное пособие / Р. А. Томакова, В. В. Апальков;
Юго-Зап. гос. ун-т. – Курск: ЮЗГУ, 2015. – 164 с.
5. Черноруцкий, И. Г. Методы принятия решений [Текст]: учебное пособие для студентов вузов / И. Г. Черноруцкий. – СПб.:
БХВ-Петербург, 2005. – 416 с.