Решающее правило метод свертки. Сравнение полученных результатов. Метод свёртывания критериев

11.08.2019 Пенсионный фонд РФ

Другая очень распространенная группа методов скаляризации векторной задачи математического программирования - свертка критериев.

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

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

A = {ak ,k = 1~K}. (64)

Весовые коэффициенты обычно используются в нормированном виде и удовлетворяют равенству:

X ak = 1, ak > 0, Vk е K , (65)

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

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

F0 = max X af (X). (66)

В результате решения данной задачи получается точка оптимума X0.

Основным достоинством данной свертки является то, что с ней связаны классические достаточные и необходимые условия оптимальности по Парето (теоремы Карлина).

Теорема Карлина 1.

В выпуклой задаче многокритериальной оптимизации точка X0 е S оптимальна по Парето, если существует вектор весовых коэффициентов A0 = {a° > 0, k = 1,K}, для которого выполняется соотношение:

X«Оf0(X0) = maxX«0h (X). (67)

Теорема Карлина 2.

Если в выпуклой задаче многокритериальной оптимизации точка X0 е S Парето-оптимальна, то существует вектор весовых коэффициентов A0 = {a° > 0, к = 1,К}, для которого выполняется соотношение:

X«0f^X°) = maxX«0fk (X). (68)

«h (X) =ma„xXakJkк=1 40eS к =1

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

Примером данной свертки может служить итоговый рейтинг надежности банка Кромонова, полученный как аддитивная свертка ряда коэффициентов.

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

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

Другим методом борьбы с данным недостатком - неприемлемо низкими значениями отдельных критериев при хорошем значении суммарного критерия - является применение сверток не аддитивного, а мультипликативного вида:

F0 = max П (af (X))Рк. (69)

Однако данная свертка не получила большого распространения ввиду того, что существуют аналогичные, но более перспективные виды сверток.

Так, существует свертка вида: (70)

minF0 =X| f (X)V

fк Наиболее широкое применение данная свертка получила при p = 2, которая трактуется как минимизация суммы квадратов относительных отклонений функционалов от своих достижимых оптимальных значений. Данная точка в случае равноценности критериев показывает решение, наиболее близкое к недостижимой «идеальной» точке (в которой все критерии принимают свое максимальное значение). Однако данной свертке также свойственен следующий распространенный недостаток: «хорошее» значение сводного критерия достигается ценой низких значений некоторых частных критериев.

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

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

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

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

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

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

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

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

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

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

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

Из презентаций

здесь x – альтернатива из множества Парето

fi (x ) – оценка альтернативы x по i -му критерию

Ci – коэффициенты относительной важности критериев

Использование линейной свертки

Это задачи, связанные с критериями

суммарного ущерба или прибыли ,

дохода ,

денежных или временных затрат

по годам планирования или по этапам

жизненного цикла экономических информационных систем и т. п.,

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

Квадратичная свертка

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

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

здесь x – альтернатива из множества W;

f i (x) – оценка альтернативы x по i-му критерию;

с i – весовые коэффициенты, с которыми оценки альтернатив входят в интегральный критерий. с i – коэффициенты значимости, или коэффициенты относительной важности критериев.

Коэффициенты с i можно найти, например, из специально организованной экспертизы: m экспертов должны расставить (ранжировать) критерии по важности:ранг 1 присвоить самому важному критерию и т.д. Пусть r ij – ранг, который присвоил j-ый экперт i-му критерию. Чтобы получить числовую оценку, введем новый коэффициент

Тогда коэффициент значимости i-го критерия с точки зрения j-го эксперта:

Обобщенные коэффициенты получим, усреднив оценки экспертов.

Пусть g j – компетентность j-го эксперта, тогда

Еще один метод назначения коэффициентов относительной важности основан на внесении предпочтений во множество критериев. Он состоит в следующем.

Пусть удается количественно выразить отношения предпочтения между критериями: критерий f i предпочтительнее критерия f j в h раз: . Тогда коэффициенты относительной важности этих критериев связаны между собой линейным уравнением C i =hC j . Это следует из теоремы:

Th. Если , то C i =hC j , C i >0, åC i =1.

Решая систему линейных уравнений, получим искомые коэффициенты.

Пример. Пусть варианты некоторой системы оцениваются по четырем критериям с пятибалльной шкалой. Значения критериевf i (х) даны в табл.13.

Пусть известно, что , f 2 ~ f 3 , .

Решение . Составим систему линейных уравнений для определения коэффициентов C i :

C 1 =1,5C 2 ; C 2 =C 3 ; C 3 =C 4 ; C 1 +C 2 +C 3 +C 4 =1;

Отсюда следует, что C 1 =3/8; C 2 =2/8; C 3 =2/8; C 4 =1/8.

В табл. 13 приведены значения интегрального критерия «Линейная свертка ».

Таблица 13

Оценки вариантов по критериям

	f 1 f 2 f 3 f 4
Х1 Х2 Х3 Х4 Х5 Х6	2 5 4 5 5 3 4 3 3 2 5 5 4 3 4 4 3 4 4 4 4 3 3 4	3/82+2/85+2/84+1/85=29/8 32/8 28/8 30/8 29/8 28/8

По этому критерию лучшая альтернатива – Х 2 .

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

Свертка может быть не только линейной , но и квадратичной :

сверткой порядка t :

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

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

Если t →0, т.е. требуется обеспечение примерно одинаковых уровней значений отдельных частных критериев, то интегральный критерий имеет вид

– мультипликативная функция.

При t=1 имеем линейную свертку, при t=2 – квадратичную.

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

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

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

где f i * (x) – оценка альтернативы x по i-му критерию в «родной» шкале, f i max и f i min – максимальное и минимальное значения альтернатив по i -му критерию. Полученные оценки принадлежат отрезку и являются дробными, что не всегда удобно для расчетов. Поэтому можно, умножив все оценки по соответствующим критериям на наименьшее общее кратное, перейти в целочисленную шкалу. Сдвиг по шкале на общую для каждого из критериев величину позволит избавиться от отрицательных оценок.

Вариант8,19 Методы решения МКЗ при равнозначных критериях

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

Назначение сервиса . Сервис предназначен для онлайн решения многокритериальных задач оптимизации методом последовательных уступок .

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel .

При этом ограничения типа x i ≥ 0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом .

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП

Решение транспортной задачи

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

Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
Объем товара Х (в партиях)	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Алгоритм метода последовательных уступок (компромиссов)

Вначале производится качественный анализ относительной важности критериев. На основании такого анализа критерии нумеруются в порядке убывания важности.
Ищем максимальное значение f 1 * первого критерия f=f 1 (x) на всем множестве допустимых решений. Затем назначаем величину «допустимого» снижения (уступки ) Δ 1 критерия f 1 (x) и определяем наибольшее значение f 2 * второго критерия f=f 2 (x) при условии, что значение первого критерия должно быть не меньше, чем f 1 (x)-Δ 1 . Затем назначаем величину «допустимого» снижения (уступки ) Δ 2 критерия f 2 (x) и определяем наибольшее значение f 3 * третьего критерия f=f 3 (x) при условии, что значение второго критерия должно быть не меньше, чем f 2 * - Δ 2 и т. д. Таким образом, оптимальным решением многокритериальной задачи считается всякое решение последней из задач последовательности:
1) найти max f 1 (x)=f 1 * в области x ∈ X;
2) найти max f 2 (x)=f 2 * в области, задаваемой условиями x ∈ X; f 1 (x) ≥ f 1 * -Δ 1 (6)
……………………………………………………………….
m) найти max f m (x)=f m * в области, задаваемой условиями
x ∈ X; f i (x) ≥ f i * -Δ i , i=1,...,m-1
Очевидно, что если все Δ i =0, то метод уступок находит только лексикографически оптимальные решения, которые доставляют первому по важности критерию наибольшее на Х значение. В другом крайнем случае, когда величины уступок очень велики, решения, получаемые по этому методу, доставляют последнему по важности критерию наибольшее на Х значение. Поэтому величины уступок можно рассматривать как своеобразную меру отклонения приоритета частных критериев от жесткого лексикографического.
Метод последовательных уступок не всегда приводит к получению только эффективных точек, но среди этих точек всегда существует хотя бы одна эффективная. Это следует из следующих утверждений.
Утверждение 3 . Если X ⊂ R n - множество замкнутое и ограниченное, а функции f i (x) непрерывны, то решением m-й задачи из (6) является, по крайней мере, одна эффективная точка.
Утверждение 4 . Если x * - единственная (с точностью до эквивалентности) точка, являющаяся решением m-й задачи из (6), то она эффективна.

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

Пример №1 . Решить методом последовательных уступок многокритериальную задачу.
f 1 (x)=7x 1 +2x 3 -x 4 +x 5 → max ,

при ограничениях
-x 1 +x 2 +x 3 =2 ;
3x 1 -x 2 +x 4 =3 ;
5x 1 +2x 2 +x 3 +x 4 +x 5 =11;
x i ≥ 0 для i=1,2,...,5.
Упорядочим критерии согласно их нумерации, то есть будем в начале работать с критерием f 1 (x), а затем с критерием f 2 (x).
При решении примера методом искусственного базиса была получена симплекс-таблица (табл.). Возьмем ее в качестве начальной, вычислив относительные оценки для функции f=f 1 (x). Получим таблицу 10. Таблица 11 определяет точку, доставляющую функции f1(x) наибольшее значение f 1 * , равное 16.
Таблица 10. Таблица 11.

		7	0
c в		X 1	x 2			x 4	x 2
2	x 3	-1	1	2	x 3	1/3	2/3	3
-1	x 4	3	-1	3	x 1	1/3	-1/3	1
1	x 5	3	2	6	x 5	-1	3	3
	f 1	-9	5	7	f 1	3	2	16

Далее переходим к решению задачи
f 2 (x)=x 1 -5x 2 -4x 3 +x 4 → max
при ограничениях задачи, к которым добавлено новое ограничение f 1 (x)≥f 1 * -Δ:
-x 1 +x 2 +x 3 =2,
3x 1 -x 2 +x 4 =3 , (7)
5x 1 +2x 2 +x 3 +x 4 +x 5 =11,
7x 1 +2x 3 - x 4 +x 5 ³16-Δ,
x i ≥ 0 для i=1,2,...,5.
Новое ограничение преобразуем в равенство и заменим переменные x 1 , x 3, x 5 , используя таблицу 11, выражениями
x 1 =1/3x 2 -1/3x 4 +1, x 3 =-2/3x 2 -1/3x 4 +3, x 5 =-3x 2 +x 4 +3.
В результате этих преобразований дополнительно введенное ограничение примет вид -2x 2 -x 4 +x 6 =-16+Δ. Итак, получили задачу параметрического программирования с параметром в правой части ограничений.
В качестве начальной таблицы для задачи (7) можно использовать таблицу 12, которая получена из таблицы 11 в результате пополнения ее еще одной строкой и пересчета строки относительных оценок. Решим задачу (7) для произвольного параметра Δ≥0. Для этого столбец правых частей ограничений в таблице 12 представим в виде двух столбцов z′, z″: z i 0 =z i ′+z i ″Δ. При выборе главной строки в таблице 12 следует использовать значения из столбца z′. Полученная далее таблица 13 является оптимальной при Δ=0 и при всех значениях Δ, удовлетворяющих условиям
3+(-1/9) Δ ≥ 0, 1+(-1/9) Δ ≥ 0, 3+1/3 Δ ≥ 0, 0+1/3 Δ ≥ 0.
Из этой системы неравенств получаем 0 ≤ Δ ≤ 9. При этих значениях параметра решением задачи является точка x*=(1+(-1/9)Δ, 0, 3+(-1/9)Δ, 0+1/3Δ, 3+1/3Δ).
Таблица 12. Таблица 13.

		1	-5
с в		x 4	x 2	z′	z″		x 6	x 2	z′	z″
-4	x 3	1/3	2/3	3	0	x 3	-1/9	4/9	3	-1/9
1	x 1	1/3	-1/3	1	0	x 1	-1/9	-5/9	1	-1/9
0	x 5	-1	3	3	0	x 5	1/3	11/3	3	1/3
0	x 6	3	2	0	1	x 4	1/3	2/3	0	1/3
	f 2	-2	2	-11	0	f 2	2/3	10/3	-11	2/3

При Δ > 9 таблица 13 не является оптимальной, и нужно выполнить шаг двойственного симплекс-метода с главным элементом, стоящим на пересечение второй строки и первого или второго столбцов. Получим таблицу 14, из которой видно, что при Δ > 9 решениями являются точки, доставляющие функции f 2 (x) значение –5. Таблица 14 определяет опорное решение x ** =(0,0,2,3,6).
Таблица 14.

	x 1	x 2	z′	z″
x 3	-1	1	2	0
x 6	-9	5	-9	1
x 5	3	2	6	0
x 4	3	-1	3	0
f 2	6	0	-5	0

Найдем эти решения. Выберем главным столбец с 0-оценкой. В зависимости от Δ главной строкой будет первая или вторая строка. Если
(-9+Δ)/5 > 2, то главной строкой будет выбрана 1-я. А значит, следующей будет таблица 15. Она определяет опорное решение X=(0,2,0,5,2) , если
–19+Δ≥0. Итак, если D≥19, оптимальными решениями будут все точки выпуклой комбинации
ax ** +(1-a)x * =(0, 2-2a, 2a,5-2a,2+4a), где a∈.
Таблица 15.

	x 1	x 3	z′	z″
x 2	-1	1	2	0
x 6	-4	-5	-19	1
x 5	5	-2	2	0
x 4	2	1	5	0
f 2	6	0	-5	0

Если (-9+Δ)/5 > 2, то главной строкой будет выбрана 2-я. А значит, следующей после таблицы 14 будет таблица 16. Таблица 16 определяет решение X=(0, (-9+Δ)/5, (19-Δ)/5, (6+Δ)/5, (48-2Δ)/5), если –19+Δ≤0. Итак, если Δ≤19, оптимальными решениями будут все точки выпуклой комбинации
ax**+(1-a)x*=(0, (1-a)(-9+Δ)/5, (19-Δ)/5+a(-9+Δ)/5, (6+Δ)/5+a(9-Δ)/5, (48-2Δ)/5+a(-18+2Δ)/5), где a∈.
Таблица 16.

	x 1	x 6	z′	z″
x 3	4/5	-1/5	19/5	-1/5
x 2	-9/5	1/5	-9/5	1/5
x 5	33/5	-2/5	48/5	-2/5
x 4	6/5	1/5	6/5	1/5
f 2	6	0	-5	0

Окончательный результат формулируется следующим образом: решением многокритериальной задачи являются:
точки x*=(1+(-1/9)Δ, 0, 3+(-1/9)Δ, 0+1/3Δ, 3+1/3Δ), если 0 ≤ Δ ≤ 9,
точки x**=(0, (1-a)(-9+Δ)/5, (19-Δ)/5+a(-9+Δ)/5,
(6+Δ)/5+a(9-Δ)/5,(48-2Δ)/5+a(-18+2Δ)/5), если 9 < Δ ≤ 19,
точки x *** =(0, 2-2a, 2a,5-2a,2+4a), если Δ ≥ 19,
где a∈.

Пример №2 . Методом последовательных уступок найти решение задачи, считая, что критерии упорядочены по важности в последовательности {f 2 ,f 1 }, и Δ 2 =1.
f 1 =-x 1 +3x 2 → max,
f 2 (x)=4x 1 -x 2 → max ,
Первая задача из последовательности (6) в данном случае имеет вид:
f 2 (x)=4x 1 -x 2 → max ,
при ограничениях
-x 1 +x 2 ≤1, x 1 +x 2 ≥3, x 1 -2x 2 ≤0 , x 1 ≤4 , x 2 ≤3.
Решение этой задачи можно найти графически. Из рисунка 14 видно, что максимум критерия f 2 (x) на множестве X достигается в вершине x 5 =(4,2) и f 2 * =f 2 (x 5)=14.
Графическое решение примера №2.

Рис.
Добавим к ограничениям задачи условие f 2 ≥f 2 * -Δ и сформулируем вторую задачу последовательности (6):
f 1 =-x 1 +3x 2 → max,
-x 1 +x 2 1 , x 1 +x 2 3, x 1 -2x 2 0 , x 1 4 , x 2 3,
4x 1 -x 2 13
Ее решением (рис.) будет вершина x 4 =(4,3) и f 1 * =f 1 (x 4)=5. Так как, оптимальное решение последней задачи единственно, то в силу утверждения 5, x 4 принадлежит множеству Парето.
Отметим, что при Δ∈ методом последовательных уступок будет найдена одна из точек отрезка , а при Δ>1, одна из точек отрезка . Все эти точки и только они принадлежит множеству Парето.

Целью изучения данной темы является ознакомление студентов с методами многокритериального выбора.

Задачи:

Ознакомить студентов с методами измерения показателей, используемых в качестве критериев при принятии управленческих решений.

Описать подходы к формированию системы показателей, используемых при многокритериальном выборе.

Дать представление о методах многокритериального выбора и особенностях их применения.

1. Шкалы измерения

Наиболее «простой», точнее говоря, слабой является номинальная шкала. “Nome ” на латыни – имя, то есть речь идёт о шкале наименований. В этой шкале различаются только классы объектов, например, резиденты и нерезиденты. Разумеется, шкала может содержать и больше классов (отраслевой классификатор и т.п.), хотя дихотомическое деление является важным частным случаем.

Номинальная шкала используется, в основном, для решения двух задач:

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

Во втором случае накопленная статистика подвергается обработке численными методами с целью анализа того или иного явления.

Более «сильной» является ординальная (порядковая) шкала. Её также часто называют шкалой рангов. Задача, решаемая с помощью ординальной шкалы, - это упорядочивание объектов (альтернатив, с точки зрения процесса принятия управленческого решения) по предпочтению. Различают отношения нестрогого предпочтения (этот объект не хуже того) и строгого («больше – меньше»).

Измерения в ранговой шкале не отвечают на вопрос «насколько больше?». Отчасти эта проблема решается увеличением числа рангов. Общая рекомендация при конструировании ранговых шкал состоит в составлении не слишком дробной шкалы, так как в противном случае затрудняется экспертное оценивание, однако количество рангов должно быть достаточным, чтобы улавливать все существенные различия.

Типичным примером измерений в ранговых шкалах являются различные рейтинги. Определённую роль играет использование этой шкалы в микроэкономике, так как позволяет снять некоторые спорные постулаты о природе ценностей.

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

Следующая «по силе» - интервальная шкала. Эта шкала классифицирует объекты по принципу «больше на определённое количество единиц – меньше на определённое количество единиц». Следует различать абсолютную и относительную величину интервалов. Например, если студент А решил задачу за 2 сек., а студент Б за 22 сек., то в абсолютном выражении интервал будет таким же, как и в том случае, когда студент В решает задачу за 222 сек., а Г - за 242 сек. Понятно, что «значимость» интервала в 20 сек. в рассмотренных случаях может быть различной.

Интервальная шкала даёт точное представление об отношении длин отрезков, однако в ней даже зная расстояние между 1-ой и 2-ой и 2-ой и 3-ей точкой нельзя точно указать расстояние между 1-ой и 3-ей точками, так как их взаимное расположение не определено однозначно. В интервальной шкале в этой ситуации можно делать однозначные заключения только о соотношении длин отрезков, но не их удалённости от какой-либо точки.

Абсолютная шкала получается из интервальной введением точки отсчёта. Это решает обсуждавшиеся выше проблемы. Именно для абсолютной шкалы справедливы обычно используемые на практике операции с расстояниями.

2. Требования к построению системы критериев

Наряду с проблемой измерения важной проблемой является построение системы показателей, отражающих генеральную цель. В литературе 1 сформулирован целый ряд требований, которые необходимо соблюдать, чтобы использование системы показателей было оправданным. Это требования полноты, действенности, разложимости, неизбыточности и минимальной размерности.

Полнота

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

Действенность (операционность)

Используемые показатели должны быть однозначно понимаемы, измеримы и доступны оценке.

Разложимость

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

Неизбыточность

Дублирование показателей «засоряет» информационные каналы, снижает как скорость, так и качество сбора и обработки информации.

Минимальная размерность

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

3. Методы многокритериального выбора

Метод свёртки критериев

Стандартный приём «борьбы» с многокритериальным выбором это переход к однокритериальной задаче с использованием метода свёртки критериев.

Свёртка критериев означает построение интегрального показателя на основе частных критериев. Интегральный показатель I рассчитывается или как взвешенная сумма частных показателей (выражение (1) - аддитивная форма) или как их произведение (выражение (2) – мультипликативная форма), опять же нормированное на соответствующие веса (важность критериев).

K – частный критерий,

a – вес критерия, причём ,

N – количество критериев,

v - номер критерия.

Использование такого метода как свёртка критериев предполагает, что частные критерии измеряются в абсолютной шкале. Кроме того, критерии должны быть независимы друг от друга. Это означает, что справедливы выражения (3) и (4), то есть отношение предпочтения определяется либо критерием «2» - выражение (3), - либо критерием «1» - выражение (4).

(xi1, xi2) < (xi1,xj2) => (xj1, xi2) < (xj1, xj2) (3)

(xi1, xi2) < (xj1,xi2) => (xi1, xj2) < (xj1, xj2) (4)

Вес критериев, как правило, определяется экспертным методом.

Типичным примером использования метода свёртки критериев является построение интегрального показателя качества продукции.

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

Лексикографический метод

Лексикографический метод предполагает, что имеющийся ряд критериев упорядочен по важности.

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

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

Процедура заканчивается на той итерации, на которой удаётся упорядочить объекты по предпочтительности, или когда проведены сравнения по всем критериям.

Наверное, наиболее известный пример использования лексикографического метода – определение места команды в спортивном состязании, например, чемпионате по футболу. В этом случае победитель определяется по количеству набранных очков. В случае их равенства последовательно используются дополнительные показатели - количество побед, разность мячей, результаты очных встреч и т.п.

Выделение множества Парето

В наибольшей степени идеологии многокритериального выбора соответствует процедура выделения множества Парето (ядра графа).

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

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

Таблица 1.

Характеристика инвестиционных проектов

Показатель	Проект №1	Проект №2	Проект №3	Проект №4	Проект №5	Проект №6	Проект №7
Прибыль, млн. руб.
Кап. вложения, млн. руб.

Попарное сравнение проектов показывает, что проект №5 доминирует проект №2, а проект №1 доминирует проект №3. Эти проекты должны быть исключены из рассмотрения. Каждый из остальных проектов в каком-то смысле лучше другого оставшегося, а в каком-то хуже: или он даёт больше прибыли, но требует больших капитальных вложений, или наоборот. Проекты 1, 4, 5, 6 и 7 оптимальны по Парето. Выбор одного из них требует дополнительных соображений.

ВЫВОДЫ

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

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

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

Наиболее распространённым методом решения многокритериальных задач является построение интегральных показателей на основе метода свёртки критериев.

Для использования метода свёртки критериев необходимо измерение значений критериев в абсолютной шкале, а также соблюдение требования независимости критериев.

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

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

Вопросы для самопроверки

Какие шкалы используются для измерения значений показателей – критериев при принятии управленческих решений?
В каких целях используются номинальная шкала?
Каковы особенности измерения в ранговой шкале?
Какие требования предъявляются к системе показателей, являющихся критериями при принятии управленческого решения?
Какие существуют методы многокритериального выбора?
Каковы особенности процедуры свёртки критериев?