Распределите ресурсы самым честным способом - PullRequest
Новая
       14

Распределите ресурсы самым честным способом

0 голосов
/ 21 июня 2019

Работая над личным проектом, я столкнулся с проблемой, которую постараюсь обобщить здесь.

Учитывая список ресурсов разной ценности (например, resources = [1, 0.8, 1.5, 0.8, 1.2...]), я хочу поделиться ими с группой из N человек так, чтобы это было настолько справедливо, насколько это возможно (т.е. никто не заканчивает тем, что накапливает слишком большую ценность, в то время как другие слишком мало).

Полагаю, хорошим способом решения этой проблемы является минимизация функции: 

f(r1,...,rN) = (avg - r1)^2 + (avg - r2)^2 + ... + (avg - rN)^2

Где avg = sum(resources) / N и rx - ресурсы, назначенные человеку x.

Я наткнулся на scipy.optimize.minimize, и я думаю, что это может быть полезно, но я не могу понять, как описать ограничение, что значения r1, ..., rn не могут быть произвольными, а вместо этого должны быть взяты из resources (и таким образом, что один и тот же ресурс не предоставляется более чем одному человеку в решении), поскольку у меня нет ни опыта работы с этим модулем, ни достаточных математических знаний, применимых к решению проблем такого типа.

Есть ли простой способ решить эту проблему с помощью scipy?

1 Ответ

0 голосов
/ 22 июня 2019

Это обобщенный вариант проблемы разбиения (вариант оптимизации NP-hard).

Различия в вашем случае:

    1. вместо целых чисел вы получили реалы
    1. вы ищете n-way раздел
    1. у вас есть другая метрика потерь (квадратичная или линейная | l2-норма против l1-норма)

Теперь я, не колеблясь, скажу, что ваша проблема все еще NP-сложна, хотя при необходимости доказательства можно позаботиться о вышеупомянутых различиях (1. обычно легко в мягких условиях; например, в вашем случае: умножьте на 10 ; 2. легко 3. не уверен, как бы я справился с этим).

Начните с Статья на вики-разделе , в которой изложены основные результаты и подходы (вы увидите: между сложностью 2 раздела и n> 2 различие сложнее).

Поскольку это проблема дискретной оптимизации (например, сформулированная как двоичное квадратичное программирование), scipy не может предложить ничего с точки зрения хорошо выбранных подходов: например, нет (двоичное) целочисленное программирование.

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

...