Двухстороннее сопоставление с делимыми задачами

Question

Я пытаюсь решить проблему с заданием, где делятся и задачи, и человеческие часы.

например, у человека X есть 4 часа в день, он может выполнить 1/3 задачи A за 2 часа, 1/4 задачи B за 4 часа. Человек Y, имеющий 10 часов, может выполнить 1/5 задачи A за 1,3 часа, 1/8 задачи B за 6 часов. Есть ли расширение соответствия BiPartite, которое может решить эту проблему?

Спасибо!

Answer 1

Я не думаю, что вы можете легко смоделировать это как двустороннее соответствие. Однако, должно быть довольно легко создать линейную программу для вашей задачи. Просто имейте для каждого работника набор переменных x_{i,j}, который указывает, сколько времени у меня уходит на задачу j.

Пусть h_i будет количеством часов, доступным для человека i. Тогда, для каждого человека я должен держать это

Пусть a_{i,j} будет "эффективностью" человека i в задаче j, т. Е. Сколько работы человек может выполнить за один час. Тогда для каждой задачи j она должна содержать следующее:

Вот и все. Нет ограничений целостности или что-нибудь.