Калькулятор задачи о назначениях (Венгерский метод)
Пошаговое решение задачи о назначениях венгерским методом: редукция строк и столбцов, покрытие нулей минимальным числом линий и оптимум.
| Задача 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 шагов)
В каждой строке находится минимальный элемент и вычитается из всех элементов данной строки. В каждой строке образуется хотя бы один ноль.
В каждом столбце редуцированной матрицы находится минимальный элемент и вычитается из элементов столбца, обеспечивая наличие нулей во всех столбцах.
Все нули покрываются минимальным числом горизонтальных и вертикальных прямых. Если число линий равно n, найдено оптимальное назначение (переход к шагу 5). Если меньше n — переход к шагу 4.
Среди непокрытых элементов выбирается наименьший элемент k. Значение k вычитается из всех непокрытых элементов и прибавляется к элементам на пересечении двух линий. Возврат к шагу 3.
Выбираются n независимых нулей (не лежащих в одной строке или столбце). По исходной матрице вычисляется суммарная минимальная стоимость.
3. Разобранный пример: 4 исполнителя × 4 работы
Пошаговая редукция матрицы затрат 4×4 и сверка с результатом калькулятора.
| Worker / Machine | Task 1 (T₁) | Task 2 (T₂) | Task 3 (T₃) | Task 4 (T₄) |
|---|---|---|---|---|
| Исполнитель 1 (W₁) | 9 | 2 | 7 | 8 |
| Исполнитель 2 (W₂) | 6 | 4 | 3 | 7 |
| Исполнитель 3 (W₃) | 5 | 8 | 1 | 8 |
| Исполнитель 4 (W₄) | 7 | 6 | 9 | 4 |
А. Редукция строк (вычитание минимумов строк)
Стр. 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 Worker | Matched Task | Original 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 вычитается из непокрытых клеток и прибавляется ТОЛЬКО к элементам на пересечении двух линий; элементы, покрытые одной линией, не меняются.