Многокритериальные задачи: функция полезности, лексикографический анализ

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

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

1) основаны на том, что ЛПР может выразить свои предпочтения до начала процесса многокритериальной оптимизации;

2) интерактивные (диалоговые) методы;

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

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

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

Методы первой группы

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

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

В XIX веке экономисты высказали предположение о существовании у каждого индивидуума определённого количественного измерителя счастья или полезности – “пользометра”. Единицы измерения этого прибора назвали “утилями” (от английского utility – полезность). Согласно этой модели потребительского поведения каждый потребитель выбирает так товары и услуги, чтобы максимизировать свою полезность в пределах средств, которыми он располагает. Эта идея перенесена на многокритериальные задачи и интенсивно разрабатывается в теории полезности, ставшей самостоятельным направлением прикладной математики.

Применительно к многокритериальной задаче в качестве товаров и услуг выступают критерии, а в качестве потребителя – ЛПР. При этом предполагается существование на множестве значений критериев y ₁ ,y ₂ ,….,y_m скалярной оценки предпочтений ЛПР, называемой полезностью.

Приведём строгое определение этого понятия. Функция U, которая каждой точке Y критериального пространства ставит в соответствие действительное число U (Y),называется функцией полезности (ценности) ЛПР, если

 

Y¢ ~ Y^"Û U (Y')= U (Y"),

Y'ýY"Û U (Y')> U (Y").

 

Таким образом, функция полезности представляет собой математическую модель предпочтений ЛПР. Если функция полезности известна, то многокритериальная задача сводится к стандартной задаче оптимизации: найти вектор X ÎD, максимизирующий U [Y(X)]. Множество точек критериального пространства, одинаковых по предпочтительности (для которых U (Y )= Const), образует гиперповерхность равного уровня функции полезности. Гиперповерхности равного уровня U (Y) называются кривыми безразличия, а семейство всех кривых безразличия – картой безразличия. Такая терминология связана с тем, что для любых двух альтернатив Y' и Y", лежащих на одной кривой безразличия, U (Y')= U (Y"), т.е. ЛПР всё равно, достигнет он Y ' или Y". Пример карты безразличия некоторой функции полезности и нахождение по ней оптимального решения показаны на рис. 10.4.

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

G

Чтобы построить U (Y), прежде всего необходимо установить её вид, который определяется структурой предпочтения ЛПР. Выявление структуры предпочтений – самый ответственный этап построения функции полезности. Следует однако заметить, что если функция U однозначно определяет всю структуру предпочтений, то обратное неверно. Это значит, что одна и та же структура может быть представлена разными функциями полезности, которые являются стратегически эквивалентными. Функции полезности U ₁(Y) и U ₂(Y) стратегически эквивалентны, если они приводят к одинаковому упорядочению по предпочтению. Так любые U ₁ и U ₂, связанные какой-либо монотонно возрастающей функцией Т(), являются эквивалентными. Действительно, максимизация U ₁(Y) и U ₂(Y)= T [ U ₁(Y)] приведет к одному результату, т.е. обе функции одинаково отражают структуру предпочтений ЛПР.

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

U(y ₁ ,y ₂ ,...,y_m)=F [ U ₁ (y ₁ ),U ₂ (y ₂ ),...,U_m(y_m) ], (10.7)

т.е. многомерная функция определяется через одномерные функции полезности значений одного отдельно взятого критерия. Типичные примеры таких функций для m =2:

U (Y)= C ₁ y ₁ + С ₂ у ₂, С ₁ >0, С ₂ >0,

, >0, >0.

Формализация структуры предпочтений основана на
исследовании возможности взаимной компенсации значений различных критериев. Это проблема замещения по полезности. Возможные замещения на наборе критериев может дать только ЛПР, а выявить их у ЛПР и формально описать - задача аналитика. Далее будем предполагать, что критерии независимы по предпочтению (см. раздел 10.1.3), и рассмотрим простейшие случаи построения U (Y) для m =2.

Предельный коэффициент замещения критерия y ₁ на критерий у ₂ в точке (, ) равен , если ЛПР согласен уступить единиц критерия y ₁ за единиц критерия у ₂, где - достаточно малая величина (строго говоря, при 0). В общем случае предельные коэффициенты замещения зависят от значений y ₁ и у ₂. Возвращаясь к рис.10.4 нетрудно понять, что предельный коэффициент есть тангенс угла наклона касательной к кривой безразличия в точке (, ), взятый с обратным знаком. Отсюда ясно, что определение коэффициентов замещения дает представление о карте безразличия, а следовательно, и о виде функции полезности.

Если коэффициент замещения не зависит от значений y ₁ и у ₂, то это означает, что кривые безразличия – прямые, имеющие вид

y ₁ + y ₂ =Const,

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

U (Y )=y ₁ + y ₂. (10.8)

Если предельный коэффициент замещения зависит от значения у ₂, но не зависит от y ₁, то подходящей составной функцией полезности может быть

U (Y )=y ₁ + U ₂ (y ₂ ). (10.9)

Возможный путь получения U ₂ (y ₂ ) состоит в следующем. Примем произвольно U ₂ ()=0, что дает точку отсчета значений U ₂. Тогда U ₂ () есть сумма в единицах y ₁, которую ЛПР согласен "заплатить" за переход от к . Выявив у ЛПР эти суммы для ряда значений у ₂, получим график функции U ₂ (y ₂ ) как, например, на рис.10.5.

Карта безразличия, соответствующая структуре предпочтений (10.9), имеет вид семейства кривых, которые получаются простым сдвигом по горизонтали (по оси у ₁) одной из них. Аналогичный подход применяется и в случае, когда зависит от y ₁, но не зависит от у ₂.

Из ситуаций, когда коэффициент замещения зависит от значений обоих критериев, рассмотрим самую простую: структура предпочтений ЛПР аддитивна. Обратимся к рис 10.6. Если вместо знака вопроса (?) ЛПР поставит d, т.е. он согласен заплатить d единиц у ₁ за увеличение у ₂ на с в точке D и это остается в силе при любых значениях а, b, с и d и в любых точках А, В, С и D, образующих прямоугольник, то имеет место условие соответственных замещений.

Доказано, что структура предпочтений аддитивна и, следовательно, описывается функцией полезности вида

U (Y )=U ₁ (y ₁ )+ U ₂ (y ₂ ) (10.10)

тогда и только тогда, когда выполняется условие соответственных замещений.

Одна из процедур построения функции (10.10), которую
рассмотрим ниже, использует эквивалентность замещений в разных
диапазонах одного из критериев. Приведем необходимые
определения. Пара () эквивалентна по разности полезности
паре (), где < и < , если для любого исходного
значения критерия у ₂ ЛПР согласен "заплатить" одно и то же
количество единиц у ₂ за увеличение y₁ как от до , так и от
до . Средней по полезности точкой интервала [ ] значений критерия y_i называется точка, которая образует
эквивалентные по разности полезности пары [ ] и [ ].
Заметим, что из условия соответственных замещений следует независимость значения средней точки для данного интервала y ₁от значений критерия у ₂, хотя "плата" за изменение у _i (в единицах у ₂) будет зависеть от уровня у ₂.

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

U(y ₁ ,y ₂ )= ₁ U ₁ (y ₁ )+ ₂ U ₂ (y ₂ ), (10.11)

где

U_i()=0, U_i()= 1, (10.12)

>0, ₂ >0 и ₁ + ₂ = 1. (10.13)

В процедуре отыскания U в виде (10.11), приводимой ниже, одинаковость пар и значения средних точек определяет ЛПР в диалоге с аналитиком.

I.Строим U ₁ в следующей последовательности:

-находим среднюю по полезности точку у интервала [ ] и полагаем U ₁ (y )=0,5;

-находим среднюю по полезности точку у интервала [у , ] и полагаем U ₁ (y )=0.75;

-находим среднюю по полезности точку у интервала [ ] и принимаем U ₁ (y )=0,25;

-проверяем согласованность результатов: является ли у средней по полезности точкой интервала [ у , у ]? Если нет, то придется корректировать эти точки до достижения согласованности.

-по пяти определенным точкам (или большему числу, если продолжить дробление интервалов) строится график функции U ₁ (y ₁ ).

2. Таким же образом находим U ₂ (у ₂ ).

3. Определяем коэффициенты шкалирования и ₂. Для этого выбираем любые две одинаковые по предпочтительности пары (y ₁ ,y ₂). Пусть, например, это пары () и (). Тогда

U ()= U ()

или

. (10.14)

Значения U ₁ и U ₂ в точках и определяются по построенным графикам. Добавив к (10.14) равенство (10.13), находим значения и .

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

С увеличением размерности критериального пространства трудоемкость построения функции полезности даже в аддитивном виде резко возрастает. А при более сложной структуре предпочтений ЛПР отыскание адекватной U (Y)становится весьма проблематичным.

Несмотря на то что имеется целый ряд хорошо разработанных процедур построения функции полезности (например, Р.Кини и Х.Райфа) рассмотренный подход к решению многокритериальных задач находит ограниченное применение. И прежде всего это связано с необходимостью длительной и напряженной работы с ЛПР. А как известно, руководители - народ занятой, да и далеко не все из них могут высказывать непротиворечивые суждения. Проблема многократно усложняется в ситуациях группового принятия решений. В то же время следует отметить главное достоинство метода: функция полезности наиболее полно и адекватно отражает систему ценностей ЛПР и позволяет относительно просто находить решение, наиболее предпочтительное (и в этом смысле оптимальное) для ЛПР с помощью одной стандартной задачи оптимизации.