КАБИНЕТМИНИСТРОВ УКРАИНЫ
ЮЖНЫЙФИЛИАЛ
НАЦИОНАЛЬНОГОУНИВЕРСИТЕТА БИОРЕСУРСОВ и ПРИРОДОПОЛЬЗОВАНИЯ УКРАИНЫ
«КРЫМСКИЙАГРОТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультетэкономический
Кафедраприкладной математики и экономической кибернетики
КУРСОВАЯРАБОТА
подисциплине моделирование экономики
натему: МОДЕЛЬЭКСПЕРТНОЙ ОЦЕНКИ
Выполнила:
Студентка4 курса группы ЭК-43
АнтипкинаТ. Н.
Проверил:доцент кафедры прикладной математики и экономической кибернетики
СтепановА. В.
Cимферополь,2010
СОДЕРЖАНИЕ
Введение
1. Содержательнаяпостановка задачи
2. Формальнаяпостановка задачи
3. Математическиеметоды решения
4. Описаниеалгоритма
4.1 Определениепобедителя Борда
4.2 Нахождениеоценки Копленда
4.3 Алгоритмопределения победителя за правилами Борда или Копленда
5. Описаниепрограммы
5.1 Выбортехнологии программирования
5.2 Структурапрограммы
5.3 Инструкцияпользователю
6. Контрольныйпример
Выводы
Список литературы
Дополнения
Введение
«Демократиякак метод управления использует результаты общественных решений граждан навыборах и решений законодателей в представительских органах»
(Рикер [1982])
Большинствообщественных распределенных решений (таких, как налоги и общественные расходы)принимаются на основе голосования. Выборы также используются для пополнениямногих общественных заведений. Здесь мы имеем важные примеры чистыхобщественных продуктов (например, все граждане данного города без каких-либоисключений принимают участие в «потреблении» своего мэра), которыевыбираются на основе голосования и без побочных платежей.
Начинаяс политической философии Просветительского, выбор правил голосования былглавной этической проблемой, повъъязаной с дополнениями, которые далеко идут,для функционирования большинства политических институтов. Дебаты осправедливости разнообразных методов голосования начались с исследований гдеБорда [1781] и Кондорсе [1785]. В 1952 году Ерроу предложил формальную модель,что в течение трех десятилетий анализировалась в многочисленных работахматематической ориентации по так называемом коллективном выборе.
Формальноправило голосование решает задачу коллективного принятия решения, у которойнесколько индивидуальных агентов (избирателей) должны совместно выбрать один изнескольких результатов (также называемых кандидатами), относительно которых ихмысли расходятся. Будем допускать, что конечное множественное число Nизбирателей должно избрать одного кандидата из конечного множественного числаА. Для простоту допустим, что индивидуальные мысли (или преимущества) недопускают случаи безразличия. Каждое такое преимущество является произвольнымлинейным порядком на А.
Правилоголосование выбирает кандидата на основе поставленных в известность порядковыхпреимуществ и только на основе этих преимуществ. В этом существенное отличие отмоделей, в которых деньги и другие продукты позволяли осуществлять произвольномалые компенсации для агентов. Голосование не допускает уступки между двумякандидатами иначе, чем за счет возможного избрания третьего кандидата.
Есликандидатов только два, то обычное правило голосования большинством голосовбесспорно является наиболее справедливым методом. Этот принцип большинства — исходный пункт процесса демократического принятия решений. Он был ясносформулирован два столетия потому, а его основа является намного древнее.Аксиоматическая формализация принципа большинства предложена Мэем.
Рассмотрениюметодов голосования и воплощению в программу одного из них и посвященная данакурсовая работа. Будет проведена сравнительная характеристика разных методовголосования, и с помощью контрольного примера продемонстрированная робота одногоиз них.
1. Содержательная постановка задачи
Задание,которое относится передо мной в данной курсовой работе, – обеспечить процессвыборов, то есть конечное множественное число N избирателей должно избратьодного кандидата из конечного множественного числа А. Обязательным условиеместь избрание единственного кандидата. Для простоты допустим, чтоиндивидуальные мысли (или преимущества) не допускают случаи безразличия. Каждаятакое преимущество есть произвольным линейным порядом на А (то есть полное транзитивноеи асимметричное бинарное отношение). Это предположение не приводит ксущественным потерям всеобщности.
Формальноправило голосование решает задачу коллективного принятия решения, у которойнесколько индивидуальных агентов (избирателей) должны совместно выбрать один изнескольких результатов (также званых кандидатами), относительно которых ихмысли расходятся.
Правилоголосования являет собой систематическое решение, которое во всей полнотеопирается по индивидуальным мнениям. Обозначим через L(А) множественное числолинейных порядков на А, тогда правило голосование является отображением L(А) Nв А. То, что правило голосования может быть определено для любой мыслимойконфигурации преимуществ, выражает фундаментальный принцип свободы мыслей:каждый избиратель имеет право ранжировать кандидатов любым образом. Однако внекоторых моделях голосования, которые содержат экономические переменные илинеопределенные результаты, можно допускать, что преимущества избирателейудовлетворяют некоторому общему условию. Это особенно удобно при стратегическоманализе голосования и при агрегации преимуществ.
Правилоголосования выбирает кандидата на основе поставленных в известность порядковыхпреимуществ и только на основе этих преимуществ. В этом существенное отличие отмоделей, в которых деньги и другие продукты позволяли осуществлять произвольномалые компенсации для агентов. Голосование не допускает уступку между двумякандидатами иначе, чем за счет возможного избрания третьего кандидата.
Пустьдано как контрольный пример следующий профиль для 9 избирателей и 5-тикандидатов:1 4 1 3
a
b
c
d
e
c
d
b
e
a
e
a
d
b
c
e
a
b
d
c
Вкаждом столбце кандидаты расположенные в порядке уменьшения их значимости длякаждой группы избирателей. То есть, для первого столбца (группы избирателей,которая состоит из одного человека) можно определить преимущества следующимобразом: группа избирателей, которая состоит из одного лица, считает кандидатаа наилучшим. На втором месте они ставят кандидата b, на третьем месте c и такдалее аналогично кандидаты ранжированы в каждой группе.
Задание:определить единственного победителя выборов.
Существуютмного способов определения победителя. Они будут описаны и соответствующимобразом сравнены в следующих разделах.
Отметимсейчас, что дана курсовая работа посвященная рассмотрению и воплощению впрограмму метода Копленда и сравнению полученного результата с результатом заметодом Борда.
Определимправило Копленда.
Сравнимкандидата а с любым другим кандидатом x. Начислим ему +1,если для большинства а лучше за x, -1, если для большинства xлучше за а, и x, x?a,получаемоценку Копленда для а. Избираем кандидат, названный победителем заКоплендом, с наивысшей такой оценкой.
Вданном правиле не указано, что делать в том случае, когда найдутся два илибольше кандидаты с одинаковой оценкой Копленда. Допустимо, что изберется тоткандидат, имя и фамилия которого стоит ближайшее по списку. Это предположениенарушает правило нейтральности, но, как будет доказано в следующих разделах,каждое правило голосования Копленда является наиболее наглядным и легким длякомпьютерной реализации.
ПравилоБорда: каждый избиратель сообщает свои преимущества,ранжируя p кандидатов от наилучшего к наихудшему (безразличие запрещается).Кандидат не получает очки за последнее место, получает одно очко запредпоследнее место и так далее, получает p-1 очков за первое место. Побеждаеткандидат с наибольшей суммой очков. Он называется победителем по Борду. Здесьтак же не указывается, что делать при равенстве очков, то есть также можетнарушаться условие нейтральности.
Охарактеризуемвыше поставленную задачу.
Еекритерием качества является максимизация оценки Копленда (Борда).
Ограничениямивыступают преимущества избирателей и их ранжирования кандидатов. Как будетуказано дальше, фактически нужно налагать также ограничение и на количествоизбирателей и количество кандидатов. Однако это ограничение не являетсясущественным, так как всегда при голосовании можно провести деление на округа.
Зауровнем сложности это есть задача Р-типа. Время решения данной задачисоставляет t0=a0+a1x+… +anxnі зависитот количества групп избирателей и количества кандидатов.
Нахожденияпобедителя по правилам Копленда и Борда являются самыми простыми за своейструктурой, оптимальные по Парето, анонимные, нейтральные (если не указывать,что делать при равенстве очков). Кроме того, правило Борда также удовлетворяетаксиоме участия и пополнения (они будут рассмотрены в следующем разделе).
Оптимальностьпо Парето:
Есликандидат а для всех лучший от кандидата b, то b не может быть избран.
Анонимность:
Именаизбирателей не имеют значения – если два избирателя поменяются голосами, торезультат выборов не изменится.
Нейтральность:
Именакандидатов не имеют значения. Если мы поменяем местами кандидатов а и b впреимуществе каждого избирателя, то результат голосования изменитсясоответственно (если раньше выбирался а, то теперь будет выбираться b инаоборот; если выбирался некоторый х, отличающийся от но и b, то он же и будетизбран).
Монотонность:
Допустимо,что а выбирается (среди победителей) при данном профиле и профиль изменяетсятолько так, что положение а улучшается, а относительное сравнение пары любыхдругих кандидатов для любого избирателя остается неизменным. Тогда а как ираньше будет избран (опять среди победителей) для нового профиля.
2. Формальная постановка задачи
Приведемеще раз задачу данной курсовой работы: используя профиль преимуществизбирателей, определить единственного победителя из множественного числазаданных. Должна существовать возможность проверки корректности заданияпрофиля. Ограничениями на задачу является отсутствие безразличия и ранжировкикандидатов в строгом порядке. Опишем методы голосования, которые могутиспользоваться для решения данной задачи и наведем ряд основных определений итеорем.
Правилоотносительного большинства. Каждый избиратель отдает своиголос наилучшему для себя кандидату. Избирается кандидат, упомянутый внаибольшем количестве бюллетеней. Это правило может противоречить мнению большинства(см. 1, пример 9.1).
Определение2.1. Правило Борда. Каждый избиратель сообщает своипреимущества, ранжируя р кандидатов от лучшего к хуже (безразличиезапрещается). Кандидат не получает очков за последнее место, получает одно очкоза предпоследнее и так далее, получает р-1 очков за первое место. Побеждаеткандидат с наибольшей суммой очков. Он называется победителем по Борду.
Мыне уточняем, что делать при равенстве очков.
Определение2.2.Для заданного профиля преимуществ победителем по Кондорсу называется кандидата, что побеждает любого другого кандидата при парном сравнении по правилубольшинства:
длявсякого b?аизбирателей,которые считают а лучшим за b, больше, чем тех, кто считает, что b лучшим за а.
Зажиточноепо Кондорсу правило выбирает победителя по Кондорсу, если такой существует.
Отсутствиепобедителя по Кондорсу является знаменитым «парадоксом голосования».Как часто может наблюдаться парадокс голосования? В общем случае вероятность p(p,n)того, что победителя по Кондорсу не существует при р кандидатах и nизбирателях, растет по р и растет по числу избирателей от n к n+2.Это может быть проверено на основе вычисления p(п,р)длямалых значений n и р, но в общем случае это утверждение остаетсянедоказанным предположением.
Парадоксголосования становится почти достоверным событием, когда число кандидатовстановится достаточно большим при фиксированном n. Если числоизбирателей становится достаточно большим при фиксированном р, топредельная вероятность p(p) можетбыть оценена по Фишберну [1984]:
/>
котораясправедлива с точностью до половины процента при р?50.
Определение2.3. Правила голосования с подсчетом очков.
Фиксируемпоследовательность вещественных чисел, которая не спадает
s0?s1?…?sp-1приs0
Избирателиранжируют кандидатов, причем s0очков дается за последнееместо, s1 — за предпоследнее и так далее. Избирается кандидатс максимальной суммой очков.
Определение2.4. Правило Копленда. Сравним кандидата а с любымдругим кандидатом х. Начислим ему +1, если для большинства алучше за х, -1, если для большинства х лучше за а, и 0 приравенстве. Суммируя общее количество очков по всем х,х?а,получаемоценку Копленда для а. Избирается кандидат, названный победителем заКоплендом, с наивысшей из таких оценок.
Определение2.5.Правило Симпсона. Рассмотрим кандидата а, любого другого кандидата х иобозначим через N(а,x) число избирателей, для которых а лучше за х. ОценкойСимпсона для а называется минимальное из чисел N(а,x) по всем х,х?а.Избирается кандидат, названный победителем по Симпсону, с наивысшей такой оценкой.Оба этих правила зажиточные по Кондорсу.
Оптимальностьпо Парето. Если кандидат а для всех лучший откандидата b, то b не может быть избранным.
Анонимность.Имена избирателей не имеют значения: если два избирателя поменяются голосами,то результат выборов не изменится.
Нейтральность.Имена кандидатов не имеют значения. Если мы поменяем местами кандидатов аи b в преимуществе каждого избирателя, то результат голосованияизменится соответственно (если раньше выбирался а, то теперь будет выбираться bи наоборот; если выбирался некоторый х, отличающийся от а и b, то он же и будетвыбран).
ПравилаКопленда и Симпсона оптимальные по Парето, анонимные и нейтральные, если мырассматриваем их как отображения, которые ставят в соответствие каждому профилюпреимуществ подмножество победителей. Анонимность и нейтральность очевидны.Проверить, что множественные числа победителей по Борду (Копленду, Симпсону)содержат только оптимальные по Парето результаты, достаточно просто. Да, оценкаСимпсона кандидату, что доминируется по Парето, равняется нулю, а дляоптимального по Парето кандидата она позитивна.
Монотонность.Допустим, что а выбирается (среди победителей) при данном профиле ипрофиль изменяется только так, что положение а улучшается, аотносительное сравнение пары любых других кандидатов для любого избирателяостается неизменным. Тогда а как и раньше будет избран (опять средипобедителей) для нового профиля.
Всеправила подсчета очков, а также правила Копленда и Симпсона являютсямонотонными.
Относительноебольшинство с выбыванием. В первом раунде каждый избирательподает один голос за одного кандидата. Если кандидат набирает суровоебольшинство голосов, то он и избирается. В противном случае во втором турепроводится голосование по правилу большинства с двумя кандидатами, которыенабрали наибольшее количество голосов в первом туре.
Сторонникиэтого метода подтверждают, что он почти так же простой, как и правилоотносительного большинства (избирателям не нужно сообщать полное ранжированиекандидатов), и исключает расточительные выборы. При обычном правилеотносительного большинства, если я голосую за кандидата, который получаетмаленькую поддержку, то мой голос будет напрасным. Однако при выбывании у меняесть еще один шанс повлиять на результат.
Однакоэтот метод не является монотонным, как показывают такие два профиля с 17избирателями:Профиль А Профиль B 6 5 4 2 6 5 4 2 a c b b a c b a b a c a b a c b c b a c c b a c
Припрофиле А во второй тур проходять а и b и выигрывает а (11голосов против 6). Профиль В такой же за одним исключением. У двух избирателейпреимущество b>a>с изменяется на преимущество а>b>с, то есть дляних теперь а лучше b. Теперь во второй тур проходять а и с,причем выигрывает с (9 голосов против 8). Таким образом, улучшениепозиции кандидата а приводит к его поражению!
Методальтернативных голосов. Исключим сначала тех, кто получилнаименьшее количество голосов. Потом посчитаем голоса для кандидатов, которыеостались, и опять исключим неудачников. Будем повторять эту операцию до техпор, пока не останется один кандидат (или множественное число кандидатов сровным числом голосов).
Здесьглавное внимание уделяется потому, чтобы не потерять никаких голосов и каждомудать шанс поддержать кандидата, который нравится больше всего. В этом подходеповторно используются методы подсчета очков для исключениякандидатов-неудачников. К сожалению, любое правило, основанное напоследовательном исключении по методу подсчета очков, должно нарушать свойствомонотонности для некоторых профилей.
Пополнение(однозначные правила голосования). Две группыизбирателей N1, N2, что не пересекаются, имеют дело с тем жемножественным числом А кандидатов. Пусть избиратели N1 и N2выбирают того же кандидата а. Тогда избирателе N1EN2такжеизберут а из А.
Этосвойство является очень обоснованным, когда единственный избирательный органразбит на большое количество подмножеств, как в случае региональных ассамблей иподкомитетов.
Пополнение(отображение голосования). Две группы избирателей N1, N2,что не пересекаются, имеют дело с тем же множественным числом Акандидатов. Пусть избиратели Ni избираютподмножество Вiз А при i=1,2. Если В1 и B2пересекаются, то избирателе N1EN2изберутВ1CB2какмножественное число наилучших для себя результатов.
Теорема2.1(Янг [1975])
(а)Все отображения голосования, основанные на подсчете очков (подмножествакандидатов, которые выбирают, с наибольшим суммарным количеством очков),удовлетворяют аксиоме пополнения. Если при равенстве очков выбор проводится наоснове фиксированного порядка на А, то соответствующие правила голосованиятакже удовлетворяют аксиоме пополнения.
(b)Не существует зажиточного по Кондорсу правила голосования (или отображениеголосования), которое бы удовлетворяло аксиоме пополнения.
Аксиомаучастия. Пусть кандидат а выбирается из множественногочисла А избирателями из N. Рассмотрим дальше избирателя и за N. Тогдаизбиратели из NE{i} должныизбрать или а, или кандидата, что для агента I и строго лучше а.
Значит,что если дополнительный голос действительно изменяет результат выборов, то этоможет быть только на руку «ключевому» избирателю.
Теорема2.2 (Мулен[1986с])
(a)Для всех правил голосования с подсчетом очков, когда при равенстве очков выборосуществляется с помощью заданного порядка на А, выполняется аксиома участия.
(b)Если А состоит хотя бы из четырех кандидатов, то ни одно зажиточное по Кондорсуправило голосования не удовлетворяет аксиоме участия.
Непрерывность.Пусть избиратели из N1 избирают кандидата а из A, а группа N2, которая непересекается из N1, избирает другого кандидата b. Тогда существует достаточнобольшое число m дублей группы избирателей N1, такоечто комбинированная группа избирателей (mN1)EN2выберет а.
Теорема2.3 (Янг[1975]).
Отображениеголосования основано на методе подсчета очков (определение 2.3 без фиксацииправила для случая равенства очков) тогда и только затем, когда оно удовлетворяеттаким четырем свойствам:
анонимность,нейтральность
аксиомапополнения и непрерывность.
/>
Голосованиес последовательным исключением.
Сначалапо правилу большинства исключается или а, или b, потом по правилу большинствапроводится сравнение победителя первого раунда и с и так далее. В случаеравенства проигрывает нижний кандидат.
Вэтом процессе поправок пусть а — поправка, b — поправка к поправке, с — исходное предложение, d — status quo.
Этотметод удовлетворяет аксиоме по Кондорсу: если а — победитель по Кондорсу, то онвыигрывает. В действительности возможность при сравнениях по правилубольшинства справедливая в более широком содержании.
Возможностьпо Смиту. Если множественное число А кандидатов разбивается на два подмножестваВ1, B2, что не пересекаются, и каждый кандидат b1IВ1выигрывает(за суровым большинством) у любого кандидата b2IВ2,то должен быть избран результат из В1.
Сдругой стороны, голосование при последовательном исключении очевидно неявляется нейтральным. Порядок исключений, конечно, влияет на результат.
Правилоравномерного исключения. Сначала по правилу большинствавыравниваются пары а из b и с из d. Победители встречаются в финале, гдесравниваются по правилу большинства. В случае равенства выбирается кандидат,который идет раньше по алфавиту.
Это- опять зажиточный по Кондорсу метод. Более того, для избрания каждомукандидату х нужно победить в двух сравнениях по правилу большинства. Допустимосначала, что равенства при сравнении с этими двумя кандидатами нет (хвыигрывает для сурового большинства). Тогда х не может доминироваться по Паретонекоторым кандидатом в, иначе b был бы победителем по Кондорсу. Следовательно,метод равномерного исключения выбирает оптимальный по Парето результат вслучае, когда при бинарных выборах нет равенств. Однако если равенствавозможны, то оптимум по Парето может нарушаться.
Бинарнымдеревом на А есть такое конечное дерево, в котором каждойнефинальной вершине (включая начальную) отвечают ровно две следующие, а каждойфинальной вершине (у которой нет следующих) приписан кандидат (элемент из A),причем каждый кандидат появляется по крайней мере в одной финальной вершине.
Средибинарных деревьев самыми простыми являются те, в которых каждый кандидатприписан ровно одной вершине. Назовем их деревьями без повторных исключений.
Лемма2.1(а) Если А состоит из трех кандидатов, то дерево после последовательногоисключения является единственным безповторним деревом. Соответствующее правилоголосования оптимально за Парето (при нашем условии, что все сравнения побольшинства суровые). (b) Если А состоит из четырех кандидатов, то есть толькодва безповторних деревья: последовательное исключение и ривнобижне исключение.Первое из них нарушает оптимум за Парето, а последнее — нет. (c) Если Асодержит пять или больше кандидатов, то любое исключение по безповторномудереву приводит к избранию кандидата для некоторых профилей, во чтодоминируется по Парето.
Существуетбинарное дерево, определенное для произвольного количества участников, чтопозволяет избежать обеих этих опасностей. Соответствующие последовательныеисключения порождают оптимальное по Парето, анонимное и монотонное правилоголосования. Это дерево называется деревом многоэтапного исключения.
Длякаждого конкретного упорядочения кандидатов существует по одному такому дереву.Обозначим через Гp(1,2,…,р) дерево, которое отвечает порядку A={1,2..., р}.Определим его индуктивно по размеру А:
/>
Да,для трех и четырех кандидатов получаем:
/>
Прир кандидатах образуются 2p-l финальные вершины; кандидат 1 приписанный 2p-2финальным вершинам, а кандидат р только одной. Тем не меньше для избрания дажекандидату р нужно победить в р-1 дуэлях (хотя ему возможно придется понескольку раз столкнуться с тем же оппонентом). Хотя дерево многоэтапногоисключения большое, его решение (то есть вычисление кандидата, которыйвыигрывает) может быть получено с помощью очень простого алгоритма.
Теорема2.4(Шепсл и Вейнгаст [1984]).
Заданыдерево многоэтапного исключения Гp(1,2,… ,ри профиль преимущества, которое отвечает мажоритарному турниру Т. Кандидат а*может быть найден по такому алгоритму:
/> (12)
Следствиетеоремы 2.4.
Кандидата, что выбирается по дереву многоэтапного исключения с турниром Т,удовлетворяет условию:
длялюбого bIА,b?а:
{аТb}і/или {для некоторого с,аТс і сTb}. (14)
Вчастности, а оптимальный по Парето. Более того, дерево многоэтапногоисключения порождает монотонный метод голосования.
Средизажиточных по Кондорсу правил голосования мы обнаружили три метода, которыеудовлетворяют основным требованиям оптимума по Парето, анонимности имонотонности: множественное число победителей по Копленду, множественное числопобедителей по Симпсону и дерево многоэтапного исключения. Первые дванейтральные, но могут выделять несколько победителей (дополнительное правилопри равенстве очков нарушит нейтральность). Заметим, что победитель примногоэтапном исключении находится быстрее, поскольку алгоритм (12) в среднемнуждается в сравнении не больше половины от всех p(p-l) пар. В то же время дляопределения победителей по Копленду и Симпсону нужно провести весь турнирсравнений по правилу большинства.
3. Математические методы решения
Впредыдущем разделе были описанные методы подсчета глазков и основные требованияк ним. Сравним эти методы. Как было отмечено, найлегшим среди них, но инаихудшим, есть правило относительного большинства. Можно убедиться, что вдействительности оно противореччит мнению большинства. Поэтому оно не можетбыть выбрано для компьютерной реализации. Как Борда, так и Кондорсе заметили,что правило относительного большинства может приводить к избранию плохогокандидата, точнее такого кандидата, что в парном сравнении по правилубольшинства проигрывает любому другому кандидату.
Длятого, чтобы перебороть этот изъян, Кондорс и Борде предложили отказаться отправила относительного большинства, причем каждый из них предложил свое правиловместо данного. Кондорс предложил выбирать кандидата, который побеждает любогодругого кандидата в парном сравнении, если такой победитель по Кондорсусуществует. Борде предложил приписать очко каждому кандидату, который линейнорастет в зависимости от его ранга в преимуществе избирателя. Потом он предложилизбрать кандидата, который получил наибольшее суммарное количество очков у всехизбирателей. Эти две идеи порождают два больше всего важных семейств правилголосования.
Результатыэтих правил голосования могут сильно отличаться по свойствам. Одним из такихсвойств есть аксиома монотонности. Правило голосование называется монотонным,если кандидат остается избранным при усилении его поддержки (то есть когдаотносительная позиция данного кандидата в чьих-то преимуществах улучшается, аотносительные позиции других кандидатов не изменяются). Все методы подсчетаглазков являются монотонными, но некоторые известные методы, что возникают изподсчета глазков, не являются такими. Примерами таких правил служит оченьпопулярное правило относительного большинства с выбыванием и методальтернативних голосов.
Естьдве аксиомы, которые приводят к критике зажиточных по Кондорсе правил(поскольку данные правила нарушают эти аксиомы). С другой стороны, на этихаксиомах основана характеризация метода подсчета глазков. Эти аксиомысравнивают кандидатов, избранных разнообразными группами избирателей. Ониназываются свойствами пополнения и участия. Пополнение значит, что если двегруппы избирателей, которые не пересекаются, (например, сенат и палатапредставителей) избирают того же кандидата а, то объединение этих двухизбирательных органов подтвердит избрание а. Участие значит, что избиратель неможет выиграть, воздерживаясь от голосования, в сравнении с возможностьюпринимать участие в голосовании и выразить свои преимущества. Любое зажиточноепо Кондорсе правило нарушает обе этих аксиомы. В противовес этому правилаподсчету очков характеризуются свойством пополнения (теорема Янга) иудовлетворяют аксиоме участия. Теорема Янга в настоящее время является самымсущественным доказательством в поддержку методов подсчета очков, в частностисистемы очков Борда.
Зажиточныепо Кондорсу правила голосования все же чрезвычайно популярны, в частности,благодаря простоте доведения парного сравнения по правилу большинства.Соответствующий класс зажиточных по Кондорсу методов основан напоследовательных сравнениях по правилу большинства. Законопроект имногочисленные поправки к нему в конгрессе США голосуются именно такимспособом. Известен метод последовательного исключения может нарушать условиеоптимума по Парето. Другие методы, основанные на бинарных деревьях парныхсравнений по правилу большинства, противоречат аксиоме монотонности. Наиболеепростое правило, которое основано на последовательном сравнении и являетсяоптимальным по Парето и монотонным, называется многоэтапным методом исключения.При использовании этого метода нужно меньше парных сравнений, чем в других,концептуально более простых методах, например в правиле Копленда. По последнемуправилу избирается тот, кто выигрывает большинство парных дуэлей. Такимобразом, голосование, основанное на последовательных парных сравнениях, можетудовлетворять больше всего важным аксиоматическим требованиям, но только в томслучае, если мы аккуратно выберем эту последовательность.
ПравилаБорда, относительного большинства и антибольшинства являют собой примеры правилголосования с подсчетом очков. Однако правило антибольшинства явно немонотонно, а правило относительного большинства – несправедливое.
ПобедительБорда не может быть наихудших по Кондорсу, так как он является кандидатом,который имеет наивысший средний балл. По этому правилу всегда находятсяоптимальный по Парето победитель или их множественное число. Примерамизажиточных по Кондорсу правил являются правила Копленда и Симпсона. Так же, каки правило Борда или любой другой метод подсчета очков, эти правила выбирают длякаждого профиля подмножество победителей, которое может состоять из несколькихкандидатов, которые получили одинаковую оценку.
Какуже было отмечено, правила голосования должны быть монотонные, оптимальные поПарето, анонимные и нейтральные. Все правила голосования с подсчетом очков,кроме правила антибольшинства, оптимальны по Парето, монотонные, анонимные инейтральные, если мы не указываем, что делать при равенстве очков. Кроме того,правила голосования должны удовлетворять аксиоме участия и пополнения. МетодБорда относится к этим правилам (это было показано в предыдущем разделе).
ПравилаБорда и Копленда, как отмечает Мулен, опираясь на практику, не очень частиприводят к равенству очков, потому в этом ракурсе является наилучшими. Однако методыКондорсе, к которым относится и правило Копленда, для некоторых профилей можетне удовлетворять аксиоме участия.
Следующейгруппой правил являются правила, основанные на последовательном исключении заметодом подсчета очков (относительное большинство с выбыванием, методальтернативных голосов). Однако эти правила, как и любые другие методы, свыбыванием кандидатов нарушают свойство монотонности для некоторых профилей.
Методривнобижного исключения выбирает оптимальный за Парето результат в случае, когдапри бинарных выборах нет ривностей. Однако если равенству возможные, то оптимумза Парето может нарушаться. Невзирая на выше перечисленные трудности,возможность за Кондорсе, широко известная в качестве демократического принципа,в то время как правило Борда «скрывает» настоящие симпатииизбирателей за математической формулой. К зажиточным по Кондорсу правиламотносят также следующие методы голосования:
а)голосование с последовательным исключением. При очевидных причинах это правилоне является нейтральным и оптимальным по Парето, так как порядок исключенийвлияет на результат голосования. Определяя повестку дня, председательфактически контролирует процесс выборов. Однако это правило достаточно широкоиспользуется Конгрессом США;
б)правило равномерного исключения. Оно порождает дерево без повторных исключенийи требует проведения целого ряда мажоритарных турниров. Как было доказано впредыдущем разделе, бинарное дерево может дать оптимальное по Парето правилоголосование только в более сложном случае, чем безповторне дерево. Также можетнарушаться монотонность;
в)дерево многоэтапных исключений. Этот метод обеспечивает проведение наполовинуменьшего количества мажоритарных турниров, чем метод Копленда. Оно имеетбольшой размер. Кандидатам, возможно, нужно принимать участие в дуэлях с тем жеоппонентом по нескольку раз. Однако его алгоритм является достаточно простым.Дерево многоэтапного исключения порождает оптимальный за Парето и монотонныйметод голосования. Всегда находится единственный победитель, а не множественноечисло. Однако этот метод порождает все трудности, которые связаны сиспользованием бинарных деревьев.
Такимобразом, была проведена сравнительная характеристика всех методов голосованиябольшинством голосов с исключением случаев безразличия и представлениянеправдивой информации.
Средизажиточных по Кондорсу правил голосования мы обнаружили три метода, которыеудовлетворяют основным требованиям оптимума по Парето, анонимности имонотонности: множественное число победителей по Копленду, множественное числопобедителей по Симпсону и дерево многоэтапного исключения. Среди методовподсчета очков наилучшим оказался метод определения победителя по Борду.Зажиточные по Кондорсу правила примененные на парном сравнении кандидатов поправилу относительного большинства. Для рядового избирателя они являютсянаиболее понятными.
ПравилоБорда удовлетворяет аксиоме участия и пополнения, но скрывает за математическойформулой настоящие преимущества избирателей.
Дляпрограммной реализации выберем один из методов Копленда как самый простой и длясравнения определим победителя за Борда.
Приведемеще раз правила Копленда и Борда для того, чтобы перейти к формулировкеалгоритма программы.
ПравилоБорда. Каждый избиратель сообщает свои преимущества,ранжируя р кандидатов от лучшего к худшему (безразличность запрещается).Кандидат не получает очков за последнее место, получает одно очко запредпоследнее и так далее, получает р-1 очков за первое место. Побеждаеткандидат с наибольшей суммой очков. Он называется победителем по Борду.
ПравилоКопленда. Сравним кандидата а с любым другим кандидатом х.Начислим ему +1, если для большинства а лучше за х, -1, если для большинства хлучше за а, и 0 при равенстве. Суммируя общее количество очков по всем х,х?а получаем оценкуКопленда для а. Избирается кандидат, названный победителем по Копленду, снаивысшей из таких оценок.
Считаем,что входными данными задачи является уже сгруппированная информация:сформированные группы избирателей с одинаковыми в каждой группе рангамипреимуществ. Однако допускается и занесение информации каждым избирателемотдельно.
4. Описание алгоритма
Вданном разделе наводятся алгоритмы для нахождения победителей выборов. Дляопределения победителей Борда и Копленда воспользуемся непосредственноприведенными выше правилами, то есть реализуем их программно. Сложностьалгоритмов, описанных ниже, прямо пропорциональна количеству групп избирателейи количества кандидатов, что еще раз подтверждает принадлежность данной задачик Р-типу.
4.1 Определение победителя Борда
Длянахождения оценок Борда кандидаты ранжируются, то есть за каждое место в шкалеизбирателей кандидат получает определенное количество баллов.
Далееэти баллы суммируются.
Введемследующие переменные.
ПустьМ – количество кандидатов;
S– количество групп избирателей;
Nаme[M]– массив имен избирателей;
Rаng[1..M,1..S] – профиль преимуществ;
Many[S]– количество избирателей в каждой группе;
Bord[M]– массив оценок кандидатов.
Рассматриваемотдельно каждую группу избирателей. Для этой группы кандидат получает оценку[количество избирателей many[i]]*([количество кандидатов M] – [текущее значениесчетчика j]). Найденная оценка добавляется к предыдущей. Алгоритм продолжаетработу до тех пор, пока не будут рассмотрены все группы избирателей (i=S).
Поправилу Борда получаем следующий алгоритм для нахождения оценок Борда.
/>
Рис. 4.1 Алгоритм нахождения оценокБорда.
/>
Рис. 4.2 Алгоритм нахождения оценокКопленда (начало)
4.2 Нахождение оценки Копленда
Длянахождения оценки Копленда кроме выше приведенных используем следующиепеременные: Kopl[M] – массив оценок Копленда; Vybor1, vybor2 – вспомогательныепеременные; используются для пересмотра имен кандидатов из массива имен name.
Сравнениепроходит следующим образом.
Переменнойvybor1 присваиваем значение имени первого кандидата из множественного числаимен name (contrl=1), а vybor2 – следующее (k=contrl+1). Если vybor1 находитсявыше, чем vybor2, в преимуществах избирателей всех групп, то к оценке Копленда(kopl[contrl]) кандидата vybor1 добавляется глазок, а vybor2 (kopl[k]) –отнимается и наоборот. Дальше переменной vybor2 присваивается следующеезначение из массива имен (k=k+1), и процедура сравнения опять повторяется. Циклпродолжается до тех пор, пока не исчерпаются имена в списке кандидатов.
Послеэтого переменной vybor1 присваивается второе имя из списка кандидатов(contrl=contrl+1), а vybor2 – третья. Опять проходит цикл по переменной vybor2.Цикл по переменной vybor1 заканчивается тогда, когда будут пересмотренывсе кандидаты.
Получаемследующий алгоритм нахождения оценки Копленда.
/>
Рис. 4.3 Алгоритм нахождения оценокКопленда (конец)
4.3 Алгоритм определения победителя заправилами Борда или Копленда
Какможно было увидеть, победителем по Борду (Копленду) является кандидат снаивысшей суммой очков. Поэтому процесс его определения является одинаковым дляобоих случаев, и я его объединила одним алгоритмом. Как известно, правилаКопленда и Борда порождают множественное число решений. Для нахожденияпобедителя используем следующие переменные: K – количество победителей; Max –оценка победителей; Hl[M] – массив номеров победителей.
Сначаламассив номеров победителей заполняем нулями.
Массивыоценок Копленда и Борда (kopl и bord) заменим формальным массивом v[M].
Послетого, как мы нашли оценки для кандидатов (массивы kopl и bord), среди них ищеммаксимальную (max). Дальше отбираем кандидатов, оценка которых равняется max(их номера из массива name заносятся в массив hl), и считаем количествопобедителей (k).
Пересматриваемзаполненный массив hl. Если в нем только первое значение отличающееся от нуля,то значит, что мы нашли единственного победителя, и, следовательно, сохранилиусловие нейтральности.
Вдругом случае просматриваем те значения имен кандидатов (массив name), номеракоторых встречаются в массиве hl. Отобраны имена кандидатов упорядочиваем посписку. Победителем становится тот, имя которого находится первым в данномсписке.
Вданном случае условие нейтральности не сохраняется.
Мыполучили следующий алгоритм.
/>
Рис. 4.4 Алгоритм определения победителя(начало).
/>
Рис. 4.5. Алгоритм определенияпобедителя (конец).
5. Описание программы
5.1 Выбор технологии программирования
Наиболеераспространенными парадигмами программирования, которые к тому же могут бытьиспользованы в данной курсовой работе, являются парадигмы процедурного иобъектно-ориентированного программирования.
Парадигмапроцедурного программирования больше всего широко распространена средисуществующих словно программирование (например, Си и Паскаль). Здесь явно выделяютдва вида разнообразных сущностей:
1) процедуры,которые исполняют активную роль, то есть представляются тем, которое задаетповедение (функционирование) программы;
2) данные,что исполняют пассивную роль, то есть представляют тем, которое прорабатываетсясредством, продиктованным процедурами. Возможность составлять процедуры изкоманд (операторов) и вызывать их является ключом данной парадигмы.Особенностью этой парадигмы являются «боковые эффекты», которыевозникают в тех случаях, когда разнообразные процедуры, которые используютобщие данные, независимо их изменяют.
Впроцедурной парадигме активная роль в организации поведения уделяетсяпроцедурам, а не данным; причем процедура активизируется вызовом. Подобныесредства задания поведения удобны для описаний детерминированнойпоследовательности действий или одного процесса, или нескольких, но строговзаимозависимых процессов. При использовании программирования, ориентированногона данные, активную роль играют данные, а не процедуры. Здесь со структурамиактивных данных связывают некоторые действия (процедуры), которыеактивизируются тогда, когда осуществляется доступ к этим данным. Некоторыеспециалисты называют это средство активации действий «демонами».Программирование, ориентированное на данные, позволяет организовать поведениемало зависимых процессов, что тяжело реализовать в процедурной парадигме. Имелазависимость процессов значит, что они могут рассматриваться и программироватьсяотдельно. Однако при использовании парадигмы, управляемой данными, этинезависимо запрограммированные процессы могут взаимодействовать между собой безих изменения (то есть без перепрограммирования). Парадигма объектногопрограммирования в отличие от процедурной парадигмы не разделяет программу напроцедуры и данные. Здесь программа организуется вокруг сущностей, названныхобъектами, что включают локальные процедуры (методы) и локальные данные(переменные). Поведение (функционирование) в этой парадигме организуется путемпересылки сообщений между объектами. Объъект, получив сообщение, осуществляетего локальную интепретацию, базируясь на локальных процедурах и данных. Такойподход позволяет описывать сложные системы наиболее естественным путем.Особенно он удобен для интегрированных IC. Объектно-ориентированноепрограммирование (ООП) базируется на абстракциях данных. В основе этого методалежит представление предметной области в виде совокупности объектов, которыевзаимодействуют между собой через передачу сообщений. Модель абстракции данныхзаключается в инкапсуляции данных и операций над ними в отдельный классовыйтип. Доступ к данным возможная лишь с помощью инкапсулированных операций.Классовый тип является автономно завершенным и позволяет полное или частичноенаследование для других классов. ООП концентрируется на цели задачи, длякоторой разрабатывается программа. Задача строится как совокупность объектов,которые взаимодействуют между собой с помощью сообщений. Элементы программыразрабатываются в соответствии с объектами в описании задачи. Суть ООПзаключается в определении наиболее удачных объектовых типов. Объектовый типслужит модулем, который может быть использованным для решения других подобныхзадач. Такой подход не нуждается в специальной вычислительной технике, носущественно отличается характером мышления исполнителей в сравнении спроцедурными языками программирования.
Черезочевидную простоту алгоритма для реализации задачи лучше всего выбратьпроцедурную парадигму программирования и языка Паскаль или Си. Конечно, длянаписания красивого интерфейса можно взять объектно-ориентированные языки CBuilder или Delphi. Однако, как можно было увидеть из рассмотрения алгоритмазадачи, построение интерфейса сводилось бы к последовательному выведению окон.Еще одним аргументом в интересах словно Паскаль или Си есть размеры программы,которые бы при использовании C Builder или Delphi были намного большими.
Средидвух языков – Паскаль и Си, – я изберу Паскаль как более привычный для себя.
5.2 Структура программы
Структурноданную программу можно разделить на блоки.
Каждыйблок может быть отнесен к одной из функциональных групп:
1. Построениеинтерфейса;
2. Реализацияалгоритмов, представленных в разделе 4.
Следовательно,программа имеет следующую структуру:
Процедура victory –это реализация алгоритма определения победителя, описанного в предыдущемразделе. Во время вызова данной процедуры задается массив оценок Борда илиКопленда, а также текст, для выведения результатов (им служат слова «Копленда»и«Борда»). В предыдущем разделе уже было обосновано, почему дляопределения победителя за разными правилами использован единственный алгоритм.Процедура help выводит список имен кандидатов в нижней строке экрана. Онавведена для облегчения ввода информации пользователем.
/>
Рис. 5.1 Структура программы.
Процедура exampleсодержит данные контрольного примера. Она введена для облегчения проверкиправильности работы программы и носит демонстрационный характер.
Процедура rightпредназначена для проверки правильности вводу символа. Она используется привыборе внесения информации (демонстрация контрольного примера илисамостоятельное внесение профиля) и выборе способа заноса данных (отдельнымиизбирателями или работниками избирательного комитета).
Перейдем крассмотрению основной программы.
Прежде всего в нейпроходит вызов и взаимосвязь описанных выше процедур.
Процедурыпостроения интерфейса вызываются в начале работы программы. Они предназначенныедля облегчения внесения данных.
Процедураvictory определяет победителя и выводит результат голосования по определенномуправилу. Потому ее вызов происходит напоследок основной программы.
Опишемпеременные, которые используются в основной программе.
N:кол-во избирателей;
M:кол-во кандидатов;
s:кол-во групп;
rang:профиль преимуществ;
а,b:для определения оценки Копленда (используется в бинарных сравнениях);
kopl:массив оценок Копленда;
vybor1,vybor2: переменные внешних циклов при определении оценки Копленда;
bord:массив оценок Борда;
name:массив имен кандидатов;
к,и, j, l, r: вспомогательные переменные;
many:массив групп избирателей.
Опишемструктуру программы.
Сначалапрограмма просит внести всю нужную информацию. Пользователь должен указатьколичество избирателей и кандидатов и способ заноса информации (будет ли своипреимущества вносить каждый избиратель отдельно, будет ли это проводитькомиссия, оперируя сгруппированными данными). Дальше идет внесение профиляпреимуществ и проверка на его корректность. Профиль является некорректным, еслив нем встречается имя лица, которое не является выше указанным кандидатом, илиже имена кандидатов повторяются.
Впрограмме используются алгоритмы правил Борда и Копленда, указанные впредыдущем разделе. Согласно полученных оценок определяется победитель с помощьюпроцедуры victory, и проходит выведение результата.
Следуетзаметить, что полученные победители Копленда и Борда могут не совпадать, чтоеще раз свидетельствует о несовершенстве правил голосования большинствомголосов. Результаты работы алгоритма будут показаны в соответствующем разделе.
Сложностьпрограммы (в данном случае понимается время, тратящее на выполнение), прямопропорционально зависит от величины количества избирателей и кандидатов.
Таккак данная программа носит более демонстрационный характер, то я ввела границудля количества избирателей и кандидатов для того, чтобы ограничить времявыполнения – 200 и 50 соответственно. В общем оно не является существенным, таккак всегда можно разбить избирательный округ на более малый с условием того, чтобывыполнялось данное ограничение.
5.3 Инструкция пользователю
Даннаяпрограмма предназначенная для определения победителя выборов по правиламКопленда и Борда и сравнение полученных результатов.
Вначале работы программы пользователь может выбрать, просматривать ли результатырешения контрольного примера, вносить ли собственные данные. В обоих случаяхопределяются победители за Коплендом и Борда.
Сначалаработники избирательного органа вносят общую информацию: количество избирателейв данном округе то количество кандидатов. Дальше заносятся имена кандидатов иуказывается способ заноса профилей преимуществ: каждым избирателем отдельно илиработниками избирательного округа. В последнем случае информация сгруппирована(аналогично к контрольному примеру).
Внизуекрана выводятся имена всех кандидатов. Каждый избиратель (работник лиизбирательного округа) вносит профиль преимуществ, располагая кандидатов встрого определенном порядке.
Длякаждого избирателя не допускается случаев безразличия; кроме того, кандидатыдолжны быть строго ранджовани (то есть каждый из них занимает свое место впреимуществе избирателя, и на одном уровне не могут находиться два кандидата).Имена кандидатов, которые заносятся избирателями, повинны совпадать с именами,указанными в начале заполнения информации.
Послезаноса всех этих данных выдается результат работы программы.
Сначалавыводится победитель Копленда и указывается, определен ли он с сохранениемнейтральности. Для победителя указывается его оценка. В противном случаевыводится множественное число победителей (кандидатов, сумма глазков которыхравняется максимальной оценке).
Аналогичноопределяется победитель Борда.
Какбудет показано в контрольном примере, оценки кандидатов, полученных по правиламБорда и Копленда, могут ранджуватись в противоположном порядке.
6. Контрольный пример
Пустьдан следующий профиль для 9 избирателей и 5-ти кандидатов:1 4 1 3
a
b
c
d
e
c
d
b
e
a
e
a
d
b
c
e
a
b
d
c
Вкаждом столбце кандидаты расположенные в порядке уменьшения их значимости для каждойгруппы избирателей. То есть, для первого столбца можно определить преимуществаследующим образом: группа избирателей, которая состоит из одного лица, считаеткандидата а наилучшим. На втором месте они ставят кандидата b, на третьем местеc и т.д.
Продемонстрируемрешение контрольного примера по правилу Копленда. Определяем оценку Копленда.
Кандидата является лучшим за b для 1+1+3 избирателей, а для 4-х избирателей кандидат bявляется лучшим за а. Определим такие преимущества для каждого кандидата, сравнимего со всеми другими.
ab – 5
ac – 5
ad – 5
ae – 1
ba – 4
ca – 4
da – 4
ea – 8
bc – 5
bd – 4
de – 5
cb – 4
db – 5
eb – 4
cd – 5
ce – 5
dc – 4
ec – 4 de – 5 ed – 4
Определимоценку Копленда для каждого кандидата. Кандидат а является лучшим за b(добавляем +1); он также является лучшим за c и d (добавляем два разы +1) ихудшим за e (добавляем –1). Следовательно, оценка Копленда для аровна 2.
Найдемоценку для других кандидатов.
a=+1+1+1-1=2
b=-1+1-1+1=0
c=-1-1+1+=0
d=-1+1-1+1=0
e=+1-1-1-1=-2
Средиполученных оценок определяем максимальную. Как видим, она равняется 2 ипринадлежит кандидату а. Следовательно, а – победитель Копленда.
Еслибы у нас получились два кандидата с максимальной оценкой, например b и f, мы быизбрали кандидата b, так как он расположен ближе за алфавитом.
Дляэтого же профиля найдем победителя Борда.
Следовательно,получаем такие оценки:
a=1*4+4*0+1*3+3*3=16
b=3*1+2*4+1*1+2*3=18
c=2*1+4*4+0+0=18
d=1*1+4*3+2*1+1*3=18
e=1*4+1*4+3*4+0=20
Победителемза Борда является кандидат е.
Каквидим, оценки Борда ранжируют кандидатов в порядке, противоположном до того,который получается по оценкам Копленда.
Выводы
Даннаякурсовая работа была посвящена обзору методов голосования большинством голосов.Была проведена сравнительная характеристика каждого из методов и из ихмножественного числа избраны наилучшие. К ним относятся:
1.зажиточные за Кондорсе правила Копленда и Симпсона, дерево многоэтапного исключения;
2.один из методов подсчета очков – правило Борда.
Всеэти правила удовлетворяют условиям оптимума по Парето, монотонности ианонимности. Кроме того, правило Борда удовлетворяет также аксиоме участия ипополнения.
Дляпрограммной реализации были избраны методы Копленда и Борда.
Результатыработы программы продемонстрированы на контрольном примере.
Списоклитературы
1. Мулен Э. «Кооперативное принятие решений: Аксиомы имодели» – Москва, Мир, 1991.
2. Миркин Б. Проблема группового выбора. – Москва, Наука,1974.
3. Льюс Р.Д., Райфа Х. Игры и решения. М.: ИЛ, 1961.
4. Антонов А. В. «Системный анализ», М.-2004г.
5. Ларичев О.И. Наука и искусство принятия решений. – М:Наука, 1979. – 200 с.
6. Макаров И.М. Теория выбора и принятия решений. – М.:Наука,1987. – 350 с.
7. Кузнецов А.В., Сакович В.А., Холод Н.И. «Высшаяматематика. Математическое программирование », Минск, Вышейшая школа,2001г.
8. Красс М.С., Чупрынов Б.П. «Основы математики и ееприложения в экономическом образовании», Издательство «Дело»,Москва 2001г.
9. В.И. Ермаков «Общий курс высшей математики дляэкономистов», Москва, Инфра-М, 2000г.
10. Теория прогнозирования и принятия решений. М:1989. 160 стр.
Дополнения
Программа
useswincrt;
labelв,z;
typemas = string[6];
typeball =array[1..10] of shortint;
varN: byte; {кол-во избирателей}
M:byte; {кол-во кандидатов}
s:byte; {кол-во групп}
rang:array[1..10,1..100] of mas; {профильпреимуществ}
к,i,j,l,r,contrl:byte;
а,b:byte; {для проведения парных сравнений}
kopl:ball; {массив оценок Копленда}
vybor1,vybor2: mas;
bord:ball; {массивоценокБорда}
name:array[1..10] of mas; {массив именкандидатов}
many:array[1..100] of byte; {массив группизбирателей}
n1:array[1..10] of mas;
c:char;
{данныеконтрольного примера}
{---------------------------}
procedureexample;
varи,j: byte;
begin
clrscr;M:=5; n:=9; s:=4;
name[1]:='a';name[2]:='b'; name[3]:='c'; name[4]:='d'; name[5]:='e';
many[1]:=1;many[2]:=4; many[3]:=1; many[4]:=3;
rang[1,1]:='a';rang[1,2]:='c'; rang[1,3]:='e'; rang[1,4]:='e';
rang[2,1]:='b';rang[2,2]:='d'; rang[2,3]:='a'; rang[2,4]:='a';
rang[3,1]:='c';rang[3,2]:='b'; rang[3,3]:='d'; rang[3,4]:='b';
rang[4,1]:='d';rang[4,2]:='e'; rang[4,3]:='b'; rang[4,4]:='d';
rang[5,1]:='e';rang[5,2]:='a'; rang[5,3]:='c'; rang[5,4]:='c';
gotoXY(15,1);
writeln;writeln('Число избирателей: ', N);
writeln('Числокандидатов: ', M);
writeln('Профильпреимуществ:');
fori:=1 to 40 do
write('-');
writeln;write('Число избирателей ');
gotoXY(19,7);
fori:=1 to s do
write(many[i]' ');
writeln;gotoXY(19,9);
fori:=1 to M do
begin
forj:=1 to s do
write(rang[і,j]' ');
gotoXY(19,9+i);
end;
gotoXY(1,15);
end;
{---------------------------}
{проверяетправильность ввода варианта выбора} procedure right;
labell;
begin
l:readln(c);
if(c'0') and (c'1') then
begin
write('Повторитепопытку: ');
gotol;
end;
end;
{---------------------------}
{выводитсписок имен кандидатов}
procedurehelp;
varx,y,i: byte;
begin
x:=WhereX;
y:=WhereY;
gotoXY(1,24);
write('Именакандидатов: ');
fori:=1 to M do
ifiM then write(name[i] ', ')
elsewrite(name[i]);
gotoXY(x,y);
end;
{---------------------------}
{определениепобедителявыборов}
procedurevictory(v: ball; s: string);
varmax, t: shortint;
hl:array[1..10] of byte;
begin
{определениемаксимальной оценки}
help;
max:=v[1];
fori:=1 to M do
ifmax
max:=v[i];
t:=1;
{определениекандидатов с максимальной оценкой}
fori:=1 to M do
if(v[i]-max)=0 then
begin
hl[t]:=i;
t:=t+1;
end;
if(t-1)=1 then
begin
write('Победительза ', s ' с сохранением нейтральности: ');
writeln(name[hl[1]]);writeln('Сумма очков- ', max);
end
else
begin
vybor1:=name[hl[1]];
fori:=2 to t-1 do
ifname[hl[i]]
vybor1:=name[hl[i]];
write('Победительза ', s ' без сохранения нейтральности: ');
writeln(vybor1);
writeln('Суммаочков- ', max);
writeln('избранныйиз множественного числа наилучших:');
fori:=1 to t-1 do
writeln(name[hl[i]]);
end;
end;
{---------------------------}
{основнаяпрограмма}
begin
gotoXY(21,1);writeln('Определение победителя выборов');
writeln;writeln('Запуск контрольного примера — 1; Самостоятельное внесение профиля 0');
right;
ifc='1' then
begin
example;
help;
gotoz;
end
elseclrscr;
write('Введитеколичество кандидатов: ');
readln(M);
write('Введитеколичество избирателей: ');
readln(N);
writeln('Введитеимена кандидатов');
fori:=1 to M do
begin
write('Кандидат', и ': ');
readln(name[i]);
end;
writeln('Какбудет осуществляться занос
информации?');
write('1-отдельными избирателями, 0- комитетом: ');
right;
ifc='1' then
fori:=1 to N do
many[i]:=1;
clrscr;writeln('Введите профильпреимуществ');
s:=1;contrl:=0;
whilecontrlN do
begin
ifc='1' then writeln('Избиратель', s)
elsewriteln('Группа ', s);
fori:=1 to m do
n1[i]:='';
help;
forj:=1 to M do
begin
y:readln(vybor1);
{проверкана корректность введенного профиля}
r:=0;a:=0; b:=0;
n1[j]:=vybor1;
forl:=1 to M do
begin
ifvybor1=name[l] then
begin
b:=1;
fora:=1 to M do
{такоеимя уже было введено в данном профиле}
if(vybor1=n1[a]) and ((a-j)0) then r:=1;
end;
{имявведенного кандидата не совпадает с ни одним из списка}
if(vybor1name[l]) and (l=M) and
(b1)then r:=1;
end;
ifr=1 then
begin
n1[j]:='';
writeln('Внимательновводите имена кандидатов');
gotoв;
end
elserang[j,s]:=vybor1; {профиль корректен}
end;
ifc='0' then
begin
writeln('Количествоизбирателей в
группе', s);
readln(many[s]);
contrl:=contrl+many[s];
end
else
contrl:=contrl+1;
s:=s+1;
clrscr;
end;{while}
{Определениеоценок Копленда}
z:contrl:=1;
whilecontrl
begin
k:=contrl+1;
vybor1:=name[contrl];vybor2:=name[k];
whilek
begin
i:=1;a:=0; b:=0;
whilei
begin
forj:=1 to M do
ifrang[j,i]=vybor1 then l:=j
else
ifrang[j,i]=vybor2 then r:=j;
ifl
else
ifl>r then b:=b+many[i];
i:=i+1;
end;
ifa>b then
begin
kopl[contrl]:=kopl[contrl]+1;
kopl[k]:=kopl[k]-1;
end
else
ifa
begin
kopl[k]:=kopl[k]+1;
kopl[contrl]:=kopl[contrl]-1;
end;
k:=k+1;
vybor2:=name[k];
end;{while пок}
contrl:=contrl+1;
end;{while поcontrl}
{определениеоценок Борда}
fori:=1 to s do
forj:=1 to M do
begin
fork:=1 to M do
ifrang[j,i]=name[k] then r:=k;
bord[r]:=many[i]*(M-j)+bord[r];
end;
victory(kopl,'Коплендом');
writeln('Нажмителюбуюклавишу
');readkey; writeln;
victory(bord,'Борда');
end.
Результатыработы программы
Самостоятельноевнесение профиля.
Введитеколичество кандидатов: 5
Введитеколичество избирателей: 9
Введитеимена кандидатов
Кандидат1: а
Кандидат2: b
Кандидат3: c
Кандидат4: d
Кандидат5: е
Какбудет осуществляться занос
информации?
1-отдельнымиизбирателями, 0 –
комитетом:0
Введитепрофиль преимуществ
Группа1
a
b
c
d
e
Количествоизбирателей в группе 1: 1
Группа2
c
d
b
e
a
Количествоизбирателей в группе 2: 4
Группа3
e
a
d
b
c
Количествоизбирателей в группе 3: 1
Группа4
e
a
b
d
c
Количествоизбирателей в группе 4: 3
Победительпо Копленду с сохранением нейтральности – а
Суммаочков – 2
Победительпо Борду с сохранением нейтральности – е
Суммаочков – 20
Результатыработы программы
/>