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