Задача назначений
Зада́ча назначе́ний, задача поиска такого распределения работ по исполнителям (работникам, машинам и т. п.), при котором получается наибольший эффект. Точнее, пусть имеется вакантных должностей (работ), на которые претендуют работников, . Эффективность -го претендента на -ю должность задаётся величиной . Требуется назначить на каждую должность работника (из числа претендентов) так, чтобы общая эффективность назначений была максимальной. В наиболее известном варианте задачи назначений .
В задаче назначений обычно вводятся переменные , которые принимают значение 1 в случае назначения -го претендента на -ю должность и 0 в противном случае, тогда задача назначений формализуется следующим образом:
Эта задача является задачей целочисленного линейного программирования и решается методами, разработанными в этом разделе математики.