Статья:

Использование Венгерского метода для решения задачи о назначениях

Конференция: LXXXV Студенческая международная научно-практическая конференция «Молодежный научный форум»

Секция: Физико-математические науки

Выходные данные
Гребенников Д.С., Логачев А.А. Использование Венгерского метода для решения задачи о назначениях // Молодежный научный форум: электр. сб. ст. по мат. LXXXV междунар. студ. науч.-практ. конф. № 16(85). URL: https://nauchforum.ru/archive/MNF_interdisciplinarity/16(85).pdf (дата обращения: 11.08.2020)
Лауреаты определены. Конференция завершена
Эта статья набрала 82 голоса
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Использование Венгерского метода для решения задачи о назначениях

Гребенников Дмитрий Сергеевич
студент, Самарский национальный исследовательский университет имени Академика С.П. Королева, РФ, Самара
Логачев Артем Алексеевич
студент, Самарский национальный исследовательский университет имени Академика С.П. Королева, РФ, Самара
Додонова Наталья Леонидовна
научный руководитель, к.ф.-м.н., доцент, Самарский национальный исследовательский университет имени Академика С.П. Королева, РФ, Самара

 

Введение

Оптимизация процессов является неотъемлемым этапом формирования любого предприятия. Использование Венгерского метода позволяет существенно упростить рационализацию затрат с целью получения максимальной прибыли предприятия.

Основные задачи исследования:

1. Обзор литературы

2. Реализация алгоритма задачи о назначениях

3. Варианты практического применения данного алгоритма.

В первую очередь рассмотрим понятие Венгерского метода. Данный метод является алгоритмом для оптимизации, который используется для решения задачи о назначениях за полиномиальное время. Был создан известным американским математиком Гарольдом Куном в 1955 году. Название “Венгерский алгоритм” получил по причине того, что данный алгоритм брал за основу работы венгерских математиков: Денеш Кёниг и Эгервари Эйген.

Описание алгоритма в виде матричной интерпретации

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

 

Рисунок 1. Исходные данные

 

Первым этапом будет нахождение максимальной оценки во всех строках таблицы. Затем нужно значение оценки минусовать из всех элементов строки. После умножаем всю таблицу на (-1).

 

Рисунок 2. Иллюстрация вычисления первого этапа

 

Рисунок 3. Результат вычислений первого этапа

 

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

 

Рисунок 4. Нахождение нулей в каждой строке

 

Рисунок 5. Нахождение минимального элемента в строке/столбце и вычитание его из элементов строки/столбца

 

Затем нужно определить нули так же, как мы делали на первом этапе:

 

Рисунок 6. Нахождение нулей

 

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

 

Рисунок 7. Последний этап

 

В итоге получаем матрицу, показывающую самое эффективное распределение задач по исполнителям.

 

Рисунок 8. Итоговая матрица

 

Практическое применение

  • Задача о распределении должностей между работниками компании. Достижение максимальной эффективности и минимальных затрат при распределении должностей
  • Отбор кандидатов на различные должности по определенным критериям эффективности.
  • Рационализация автомобильного производства. Распределение производственного конвейера для снижения затрат на содержание.
  • И многие другие.

 

Список литературы:
1. Диниц Е.А., Крондрл М.А. Один алгоритм решения задачи о назначении. / ДАН.-2009. - Т. 189. - №1. - С. 23-25.
2. Карлин С. Математические методы в теории игр, программирования и экономике. - М.: Мир, 1964.
3. Ершов В.А., Ирбенек А.С. Алгоритм решения задачи назначения на матрицах специального вида. - М., 1981. - 20 с. (Препр. Ин-т точн. Механ. и вычислит. техн. Им. С.А. Лебедева; №4).