В большинстве стран применяется экономическая модель свободного рынка, отличительным признаком которой является свободная конкуренция. На рынке трудоустройства это стремление очень часто приводит к негативным последствиям. Данную проблему частично поможет решить система, которая однозначно бы сопоставляла студента и работодателя. Главным преимуществом данной системы станет независимость от людей, что приведет к оптимизации времени и затраченных сил.
Рассмотрим алгоритм образования стабильных пар, разработанный математиками Дэвидом Гейлом и Ллойдом Шепли для решения задачи о марьяже1.
Пусть даны два множества M и Ж. Для каждого элемента из множества М элементы из множества Ж отсортированы в некотором порядке. Сортировки для каждого элемента могут быть свои. Аналогичные предпочтения введены и для элементов из множества Ж. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. Задача сводится к разбитию M и Ж на пары. Стабильность пары будет означать отсутствие пары (m, ж) и (m’, ж’), обладающие таким свойством: для m элемент ж’ является предпочтительнее ж, а для ж’ элемент m является предпочтительнее m’.
Данный алгоритм имеет широкое практическое применение. Одна из прикладных задач, решаемых с помощью этого правила – это поиск стабильных пар
«выпускник – работодатель». Работодатель может принять больше одного выпускника на работу. Точное количество актуальных мест будем называть «квотой».
Рассмотрим два конечных непересекающихся множества игроков: M {m1,...,mn} - выпускники и W = {w1,...,wk} — работодатели. Размещением или распределением по парам будем называть взаимно однозначное отображение множества M U W на себя и обладающее свойствами:
- каждый игрок соединен с лицом противоположного множества или остался один;
- если выпускник mi соединен с работодателем wi, то работодатель wi соединен с выпускником mi;
Нестабильным будем называть распределение, если существует такая пара, где:
- существуют выпускники, которые предпочитают связаться с другим работодателем, чем остаться с текущим работодателем;
- существует игрок, который хочет разорвать в одностороннем порядке связь, предписанную в распределении.
Распределение по парам будем считать стабильным, если оно не удовлетворяет ни одному условию нестабильного распределения.
Алгоритм распределения (Рис. 1):
- все студенты делают предложения наиболее предпочтительным компаниям;
- компании выбирают некоторое количество студентов, равное квоте, и принимают их кандидатуры на рассмотрение. Остальные выпускники будут отвергнуты;
- оставшиеся выпускники делают предложения следующим компаниям в списке приоритетов;
- компании рассматривают все заявки (новые и старые), выбирают наиболее предпочтительных выпускников и принимают их на рассмотрение. Остальные отвергаются.
Алгоритм продолжается до тех пор, пока есть компании, готовые принять выпускников, и нетрудоустроенные выпускники. Все выпускники, находящиеся на рассмотрении, получают приглашение на работу.
Рис. 1 Блок-схема алгоритма
Модель была реализована с помощью языка программирования C#. Оболочка алгоритма была написана на базе Windows Forms, на языке программирования C# (Рис 2-4).
Рис. 2 Информация о компании (аналогично для выпускников)
Рис. 3 Расстановка приоритетов выпускниками(аналогично компаниями)
Рис. 4 Результаты
Вывод. Преимущества данного алгоритма состоят в создании оптимальных пар «работодатель – выпускник», так как в результате работы алгоритма студенты получат возможность устроиться на престижную работу, а работодатели уменьшат риски получения неподходящего сотрудника. Как следствие – экономия времени, затрачиваемого специалистом и студентом на собеседования.
Список литературы
1. "Задача о марьяже"[Электронный ресурс] // https://ru.wikipedia.org/wiki/Задача_о_марьяже
2. "Давай поженимся"[Электронный ресурс] // http://lenta.ru/articles
3. Е. Железова, С. Измалков, К. Сонин, И. Хованская "Теория и практика двусторонних рынков"//"Вопросы экономики", № 1, 2013
4. "Задача об устойчивом паросочетании"[Электронный ресурс]// https://neerc.ifmo.ru/wiki/index.php?title=Задача_об_устойчивом_паросочетании
5. Тригер В.В "Жизнь и творчество Ллойда Шепли"
6. "Матчинг"[Электронный ресурс]// http://xity.narod.ru/game/
7. "Задача о марьяже"[Электронный ресур]// https://ru-wiki.ru/wiki/Задача_о_марьяже
8. "Стабильная проблема брака"[Электронный ресурс]// https://en.wikipedia.org/wiki/Stable_marriage_problem
9. "Как всем пережениться"[Электронный ресурс]// https://habr.com/ru/post/463391/
10. Н. Вирт. 3.6. "Задача о стабильных браках"// Алгоритмы и структуры данных
11. "Устойчивость супружеских пар и другие комбинаторные задачи"[Электронный ресурс]// http://kek.ksu.ru/eos/Lerner/KnuthRu.pdf
12. Peter Biro "Student Admissions in Hungary as Gale and Shapley Envisaged"