Батищев Д. - Многокритериальный выбор с учетом индивидуальных предпочтений
РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРИКЛАДНОЙ ФИЗИКИ
В монографии рассматриваются человеко-машинные процедуры решения задач многокритериального выбора.
Основное внимание уделяется анализу и использованию качественной информации об относительной важности критериев оптимальности при принятии решений. Описывается диалоговая программная система многокритериального выбора и приводятся примеры решения конкретных задач.
ВВЕДЕНИЕ
Задачи принятия решений представляют собой широкий класс задач в различных предметных областях, в частности в системах автоматизированного проектирования (САПР) и в автоматизированных системах научных исследований (АСНИ). При этом проектировщик (исследователь, разработчик) должен, во-первых, подготовить множество допустимых для выбора вариантов решения, во-вторых, сформулировать цели принятия решения и, в-третьих, осуществить выбор либо одного, либо множества решений, оптимальных с его точки зрения. Одной из возможностей решения поставленной задачи является переход от задачи принятия решения к задаче нелинейной оптимизации.
Однако такой переход связан с рядом трудностей. Основная трудность - преодоление неопределенности целей. Для сведения задачи принятия решения к задаче нелинейной оптимизации проектировщик должен оценить качество каждого варианта в виде числовой характеристики (критерия) и выбрать лучший вариант с наибольшим (или наименьшим) значением.
Но дать такую оценку довольно сложно. Техническое устройство характеризуется несколькими критериями качества, зачастую противоречивыми, т. е. улучшение одной характеристики приводит к ухудшению другой.
Для решения подобной многокритериальной задачи необходимо учитывать относительную важность частных критериев оптимальности.
Наиболее распространенный способ учета предпочтений проектировщика назначение критериям весовых коэффициентов. Но неопределенность остается: одинаковые предпочтения могут определить совершенно разный набор весовых коэффициентов.
В данной монографии описываются эффективные человеко-машинные процедуры многокритериального выбора, обеспечивающие сочетание экспертной информации об отношениях предпочтения на множестве критериев с результатами решения экстремальных задач, обеспечивающих эффективность по Парето.
Описываются различные методы решения многокритериальных задач оптимизации, использующие качественную и количественную информацию о предпочтениях на множестве критериев. Основное внимание уделено методу свертывания векторного критерия оптимальности с использованием весовых коэффициентов относительной важности частных критериев.
В качестве обобщенных критериев рассматриваются аддитивный критерий оптимальности; обобщенные логические критерии оптимальности; среднестепенной обобщенный критерий.
Описываются существующие способы назначения весовых коэффициентов, при использовании которых от лица, принимающего решение (ЛПР), требуется либо дать точные численные оценки, либо сравнить по важности все частные критерии между собой.
Предлагается подход, при котором учитывается зависимость весовых коэффициентов от значения частных критериев в каждой точке области допустимых решений. В этом случае весовые коэффициенты можно рассматривать как неконтролируемые факторы с областью допустимых значений и вычислить их, применяя принцип гарантированного результата.
Подробно рассматриваются виды дополнительной качественной информации об относительной важности частных критериев и их влияние на область допустимых значений весовых коэффициентов.
Вторая глава содержит решение задач по определению по принципу гарантированного результата оптимальных значений весовых коэффициентов важности для различных типов обобщенных критериев и-дополнительной информации о бинарных отношениях предпочтения при заданных значениях векторных оценок альтернатив. В п. 2.1 приводится решение задачи вычисления весовых коэффициентов для аддитивного критерия оптимальности. В п. 2.2 приводится решение задачи вычисления весовых коэффициентов для обобщенных логических критериев оптимальности.
В п. 2.3 приводится решение задачи вычисления весовых коэффициентов для среднестепенного обобщенного критерия. Решения приводятся в аналитическом виде или в виде алгоритмов вычисления.
Все решения приводятся в виде теорем с доказательствами.
Третья глава посвящена характеристике диалоговых систем поддержки принятия решений. Описывается диалоговая программная система, построенная на основе разработанных моделей и методов: архитектура, возможности, средства ведения диалога.
В четвертой главе приведены примеры решения конкретных практических задач.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований. Грант 94-01-01465.
Глава 1 ПОСТАНОВКА И МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА
В данной главе проведен краткий анализ работ по многокритериальной оптимизации, основное внимание уделено методам решения многокритериальных задач в условиях определенности с учетом качественной информации об относительной важности частных критериев. Рассмотрены методы свертывания векторного критерия оптимальности, способы назначения весовых коэффициентов относительной важности частных критериев, виды дополнительной качественной информации ЛПР о важности частных критериев и решается задача определения оптимальных значений весовых коэффициентов по принципу гарантированного результата с учетом отношений предпочтения на множестве критериев.
Задачи многокритериального выбора и подходы к их решению
В связи с развитием автоматизированных систем проектирования (САПР) и управления (АСУ) все больше внимание ученых и специалистов привлекают новые информационные технологии, основанные на использовании ЭВМ и математического моделирования, включающего в себя методы построения и анализа математических моделей. Особое место в новых информационных технологиях занимает проблема принятия решений при наличии нескольких критериев оптимальности, которые обычно являются противоречивыми в том смысле, что не существует решения наилучшего одновременно по каждому из них.
Для построения математической модели принятия решений в условиях многокритериального выбора введем ряд вспомогательных определений.
Под сложной системой будем понимать материальный или абстрактный объект, относительно которого может приниматься одно решение из множества возможных на основе анализа описывающей данный объект информации.
Данное весьма абстрактное определение охватывает широкий круг конкретных задач (оптимизацию режимов функционирования конкретной технической или технологической системы; выбор конкретного типа приобретаемого оборудования; определение параметров проектируемого устройства и т. д.). Однако, несмотря на различие описывающих эти сложные системы математических моделей, характерной общей чертой в них является наличие качественной информации о предпочтениях между вариантами сложной системы и формирование на ее основе критериев оптимальности, позволяющих сравнивать варианты решения.
Под лицом, принимающим решения (ЛПР), будем понимать исследователя (разработчика, проектировщика, инженера и т. д.), который стремится поставить и решить задачу (принять решение) в конкретной предметной области на основе своих представлений относительно важности параметров х = {х?..., хп) и характеристик у = (у?
.... ут) описываемой сложной системы.
ЛПР определяет наилучшее, с его точки зрения, рациональное решение, под которым понимается наличие рациональных, понятных другим людям причин, приведших к выбору данного решения из множества альтернативных.
Под математической моделью сложной системы будем понимать зависимость характеристик у = {у{.....ут) системы от ее параметров х - (х?...,хп):
Уі= Уу(х .....хп),
(1.1)
Зависимости у{ = у( (лс), і = 1, т, могут быть описаны различными способами (с помощью аналитических выражений, совокупности таблиц, алгоритмов или программных систем). В дальнейшем будем считать, что математическая модель сложной системы представляет собой черный ящик (рис.
1).
Под математической моделью принятия решения будем понимать следующий набор элементов:
список варьируемых параметров,
область допустимых решений задачи,
список критериев оптимальности,
метод выбора рационального решения из множества допустимых.
В процессе принятия решений (выбора конкретных числовых
значений вектора варьируемых параметров х) необходимо учитывать только допустимые значения, соответствующие характеристикам предметной области. Эти ограничения могут быть сформулированы как система линейных и нелинейных выражений:
У,
Математическая модель объекта
Параметры управления х Характеристики У
Рис. I. Схема математической модели объекта
aj Xj Ь., / = Т7л,
у~ Уі(х) у*, і = TTm, (1.2)
где dj, bj фиксированные значения /-го параметра, характеризующие область его допустимых значений и зависящие от эксплуатационных, технологических, физических требований и других условий;
у~, у. ограничения на значения требований, налагаемых на і-ю характеристику в соответствии с техническим заданием.
В общем случае область D допустимых решений, удовлетворяющих системе (1.2), может быть представлена в виде следующего множества:
D = {* I gk (х) 0, k = ТГК}.
В дальнейшем будем считать, что область D непуста. Тогда для оценки относительной важности одного допустимого решения
хк е D по сравнению с другим допустимым решением х1 е D введем частный критерий оптимальности Q{ (х), і = 1, N, который
k
позволяет считать, что решение х не менее предпочтительно, чем
і
решение х, если выполняется соотношение
хк }¦ х1 Q, (Л (1.3)
где Q{ (х) численная оценка решения х в соответствии с частным критерием оптимальности Q{, измеренным в некоторой шкале А (Qt) множестве числовых значений.
В таком случае математическая модель принятия решений
представляет собой задачу нелинейного программирования:
Q\= Qt{x)= mina (де). (1.4)
же D
Если в задаче принятия решений существует несколько частных критериев оптимальности Q. (ж), і = N, то ЛПР должно выбрать
допустимое решение ж е Д обеспечивающее наименьшее значение N частным критериям оптимальности одновременно. Тогда математическая модель принятия решений представляет собой задачу многокритериальной (векторной) оптимизации:
min Q. (ж), min Д(ж), .... min Q„(x). (1.5)
же D же/) ж е?
В частном случае задача принятия решений может представлять собой выбор рационального проекта, характеризуемого набором параметров ж из множества нескольких технических проектов с
параметрами ж , k = 1, М, определенными в табл. 1 альтернативы критерии, где Qt (ж*) значение і-го частного критерия оптимальности для ?-го вект^оа варьируемых параметров.
| Таблица 1 | |||||||||||||||||||||||||
|
(1.6)
min Д(ж), Ж 6 { ж1, ....Ж*}
/т/п mxQn(x)-же{ ж1.....ж}
Далее будем считать, что шкалы измерений частных критериев оптимальности (^(ж), і = 1, N определены и численное значение
вектора Q (ж) = (?L (ж),..., QN (ж)) может быть получено для любого
допустимого решения же D. Допустим также, что частные критерии оптимальности имеют одинаковую шкалу измерения [а, Р], О а р, и приведены к безразмерному типу при помощи, например, положительного линейного преобразования, сохраняющего отношения предпочтения на множестве численных оценок А (QJ):
(1.7)
_ Q, (.х) - QJ
V, (Q, (*)) = $,(*)= ;1 (Р - а)+ а,
Qt - Q{
Q+i = max Qt (де); QJ = min (де); Qj * QJ, i = TJJ. xeD xeD
В данной модели коэффициент af = (Р - ol)/(QJ - QJ) характеризует шкалу, коэффициент b{ = (aQj - р(?7)/(?; - QJ) позволяет привести частные критерии оптимальности к общему началу отсчета и к одинаковому интервалу измерения.
Областью критериев DQ назовем отображение области допустимых решений D cz Rn в пространстве RN:
Dq= {?!?,= ?,(*), i=T7N; хе D}. (1.8)
k k k k
Любые два векторных критерия Q = (Ql.....Q^= (@i (* )
Qn (**)) и Ql = (Qp ..., QlN) = (Q{ (x‘),.... Qn (x')) являются противоречивыми, если Q!, i e Iv Q* Q*, / e /2, IXU12 = {1 N} и
по крайней мере одно из этих соотношений является строгим. В случае доминирования Qk над Ql: Qk Qlf, i = 1, N, и хотя бы для
одного из і это неравенство строгое, альтернатива х может быть
и
исключена из рассмотрения, так как альтернатива Q лучше альтернативы Q1 по всем частным критериям.
Совокупность векторов Q е Dq, для которых нет ни одного доминирующего их вектора из области критериев DQ, образует область компромиссов Dk с DQ, а соответствующие им значения параметров х образуют область решений, оптимальных по Парето Dpcz D :
Dk= {Q е DjnBQ'tQ'e Dq,Q* * Q): Q. Q., i= TJJ),
Dp = {xe D\Q(x)e Dk}. (1.9)
Решение задач многокритериальной оптимизации привлекает большое внимание как ученых, так и практиков. Основные результаты в этом направлении связаны с работами Гермеера Ю. Б. [20], Моисеева Н. Н. [30], Емельянова С. В. [23], Михалевича В. С. [29], Краснощекова П. С. [26], Ларичева О. И. [27] и их многочисленных учеников.
Известно несколько подходов к решению многокритериальных задач оптимизации. Отметим некоторые их них.
1. Развитие в рамках абстрактной модели выбора многошкальных экстремальных механизмов, позволяющих осуществлять рациональный выбор по векторному критерию (Айзерман М. А. [1], Емельянов С. В. [23], Макаров И. М. [37], Березовский Б. А. [15] и др.).
2. Применение теории полезности для многокритериального выбора альтернатив из дискретного множества в условиях риска и неопределенности (Кини Р. Л. [25], Райфа X. [25], Фишберн Р. С. [39], Борисов А. Н. [16, 17], Жуковин В. Е. [24]).
3. На основе некоторой системы требований, предъявляемой к оптимальному решению, формализованной в виде совокупности аксиом, выводится схема многокритериального выбора как следствие этой системы аксиом (Подиновский В. В. [35], Вилкас Э. И. [18] и др.).
4. Сведение многокритериальной задачи выбора к скалярной оптимизации с помощью некоторой свертки векторного критерия (Гермейер Ю. Б. [20], Краснощеков П. С. [26], Евтушенко Ю. Г. [22], Штойер Р. [41], Cohon J. L. [46]).
5. Разработка человеко-машинных процедур решения многокритериальных задач оптимизации в интерактивном режиме (Емельянов В. Л. [23], Джоффрион А. М. [21], Штойер Р. [41]).
6. Построение области компромиссов и соответствующего ей множества Парето-оптимальных решений для некоторых классов многокритериальных задач оптимизации (Cohon J. L. [46], Villareal В. [48], Karwan М. Н. [47], Zionts S. [49]).
В связи с развитием вычислительной техники, в частности ПЭВМ, большое распространение получили человеко-машинные методы решения многокритериальных задач.
Человеко-машинная процедура представляет собой циклический процесс взаимодействия ЛПР и ЭВМ. Цикл состоит из фазы анализа и принятия решений, выполняемой ЛПР (фаза постановки задачи для ЭВМ), и фазы оптимизации, выполняемой ЭВМ (фаза поиска решения и вычисления его характеристик). В процессе взаимодействия ЛПР уточняет свои предпочтения и параметры задачи. Процесс заканчивается, когда получено приемлемое для ЛПР решение и при этом ЛПР убеждается в нецелесообразности дальнейших попыток улучшить его.
Существующие человеко-машинные процедуры принятия решений в условиях многокритериального выбора обладают в болыпин-стве случаев серьезным недостатком: в качестве ЛПР должен выступать человек, компетентный в заложенных в процедуру моделях и методах, поскольку для получения более совершенного решения от ЛПР требуется детальное знание алгоритмов и детальная формулировка своих предпочтений.
Описываемая в дальнейшем интерактивная система мнбгокри-териального выбора в значительной степени лишена этих недостатков. От ЛПР не требуется детального знания математических и алгоритмических вопросов принятия решений. Информация, необходимая системе, вводится в доступной форме парных сравнений по важности частных критериев. При работе с системой ЛПР имеет возможность детального и всестороннего анализа задачи с целью выбора метода и принятия наилучшего решения.
Система, в частности, предоставляет пользователю ряд графических возможностей: отображение численных значений векторных оценок альтернатив в виде диаграмм Кивиата, графическое изображение области компромиссов и т. д. Подробнее визуализация исходных и результатных данных рассматривается в гл. 3.
Общая схема сведения многокритериальных задач к задаче нелинейного программирования
Рассмотрим решение задачи многокритериальной оптимизаций:
min ?. (ж),.... min QN (ж), (1.10)
х s О xgD
где
D = {x\gt(x)0, і = Т77С}. (1.11)
В частном случае область D может быть дискретным множеством решений ж:
D = {xl.....ж*}. (1.12)
Методы поиска рационального решения ж0 задачи (1.10)(1.11) получили широкое развитие и отражение в литературе. Важное значение имеют методы, использующие качественную информацию о множестве частных критериев.
Среди них можно отметить следующие.
1. Метод выделения главного критерия. Основная идея этого метода минимизация наиболее важного (главного) критерия (ж), при условии, что значения других критериев Q. (ж), і = 2, N,
не превышают пороговых значений
(1.13)
D' = Dn{x\Ql(x)ZQi,i = ZJI}. (1.14)
Основная трудность этого метода состоит в определении пороговых значений Qr для вычисления которых, в свою очередь, применяются специальные методы.
2. Метод лексикографического упорядочения критериев. В данном методе оптимизация А-го частного критерия начинается только тогда, когда получены минимальные значения всех предыдущих (?-1) частных критериев. Метод позволяет получить сколь угодно малое приращение более важного критерия за счет сколь угодно больших потерь по остальным, менее важным критериям.
Однако на практике очень часто уже после первого шага оптимизации (решения задачи оптимизации по первому критерию) решение вырождается в точку и остальные критерии не учитываются.
3. Метод последовательных уступок представляет собой мо
дификацию метода лексикографического упорядочения, заключающуюся в том, что на каждом А-м шаге последовательной оптимизации вводится уступка характеризующая допустимое откло
нение (А-І)-го частного критерия от его минимального значения.
Все перечисленные выше методы предполагают наличие подавляющего превосходства одного критерия над другим.
4. Метод свертывания векторного критерия [6, 20, 26, 27, 36 и др.]. Этот метод является наиболее распространенным методом, учитывающим относительную важность частных критериев оптимальности с помощью построения скалярной функции F, являющейся обобщенным критерием относительно векторного критерия Q (х), и решения однокритериальной задачи оптимизации:
min\F(w,Q(x)), (1.15)
хе ГУ
где w = { wy ш^} весовые коэффициенты относительной важности
частных критериев [6, 27, 33 и др.]. В качестве обобщенных критериев могут быть использованы функции F следующего вида:
а) аддитивный критерий оптимальности:
N
(1.16)
Fz (да, Q (*)) = X wi Qi (*);
=1
б) мультипликативный критерий оптимальности:
N
Fz(w, Q (x)) = [[,?,(*); (1.17)
i= 1
в) обобщенные логические критерии оптимальности:
^max (®* Q (*)) = ПІЯХ { ОУ,- ?/ (*) }; (1-18)
1 1 Л
^min (w'?(*)) = , тіп ( w. Qi (х)}; (1.19)
mto 1iN
г) среднестепенной обобщенный критерий оптимальности:
N
Fp (, Q (*)) = (jj X ш, Q? {x))i/p, p 0. (1.20)
і= l
5. Метод идеальной точки" [10, 11, 43]. При использовании этого метода ЛПР должно задать дополнительную информацию в
виде идеального решения Q* = (QJ,..., Q*N), учитывая следующее соотношение:
- о Q* min Q, (х), і = 1, N. (1.21)
xeD
Тогда исходная задача может быть решена путем построения обобщенного критерия в виде
F* (w. Q (х), ?*) = F (да, (Q (х) - (?*)), (1.22)
и решения однокритериальной задачи оптимизации в виде
min F* (да, Q (ж), (?*), (1.23)
хе D
обеспечивающей наилучшее приближение к идеальному решению. Здесь в качестве обобщенного критерия оптимальности F может использоваться одно из выражений (1.16)(1.20), например:
N
F = 'Lwi (Qi (*) - ?,-) или /=1
F = max {w{ (Q( (x) - Q't)}.
1 ійп
В обобщенный критерий F (w, Q (x)) входят неотрицательные
N
весовые коэффициенты tt( ? 0, i = 1, N\ ^ ш/ = 1 отражающие отно-
/=і
сительную важность частных критериев. Здесь важность критериев понимается в смысле аксиоматической теории важности [35], что позволяет считать: если известна дополнительная информация вида і-й критерий не менее важен, чем j-й критерий (?, Qj), то для весовых коэффициентов и{ и Wj справедливо соотношение:
Qf Qj =w( Wj. (1-24)
Способы назначения весовых коэффициентов широко описаны в литературе. Среди них можно отметить следующие:
упорядочение критериев по важности;
определение отношений весовых коэффициентов, при этом ЛПР задает отношение w./Wj в числовом виде;
построение таблиц на основе попарного сравнения критериев по важности;
метод определения весов при помощи совокупности последовательных сравнений (метод Черчмена-Акоффа);
методы, использующие информацию о качестве оптимальных значений частных критериев;
теоретико-игровые методы назначения весовых коэффициентов и другие.
Кроме перечисленных методов назначения весовых коэффициентов существуют способы указания области допустимых значений весовых коэффициентов: оценки предпочтительности вариантов; применение принципа гарантированного результата; существуют методы, при которых значения коэффициентов важности оцениваются на основе информации о сравнении контрольных векторных оценок, затем составляется система неравенств и выбираются коэффициенты по принципу гарантированного результата и т. д.
Во всех вышеперечисленных методах определения численных значений весовых коэффициентов от ЛПР требуется либо дать точные численные оценки, либо сравнить по важности все частные критерии между собой, причем в последнем случае различные методы дадут различные значения коэффициентов при одних и тех же предпочтениях на множестве критериев.
Кроме этого, в указанных методах предполагается, что назначенные значения весовых коэффициентов важности да остаются неизменными для всей области допустимых решений D.
Однако в ряде случаев [6, 44] в процессе принятия решения приходится учитывать зависимость весовых коэффициентов от значения частных критериев в каждой точке области допустимых решений D. Допуская, что ЛПР не может точно определить численные значения весовых коэффициентов да, их можно рассматривать как неконтролируемые факторы и, применяя принцип гарантированного результата [20], перейти к следующей модели принятия решения:
min {max F (да, Q (ж))}, (1.25)
xeD wbDw
где D = {x I g{ (ж) 0, t - T7K},
N
Dw = {ю I да, 0, i = T7N-, ? да, = 1}.
i = 1
В частности, при использовании обобщенного критерия оптимальности аддитивного типа приходим к следующей экстремальной задаче:
N
min {max ?да,0,(ж)}. (1.26)
xeD toe DWi_t
Если предположить, что структура области допустимых значений весовых коэффициентов Dw остается неизменной в процессе
поиска оптимального решения задачи (1.25), то весовые коэффициенты да являются функциями от параметров х:
да, = да, (ж), і = 1, N, (1.27)
численные значения которых при постоянных значениях ж можно определить из решения экстремальной задачи относительно вектора да
да (ж) = arg max {F (да, Q (ж))} (1.28).
xeDw
Таким образом, исходная многокритериальная задача оптимизации (1.10)(1.11) сводится к задаче нелинейного программирования:
min {F (да (ж), Q (ж))}. (1.29)
xeD
В дальнейшем будем считать, что в общем случае (при отсутствии качественной информации о предпочтениях частных критериев) весовые коэффициенты wp і = 1, N, отнормированы относительно положительного параметра R о и могут принимать численные значения не меньше некоторой неотрицательной величины wQ:
