Калькулятор задачи о назначениях (Венгерский метод)

Пошаговое решение задачи о назначениях венгерским методом: редукция строк и столбцов, покрытие нулей минимальным числом линий и оптимум.

3
Задача 1Задача 2Задача 3
Исполнитель 1
Исполнитель 2
Исполнитель 3
Дискретная оптимизация и двудольные графы

Задача о назначениях и Венгерский метод: Академическое руководство

Строгое математическое описание алгоритма Куна-Манкреса (Венгерского метода) для взвешенного паросочетания и минимизации затрат.

1. Какую задачу решает модель назначений?

Задача о назначениях — классическая модель дискретной оптимизации, в которой n исполнителей (рабочих, станков) должны быть распределены по n работам на взаимооднозначной основе (1 к 1). Для матрицы затрат C, где cᵢⱼ — стоимость выполнения работы j исполнителем i, требуется минимизировать суммарные затраты ∑ cᵢⱼ xᵢⱼ при условии ∑ xᵢⱼ = 1 по строкам и столбцам и xᵢⱼ ∈ {0, 1}. Венгерский метод решает данную задачу за строго полиномиальное время O(n³).

2. Алгоритм Венгерского метода (5 шагов)

Шаг 1: Редукция строк

В каждой строке находится минимальный элемент и вычитается из всех элементов данной строки. В каждой строке образуется хотя бы один ноль.

Шаг 2: Редукция столбцов

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

Шаг 3: Минимальное покрытие линиями

Все нули покрываются минимальным числом горизонтальных и вертикальных прямых. Если число линий равно n, найдено оптимальное назначение (переход к шагу 5). Если меньше n — переход к шагу 4.

Шаг 4: Модификация матрицы

Среди непокрытых элементов выбирается наименьший элемент k. Значение k вычитается из всех непокрытых элементов и прибавляется к элементам на пересечении двух линий. Возврат к шагу 3.

Шаг 5: Выбор оптимальных назначений

Выбираются n независимых нулей (не лежащих в одной строке или столбце). По исходной матрице вычисляется суммарная минимальная стоимость.

3. Разобранный пример: 4 исполнителя × 4 работы

Пошаговая редукция матрицы затрат 4×4 и сверка с результатом калькулятора.

Worker / MachineTask 1 (T₁)Task 2 (T₂)Task 3 (T₃)Task 4 (T₄)
Исполнитель 1 (W₁)9278
Исполнитель 2 (W₂)6437
Исполнитель 3 (W₃)5818
Исполнитель 4 (W₄)7694

А. Редукция строк (вычитание минимумов строк)

Стр. 1: min=2 → [7, 0, 5, 6] | Стр. 2: min=3 → [3, 1, 0, 4] | Стр. 3: min=1 → [4, 7, 0, 7] | Стр. 4: min=4 → [3, 2, 5, 0].

Б. Редукция столбцов (вычитание минимумов столбцов)

В столбце 1 минимум равен 3 → [4, 0, 1, 0]. Столбцы 2, 3 и 4 уже содержат нули и не меняются: Ст. 2 = [0, 1, 7, 2], Ст. 3 = [5, 0, 0, 5], Ст. 4 = [6, 4, 7, 0].

В. Покрытие нулей прямыми и проверка

Нулевые элементы: (W₁, T₂), (W₂, T₁), (W₂, T₃), (W₃, T₃), (W₄, T₁), (W₄, T₄). Минимальное число прямых для их покрытия равно 4 (= n). Оптимальное решение достигнуто сразу без дополнительных преобразований.

Assigned WorkerMatched TaskOriginal Cost
Исполнитель 1 (W₁)Работа 2 (T₂)2 ₽
Исполнитель 2 (W₂)Работа 1 (T₁)6 ₽
Исполнитель 3 (W₃)Работа 3 (T₃)1 ₽
Исполнитель 4 (W₄)Работа 4 (T₄)4 ₽

Итоговая минимальная стоимость

Общая стоимость Z* = 2 + 6 + 1 + 4 = 13 ₽. (Каждый исполнитель назначен на отдельную работу с минимальными глобальными затратами).

4. Частые ошибки при решении

⚠

Задачи максимизации без преобразования матрицы

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

⚠

Несбалансированные прямоугольные матрицы (m ≠ n)

Венгерский метод требует строго квадратной матрицы. При несовпадении размерностей добавляются фиктивные строки или столбцы с нулевыми тарифами.

⚠

Ошибки модификации матрицы на шаге 4

Величина k вычитается из непокрытых клеток и прибавляется ТОЛЬКО к элементам на пересечении двух линий; элементы, покрытые одной линией, не меняются.