Тема: Ситуации равновесия в задачах о назначениях

В данной работе будут рассматриваться различные модели приема абитуриентов в вузы. Начиная с 2009 года, система приема абитури­ентов в вузы в Российской Федерации изменилась: абитуриенты стали поступать в вузы по результатам ЕГЭ, при этом каждый абитуриент имеет право подать документы в несколько вузов, причем прием осу­ществляется в несколько волн: например, в 2011 поступление произво­дилось в три волны, но с 2012 поступление в большинство вузов стало происходить в две волны. Однако до сих пор в ряде вузов существует приемные кампании в одну волну, например, поступление в магистра­туру в СПбГУ [15].
Существуют и другие модели распределения абитуриентов по ву­зам. Например, в советские времена при обязательном распределении выпускников по организациям, подавшим свои заявки, использовался следующий алгоритм [3]: все выпускники ранжировались по среднему баллу зачетной книжки и, в порядке убывания среднего балла, выби­рали по очереди наиболее предпочтительную организацию среди тех, в которых еще остались свободные места (считалось, что каждый выпуск­ник имеет свое линейное упорядочение на множестве всех организаций). В действительности, этот алгоритм являлся модернизированным алго­ритмом Гейла-Шепли в задаче о назначении [9], который можно при­менять для задачи распределения абитуриентов по вузам.
В 1962 году Дэвид Гейл и Ллойд Шепли предложили алгоритм рас­пределения мужчин и женщин на брачные пары [10]. Этот алгоритм всегда давал устойчивое распределение в том смысле, что не находи­лось никакой пары, которая, разорвав свои союзы, образовывала бы но­вую пару, в которой оба партнера были более счастливыми. Алгоритм нахождения устойчивых паросочетаний, помимо задачи распределения выпускников по организациям, применяется в задаче выбора соседей по комнате, распределении донорских органов по реципиентам и в других задачах. В дальнейшем за решение таких задач о назначениях Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике 2012 года [1, 6].
Модернизированный алгоритм Гейла-Шепли можно также приме­нять для случая, когда выпускники соответствуют абитуриентам, а ор­ганизации — вузам [12, 13]. Поскольку истинное качество абитуриентов неизвестно, то вуз имеет предпочтение только в соответствии с форми­руемым вузом рейтингом, который получается благодаря результатам ЕГЭ и вступительным экзаменам, если они есть. Таким образом, вуз заинтересован в абитуриентах, находящихся как можно выше в рей­тинге. При выполнении алгоритма Гейла-Шепли образуются устойчи­вые пары [10]: если поступивший в некоторый вуз абитуриент мечтал о другом вузе больше, чем о том, в который поступил, то другой вуз предпочтет абитуриента, находящегося выше в рейтинге, и наоборот, если среди непоступивших в некоторый вуз есть абитуриенты, нахо­дящиеся выше в общем рейтинге, чем последний поступивший в этот вуз, то они предпочитают другой вуз, а этого вуза нет списке прием­лемых для рассматриваемых абитуриентов. Кроме того, эта процедура устойчива относительно манипулирования (никто не получает выгоды от искажения своих истинных предпочтений [2, 11]). К сожалению, в России данная процедура поступления не используется ввиду ее слож­ности и недостатка матобеспечения.
Для остальных описанных правил возможны варианты неустойчи­вости результатов приема [2, 11, 7, 8]: могут быть ситуации, когда место в более приоритетном для некоторого абитуриента вузе может быть занято другим абитуриентом, находящимся в рейтинге ниже, то есть не будет соблюдаться условие истинной устойчивости, но эти правила приема абитуриентов в вузы применяются в Российской Федерации, а алгоритм Гейла-Шепли — нет.
Цель работы состоит в исследовании различных правил распреде­ления абитуриентов по вузам, а также в разработке квазиоптимальных стратегий поведения абитуриентов. В данной работе эталонным счита­ется распределение по модернизированному алгоритму Гейла-Шепли, и сравнение результатов работы других алгоритмов будет производиться с ним.
Предлагается оценивать результаты рассматриваемых алгоритмов по количеству неустойчивых пар вида университет-абитуриент (то есть сравнение с результатами алгоритма Гейла-Шепли путем пересчета от­личающихся пар), а также по номеру последних поступивших абитури­ентов в каждый вуз или по среднеарифметическому количеству запол­ненных мест в каждом вузе (в зависимости от начальных данных мо­дели). Для сравнения производится имитационное моделирование всех этих алгоритмов, начиная с построения предпочтений абитуриентов на множестве вузов, затем происходит применение каждого алгоритма к текущему построению, в конце — сравнение с алгоритмом Гейла-Шепли и получение статистических данных для различных начальных условий модели.
Купить

В данной работе были рассмотрены различные алгоритмы распре­деления абитуриентов по вузам, а также проведено сравнение с эталон­ным — алгоритмом Гэйла-Шепли. Разработан новый алгоритм поведе­ния абитуриентов, который дает приемлемые результаты при некото­рых параметрах.
Исходя из полученных результатов, сделаны следующие выводы:
1. При моделировании различных вариантов приемной кампании (ко­личество квот, абитуриентов) наиболее близким по результатам к алгоритму Гейла-Шепли во всех случаях является алгоритм по­ступления по правилу математического ожидания с А = S — 1.
2. Нельзя определенно сказать, какое количество волн является наи­более оптимальным. Чем больше волн, тем среднеарифметиче­ский номер последнего поступившего абитуриента меньше, одна­ко количество неустойчивых пар меньше при поступлении в одну волну. Поступление в три волны не дает значительного преиму­щества по сравнению с поступлением в одну и две волны, поэтому отказ от приема в три волны в РФ можно считать правильным, ввиду сложности и необходимости дополнительных расходов на проведение дополнительной волны.
3. Стратегии абитуриентов с небольшой степенью степенью риска (А = (S-1)/2, А = (v-1)/v) ведут к неприемлемому результату как для абитуриентов (поступление в вузы, которые не являются наиболее приоритетными, а поступление по принципу хотя бы куда-нибудь из множества приемлемых вузов), так и для вузов (высокое сред­неарифметическое места последнего поступившего абитуриента по сравнению с алгоритмом Гейла-Шепли, как следствие — сильно различающийся уровень абитуриентов).
4. Однако и стратегии с высокой степенью риска (поступление в од­ну волну с одним приоритетом) неприемлемы. Данный алгоритм является частным случаем модифицированного алгоритма Гейла- Шепли, где абитуриенты хотят поступить только в один вуз. Оба алгоритма моделировались на одинаковых данных, однако полу­ченные результаты у алгоритма Гейла-Шепли существенно лучше.
Купить