Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Многокритериальные задачи принятия решений. Часть 2. Свёртка критериев

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

Что такое свёртка критериев и зачем это надо

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

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

Пусть у нас есть n критериев, при этом для варианта x оценки по критериям следующие:

Если по i-ому критерию x - безукоризненный вариант (по крайней мере, другие варианты выбора не лучше его по данному критерию), то оценка = 1, если отвратительный, то 0, если "так себе" - где-то между 0 и 1. Как выставлять такую оценку более чётко, поясним ниже при описании так называемой нормировке критериев.

Приоритеты критериев следующие:

Их же иногда именуют весами критериев. Приоритеты одинаковы для всех вариантов выбора. Такое введение напоминает свойства вероятностей, но это ложная аналогия) Кстати, приоритет может быть равным нулю или единице, но это нежелательно (если единица, то выходит, что у нас единственный критерий, а не несколько; если ноль, то по сути критерий не играет никакой роли).

Оператор свёртки критериев для варианта x имеет вид:

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

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

Функция g должна быть конкретизирована. Важное условие: она должна давать значения на отрезке [0; 1] при любых допустимых приоритетах и критериальных оценках.

Конкретные примеры операторов свёртки

Приведём несколько примеров функции g.

Простейший пример - линейная свёртка (она же аддитивная свёртка):

Если вариант x ужасный (все f обращаются в нуль), то w(x)=0, если наилучший, (все f - единицы), то w - сумма приоритетов, что по определению означает w(x)=1. Таким образом, w(x) не вылезает за 0 и 1.

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

Мультипликативная свёртка посложнее аддитивной свёртки:

Такая свёртка удачна, когда низкие оценки даже по одному-двум критериям в принципе нежелательны. Заметьте: если хоть одна из f нулевая, единая оценка тоже нулевая.

А теперь пример подходящего случая. Скажем, на вооружение армии Республики Бананос нужно принять новый вид танков. Есть несколько вариантов. Критерии - характеристики орудия, защищённость, быстрота. Командование считает, что ни паршивая пушка, ни слабая броня, ни тормознутость ничем не компенсируются. Рассуждения "танк Т-2098 слабо защищённый, зато дальность орудия - абалденная" не принимаются. Военные деятели Бананос считают: "мы не можем допустить, чтобы враги разносили в клочья наши танки, а экипажи погибали один за другим, хоть от слабой брони, хоть от медлительности, хоть от того, что наше орудие бесполезно - им нельзя отбиться от вражеских машин". И добавляют "мы будем принимать решение с помощью мультипликативной свёртки". А вот аддитивная свёртка тут плохо подходит - едва ли приведённые в примере критерии легко компенсируют друг друга.

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

Нормировка критериев

Оценки по разным критериям могут иметь разные шкалы, например, в примере про танки защищённость можно упрощённо считать как толщину брони и измерять в мм, а скорость измеряется в м/с. Кроме того, могут быть в принципе схожие единицы измерения, но слишком различные размеры. Как толщина брони, так и дальность орудия измеряются единицами длины, но только первая - порядка 100-200 мм, вторая может достигать многих километров.

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

Один из способов нормировки - по эталону:

Пусть, например, все известные командованию танки имеют орудия, дальности которых до 10 км. Пусть орудие танка Т-2098 имеет дальность 9,5 км. Тогда критериальная оценка составит 0,95.

Вполне может быть, что показатель требуется не максимизировать, а минимизировать, пример - критерий "расход топлива автомобилем". Тогда берём не ту величину, что определяется по только что приведённой формуле, а обратную, то есть делим эталонное на измеренное. Скажем, никакие известные нам тачки не расходуют топливо меньше, чем 0,02 л/км. Перед нами тачка с расходом 0,025 л/км. Тогда её критериальная оценка 0,02/0,025 = 0,8.

Часто бывает, что мы не можем точно сказать, что такое идеальный вариант по данному критерию. Скажем, нам нужно выбрать технологию производства деталей. Лучшая из известных нам даёт производительность 30 дет/ч, при этом мы не знаем точно, насколько велика предельно возможная производительность в нашем производстве (может, кто-то уже создал секретную технологию с производительностью 100 дет/ч, а может, такой показатель можно будет достичь только через 50-60 лет - сейчас наука и техника ещё далеки до этого). Или есть ещё вариант - мы знаем идеал, но нам его не достичь (скажем, у нас нет средств внедрить самую производительную в мире технологию).

У нас есть несколько вариантов. У лучшего с точки зрения критерия К оценка по критерию К составляет fmax, у худшего - fmin. Тогда нормировка для fизмер выполняется вот так:

Вернёмся к многострадальной республике, которой нужны новые танки. Пусть у Т-2098 дальность орудия составляет 9,5 км, у Х-1 - 8 км, у Х-2 - 11 км, у ХХХ-44 - 8,6 км. Тогда fmin = 8; fmax = 11. Соответственно вот какими будут оценки после нормировки:

ТанкНормированная дальность пушки
Т-2098(9,5 - 8)/(11 - 8) = 0,5
Х-10
Х-21
ХХХ-44(8,6 - 8)/(11 - 8) = 0,2


Если же нам нужна минимизация, то вычисляем нормированные оценки как f = (fmax - fизмер)/(fmax - fmin).

Определение весов критериев

Теперь остался вопрос, как определить веса.

Первый из способов - простое ранжирование. Пусть у нас n критериев. Самому важному присваиваем n очков, следующему по важности n-1 очков, последнему одно очко. Полученные оценки делим на (1 + 2 + ... + n) - чтобы сумма весов была равна единице.

Опять танки) Пусть ставка верховного командования Республики Бананос сочла, что защищённость танка важнее характеристик орудия, а последние важнее манёвренных качеств танка. Тогда защищённость - 3 очка, орудие - 2 очка, манёвренность - 1 очко. 1 + 2 + 3 = 6, поэтому защищённость: 3 / 6 = 0,5; орудие: 2 / 6 = 0,33; манёвренность: 1 / 6 = 0,17.

Возникает вопрос: а если есть критерии с равными приоритетами, например, защищённость танка важнее прочего, но манёвренность танка и характеристики орудия имеют равные приоритеты. Тогда вот что получается: на орудие и манёвренность в сумме должно прийтись 3 очка (1 + 2), но поскольку эти критерии равноценны, перераспределяем эти 3 очка поровну: по 1,5 каждому. На защищённость по-прежнему "выделено" 3 очка. В итоге получаем веса 3/6 = 0,5; 1,5/6 = 0,25; 1,5/6 = 0,25.

Пример посложнее: вожди Бананос сочли, что равно важны и важнее всего прочего защищённость танка и мощь орудия, менее важны манёвренность и расход топлива, причём последние два критерия имеют одинаковый приоритет. На первые два критерия должны прийтись 4 + 3 = 7 очков, делим их поровну и получаем 3,5 очка на каждый. На последние два: 2 + 1 = 3 очка, делим поровну и получаем по 1,5 очка. Нормируем делением на 1 + 2 + 3 + 4 = 10 и получаем веса 0,35; 0,35; 0,15; 0,15.

Есть также пропорциональный метод. Скажем, Ставка верховного командования считает, что защищённость танка втрое важнее, чем манёвренность, а мощь орудия - вчетверо важнее манёвренности. Пусть вес критерия манёвренности равен z, тогда вес защищённости = 3z, мощи орудия = 4z. По свойству суммы весов получаем, что 8z=1, то есть получаем следующие веса:

Защищённость0,375
Орудие0,5
Манёвренность0,125


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

Пример свёртки критериев

А теперь примерчик. Возьмём на вооружение аддитивную свёртку. Допустим, мы выбираем производственную технологию, критерии - производительность, срок обучения персонала, стоимость внедрения. Варианты:

ТехнологияПроизводительность, изделий/часСрок обучения, месСтоимость внедрения, тыс. руб.
Т115340
Т230660
Т310210
Т420425


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

Займёмся нормировкой критериев без эталонов. Для производительности: наилучшия = 30, наихудшая = 10; стало быть для Т1 получаем (15 - 10) / (30 - 10) = 0,25; для Т4 получим (20 - 10) / (30 - 10) = 0,5. Для срока обучения персонала: лучший - 2 месяца, худший - 6 месяцев, тут пользуемся формулой f = (fmax - f)/(fmax - fmin). Стало быть, для T1 будет (6 - 3)/(6 - 2) = 0,75; для T4 (6 - 4)/(6 - 2) = 0,5. Аналогично с затратами бабла - их хотелось бы тоже меньше.

ТехнологияПроизводительность, изделий/часСрок обучения, месСтоимость внедрения, тыс. руб.
Т10,250,750,4
Т2100
Т3011
Т40,50,50,7


Теперь остался вопрос приоритетов. Скажем, нас очень заинтересовало повышение производительности; срок обучения и вложение бабок примерно равны по важности, но находятся на втором плане. Тогда на основной критерий - 3 очка, на прочие два: 2 + 1 = 3 очка, то есть по 1,5 на каждый. В итоге:

Производительность3/6 = 0,5
Срок обучения персонала1,5/6 = 0,25
Экономность1,5/6 = 0,25


В итоге получаем, что w(x) = 0,5f1 + 0,25f2 + 0,25f3.

w(T1)0,5 * 0,25 + 0,25 * 0,75 + 0,25 * 0,4 = 0,4125
w(T2)0,5 * 1 + 0,25 * 0 + 0,25 * 0 = 0,5
w(T3)0,5 * 0 + 0,25 * 1 + 0,25 * 1 = 0,5
w(T4)0,5 * 0,5 + 0,25 * 0,5 + 0,25 * 0,7 = 0,55

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

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X