Диссертация (1137447), страница 20
Текст из файла (страница 20)
Для абитуриента из лучшей категории 10 набор будет включать вуз своей категории и четыре вуза141категории 11 . Для абитуриента из категории 9 набор будет включать один вуз своей категории, один вуз категории 10 и три вузакатегории 11 . Для абитуриента из группы 1 наилучшим будет выбор, не включающий гарантированный вуз: один вуз из 2 , два вузаиз 3 и два вуза из 4 .Подача заявлений Какой же набор заявлений получит каждый вуз?Во-первых, число заявлений от абитуриентов собственной категорииравно числу абитуриентов, считающих вуз лучшим .
Поскольку число абитуриентов, считающих данный вуз лучшим в своей категории,одинаково для любого вуза, то общее число таких заявлений будет∀, : = > 1, =2220= 1.1. Вузы категории 1 в нашей моде-ли не получают ни одного заявления. Значения остальных можнолегко вычислить исходя из описанного выше поведения студентов.Матрица R будет выглядеть следующим образом:⎛⎜ 4.4⎜⎜ 1.1⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ =⎜ 0⎜⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎝03.32.20000001.12.22.2000001.102.22.2000001.102.22.2000001.102.22.2000001.102.22.2000001.102.22.2000001.102.20000001.1000000001.1000000000⎞⎟⎟⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟2.2 ⎟⎟⎟2.2 ⎟⎟⎟1.1 ⎟⎟⎠00(3.5)Вузы первых двух категорий получат наибольшее число заявлений.Диаграмма дает представление о том, как меняется число принятыхзаявлений в зависимости от категории вуза:Первая волна зачислений.
Поскольку вуз не различает абитуриентов одной категории, он рекомендует к зачислению всех абитуриентов142Рисунок 3.1: Число заявлений в расчете на вуз при равномерномраспределении студентовлучшей категории, а если остаются места, то целиком всех подавших заявления из следующей категории.
Соответственно, матрица S,характеризующая число рекомендованных к зачислению, будет выглядеть следующим образом:⎛1⎜ 4.4⎜⎜ 1.1⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜=⎜ 0⎜⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎝000000000000000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.100000000⎞0 ⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎠0(3.6)Теперь абитуриенты, увидев списки, принимают решение о том, куданести подлинник аттестата. На данном этапе каждый, кроме абитуриентов сильной категории, попал в ровно один вуз и отнесет свойподлинник именно туда.
Больше всех пострадают вузы категории 10 ,т.к. зачисленные ими абитуриенты в полном составе разбредутся по143более сильным вузам категории 11 . Надо сказать, что большого превышения числа мест в вузах категории 11 не будет, т.к. число заявлений не соответствует реальному спросу на места - все сильныеабитуриенты подавали заявления сразу в четыре сильных вуза.Матрица зачислений после первой волны будет выглядеть следующимобразом.⎛1⎜ 1.1⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜=⎜ 0⎜⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎝000000000000000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.100000000⎞0 ⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎠0(3.7)Вторая волна зачислений.
Вузы, у которых места оказались незанятыми (а это вузы из категории 10 ) публикуют новые списки рекомендованных к зачислению. Они предлагают поступить более слабымабитуриентам из группы 9 , которые также подавали заявления (см.матрицу ).⎛2⎜ 1.1⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜=⎜ 0⎜⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎝0000000001.100000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.100000000⎞0 ⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎠0(3.8)Абитуриенты группы 9 в соответствии с законом имеют возможность забрать свои документы из вузов 9 и отнести их в более же144лательные для них вузы 10 .
В итоге после второй волны матрицазачислений будет выглядеть следующим образом.⎛2⎜ 1.1⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜=⎜ 0⎜⎜⎜ 0⎜⎜⎜⎜ 0⎜⎜⎜ 0⎜⎜⎜ 0⎜⎝0000000001.100000000000000001.1000000001.1000000001.1000000001.1000000001.1000000001.1000000001.100000000⎞0 ⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎟0 ⎟⎟⎠0(3.9)Таким образом, вузы категории 8 , если они будут вести себя в соответствии с установленными правилами и отдадут документы абитуриентам после первой волны, останутся без студентов. На иллюстрации представлено распределение числа зачисленных студентов послеокончания работы механизма.
Высота столбца соответствует среднемучислу абитуриентов в вузе соответствующей категории.Рисунок 3.2: Среднее число зачисленных по категориям вузовНеполная информация о категориях студентовРассмотрим следующий пример.145∙ = 10, то есть 10 категорий абитуриентов и 11 категорий вузов, однако вузы могут более чётко оценить уровень подготовкиабитуриента, чем сами абитуриенты. Поэтому с точки зрения вузакаждая из категорий абитуриентов разделяется на три разноуровневые группы,∙ = 20, число вузов в категории,∙ Абитуриенты распределены по категориям равномерноДля данного примера не приводится динамику процесса зачисления,а лишь иллюстрация результата зачисления. В данном случае оказывается, что недоберут абитуриентов самые сильные вузы.
Если числоабитуриентов совпадает с числом мест, то результатом приемной кампании будет распределение, приведенное на Рисунке 3.3 . Если числоабитуриентов (в целом) окажется меньше числа мест (расчет произведен для 0, 75 ), то результатом приемной кампании будет распределение, приведенное на Рисунке 3.4. Здесь разными штриховками представлены абитуриенты из групп разного уровня подготовки (для упрощения иллюстрации абитуриенты из подгрупп внутри одной группывыделены одним типом штриховки). Отметим, что в такой ситуациираспределение не будет справедливым, и в полученном паросочетании будут существовать блокирующие пары, например, абитуриентыуровня 6 зачислены в вузы группы 8, в то время как некоторые абитуриенты уровня 7 (более сильные, чем уровень 6) попали в вузы болееслабой группы 7.146Рисунок 3.3: Среднее число зачисленных по категориям вузов,неполная информацияРисунок 3.4: Среднее число зачисленных по категориям вузов,неполная инфрормация, избыток мест1473.3Заключение по Главе 3.В настоящей главе были рассмотрены прикладные аспекты задачи распределения абитуриентов по вузам: исследована модель обобщенных паросочетаний в случае, когда предпочтения основаны на полученных абитуриентами оценках, и вузы придерживаются политики«equal treatments of equals», т.е.
одинакового рассмотрения абитуриентов с одинаковыми оценками также проанализирован механизм проведения приемной кампании в вузы России.В разделе 3.1. для модели равного рассмотрения абитуриентов были проанализированы две концепции: H-допустимость, при которойквоты не могут быть превышены; и L-допустимость, при которойквоты могут быть превышены, если это необходимо для приема последней группы абитуриентов, имеющих одинаковые оценки.
Для обеих концепций доказано существование устойчивого паросочетания иданы характеристики структуры множества устойчивых паросочетаний. Полученные структурные результаты также могут использоваться для оценки нижнего и верхнего уровней граничных оценок в задачах со случайным устранением безразличий.
Продемонстрировано,что при наличии хотя бы двух абитуриентов с одинаковыми оценкамив обеих рассмотренных концепциях равного рассмотрения абитуриенториентированный механизм отложенного принятия может быть уязвимк манипулированию предпочтениями со стороны абитуриентов.В разделе 3.2 исследован механизм организации приемной кампании в России; показаны особенности и «узкие места» используемойпсевдо-централизованной схемы.
При использовании существующейсхемы наиболее «уязвимыми» оказываются вузы с качеством подго148товки выше среднего: при соблюдении правил набора эти вузы могутсущественно недобирать абитуриентов до контрольных цифр приема,в то время как более слабые вузы будут заполнять все отведенныеместа. Продемонстрировано, что порождаемое используемым псевдоцентрализованным механизмом обобщенное паросочетание не является устойчивым.149ЗаключениеОсновные результаты работы заключаются в следующем.1.
Впервые на русском языке подготовлен аналитический обзор классических результатов в области теории обобщенных паросочетаний при предпочтениях, заданных линейными порядками, а такжеисследований используемых на практике централизованных механизмов распределения.2. Впервые рассмотрена модель обобщенных паросочетаний «один комногим» при предпочтениях в виде интервальных порядков. Доказано существование и возможность построения эффективногоустойчивого обобщенного паросочетания в этой модели. Сформулирован критерий Парето-эффективности устойчивого паросочетания и, соответственно, Парето-эффективный устойчивый механизм построения паросочетания.3.
Впервые построен неманипулируемый устойчивый механизм, прииспользовании которого в задаче с предпочтениями в виде простейших полупорядков вероятность построения неэффективногообобщенного паросочетания минимальна.4. Исследована модель обобщенных паросочетаний в случае, когдапредпочтения основаны на полученных абитуриентами оценках, и150вузы придерживаются политики одинакового рассмотрения абитуриентов с одинаковыми оценками. Показано существование устойчивого паросочетания, дана характеристика структуры множестваустойчивых паросочетаний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
