Алгоритм оптимизации открытого пространства

Question

В результате изменений в компании, мы должны изменить план сидения: одна комната с 10 столами в ней.Некоторые столы более популярны, чем другие по ряду причин.Одним из решений было бы нарисовать номер стола из шляпы.Мы думаем, что есть лучший способ сделать это.

У нас 10 рабочих мест и 10 человек.Давайте дадим каждому человеку в этом конкурсе 50 гипотетических жетонов для участия в торгах на столах.Нет предела, сколько вы ставите на одном столе, вы можете поставить все 50, что будет означать: «Я хочу сидеть только здесь, точка».Вы также можете сказать «Мне все равно», дав каждому столу по 5 жетонов.

Важное замечание: никто не знает, что делают другие люди.Каждый должен решать, основываясь только на его / ее наилучших интересах (звучит знакомо?)

Теперь предположим, что мы получили следующие гипотетические результаты:

#  | Desk# >| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
1  | Alise  | 30 | 2  | 2  | 1  | 0  | 0  | 0  | 15 | 0  | 0  | = 50
2  | Bob    | 20 | 15 | 0  | 10 | 1  | 1  | 1  | 1  | 1  | 0  | = 50
   ...
10 | Zed    | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | = 50

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

Поскольку нас всего 10 человек, я думаю, что мы можем перебором, изучая все возможные конфигурации, но мне было интересно, есть ли лучший алгоритм для решения такого рода проблем?

Answer 1

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

В вашем случае вы можете использовать cost = 50 - bid и использовать вышеизложенное (любое решение проблемы назначения).

Answer 2

Еще быстрее, если у вас есть Excel, у вас должна быть также доступна версия SOLVER.Просто установите матрицу ставок (10x10 с предложениями), матрицу назначений (10x10 с назначениями 0/1), используйте sumproduct (ставки, назначения), чтобы рассчитать значение назначения, сделайте его целевой функцией и добавьте ограничения, чтобытолько одно назначение людей на столы и столы для людей.Убедитесь, что у вас установлен флажок «> линейная модель», «предположите, что он не отрицательный», и решите проблему!Я только что установил пример проблемы 10х10 - похоже, работает нормально.