Задача о назначениях

В коммерческой сфере возникают задачи, связанные с необходимостью выбора такого варианта распределения ресурсов (трудовых, финансовых, товарных, энергетических, материальных, природных и других по некоторым объектам-магазинам, городам, предприятиям, цехам и т. п.), который обеспечил бы минимальные издержки(затраты денег, времени) или максимальные прибыль и доход.

Так, например, всегда актуальной является проблема формирования трудового коллектива, обеспечивающего желаемую эффективность.

Рассматриваемая задача является типовой задачей экономики труда, так как с её помощью можно получить ответы на следующие вопросы: «Как наилучшим образом распределить экипажи самолётов по маршрутам?», «Как назначить людей на различные должности?» (отсюда и название задачи) и т.д.

В такой постановке данная задача относится к классу комбинаторных. Количество возможных вариантов назначений равно n!, и решение задачи путём прямого перебора невозможно при достаточно больших значениях n. Для нахождения оптимального варианта применяют специальные комбинаторные алгоритмы, в частности, при решении задачи вручную эффективен так называемый венгерский метод.

Как задача линейного программирования, задача о назначениях относится к классу задач дискретного программирования, в которых переменные могут принимать лишь одно из двух значений: 0 или 1 (так называемое булево линейное программирование). Если целевая функция будет стремиться к минимуму, то задачу можно рассматривать как частный случай транспортной задачи, когда каждого работника можно рассматривать как поставщика с помощью 1, а каждую работу-как потребителя с той же мощностью. При таком подходе задачу о назначениях можно решать с помощью алгоритмов решения закрытой транспортной задачи.

Если количества работников и работ не совпадают, то задача о назначениях является открытой. В экономико-математической модели открытой задачи о назначениях ограничения имеют вид неравенств типа «меньше или равно», в связи с чем такую задачу можно решать теми же методами, что и открытую транспортную задачу.