Функция выбора. Основные понятия

ЛЕКЦИЯ № 8

Задача выбора возникает, когда из некоторого конечного или

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

Более строго функцию выбора можно определить следующим образом. Пусть А - множество элементов из которых осуществляется выбор, ХÍА - множество допустимых решений (предъявление), а С(Х)ÍХ - множество отобранных точек (выбор). Отображение j: Х®C(Х) называется функцией выбора. Алгоритм реализующий эту функцию выбора называется механизмом выбора.

Рассмотрим примеры наиболее распространенных механизмов выбора.

1) Скалярный оптимизирующий механизм - выбор вариантов, при которых некоторая скалярная функция f(х) достигает максимума.

С_опт(Х) = { хÎХ | х=arg max f(x) }

2) Условно-оптимальный механизм - выбор по схеме математического программирования, т.е. выбор таких хÎХ, при которых достигается условный максимум скалярной функции f₀(x) при выполнении системы ограничений.

С_мп(Х) = { хÎХ | х=arg[ max f₀(x)|f _i(х)£0, i=1,..,m] }

3) Механизм доминирования по бинарному отношению R – выбор тех хÎХ, которые с любым элементом из Х находится в отношении R (элемент х лучше любого y в смысле отношения предпочтении R).

С_R(Х)={ хÎХ | " yÎХ: (x,y)ÎR }

4)Механизм блокировки по бинарному отношению R - выбор тех элементов xÎX, для которых в Х нет элемента лучше в смысле отношения предпочтения R.

С^R(Х) = { хÎХ | " yÎХ: (x,y)ÏR }

5) Механизм ограничений по бинарному отношению R отбирает те элементы х, которые с фиксированной точкой u образует пару в R.

С_u(Х) = { хÎХ | (x, u)ÎR }

6) Паретовский механизм осуществляет выбор таких элементов х, для которых нет элемента y лучшего чем х сразу по всем критериальным функциям f _i(х).

С_par(Х) = { хÎХ | не $ yÎХ: f _i(y)³f _i(x) " i=1,..,m }

7) Турнирный механизм - выбор такого х, при котором достигает максимума турнирная функция f _R(x). Ее можно трактовать, как число очков, набранных элементом х во время турнира со всеми элементами из Х.

С_T(Х) = { хÎХ | х=arg max f _R(x) };