Оптимизировать распределение рабочих мест специалистам, с макс. количество рабочих мест на одного эксперта

Question

У меня есть группа «экспертов» (около 300), которые могут выполнять работу. И у меня есть множество рабочих мест, которые нужно сделать, скажем, около 500 из них. У меня также есть информация, как «хороший» один эксперт сможет выполнить определенную работу. Что привело бы к матрице размером 300 х 500, содержащей весовые коэффициенты.

Я бы хотел найти «оптимальное» распределение рабочих мест для экспертов. Но с ограничением, что один специалист должен получить только максимальное количество заданий.

У меня есть общие основы в алгоритмах оптимизации, но я понятия не имею, как смоделировать такую ​​фиксированную дискретную верхнюю границу. Кто-нибудь знает класс алгоритмов, который может справиться с такими вопросами?

Answer 1

Попробуйте моделировать его как проблему с минимальной стоимостью сетевого потока.

Добавить узел для каждого человека.

Добавление узла для каждого задания с требованием 1.

Добавить границу между каждым человеком и каждой работой с емкостью 1 и со стоимостью в соответствии с вашей матрицей.

Добавить узел источника с требованием, равным (минус) количеству заданий.

Добавить границу между источником и каждым человеком в зависимости от количества заданий, которые они могут выполнять.

Решить для максимального потока затрат (например, путем умножения затрат на -1 и используя min_cost_flow из NetworkX)

Ответ на this question дает код Python для аналогичной задачи.