Диссертация (1137447), страница 14
Текст из файла (страница 14)
Во множестве трое лучших абитуриентов, назовем их , , ∈ , таковы, что ≻ , но (≻ ) , (≻ ) . Вэтом случае, если будет выбран 2 , то в графе будет толькоодна дуга, входящая в вершину, соответствующую вузу . Прилюбом другом способе устранения безразличий в графе будетдве дуги.2. Во множестве трое лучших абитуриентов 1 , 2 , 3 таковы, чтолибо 1 ≻ 3 , 2 ≻ 3 , либо 1 ≻ 2 , 1 ≻ 3 . В этом случае97примененный способ устранения безразличий в предпочтениях неповлияет на число дуг в графе .3.
Множество содержит менее трех элементов. В этом случаеспособ устранения безразличий также не влияет на число дуг вграфе .Таким образом, преобразование предпочтений, предложенное в теореме, даёт наименьшее ожидаемое число дуг, входящих в вершину вграфе . Соответственно, вероятность нахождения УУЦ в графе также минимальна.Теорема 2.3.1 фактически даёт нам описание механизма, обладающего следующим свойством: при условии, что предпочтения абитуриентов (вузов) выбираются случайно, причем любой линейный (простейший полу-) порядок равновероятен, вероятность получения неэффективного устойчивого паросочетания наименьшая среди всех возможных способов устранения безразличий в предпочтениях. Важноотметить, что этот механизм неманипулируем со стороны абитуриентов, т.к.
при устранении безразличий не используется информация опредпочтениях абитуриентов. С точки зрения абитуриента стратегические возможности аналогичны таковым в механизме отложенногопринятия с предлагающими абитуриентами при предпочтениях вузов,заданных линейными порядками.2.4Комплекс программДля реализации предложенных механизмов построения устойчивых паросочетаний был разработан комплекс программ. Комплекс про98грамм написан на языке C#, предназначен для запуска на ПК под операционной системой Windows, имеет оконный интерфейс. Программный комплекс позволяет:∙ генерировать профиль предпочтений игроков, где предпочтенияявляются произвольными полупорядками;∙ загружать сформированный пользователем профиль предпочтенийиз файлов;∙ строить линейные расширения отношений предпочтений со случайным устранением безразличий;∙ строить линейные расширения отношений предпочтения с обратным устранением безразличий, предложенным в разделе 2.3;∙ находить устойчивое паросочетание при предпочтениях, заданныхинтервальными порядками с использованием двух версий механизма отложенного принятия;∙ с помощью предложенного в разделе 2.2 критерия проверять,является ли построенное устойчивое паросочетание Паретоэффективным с точки зрения предлагающей стороны;∙ выполнять поиск устойчивого улучшающего цикла.Для задания отношений предпочтения каждого из игроков используется интервальная функция.
Предпочтения могут быть сгенерированы автоматически либо заданы вручную (загрузка осуществляется изфайлов). Функция генерации предпочтений может быть востребованапри проведении вычислительных экспериментов. Функция загрузкипредпочтений из файла позволяет использовать разработанный комплекс программ для поиска устойчивого паросочетания в реальных99ситуациях, например, при распределении студентов по элективнымкурсам.Программный комплекс включает в себя следующие модули:1. Модуль построения задачи. Данный модуль отвечает за заданиеначальных условий, а именно количества игроков с каждой изсторон рынка и их отношений предпочтения. В рамках данногомодуля реализована два способа задания предпочтений: случайнаягенерация и загрузка из файла.2.
Модуль устранения безразличий в предпочтениях. Данный модуль обеспечивает переход от отношений предпочтения, заданныхпроизвольными полупорядками, к их линейным расширениям, чтопозволяет в дальнейшем использовать для поиска устойчивого паросочетания механизм отложенного принятия. При этом реализованы два способа устранения безразличий: случайное устранениеи процедура обратного устранения безразличий, предложенна вразделе 2.3. настоящей работы.3.
Модуль построения устойчивого паросочетания. Данный модульобеспечивает поиск устойчивого паросочетания путем применениямеханизма отложенного принятия. На вход модуль принимает задачу с предпочтениями, заданными линейными порядками, поэтому для корректной работы необходима предварительная обработкапроизвольных отношений предпочтения в модуле 2. Механизм отложенного принятия может выполняться в двух вариантах, в интересах одной (приоритетной) группы игроков. Выбор осуществляется пользователем.1004. Модуль проверки эффективности.
Данный модуль позволяет проверить, является ли построенное паросочетание Паретоэффективным с точки зрения выбранной приоритетной группы игроков. Для проверки на Парето-эффективности используется критерий эффективности, предложенный в разделе 2.2. настоящей работы.5. Модуль проведения вычислительных экспериментов. Данный модуль позволяет запускать работу комплекса программ в режимевычислительного эксперимента, т.е. большого количества повторений на случайно сгенерированных профилях предпочтений.
В качестве результата работы данный модуль возвращает файл вформате текста с разделителями, содержащие результаты расчетов,характеризующих результаты эксперимента по каждому сгенерированному профилю предпочтений.Рисунок 2.1: Схема взаимодействия модулей программного комплексаПринципиальная схема взаимодействия модулей программного комплекса представлена на рис 2.1.101Работа модулей постановки задачи, устранения безразличий и проверки эффективности основана на полученных в работе теоретическихрезультатах. Исходный код отдельных модулей программного комплекса приведен в приложении Б.2.5Заключение по Главе 2.В данной главе:∙ показано, что при предпочтениях, заданных простейшими полупорядками или интервальными порядками, всегда существует устойчивое паросочетание;∙ показано, что любое паросочетание, которое является устойчивымпри предпочтениях, заданных простейшими полупорядками илиинтервальными порядками, остается устойчивым при некоторомлинейном расширении предпочтений;∙ показано, что устойчивое паросочетание неэффективно по Паретодля игроков одной из сторон (условно называемых абитуриентами), если и только если можно построить устойчивый улучшающий цикл;∙ предложен устойчивый и Парето-эффективный для абитуриентовмеханизм поиска паросочетания;∙ предложен устойчивый и неманипулируемый механизм, позволяющий минимизировать вероятность построения неэффективногопаросочетания в случае, когда предпочтения заданы простейшимиполупорядками.102∙ описан разработанный комплекс программ, реализующих предложенные механизмы103Глава 3Прикладные аспекты задачираспределения абитуриентов повузам3.1Граничные оценки и устойчивые паросочетанияВ данном разделе будет рассмотрено построение паросочетаний через широко распространённую в прикладных задачах распределенияабитуриентов схему: установление в каждом вузе граничной оценки,означающей, что все абитуриенты, получившие оценку не ниже данной, могут быть приняты в вуз.
Оказывается, что такая система в случае централизованного применения эквивалентна построению устойчивого паросочетания. Более того, рассмотрение обобщённых паросочетаний с точки зрения концепции граничных оценок позволяет исследовать принятую в некоторых странах концепцию «equal treatmentof equals». В основе этой концепции лежит идея о том, что абитуриенты, получившие одинаковые оценки на вступительных испытаниях,абсолютно идентичны с точки зрения вуза, и, следовательно, должныполучать одинаковый результат с точки зрения зачисления в этот вуз.104Есть два варианта возможного разрешения проблемы в духе этой концепции: либо все абитуриенты, оцененные одинаково, должны бытьприняты в вуз (будем в дальнейшем называть это L-концепцией, отlow-низкий, надо понижать граничную оценку), либо все эти абитуриенты не зачислены в вуз (H-концепция, от high-высокий, надо повышать граничную оценку).
Таким образом, эти концепции исключаютвозможность случайного устранения безразличий в предпочтениях.При этом в случае L-концепции дополнительно появляется возможность зачисления абитуриентов сверх квоты, если это требуется длясоблюдения равенства между абитуриентами.Перейдем к формальной модели. Пусть = {1 , 2 , . . . , } - множество абитуриентов, = {1 , 2 , . . . , } - множество вузов, причёмчерез обозначим квоту (число мест) в вузе . У каждого абитуриента имеется лист предпочтений относительно вузов , в котором1 2 означает, что 1 стоит выше, чем 2 в списке, т.е. абитуриент предпочитает 1 по сравнению с 2 .
Пусть - итоговая оценка, полученная абитуриентом по итогам вступительных испытаний в вуз . Итоговые оценки являются положительными целыми числами длявсех приемлемых для вуза абитуриентов. В реальной практике абитуриенты с оценками ниже некоторой установленной отметки просто немогут претендовать на места в вузе. Например, в Венгрии установленаединая граница в 240 баллов из 500 возможных; абитуриент, набравший меньше указанного количества баллов не может претендовать напоступление в вуз. В нашей модели в качестве нижней границы безограничения общности рассматривается оценка 0.105Набор граничных оценок вузов описывается отображением : →N. В рамках централизованной системы зачисления абитуриент зачисляется в вуз , если он получил оценку не ниже граничной вданном вузе, и этот вуз является лучшим среди тех, куда проходитэтот абитуриент, т.е. ≥ ( ), и < ( ) для каждого вуза такого что .Если при данном наборе граничных оценок абитуриент зачисленв вуз , тогда значение соответствующей булевой переменной устанавливается как () = 1, в противном случае ее значение равно 0.∑︀Пусть () = () - количество абитуриентов, зачисленных в при наборе граничных оценок .Далее, определим , следующим образом: , ( ) = ( ) + и, ( ) = ( ) для любого ̸= .
Таким образом построим новыйнабор граничных оценок, в которм увеличим граничную оценку в вузе на (или уменьшим, если отрицательно), оставив граничныеоценки прочих вузов неизменными.Для того, чтобы ввести новые понятия H-устойчивых and Lустойчивых наборов граничных оценок, сначала введем соответствующие определения допустимости.Набор граничных оценок является H-допустимым, если () ≤ для каждого вуза ∈ . То есть, количество зачисленных абитуриентов не может превышать квоту ни в одном вузе. Это означает, чтоесли имеется группа абитуриентов, получивших одинаковые оценки, аоставшихся мест не хватает на всех абитуриентов из этой группы, тони один абитуриент из группы не получит места в вузе, и граничнаяоценка вуза должна быть выше, чем оценка этих абитуриентов.106Набор граничных оценок является L-допустимым, если для каждого вуза ∈ , такого что () ≥ , выполняется (,1 ) < .
Вэтом случае квота в вузе может быть превышена, но только за счётзачисления «последней» группы абитуриентов с одинаковыми оценками.Будем говорить, что набор граничных оценок является Hустойчивым (соответственно, L-устойчивым), если является Hдопустимым (L-допустимым), и для каждого вуза либо ( ) = 0, либо ,−1 не является H-допустимым (соответственно, L-допустимым).Таким образом, H-устойчивость означает, что ни один вуз не можетснизить граничные оценки так, чтобы количество зачисленных абитуриентов не превысило бы квоту (при условии, что остальные вузы оставляют граничные оценки на прежнем уровне). L-устойчивостьозначает, что ни один вуз не может зачислить абитуриента, если какминимум зачисленных абитуриентов имеют более высокую оценкув данном вузе, но, при прочих равных, граничные оценки должныбыть как можно более низкими.
H-устойчивость используется в централизованной системе зачисления абитуриентов в Венгрии.Следует обратить внимание на тот факт, что в случае отсутствиянеразличимых абитуриентов (т.е. в случае, когда ни в одном вузе нетабитуриентов, получивших одинаковые оценки) эти концепции совпадают и, вообще говоря, эквивалентны классической концепции попарной устойчивости паросочетания, предложенной Д.
Гейлом и Л.Шепли. Наличие соответствия между набором граничных оценок ипаросочетаниями было впервые отмечено в [45] в связи с анализомсистемы распределения абитуриентов по вузам в Турции. В [62] этот107факт также использовали при анализе моделей обобщённых паросочетаний с континуумом абитуриентов.3.1.1Механизмы построения устойчивого набора граничных оценокМеханизмы поиска как H-устойчивых, так и L-устойчивых наборов граничных оценок являются естественным расширением механизма отложенного принятия Гейла-Шепли. Единственное существенноеотличие состоит в том, что вузы не имеют возможности набрать в точности столько абитуриентов, сколько в вузе имеется свободных мест.В данном разделе будут построены два типа механизмов: строящиенабор граничных оценок, наилучший для вузов, и строящие наборграничных оценок, наилучший для абитуриентов. Чтобы исключитьповторное описание одинаковых операций, механизмы построения Hустойчивого и L-устойчивого наборов будут описаны в одном тексте,с указанием особенностей L-устойчивого механизма в скобках.Механизмы, ориентированные на вузыНа первом шаге механизма назначим граничную оценку в каждомвузе независимо от других вузов следующим образом: выберем наименьшее число, такое что, если рассматривать всех абитуриентов из, число абитуриентов, имеющих оценку не ниже установленного, непревысит квоту вуза.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
