В чём заключается комбинаторная задача о назначении?

Комбинаторная задача о назначениях заключается в поиске минимальной суммы дуг во взвешенном двудольном графе. 23

В наиболее общей форме задача формулируется так: имеется некоторое число работ и некоторое число исполнителей. 2 Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. 3 Нужно распределить работы так, чтобы выполнить их с минимальными затратами. 2

Пример: таксомоторная компания имеет три свободные машины (исполнители) и три заказчика (работы), желающих получить такси как можно быстрее. 3 Фирма заботится о времени доставки такси к заказчику, так что для каждой машины стоимость определяется временем, с которым машина доберётся до места ожидания, определённого заказчиком. 3 Решением задачи о назначениях будет распределение машин по заказчикам такое, что суммарная стоимость (суммарное время ожидания) минимальна. 3