Алгоритмы / [Из песочницы] Использование нечетких бинарных отношений при решении задачи о назначениях (распределение персонала)

Задача о назначениях известна достаточно давно, основные алгоритмы ее решения уже описаны на Хабарахабре (см. например Задача о назначениях). Тем не менее задача до сих пор актуальна при распределении сотрудников по должностям, в случае когда сотрудников и должностей и критериев очень много, обычные методы окажутся очень трудоемкими
для лица, принимающего решение (ЛПР). Более того, на данный момент для решения такой задачи возможно использование генетического алгоритма и его модификации (интерактивный генетический алгоритм). То есть возникает достаточно сложная многокритериальная задача поиска оптимальной альтернативы, которю можно разбить на две задачи. Если вакансия одна, а претендентов много, то для ЛПР для выбора эффективным будет использование метода многокритериальный выбора альтернатив с использованием правил нечеткого вывода (Многокритериальный выбор альтернатив с использованием правил нечеткого вывода.).
В данной статье предпринимается попытка решить задачу о назначениях в случае нескольких должностей и нескольких вакансий с помощью методов нечеткой логики, а именно с помощью использования нечетких бинарных отношений. Предложения/замечания/улучшения приветствуются.
Итак, что же такое нечеткое отношение?
В общем случае нечетким отношением или, более точно, нечетким k-арным отношением, заданным на множествах (универсумах) Х1, Х2,…, Хk, называется некоторое фиксированное нечеткое подмножество декартова произведения этих универсумов. Другими словами, если обозначить произвольное нечеткое отношение через Q, то по определению Q={, µQ()}, где µQ() – функция принадлежности данного нечеткого отношения, которая определяется как отображение µQ: Х1×Х2×…×Хk →[0, 1]. Здесь через обозначен кортеж из k элементов, каждый из которых выбирается из своего универсума: х1 ϵ Х1, х2 ϵ Х2,…, хk ϵ Хk.
Бинарное нечеткое отношение. В общем случае бинарное нечеткое отношение задается на базисных множествах Х1, Х2 и определяется как нечеткое отношение Q={, µQ()}. Здесь µQ() – функция принадлежности бинарного нечеткого отношения, которая определяется как отображение µQ: Х1×Х2 →[0, 1], а через обозначен кортеж из двух элементов, при этом х1 ϵ Х1, х2 ϵ Х2.
Кроме того, для построения решения задачи нам потребуются композиции нечетких бинарных отношений:
Композиция двух бинарных нечетких отношений. Пусть Q и R – конечные или бесконечные бинарные нечеткие отношения. Причем нечеткое отношение Q={, µQ()} задано на декартовом произведении универсумов Х1×Х2, а нечеткое отношение R={, µR()} – на декартовом произведении универсумов Х2×Х3. Нечеткое бинарное отношение, заданное на декартовом произведении Х1×Х3 и обозначаемое через Q x R, называется композицией бинарных нечетких отношений Q и R, а его функция принадлежности определяется следующим выражением:
Определенную таким образом композицию бинарных нечетких отношений называют иногда (max-min)-композицией или максиминной сверткой нечетких отношений.
Альтернативные операции композиции двух бинарных нечетких отношений. Нечеткое бинарное отношение, заданное на декартовом произведении Х1×Х3 и обозначаемое через Q * R, называется (max-*)-композицией бинарных нечетких отношений Q и R, если его функция принадлежности определяется следующим выражением:
В частности, если в этом выражении вместо операции «*» использовать операцию алгебраического умножения, то получим определение (max-prod)-композиции.
(min-max)-композиция. Нечеткое бинарное отношение, заданное на декартовом произведении Х1×Х3 и обозначаемое через Q + R, называется (min-max)-композицией бинарных нечетких отношений Q и R, если его функция принадлежности определяется следующим выражением:
Теперь перейдем непосредственно к задаче. Данный метод разработан для решения конкретной задачи в сфере управления персоналом, поэтому опишу его работу сразу на примере этой задачи.
Итак, есть два множества: совокупность должностей и их профили и совокупность работников, которых нужно максимально эффективно распределить. Таким образом, входными данными являются данные множества, а выходными – степени соответствия кандидатов должностям.
В связи с вышесказанным, рассмотрим нечеткую модель, основанную на двух бинарных нечетких отношениях Ϯ и Ψ. Первое из этих нечетких отношений строится на двух базисных множествах Х = {x1,…, xn} и У = { y1,…, ym }, а второе – на двух базисных множествах У = { y1,…, ym } и Z = { z1,…, zl }. Здесь Х описывает множество специальностей, по которым проводится набор на работу, У – множество характеристик (свойств) должностей а Z – множество кандидатов на должности. В интересуемом нас контексте нечеткое отношение Ϯ содержательно описывает профили специальностей, а Ψ – профили кандидатов на должности. Для определения соответствия кандидатов должностям воспользуемся композициями исходных нечетких отношений. Так, (max-min)- и (max-prod)-композиции (см. пункт 2.2) дают информацию о степени соответствии кандидата вакансии и возможности его назначения, а (min-max)-композиция возможно позволяет определить работника, который не подходит на данную работу.
Таким образом, применяются три модели:max-min – модель

max-prod – модель

min-max – модель

Была написана небольшая программа для подсчета этих композиций, но я ее здесь описывать не буду, так как она очень простая (работа с матрицами) и пост и так уже очень длинный. Перейдем сразу к экспериментам с программой.
Рассмотрим нечеткую модель, основанную на двух бинарных нечетких отношениях Ϯ и Ψ. Первое из этих нечетких отношений строится на двух базисных множествах Х и У, а второе – на двух базисных множествах У и Z. Здесь X описывает множество специальностей, по которым проводится набор на работу, У – множество психо-физиологических характеристик а Z – множество кандидатов на должности. В интересуемом нас контексте нечеткое отношение Ϯ содержательно описывает психо-физиологическое профилирование специальностей, а Ψ – психо-физиологическое профилирование кандидатов на должности. Для конкретности, пусть X = { менеджер, программист, водитель, секретарь-референт, переводчик }; У = { быстрота и гибкость мышления, умение быстро принимать решения, устойчивость и концентрация внимания, зрительная память, быстрота реакции, двигательная память, физическая выносливость, координация движений, эмоционально-волевая устойчивость, ответственность }; Z = { Петров, Иванов, Сидоров, Васильева, Григорьева }. Конкретные значения функций принадлежности μϮ () и μΨ () рассматриваемых нечетких отношений представлены следующими таблицами (табл. 3.1 и 3.2).
Поскольку рассматриваемые отношения удовлетворяют формальным требованиям, необходимым для выполнения их нечеткой композиции, результат операции нечеткой композиции может быть представлен в виде
Анализ табл. 3.3 показывает, что HR-менеджеру можно порекомендовать рекомендовать назначить людей на следующие должности (на основе максимальных значений функции принадлежности композиции рассматриваемых нечетких отношений): Петров – менеджер, водитель; Иванов – менеджер, секретарь; Сидоров – водитель; Васильева – менеджер, Григорьева – менеджер. С точки зрения назначения рассматриваемых работников на место менеджер наиболее подходят кандидаты: Петров, Иванов, Васильева и Григорьева; по специальности программист – те же кандидаты; на должность водителя – Сидоров; на должность секретаря Иванов; на работу в качестве переводчика – Сидоров и Васильева.
Рассмотрим теперь нечеткую композицию исходных нечетких отношений.
Анализ табл. 3.4 показывает, HR-менеджеру можно порекомендовать рекомендовать назначить людей на следующие должности (на основе максимальных значений функции принадлежности композиции рассматриваемых нечетких отношений): Петров – водитель; Иванов – менеджер, секретарь; Сидоров – водитель; Васильева – менеджер, Григорьева – менеджер. С точки зрения назначения рассматриваемых работников на место менеджер наиболее подходят кандидаты: Иванов и Григорьева; по специальности программист – Григорьева; по специальности водитель – Петров; по специальности секретарь – Иванов; по специальности переводчик – Сидоров и Васильева.
Следуя общим рекомендациям прикладного системного анализа относительно принципа многомодельности, можно сделать следующий вывод. Если при использовании различных моделей получены одинаковые результаты. то этот факт может свидетельствовать о наличии устойчивой связи или закономерности между отдельными элементами моделей. Применительно к рассматриваемым нечетким моделям совпадение результатов. полученных на основе операций (mах-min)-композиции и (mах-рrоd)-композиции, дает основание для более уверенных выводов относительно выбора тех или иных специальностей для обучения кандидатов.
В конце данного теста проанализируем результаты, полученные в результате (min-max)-композиции исходных нечетких отношений.
Проанализируем полученные данные. Так как для нечетких множеств на самом деле главными значениями функции принадлежности являются 0 и 1, при этом наихудшим вариантом с точки зрения выводов является значение 0,5, которое не может дать информативного ответа на вопрос о несоответствии кандидата должности.
Таким образом, исходя из анализа трех композиций можно сделать вывод о дополнении и уточнении данных полученных при помощи (max-min)- и (max-prod)-композиций и некотором расхождении с ними данных (min-max)-композиции двух нечетких отображений. Так например по результатам первых двух композиций Сидоров подходит на должность водителя, а по данным (min-max)-композиции не очень подходит.
На сегодня, я думаю все. Однако я проводил тесты с другими данными и получил результаты, которые проанализировать довольно сложно, то есть такой подход к решению задачи не всегда дает однозначный результат и требуется его доработка.