Венгерский метод - что это такое, определение и понятие
Венгерский метод - это алгоритм, позволяющий минимизировать затраты в задаче оптимизации на основе линейного программирования.
Цель венгерского метода - найти минимальную стоимость набора задач, которые должны выполняться наиболее подходящими людьми.
Он использует линейное программирование (PL) для выполнения ряда шагов, которые можно автоматизировать. Таким образом, такие инструменты, как статистическое программное обеспечение R (среди прочего), имеют несколько очень полезных пакетов для решения этих задач оптимизации.
Происхождение венгерского метода
Его создателем был венгерский математик (отсюда и название) Гарольд В. Кун в 1955 году. Другой математик, Джеймс Мункрес, пересмотрел его в 1957 году. Благодаря этому развитию он получил другие названия, такие как алгоритм распределения Мункреса или Куна-Мункреса.
С другой стороны, этот метод имеет прецедент у двух авторов, Денеса Кенига и Йену Эгервари, евреев и венгров. Первый разработал теорию графов, на которой основан этот алгоритм. Вторая обобщила теорему Кенига и позволила Куну развить метод.
Шаги венгерского метода
Следующие шаги позволяют простым способом реализовать венгерский метод с использованием электронной таблицы. Кроме того, эта схема, которую мы показываем, позволит нам глобально увидеть процесс, который мы подробно разработаем в последнем примере.
- В качестве предварительных шагов вам необходимо назначить людей (строки) в серию проектов (столбцов). Кроме того, необходимо рассчитать различные затраты на каждый проект в зависимости от того, кто его выполняет, и построить матрицу (C) с этой информацией.
- В матрице (C) ищем минимальное значение каждой строки. Мы вычитаем это из всех элементов в строке и выполняем ту же операцию со столбцами. Появится новая матрица (C`) с результатами предыдущих операций.
- Далее мы создаем «граф равенств», который позволяет нам выбирать задачи и проекты с наименьшими затратами. Оптимальными будут те элементы, результат которых равен нулю. Если верно, что нет элемента с нулевым значением, присвоенным более чем одной строке, алгоритм завершается.
- В противном случае необходимо выполнить новое назначение. Создается новая матрица, к которой применяется ряд модификаций, как мы увидим в примере. Мы воссоздаем граф и продолжаем до тех пор, пока не получим матрицу, которая имеет хотя бы один ноль в каждой строке и в неповторяющихся позициях.
- С этой информацией у нас уже есть назначенные (нули) люди и проекты, которые оптимизируют проблему. Если задача уже назначена в предыдущей строке, она отбрасывается в следующей. Чтобы вычислить минимальную стоимость, мы складываем затраты исходной матрицы, которые появляются в позиции этих нулей.
Пример венгерского метода
Давайте посмотрим на простой пример венгерского метода. Представим, что у нас есть трое рабочих, и их нужно назначить на три проекта. Мы создаем исходную матрицу (C) и значения стоимости в каждой ячейке. Для этого необходимо использовать информацию, имеющуюся в компании. Как только у нас есть все это, мы начинаем процесс. Электронная таблица может помочь.
Мы вычисляем минимумы каждой строки и вычитаем их из элементов этой строки и делаем то же самое со столбцами (шаги 1 и 2). В получившейся матрице (C`) мы проводим линии таким образом, чтобы они покрывали все нули и, в свою очередь, пересекали друг друга (шаг 3). Мы видим, что есть две строки, но наибольшее значение количества строк или столбцов равно трем. Мы должны продолжать.
Теперь выбираем наименьшее из непокрытых чисел, в данном примере это два (темно-синий). Вычитаем его из предыдущих и добавляем к тем, что расположены там, где линии пересекаются. В нашем случае это еще два (E3, T1). Остается новая матрица (шаг 4). Перерисовываем линии и считаем. Есть три строки, такие же, как количество строк или столбцов. Алгоритм закончен.
Начнем со строки или столбца с наименьшим количеством нулей (E1, T1). Если задача уже назначена, ее нельзя переназначить, например, с E2 нельзя использовать первый ноль T1, так как эта задача была назначена E1. Общая стоимость в венгерском методе будет равна сумме затрат исходной матрицы (шаг 1), расположенной в той же позиции, что и выбранные нули (шаг 5).
