Функции и механизмы выбора.

Понятия функции и механизма выбора.С помощью механизма (правила) выбора реализуется выбор одной или нескольких альтернатив из множества Х предъявлений. Механизм выбора в общем виде описывается в виде двойки , где S – структура на множестве возможных альтернатив А, L – конкретное правило, которое позволяет совершать выбор из предъявления ХÍ А, на основе существующей структуры S. Структура S создается путем формулирования принципов, которые определяют условия, на которых возможно сравнение альтернатив по качеству, или может быть установлено в результате экспериментальных исследований и опроса ЛПР. В большинстве случаев наиболее распространенные принципы могут быть описаны с помощью бинарных отношений , или могут быть сформулированы правила построения соответствующих бинарных отношений. Поэтому структуру S могут создавать: множество бинарных отношений ; важность отношений, высказанная в лексикографической или числовой форме; эталонные варианты решений и метрики, которые оценивают степень приближения к эталону; допустимые уровни качества альтернатив; правила и принципы агрегирования сложных отношений.

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

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

Если задано множество разрешенных структур ( ) и множество возможных правил выбора ( ), то этим определен класс

механизмов выбора.

Функция выбора С реализуется с помощью механизмов выбора , если функция выбора , которая определяется R, доопределяет или функцию неполного выбора (С, ,В), или частичную, или всюду определенную функцию, то есть , где Х – предъявления, В – множество возможных предъявлений, С(Х), - множества выбранных и отклоненных альтернатив предъявления Х.

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

Выбор по агрегированным отношениям осуществляется путем определения (создания, синтеза) функции F:PÞQ, которая ставит в соответствия множество заданных отношений некоторое отношение , которое называется агрегированным. Окончательный выбор альтернатив осуществляется по правилу L, которому соответствует функция выбора .

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

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

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

Обобщенный пошаговый выбор строиться путем комбинирования на разных шагах вышеприведенных механизмов.

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

Решением задачи анализа является функция выбора С_R, которая реализует механизм выбора .

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

то есть существует до определение функции С неполного выбора

которое удовлетворяет условию

и задача синтеза функции выбора в этом классе механизмов выбора всегда имеет решение.

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

Мажорантой С₊ функции неполного выбора называется всюду определенная функция, для которой справедливо условие

где Х – предъявления, - множество возможных предъявлений, С(Х), - множества выбранных и отклоненных альтернатив соответственно.

Минорантой С_- функции неполного выбора называется всюду определенная функция, для которой справедливо условие

Функция называется верхней аппроксимацией функции С в классе механизмов (где - множество всюду определенных функций , которые реализуются в М), если выполняется условие

Аналогично функция называется нижней аппроксимацией функции С в классе М, если выполняется условие

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

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

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

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