Алгоритм хантингтона-хилла
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. – 2nd 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 правил выделения альтернатив, оптимальных по заданному бинарному отношению. В частности, рассмотрены турнирное правило и метод идеальной точки.
Как и ранее, изложение относится к конечным множествам и не касается более сложных вопросов, связанных с континуальными случаями, что определяется уже самим названием на-стоящего пособия.