Алгоритм Хантингтона-Хилла

1. Выделить по одному месту каждой группе.

2. Для каждой группы подсчитать индекс Хантингтона-Хилла:

h = ,

где s – численность группы (например, население штата), k – число уже выделенных дан-ной группе мест.

3. Предоставить очередное место группе с максимальным индексом.

4. Если все места в представительном органе уже заполнены, то алгоритм прекращает ра-боту. В противном случае переходим на шаг 2 ■

Проиллюстрируем работу алгоритма Хантингтона-Хилла на данных из примера 11.

Пример 15. Напомним, что речь идёт о распределении 9 мест в совете пропорционально числу имеющихся у этих трёх компаний акций. Запишем исходные данные в первые три строки следующей таблицы 13:

 

Таблица 13

Компания	Наксон	Ароко	Евробайл
Процент акций
Начальное распределение 3-ёх мест
Индекс Хантингтона-Хилла	472/(1*2) =1104,5	372/(1*2) = 684,5	162/(1*2) = 128
Распределение 4-ёх мест
Индекс Хантингтона-Хилла	472/(2*3) ≈ 368	372/(1*2) = 684,5	162/(1*2) = 128
Распределение 5-и мест
Индекс Хантингтона-Хилла	472/(2*3) ≈ 368	372/(2*3) ≈ 228	162/(1*2) = 128
Распределение 6-и мест
Индекс Хантингтона-Хилла	472/(3*4) ≈ 184	372/(2*3) ≈ 228	162/(1*2) = 128
Распределение 7-и мест
Индекс Хантингтона-Хилла	472/(3*4) ≈ 184	372/(3*4) ≈ 114	162/(1*2) = 128
Распределение 8-и мест
Индекс Хантингтона-Хилла	472/(4*5) ≈ 110	372/(3*4) ≈ 114	162/(1*2) = 128
Распределение 9-и мест

Таким образом, при делении методом Хантингтона-Хилла получаем распределение (4,3,2). При делении методом Гамильтона получили такое же распределение (см. пример 12). Такое же рас-пределение получим методом Адамса. А метод Джефферсона даёт отличное от этого распреде-ление (5,3,1). Заметим также, что в данном алгоритме расчёт индекса на каждом шаге делается только для одной группы – именно, той, которой добавлено место на предыдущем шаге ■

Задание 8. Для данных, представленных в таблице 14, разделить пропорционально про-центу акций заданное число мест в совете четырьмя рассмотренными методами: Гамильтона, Джефферсона, Адамса и Хантингтона-Хилла. Ответы представить в небольшой таблице. Для образцов см. примеры 12 – 15.

Таблица 14

№ пп	Компания	Наксон	Ароко	Евробайл	Число мест в совете
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций
	Процент акций

■

 

Предметный указатель

 

выигрыш общий

участника

делёж Парето-эффективный

равноценный

свободный от зависти

справедливый

делитель стандартный

модифицированный

индекс Хантингтона-Хилла

квота стандартная

модифицированная

метод Адамса

Гамильтона

Джеффесона

подстраивающегося победителя

Хантингтона-Хилла

несправедливость, относительная

пара, блокирующая

паросочетание, обобщённое

устойчивое

пропорциональное представительство

пункт, делимый

неделимый

пунктов, сравнительная важность

фаза отказа

приписывания.

 

 

Литература к части 3

 

Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А.. Бинарные отношения, графы и коллективные реше-ния. − 2-е изд., перераб. и доп. − М.: ФИЗМАТЛИТ, 2012. − 344 с. – ISBN 978-5-9221-1363-2.

Воробьёв Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука. Гл. ред. физ.-мат. лит., 1985. – 272 с.

Коэн Г. Обо всём можно договориться. − М.: АСТ: АСТ МОСКВА, 2010. – 284 с. – ISBN 978-5-403-02812-7.

Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологичес-ким и экологическим задачам. − М.: Наука. Гл. ред. физ.-мат. лит., 1986. − 496 с.

Pirnot T.L. Mathematics All Around. – 2^nd ed. – Pearson Education, 2004. – 906 p. – ISBN 0-201-79511-6.

Rubchinsky A.A. Fair Division with Divisible and Indivisible Items. − Working paper WP7/2009/05. − М: НИУ ВШЭ, 2009. – 44 c. – УДК 519.8; ББК 22.18.

 

Часть 4. ПРИНЯТИЕ РЕШЕНИЙ

Процессы принятия решений лежат в основе любой целенаправленной человеческой дея-тельности. Оптимальные (эффективные) решения способствуют достижению поставленных це-лей при минимальных затратах финансовых, трудовых, материальных и сырьевых ресурсов. Методы поиска оптимальных решений для непрерывных моделей рассматриваются в разделах классической математики, связанных с изучением экстремумов функций, а для дискретных мо-делей – в разработанных значительно позднее методах решения дискретных оптимизационных задач. В обоих случаях решение представляет собой математический объект, основным свойст-вом которого является именно то, что он доставляет экстремум одной заданной функции.

В то же время в реальности мы часто встречаемся с двумя другими ситуациями:

1.Отсутствие критериев оптимизации, когда варианты или альтернативы возможных ре-шений представляют собой цельные нерасчленимые объекты, некоторые из которых можно только попарно сравнивать с точки зрения «качества» (зачастую формально не определённого).

2. Наличие нескольких критериев оптимизации, отражающих различные важные свойства и аспекты альтернатив, которые желательно одновременно улучшить.

В обоих случаях классические оптимизационные модели не работают, поэтому в послед-ние десятилетия большое внимание уделяется новым подходам и методам решения указанных и близких к ним задач. В случае отсутствия критериев оптимизации для нахождения лучших аль-тернатив используются общие понятия, модели, методы и алгоритмы теории бинарных отноше-ний, формализующей понятие оптимизации на основе попарных сравнений. Элементы этой тео-рии излагаются в главе 14 «Бинарные отношения». В главе 15 «Бинарные отношения в критери-альном пространстве» рассмотрены начальные идеи многокритериальной оптимизации, в рам-ках которой альтернативы представляются точками в критериальном пространстве, а их коор-динаты соответствуют различным свойствам альтернатив. Центральным здесь является понятие множества Парето, содержащего оптимальные с точки зрения нескольких критериев альтерна-тивы из исходного множества. Излагается алгоритм выделения множества Парето. Приводится метод Подиновского, который позволяет за счёт дополнительной качественной информации о важности критериев существенно сокращать число оптимальных альтернатив по сравнению с их числом в множестве Парето.

В главе 16 «Коллективное принятие решений» рассмотрены аспекты принятия коллектив-ных или групповых решений, которые связаны с согласованием различных точек зрения, поис-ком компромисса и т.д. Понятия и терминология в этой области в большой степени опирается на материал двух предыдущих глав. Излагаются основные методы построения групповых решений.

Глава 17 «Функции выбора» посвящена появившемуся в 70-ые годы ХХ-ого века новому понятию. Функции выбора, в отличие от бинарных отношений, формализуют понятие опти-мальности, не определяемое одними только результатами попарных сравнений альтернатив, но опирающееся на более широкии взаимозависимости между ними. В главе наряду с общим поня-тием функции выбора излагаются так называемые механизмы выбора – правила определения лучших альтернатив, основанные на понятиях бинарного отношения и критериального прост-ранства, но существенно отличающиеся от рассмотренных в главах 14 и 15 правил выделения альтернатив, оптимальных по заданному бинарному отношению. В частности, рассмотрены турнирное правило и метод идеальной точки.

Как и ранее, изложение относится к конечным множествам и не касается более сложных вопросов, связанных с континуальными случаями, что определяется уже самим названием на-стоящего пособия.