35. Постановка и экономическая интерпретация задачи о назначениях

При решении некоторых задач менеджмента приходится назначать исполнителей (людей, механизмы и т.п.) для выполнения некоторых однотипных работ. При этом дополнительно известны значения сij – эффективность (неэффективность) выполнения i-м исполнителем j-ой работы. Требуется распределить исполнителей по работам таким образом, чтобы максимизировать (минимизировать) суммарный критерий эффективности (неэффективности) выполнения всех работ. 
Данная задача носит название «задача о назначениях» и является частным случаем более общей транспортной задачи. Если число исполнителей равно числу выполняемых работ, то такая задача является сбалансированной, в противном случае – не сбалансированной. 
В случае сбалансированной задачи о назначениях выполняются два условия: каждый исполнитель выполняет только одну работу и каждая работа выполняется только одним исполнителем. Для решения сбалансированной задачи о назначениях можно предложить следующий простой алгоритм: на каждом шаге назначений, начиная с первого исполнителя, выбирать самого эффективного (неэффективного). 
Однако такой способ решения, при всей кажущейся очевидности, не приводит, как правило, к получению оптимального решения: выбор на первых шагах самых эффективных (неэффективных) исполнителей заставляет нас на последних шагах алгоритма выполнять назначения, которые вносят негативный вклад в суммарный критерий.