Аннотация. Эффективное распределение задач между исполнителями является одной из классических задач прикладной математики. В данной работе рассмотрено применение венгерского метода для решения задачи назначения, где необходимо минимизировать суммарные затраты на выполнение набора задач. В качестве исходных данных использовалась матрица стоимостей, сформированная на основе условного примера производственного подразделения. Алгоритм был реализован вручную в табличном виде и дополнительно проверен в среде Python. Были рассчитаны оптимальное распределение, общая стоимость выполнения работ и метрики эффективности, такие как экономия относительно произвольного распределения.

Ключевые слова: задача назначения; венгерский метод; оптимизация; матрица стоимостей; распределение ресурсов.

Классическая задача назначения состоит в том, чтобы назначить каждому исполнителю по одной задаче так, чтобы суммарные затраты были минимальными. Подобные задачи встречаются в логистике, планировании проектов, распределении ресурсов и других областях [1 – 2]. Для их решения применяется венгерский метод, предложенный в середине XX века, который является полиномиальным алгоритмом и используется в практике до настоящего времени [3 – 4].

В исследовании использовалась условная матрица стоимостей размером 4×4, где строки соответствовали исполнителям, а столбцы — задачам. На первом этапе вручную в Excel были выполнены операции вычитания минимальных значений по строкам и столбцам для приведения матрицы к нормализованному виду. Далее была проведена процедура покрытия нулями минимального числа строк и столбцов, а затем построено оптимальное назначение. В результате удалось распределить все задачи между исполнителями при минимальной суммарной стоимости. Для проверки решения использовалась реализация алгоритма на Python, что позволило подтвердить оптимальность полученного распределения.

Результаты показали, что суммарные затраты после оптимизации составили 124 условные единицы, тогда как при случайном распределении они достигали 178. Таким образом, экономия составила 30,3 %. Дополнительно было рассчитано среднее значение затрат на задачу и коэффициент вариации, который оказался равен 9 %, что говорит о равномерности нагрузки после оптимизации.

Рисунок 1. Сравнение суммарных затрат до и после применения венгерского метода