На семинаре GAMES обсудили, как расселить студентов в общежитии
Cтудент 4 курса образовательной программы «Экономика» Гайдаш Александр выступил с докладом «Задача о размещении студентов в общежитии». Как определить оптимальное распределение студентов по комнатам? В чем специфика данной области исследования? На эти вопросы искали ответы участники семинара Сектора эмпирического анализа рынков и компаний (GAMES).
Задача о размещении студентов в общежитии является примером проблемы, которую можно рассматривать совершенно разными сферами знания. В работе Александра на 3 курсе задача о размещении студентов в общем виде рассматривалась как задача о назначениях, в которой при помощи математических методов линейного программирования находилось оптимальное распределение студентов по комнатам путем максимизации общей функции полезности.
Рассматриваемая модель представляла научный интерес, поскольку, в отличие от классических работ на данную тему, студенты не только образуют пару и получают полезность от соседа, но и от комнаты при заселении. Моделирование происходило следующим образом:
- Поиск оптимального распределения через решение задачи о назначениях
- Система усложняется формированием пар между студентами
- Добавляются дополнительные параметры, влияющие на полезность: в частности, учитывается разница между курсами обучения соседей-студентов
- На последнем этапе, когда решение найдено, в общем виде рассматривается одна комната и поведение студентов с точки зрения теории игр.
В дипломной работе в этом году Александр планирует продолжить исследование, но с упором на теорию кооперативных игр, алгоритмы и комбинаторику. При таком рассмотрении задача будет представлять собой классическую «задачу о соседях по комнате», алгоритм поиска решений в которой был предложен Робертом Ирвингом в 1985 году. Алгоритм позволяет найти устойчивое решение (если оно существует) при заданных предпочтениях.
На семинаре обсудили дальнейшие перспективы данного исследования. Главной целью исследования станет поиск не только устойчивого, но и оптимального решения путем написания обновленного алгоритма, базирующегося на методах, предложенных Р. Ирвингом. Под оптимальностью понимается введение дополнительного условия о максимизации функции общего уровня полезности. В связи с этим, возникает вопрос о том, какие факторы оказывают влияние на полезность студентов помимо соседа.
Желаем Александру новых достижений в данном направлении исследования!
Ждем всех желающих на следующем семинаре GAMES!