Материал: Информационная система поддержки принятия решений в условиях многокритериальной оптимизации

Множество P (F) = F (P (X)) будем называть множеством эффективных оценок.

Согласно принципу Парето оптимальное решение необходимо искать среди элементов множества P (X). В противном случае всегда найдется точка x Î X, оказывающаяся более предпочтительной с учетом всех частных целевых функций f_i (x).

Точку x₁ Î X будем называть слабо эффективным решением задачи (3), если не существует x₂ Î X, для которой выполняются строгие неравенства f_i (x₂) > f_i (x₁), i = 1,., m. Т.е. решение называется слабо эффективным, если оно не может быть сразу по всем критериям “полезности”, задаваемых с помощью f_i (x), i = 1,., m.

Множество слабо эффективных решений обозначим S_F (X) или S (X), P (X) Í S (X) (S (F) = F (S (X)).

Такая система предпочтений на множестве альтернатив X, заданная с помощью векторного отображения F может быть представлена на языке бинарных отношений: "x₁, x₂ Î X

₁ R₁ x₂ Û f_i (x₁) > f_i (x₂), i = 1,., m. (4)₁ R₂ x₂ Û f_i (x₁) ³ f_i (x₂), i = 1,., m, f_i (x₁) ¹ f_i (x₂).

Бинарное отношение R_{1 -} называют отношением строгого доминирования или Слейтера, а R₂ - отношением Парето. Ядра этих отношений совпадают с множествами S_F (X), P_F (X).

1.Методы оценки многокритериальных альтернатив

Ценность или полезность альтернатив для лиц, принимающих решения, различна. При таком предположении имеет смысл задача выбора наиболее ценной или группы наиболее ценных альтернатив, либо упорядочении альтернатив по полезности.

Разные методы принятия решений при многих критериях отличаются способом перехода к единой оценке полезности альтернатив. Можно выделить ряд групп таких методов.

Прямые методы

Здесь зависимость общей полезности альтернативы от оценок по отдельным критериям известна заранее. Чаще всего используется вид зависимости, при котором определяются численные показатели важности критериев (веса), умножаемые на оценки по критериям (метод взвешенной суммы критериев). Другой метод - это дерево решений. Путем последовательного просмотра всех вариантов выбора определяются альтернативные варианты решений. Для каждого альтернативного варианта подсчитываются вероятности осуществления, которые умножаются на его ценность.

Прямые методы можно разделить на пять групп:

Постулируется сама формула зависимости полезности для многокритериальной альтернативы и все ее параметры.

ЛПР выбирает один из способов определения полезности альтернатив при неизвестной информации о вероятности различных внешних условий.

Обоснованием выбора считается привлекательность того или иного способа для ЛПР.

Постулируется основная формула зависимости, но ее параметры непосредственно назначаются ЛПР. Например, метод взвешенных сумм оценок критериев.

Основная форма зависимости задается, а ее параметры определяются путем вычислений, проводимых на основе прямой оценки ЛПР полезностей многокритериальных альтернатив.

За основу берется формула максимизации ожидаемой полезности (которая постулируется), а ЛПР определяет вероятностные оценки различных исходов на деревьях решений.

Обоснованием является представление о принципе максимизации ожидаемой полезности как о “единственном рациональном” принципе в принятии решений.

Аксиоматические методы

В литературе эта группа методов рассматривается как единственный “научно обоснованный” подход к анализу многокритериальных альтернатив, известный под названием MAUT (многокритериальная теория полезности). Аксиоматические методы разделяют на две подгруппы:

1. Оценки альтернатив по многим критериям считаются известными (принятие решений при определенности).

2. Заданы функции распределения вероятностей оценок альтернатив (принятие решений при риске).

Система аксиом:

1. Аксиомы “слабого порядка" и транзитивности. Эти аксиомы определяют отношение превосходства одной альтернативы над другой при наличии таких свойств, как связность и транзитивность.

Пусть u, v, w Î U - полезности альтернатив, тогда для любых u и v имеет место одно из следующих отношений:

=v, u>v, u<v; из u>v, v>w следует u>w.

Аксиомы, исключающие ненормальности в предпочтениях. Т.е. можно использовать любые части полезности двух альтернатив (объектов) для выражения эквивалентной полезности третьей:

Рис. 1. Схема основных этапов простого метода многокритериальной оценки (SMART).

Из u>v>w следует существование такой a, что au+ (1+a) v=w. Обычно эту аксиому называют аксиомой растворимости.

2. Аксиомы независимости. Эти аксиомы требуют, чтобы предпочтения между альтернативами не зависели от некоторых преобразований этих альтернатив.

А) Слабая условная независимость по полезности: предпочтения для двух альтернатив, отличающихся лишь оценками по шкале одного критерия, не зависят от оценок этих альтернатив по шкалам других критериев.

Б) Совместная независимость: предпочтения между альтернативами, отличающимися оценками по определенному подмножеству критериев, не зависят от одинаковых оценок по критериям оставшегося подмножества.

При справедливости этих аксиом функция полезности многокритериальной альтернативы может быть выражена в виде:

,

где xi - оценка по i - му критерию, fi - функция полезности по i - му критерию.

Методы компенсации

В этих методах делается попытка уравновесить (или скомпенсировать) оценки одной альтернативы, оценками другой, чтобы найти, какие оценки лучше.

Точки и кривые безразличия

Если в многокритериальном пространстве построены поверхности безразличия, то сравнение многокритериальных альтернатив крайне просто, поскольку эти поверхности (или исходные точки) можно упорядочить по полезности.

Построение кривой k_i:

1. Выбирается исходная точка P1 (x1, y1), где x1, y1 - значение критериев X, Y в данной точке;

2. Выбирается приращение D по критерию X (положительное или отрицательное) и определяется x2 = x1 + D;

3. Определяется значение y2 по критерию Y такое, что точка P₁¹ (x2, y2) эквивалентна по полезности точке P1 (x1, y1);

4. По найденным точкам проводится кривая безразличия.

Например, кривые безразличия для двух критериев оценки альтернатив (Рис.2).

Рис. 2. Кривые безразличия для двух критериев оценки альтернатив

Методы сравнения разностей оценок альтернатив

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

Пусть (x1, x2, …, xN), (y1, y2, …, yN) - оценки альтернатив  и  по N критериям. Тогда альтернатива  предпочтительней, чем альтернатива , если

,

где Ui - функция полезности для i - го критерия, ji - функция, определяющая влияние разностей оценок по i - му критерию на результат сравнения двух альтернатив.

Методы порогов несравнимости

Связь между любой парой альтернатив определяется последовательностью бинарных отношений. “Сильным” бинарным отношениям соответствуют большие требования к превосходству одной альтернативы над другой и, следовательно, большее число несравнимых альтернатив. Самым сильным является полное доминирование одной альтернативы над другой. Более “слабые" бинарные отношения определяют условия, при которых, несмотря на противоречивые оценки, одна альтернатива объявляется лучшей, чем другая.

На основе выбранного бинарного отношения осуществляется попарное сравнение всех альтернатив, причем альтернативы, оказавшиеся лучшими при всех сравнениях выделяются в новое множество, называемое ядром. Размер ядра характеризуется количеством альтернатив. Если бинарное отношение является отношением доминирования одной альтернативы над другой, при котором одна альтернатива имеет по всем критериям не худшие, а хотя бы по одному из критериев лучшие оценки, то появившееся при этом ядро называется множеством Парето.

После выделения ядра - множества Парето элементы этого ядра объявляются несравнимыми. После первого бинарного отношения задается второе, более слабое. Ядро, соответствующее второму бинарному отношению, содержит в общем случае меньшее число несравнимых элементов. Потом задается третье бинарное отношение и т.д. Процесс получения ядер с уменьшающимся количеством элементов продолжается до тех пор, пока количество элементов в ядре не достигнет требуемого значения.

Бинарные отношения. Каждому из N критериев, имеющих числовые шкалы, ставится в соответствие целое число p, характеризующее важность критерия. Выдвигается гипотеза о превосходстве альтернативы a над альтернативой b. Множество I, состоящее из N критериев, разбивается на три подмножества:⁺ (a, b) - подмножество критериев, по которым a предпочтительнее b;⁼ (a, b) - подмножество критериев, по которым a равноценно b;^- (a, b) - подмножество критериев, по которым b предпочтительнее a.

Далее формируется индекс согласия с гипотезой о превосходстве a над b:

 (11)

Также формируется индекс несогласия: для критериев подмножества I- (a, b) определяются d_ab - разности оценок альтернатив b и a.

Альтернатива a объявляется превосходящей альтернативу b, если c_ab³c1 и d_ab£d1 (где c1, d1 - заданные уровни).

Бинарное отношение между альтернативами в общем случае может определяться одним или несколькими индексами. При формировании этих отношений не обязательно использовать веса критериев.

Рекомендуется использовать вложенные бинарные отношения S1ÌS2ÌS3.

Методы данной группы дают возможность ЛПР вмешиваться в процесс выбора, однако обилие параметров, которыми он располагает, ставит под сомнение их эффективное использование. При использовании этих методов следует учитывать, что вид бинарного отношения, а также их последовательность существенно определяют результат выбора (Рис.3).

Человеко-машинные процедуры принятия решений

Эти процедуры применимы, когда модель проблемы известна частично. Человек взаимодействует с ЭВМ, определяя желаемое соотношение между критериями.

Существующие человеко-машинные методы принятия решений отличаются следующими чертами.

В большинстве случаев рассматривается обычная линейная модель задачи многокритериального математического программирования. Дана область допустимых решений DÎRn, определяемая линейной системой:

  xi³0, 1£i£n

Задано N критериев качества C1, C2, …, CN, где

Рис. 3. Схема основных этапов метода порогов несравнимости.

Требуется определить в области D вектор x*, обеспечивающий удовлетворительные значения по всем N критериям и наилучший компромисс между ними с точки зрения ЛПР. Иногда область допустимых решений определяется системой нелинейных уравнений.

Большинство процедур начинается с выходом на множество Парето в пространстве критериев, после чего на этом множестве осуществляется поиск компромисса. В большинстве случаев строятся структурированные методы решения, в большинстве случаев по аналогии с известными поисковыми методами решения задач оптимизации.

2. Постановка задачи об упаковке

Рассмотрим следующую задачу: имеется множество из М объектов, которое желательно упаковать в К емкостей для последующей перевозки, причем М существенно больше К. Каждый объект характеризуется количественными физическими параметрами (например весом и объемом); каждая емкость характеризуется этими же предельными физическими параметрами (например, общим объемом и грузоподъемностью. Кроме того, каждый из упаковываемых объектов имеет оценки по нескольким критериям (с порядковыми шкалами), которые характеризуют его качество, его привлекательность для лица, ответственного за перевозку. Емкость контейнеров недостаточна для упаковки всех имеющихся объектов. Желательно осуществить упаковку наилучшим образом, т.е. так чтобы:

1. Среди упакованных объектов было бы наибольшее количество таких, качество которых превосходило бы качество неупакованных - критерий О₂.

2. Число упакованных объектов было бы максимально возможным, так как все они в той или иной степени заслуживают упаковки в емкости (т.е. предварительный отбор, исключающий абсолютно плохие объекты, уже сделан) - критерий О₁.

При К = 1 и многих критериях оценки качества упаковываемых предметов мы придем к многокритериальной задаче о многомерном рюкзаке. Задача об упаковке в контейнеры менее известна. Эта задача ставится следующим образом: Имеется конечное множество объектов, причем размер каждого из них задан рациональным числом. Требуется упаковать предметы в минимально возможное количество контейнеров так, чтобы суммарный размер объектов в каждом контейнере не превышал его размер (также рациональное число).

Упаковываемые объекты имеют оценки качества по многим критериям. Требуется упаковать максимальное число объектов, а не получить минимальное число контейнеров. Введем следующие обозначения:

_ij - j-й физический параметр i-го объекта;_ij - j-й физический параметр l-го контейнера;_i - общая ценность i-го объекта.

Обозначим через I=1, 2, …, М множество номеров объектов, а через

множество тех упакованных объектов, для которых не найдется более ценных среди не упакованных.

Формальная постановка задачи имеет следующий вид:

, ,

, j = 1, …, P, l = 1, …, K,

3. Функция полезности

Пусть заданы критерии K₁,…,K_n; X = { x | x = (x₁,…,x_n) } - множество векторых оценок вариантов по этим критериям. Пусть на X задано R - отношение предпочтения. Числовая функция f: X → R, называется функцией полезности (ценности, предпочтительности), если она обладает следующим свойством: f (x) ≥ f (y) ⇔ x R y.

Если известна функция полезности, то поиск оптимального варианта сводится к задаче нахождения x* = arg max f (x), x∈X - аргумента максимума функции полезности на множестве X.

Как найти функцию полезности? Методы построения функции полезности делятся на эвристические и аксиоматические.

К эвристическим методам можно отнести метод главного критерия и метод обобщенного критерия.

Метод главного критерия сводится к оптимизации по одному выбранному критерию, при условии, что остальные критерии не больше (или не меньше) приемлемых значений.

Метод обобщенного критерия заключается в свёртке набора критериев в числовую функцию, которая и будет являться функцией полезности.

Виды свёрток:

) аддитивная свёртка: f = α₁K₁+…+α_nK_n;