ВЕНГЕРСКИЙ МЕТОД: ИЗ ЧЕГО ОН СОСТОИТ, ПРИМЕР - ДУДАС - 2025

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

Проблема распределения - это особый тип задач линейного программирования, цель которого - минимизировать стоимость или время выполнения ряда заданий несколькими людьми.

Источник: pixabay.com

Одна из важных характеристик проблемы распределения заключается в том, что машине (или проекту) назначается только одно задание (или работник).

Этот метод был разработан венгерским математиком Д. Кенигом. По этой причине он известен как венгерский метод решения задач присваивания. Он также известен как алгоритм распределения Куна-Мункреса.

Любую проблему распределения можно легко решить, применив этот метод, который состоит из двух этапов:

- На первом этапе выполняются сокращения строк и столбцов.

- На втором этапе решение оптимизируется на итерационной основе.

Что такое венгерский метод?

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

Квадратная матрица порядка n на n считается входными данными, которые должны содержать только неотрицательные элементы.

Для данной задачи, если количество строк в матрице не равно количеству столбцов, в зависимости от случая необходимо добавить фиктивную строку или фиктивный столбец. Затраты на выделение этих фиктивных ячеек всегда равны нулю.

Шаг 1: вычтите минимумы каждой строки

Для каждой строки в массиве выбирается элемент с наименьшим значением и вычитается из каждого элемента в этой строке.

Шаг 2: вычтите минимум из каждого столбца

Точно так же элемент с наименьшим значением выбирается для каждого столбца и вычитается из каждого элемента в этом столбце.

Шаг 3: закройте все нули минимальным количеством строк

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

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

В противном случае, если для покрытия всех нулей в массиве требуется менее n строк, переходите к шагу 4.

Шаг 4: создайте лишние нули

Выбирается наименьший элемент матрицы (называемый k), который не покрывается одной из строк, созданных на шаге 3.

Значение k вычитается из всех элементов, не покрытых линиями. Впоследствии значение ka добавляется ко всем элементам, которые покрываются пересечением двух линий.

Пункты, выделенные одной строкой, оставляются как есть. После выполнения этого шага вы вернетесь к шагу 3.

Оптимальное размещение

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

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

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

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

пример

Давайте рассмотрим компанию, в которой четыре вида деятельности (A1, A2, A3, A4) должны выполняться четырьмя работниками (T1, T2, T3, T4). Каждому работнику должно быть назначено одно действие.

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

Шаг 1: вычтите минимумы каждой строки

Вы начинаете с вычитания элемента с минимальным значением в каждой строке из других элементов в этой строке. Например, наименьший элемент в первой строке - 69. Следовательно, 69 вычитается из каждого элемента в первой строке. Результирующая матрица:

Шаг 2: вычтите минимум из каждого столбца

Таким же образом элемент с минимальным значением каждого столбца вычитается из других элементов этого столбца, получая следующую матрицу:

Шаг 3: закройте все нули минимальным количеством строк

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

Поскольку количество требуемых строк равно трем и меньше размера матрицы (n = 4), мы продолжаем с шага 4.

Шаг 4: создайте лишние нули

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

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

Шаг 3 (повторить)

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

Поскольку количество требуемых строк равно 4, что равно размеру матрицы (n = 4), у нас есть оптимальное распределение между нулями в матрице. Следовательно, алгоритм останавливается.

Оптимальное размещение

Как показывает метод, выбор из следующих нулей соответствует оптимальному назначению:

Такой выбор нулей соответствует следующему оптимальному распределению в исходной матрице затрат:

Следовательно, работник 1 должен выполнять действие 3, работник 2, действие 2, работник 3, действие 1, а работник 4 должен выполнять действие 4. Общая стоимость этого оптимального задания составляет 69 + 37 + 11 + 23 = 140.

Ссылки

1. Венгерский алгоритм (2019). Венгерский алгоритм. Взято с сайта hungarianalgorithm.com.
2. Исследование (2019). Использование венгерского алгоритма для решения задач о назначении. Взято с сайта study.com.
3. Мудрость Джобс (2018). Венгерский метод решения проблемы назначения - количественные методы управления. Взято с: wisdomjobs.com.
4. Гики для гиков (2019). Венгерский алгоритм для задачи присваивания. Взято с: geeksforgeeks.org.
5. Карли Мур, Натан Лэндман (2019). Венгерский алгоритм максимального соответствия. Brilliant. Взято с сайта brilliant.org.