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

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

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

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

Применительно к многокритериальной задаче в качестве товаров и услуг выступают критерии, а в качестве потребителя – ЛПР. При этом предполагается существование на множестве значений критериев y1,y2,….,ym скалярной оценки предпочтений ЛПР, называемой полезностью. Функция 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".

G

Чтобы построить U(Y), прежде всего необходимо установить её вид, который определяется структурой предпочтения ЛПР. Выявление структуры предпочтений – самый ответственный этап построения функции полезности. Следует однако заметить, что если функция U однозначно определяет всю структуру предпочтений, то обратное неверно. Это значит, что одна и та же структура может быть представлена разными функциями полезности, которые являются стратегически эквивалентными. Функции полезности U1(Y) и U2(Y) стратегически эквивалентны, если они приводят к одинаковому упорядочению по предпочтению. Так любые U1 и U2, связанные какой-либо монотонно возрастающей функцией Т(), являются эквивалентными. Действительно, максимизация U1(Y) и U2(Y)=T[U1(Y)] приведет к одному результату, т. е. обе функции одинаково отражают структуру предпочтений ЛПР. В благоприятных случаях удается описывать предпочтения ЛПР функцией полезности, имеющей сравнительно простой вид: U(y1,y2,...,ym)=F[U1(y1),U2(y2),...,Um(ym)], (10.7) т. е. многомерная функция определяется через одномерные функции полезности значений одного отдельно взятого критерия С увеличением размерности критериального пространства трудоемкость построения функции полезности даже в аддитивном виде резко возрастает. А при более сложной структуре предпочтений ЛПР отыскание адекватной U(Y) становится весьма проблематичным. Несмотря на то что имеется целый ряд хорошо разработанных процедур построения функции полезности (например, Р. Кини и Х. Райфа) рассмотренный подход к решению многокритериальных задач находит ограниченное применение. И прежде всего это связано с необходимостью длительной и напряженной работы с ЛПР. А как известно, руководители - народ занятой, да и далеко не все из них могут высказывать непротиворечивые суждения. Проблема многократно усложняется в ситуациях группового принятия решений. В то же время следует отметить главное достоинство метода: функция полезности наиболее полно и адекватно отражает систему ценностей ЛПР и позволяет относительно просто находить решение, наиболее предпочтительное (и в этом смысле оптимальное) для ЛПР с помощью одной стандартной задачи оптимизации.

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

Лексикографическое отношение определяется следующим образом. Для двух векторов и имеет место отношение тогда и только тогда, когда выполняется одно из условий:1. > 2.> (10.15)

………

m)>. В этом случае говорят, что вектор Y лексикографически больше вектора Множество векторов (решений), оптимальных по отношению на G (соответственно на D), называют множеством лексикографически оптимальных точек (OptlexY). Так как для любых двух векторов либо один лексикографически больше другого, либо они равны, то множество OptlexY, если оно не пустое, содержит только один элемент. Лексикографически-оптимальное решение достигается в процессе решения следующей последовательности задач:

1.находим при условии ;2.находим при условии ; m) находим при условии.

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

В этом методе каждому критерию соответствует своя строка относительных оценок (i-индекс критерия, j-индекс переменной). Строки располагаются в порядке убывания приоритетов критериев. Сначала симплекс-преобразования выполняются по. При достижении оптимального решения по 1-му критерию ( ) выявляют нулевые оценки небазисных переменных. Если таких нет, то решение единственное и лексикографическая оптимизация завершается. Если они есть, то в строке в столбцах с выделенными нулевыми ищут отрицательные оценки. Небазисная переменная xs, для которой а <0, вводится в базисное решение, улучшая значение 2-го критерия без ухудшения значения 1-го критерия. Этот процесс продолжается, пока будут выявляться такие перспективные переменные. Если они исчерпались или их не было, то переходят к решению по 3-му критерию, т. е. к выбору перспективных переменных по строке. Введение в решение небазисной переменной хр улучшит значение 3-го критерия без изменения первых двух, если а <0. Процесс решения многокритериальной задачи завершается, когда на последующих этапах не находятся перспективные переменные.

Метод главного критерия

Суть метода состоит в том, что ЛПР выделяет главный критерий (далее f1(X)), а на остальные критерии накладывает требования, что они были не меньше задаваемых им минимальных (пороговых) значений ti. Тогда многокритериальная задача сводится к однокритериальной задаче

(10.16)

Если эта задача разрешима, то ее решение всегда является слабо эффективным, а если оно единственно, то и эффективным. Заметим, что этот вывод не зависит от выбора главного критерия. Рис.10.7 иллюстрирует случай единственного решения задачи (10.16), а рис.10.8 – множества оптимальных решений, лежащего на границе ab, из которого только точка а является эффективной.

Линейная свертка

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

, (10.17) где Сi- положительные числа, отражающие веса критериев в структуре предпочтений ЛПР. При групповом ЛПР Ci находятся по индивидуальным весам одним из методов обработки экспертных оценок. Обычно значения Сi нормируются так, чтобы =1. Как следует из теоремы 5, точка максимума функции (10.17) при положительных Сi является эффективной.

имеет существенные недостатки. Во-первых, большие затруднения возникают при определении весов. Одно дело – расположить критерии по важности, и совсем другое - оценить на сколько или во сколько один критерий важнее другого. Во-вторых, неизвестна связь между значениями весов и значениями критериев в точке максимума F(Х). Очень часто эта зависимость оказывается существенно нелинейной (даже в линейных задачах), включая зоны нечувствительности значений fi к изменению Ci. Поэтому для получения решения, удовлетворяющего ЛПР, приходится максимизировать F(X) для нескольких наборов Сi. Наконец, заметим, что в свертке (10.17) целесообразно все критерии приводить к одним единицам измерения. С этой целью лучше представлять критерии в относительных единицах, беря за базовое максимальное или желаемое значение. Достоинство метода – в стандартности задачи, к которой сводится исходная многокритериальная проблема.

Максиминная свертка

Как и в предыдущем подходе, ЛПР должен задать веса Ci всем критериям, но обобщенный критерий записывается в виде

F(X)=. (10.I8) Тогда многокритериальная задача сводится к максимизации F(X) на Х D. Если ввести новую переменную хо, то эта задача преобразуется к виду F(Х)=хо max; хо, i= ; (10.19)

который более удобен для решения. В частности, если в исходной задаче все функции линейны, то и задача в виде (10.19) будет обычной задачей линейного программирования. Функция (10.18) подпадает под действие теоремы 5, что гарантирует получение, по крайней мере, слабо эффективного решения многокритериальной задачи. Максиминная свертка имеет те же недостатки, что и предыдущая, но отличается тем, что максимально увеличивает минимальное слагаемое в (10.17), способствуя относительному сближению значений критериев.

Метод идеальной точки

Идеальной или точкой абсолютного максимума называют точку в критериальном пространстве, в которой все критерии достигают своих максимальных значений: . Если эта точка принадлежит достижимому множеству G, то все эффективное (паретовское) множество состоит из этой единственной точки и проблемы как таковой в этом случае нет. Однако идеальная точка обычно лежит вне множества G и поэтому нереализуема. В связи с этим ее иногда называют также утопической. Идея метода состоит в том, чтобы на множестве G найти точку, наиболее близкую к идеальной. Мерой близости выступает некоторая функция расстояния , в качестве которой используют в общем случае взвешенные Lp-метрики

, где р может быть любым целым положительным числом и. Так как возведение в степень является монотонным преобразованием, то на положение экстремума оно не влияет. Таким образом, многокритериальная задача сводится к минимизации функции (10.20)

где - веса отклонений, задаваемые ЛПР ( =1, >0). На практике чаще используют значение р=2. В соответствии с теоремой 5 минимизация такой функции приводит к эффективному решению. Как и ранее, целесообразно использовать отклонения в относительных единицах, для чего выражение в квадратных скобках в (10.20) можно разделить на.

Целевое программирование (ЦП)

Целевое программирование применяется в основном для решения линейных многокритериальных задач, но может быть использовано и в нелинейных задачах. Принципиальное отличие ЦП от вышерассмотренных подходов – в изменении концепции цели. Вместо максимизации (минимизации) критериев ставится задача оптимального приближения к желаемым значениям критериев, которые называют также уровнями притязаний ЛПР. Таким образом, эти значения, обозначаемые далее как, и представляют собой цель, к которой следует стремиться. Если в методе главного критерия ограничения на критерии (10.16) могут приводить к неразрешимости задачи, то в ЦП, как будет показано дальше, желаемые значения, какими бы они ни были, не могут явиться причиной неразрешимости. Притязания ЛПР могут быть выражены по-разному в зависимости от смысла критерия:1) не меньше ; 2) не больше ;3) равно ;

4) принадлежать диапазону [ ] .

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

При целевом программировании изменяется модель задачи:

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

- с целевыми ограничениями в модель вводятся новые переменные, имеющие смысл отклонений от желаемых значений исходных критериев;

- критерий в модели ЦП строится как функция новых переменных.

Пусть, например, исходная задача содержит 4 критерия и ЛПР выдвигает по ним разные варианты притязаний:

,

.

Тогда целевые ограничения будут иметь вид:

, , ,

, , .

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

-  лексикографическое упорядочение ;

-  линейная свертка

-  минимаксная свертка

- квадратичная свертка (аналог (10.20))

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

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