Введение 5
1. Описание системы ЕГЭ 8
1.1. Постановка задачи 8
1.2. Текущие правила поступления по ЕГЭ 8
1.3. Реальные проявления несовершенств системы поступления на примере приемной кампании в СПбГУ 11
2. Алгоритмы 15
2.1. Трактовка текущих правил поступления по ЕГЭ для сравнения работы различных алгоритмов поступления в вузы 15
2.1.1. Алгоритм распределения абитуриентов по вузам по текущим правилам поступления с помощью математического ожидания в одну волну 15
2.1.2. Алгоритм поступления в две волны по правилу математического ожидания 18
2.1.3. Алгоритм поступления в три волны по правилу математического ожидания 20
2.1.4. Принцип выбора kj (qj) 20
2.2. Другие алгоритмы поступления абитуриентов в вузы 23
2.2.1. Алгоритм Гейла-Шепли 23
2.2.2. Алгоритм поступления в одну волну с одним приоритетом 25
3. Исследование результатов 26
3.1. Результаты при одинаковых квотах у вузов 26
3.1.1. Абитуриентов в два раза больше, чем суммарная квота во всех вузах 26
3.1.2. Абитуриентов столько же, сколько суммарная квота во всех вузах 28
3.2. Результаты при разных квотах у вузов 30
3.2.1. Абитуриентов в два раза больше, чем суммарная квота во всех вузах 30
3.2.2. Абитуриентов столько же, сколько суммарная квота во всех вузах 32
Заключение 35
Список литературы 37
Приложение 39
В данной работе будут рассматриваться различные модели приема абитуриентов в вузы. Начиная с 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. Однако и стратегии с высокой степенью риска (поступление в одну волну с одним приоритетом) неприемлемы. Данный алгоритм является частным случаем модифицированного алгоритма Гейла- Шепли, где абитуриенты хотят поступить только в один вуз. Оба алгоритма моделировались на одинаковых данных, однако полученные результаты у алгоритма Гейла-Шепли существенно лучше.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
