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

Многокритериальные задачи принятия решений. Часть 1. Отношение Парето

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

Что такое многокритериальные задачи принятия решений

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

Простой способ сокращения числа вариантов

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

Стратегия 2 в среднем даёт больше прибыли, чем стратегия 1, при той же надёжности. Стало быть, стратегия 1 не может быть лучшей. Стратегия 3 по ожидаемой прибыли равноценна стратегии 2, но надёжнее. Стало быть, стратегия 2 тоже невыгодна. Стратегия 3 прибыльнее стратегии 4 при той же надёжность, то есть стратегия 4 тоже неоправданна. Остаются только стратегии 3 и 5. По одному критерию превосходит одна, по другому - другая. Мы не смогли прийти к единственному варианту, но хотя бы устранили большинство заведомо неверных.

Отношение Парето, Парето-оптимальные решения, множество Парето

Теперь определим, что такое отношение Парето. Вариант x лучше варианта y по отношению Парето (далее: x > y), если x хотя бы по одному критерию лучше, чем y, а по остальным критериям не хуже, чем y. Данное отношение транзитивно (если x > y и y > z, то x > z), антерефлексивно (невозможно x > x), асимметрично (невозможно одновременно x > y и y > x), то есть это отношение строгого порядка. Заметим, что между конкретной парой (x, y) не всегда можно установить отношение Парето, как это было в случае стратегий 3 и 5 в нашем примере. Такое отношение не устанавливается, если каждый из пары в чём-то лучше, а в чём-то хуже "партнёра".

Вариант x называется Парето-оптимальным решением, если нет такого варианта y, что y > x по Парето (здесь не рассматривается, может ли таковой появиться в будущем, берём только те варианты, которые мы имеем сейчас). Множество таких решений обозвали множеством Парето. В нашем примере это стратегии 3 и 5.

Чтобы выбрать конкретное решение из Парето-оптимального множества (если в нём больше одного варианта), нужны какие-то добавочные данные, например, сведения о приоритетах критериев. Допустим, у Васи выбор - с какой девушкой встречаться: Катя красива, но тупа, Маша умна, но страшна, Дуся и тупа, и страшна. Васе нужна девушка поумнее и покрасивее. Парето-оптимальное множество: {Катя, Маша}. Дальше Парето не помощник, тут уже что важнее - ум или красота?

Парето-оптимальные решения на непрерывных множествах вариантов

Есть ещё один вопрос - а как применять всю эту теорию, если множество вариантов непрерывно? Проще всего, когда оно выпуклое, допустим, как вот этот пятиугольник (не только контур, но и собственно площадка):

Нетрудно убедиться, что Парето-оптимальное множество - северо-восточная граница контура (отрезок BC в нашем примере). Для большей уверенности убедитесь сами, что точки A, D, F не являются Парето-оптимальными решениями). Имейте в виду: это правило верно, если нам нужно, чтобы величины критерии были как можно больше. Последнее не всегда бывает так. Например, стоимость приоретения, расход топлива должны сводиться к минимуму. В этом случае требуется заменить такие "минимизируемые" критерии на "максимизируемые" аналоги, например, расход - на экономию, вероятность сбоя - на вероятность бесперебойного функционирования... Скажем, если вероятность сбоя = 0,02, то надёжность составляет 0,98.

Сложнее дело, если множество невыпуклое:

Понятно, что снова вне северо-восточной границы не может быть Парето-оптимальных вариантов. Итак, Парето-оптимальные варианты могут быть только на ломаной ABCD, но и тут есть "негодные" вариаты. Остаётся их отсеять. Проведя построения, как на рисунке, видим, что множество Парето образуется из двух групп вариантов. 1. Отрезок AE, исключая точку E (поскольку C > E), за счёт высоких показателей по второму вритерию. 2. Отрезок CD - за счёт высоких показателей по первому критерию.

Множество Парето при планировании производства

Яркий пример применения приведённой тут теории - линия производственных возможностей в экономике. Допустим, некий дедок решил не довольствоваться скудной пенсией и зарабатывать, торгуя самогоном и картошкой. Его производственные возможности выражаются следующим образом:

Нетрудно заметить, что на линии производственных возможностей и будут варианты из множества Парето. Варианты под ней не могут быть Парето-оптимальными. Глянем на рисунок и найдём точку A. Видно, что B > A (одинаковое количество самогона, но больше картошки), C > A (больше самогона, картошки поровну).

Общий вывод о пользе отношения Парето

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

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

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