Венгерский метод в excel

Обновлено: 07.07.2024

Привет, друзья! В этой статье хотел бы рассказать про интересный алгоритм из дисциплины «Исследование операций» а именно про Венгерский метод и как с его помощью решать задачи о назначениях. Немного затрону теории про то, в каких случаях и для каких задач применим данный алгоритм, поэтапно разберу его на мною выдуманном примере, и поделюсь своим скромным наброском кода его реализации на языке R. Приступим!

Пару слов о методе

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

Задача о назначении работников на должности. Необходимо распределить работников на должности так, чтобы достигалась максимальная эффективность, или были минимальные затраты на работу.
Назначение машин на производственные секции. Распределение машин так, чтобы при их работе производство было максимально прибыльным, или затраты на их содержание минимальны.
Выбор кандидатов на разные вакансии по оценкам. Этот пример разберем ниже.

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

Необходимое и достаточное условие решения задачи – это ее закрытый тип. Т.е. когда количество исполнителей = количеству работ (N=M). Если же это условие не выполняется, то можно добавить вымышленных исполнителей, или вымышленные работы, для которых значения в матрице будут нулевыми. На решение задачи это никак не повлияет, лишь придаст ей тот необходимый закрытый тип.

Step-by-step алгоритм на примере

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

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

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

(Если задача решается на минимум, то необходимо начинать с этого шага). Продолжаем решение далее. Редукция матрицы по строкам (ищем минимальный элемент в каждой строке и вычитаем его из каждого элемента соответственно):

Т.к. все минимальные элементы – нулевые, то матрица не изменилась. Проводим редукцию по столбцам:

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

Продолжаем решение дальше. Вычеркиваем строки и столбцы, которые содержат нулевые элементы (ВАЖНО! Количество вычеркиваний должно быть минимальным). Среди оставшихся элементов ищем минимальный, вычитаем его из оставшихся элементов (которые не зачеркнуты) и прибавляем к элементам, которые расположены на пересечении вычеркнутых строк и столбцов (то, что отмечено зеленым – там вычитаем; то, что отмечено золотистым – там суммируем; то, что не закрашено – не трогаем):

Как теперь видно, в каждом столбце и строке есть только один выбранный ноль. Решение задачи завершаем!

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

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

Реализация на языке программирования R

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

Данные для решения задачи берутся из файла example.csv который имеет вид:

Код добавил в спойлер ибо статья была бы слишком большой из-за него

Результат выполнения программы:

В завершение

Спасибо большое что потратили время на чтение моей статьи. Все используемые ссылки предоставлю ниже. Надеюсь, Вы узнали что-то для себя новое или обновили старые знания. Всем успехов, добра и удачи!

Пару слов о методе

Задача о назначении работников на должности. Необходимо распределить работников на должности так, чтобы достигалась максимальная эффективность, или были минимальные затраты на работу.
Назначение машин на производственные секции. Распределение машин так, чтобы при их работе производство было максимально прибыльным, или затраты на их содержание минимальны.
Выбор кандидатов на разные вакансии по оценкам. Этот пример разберем ниже.

Step-by-step алгоритм на примере

Т.к. все минимальные элементы – нулевые, то матрица не изменилась. Проводим редукцию по столбцам:

Как теперь видно, в каждом столбце и строке есть только один выбранный ноль. Решение задачи завершаем!

Реализация на языке программирования R

Данные для решения задачи берутся из файла example.csv который имеет вид:

Код добавил в спойлер ибо статья была бы слишком большой из-за него

Результат выполнения программы:

В завершение

Прочие статьи цикла

Задача выбора (назначения). Венгерский метод решения

Понятия и термины в задаче выбора

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

Постановка задачи выбора

Пусть каждый из П_i должностных лиц должен быть назначен на одну из Д_j должностей (следовательно, i, j = 1(1)n. ). Обозначим через d_ij производительность труда (эффект исполнения обязанностей) лица П_i в должности Д_j. Оптимальное назначение состоит в таком распределении претендентов (личного состава) по должностям, при котором суммарная производительность с эффектом деятельности будет наибольшей. Если xij =1, когда претендент П_i выступает в должности Д_j ; x_ij =0, в остальных случаях, то необходимо максимизировать функцию

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

Условие баланса в задаче выбора может быть записано в виде равенства m = n. В случае нарушения баланса m ≠ n необходимо добавит либо фиктивных претендентов (если m<n), либо фиктивные должности (если m >n). Задачу выбора можно решить одним из методов решения задач транспортного типа, например методом потенциалов, рассмотренным ранее. Однако специфический характер системы ограничений позволяет существенно упростить алгоритм решения задачи выбора. Один из упрощенных алгоритмов, разработанный венгерским математиком Я. Эгервари, получил наибольшее распространение и был назван в честь своего создателя "венгерским" способом. В основе этого способа используются, так называемые "эквивалентные" преобразования матрицы D_{[m, n]}. Две прямоугольные матрицы А_{[m, n]} и D_{[m, n]} одинаковой размерности m× n называются эквивалентными, если а_ij =d_ij +p_i + r_j, где p_i и r_j - некоторые произвольные действительные числа, [i=1(1)m; j=1(1)n]. Из последней формулы видно, что эквивалентное преобразование сводится к суммированию ко всем элементам любой строки или столбца одного и того же числа. Покажем, что оптимальные планы двух задач выбора, матрицы которых эквивалентны, совпадают. Пусть Х*_{[m, n]} - оптимальный план задачи выбора с матрицей ||a_ij||, элементы которой вычисляются по формуле суммы. По определению оптимального плана

Но суммы для p_i и r_j не зависят от выбранного плана, поэтому можно заключить, что план Х*_{[m, n]} минимизирует линейную форму задачи, т.е. является оптимальным для задачи выбора с эквивалентной матрицей ||d_ij||. Переход от одной матрицы к другой, ей эквивалентной, будем обозначать стрелкой ||d_ij|| → ||а_ij||. Приведем структурно-логическую схему алгоритма венгерского способа, которая включает предварительный этап и три этапа вычислений. Ниже рассмотрим эти этапы.

Структурно-логическая схема алгоритма венгерского метода решения задачи выбора

1. Предварительный этап состоит из определения начального (исходного) плана и соответствующего ему выбора, а также эквивалентного преобразования матрицы ||d_ij||. При этом под "выбором" будем понимать множество элементов d_ij, соответствующих х_ij = 1. Эти элементы условимся обозначать d*_ij.

Пример 1. Пусть заданы матрицы D_[3,3], и план Х_[3,3] для плана необходимо определить выбор, соответствующий плану.

Решение: Искомый выбор получаем при выписывании элементов матрицы D_[3,3], отвечающих х_ij = 1. Этот выбор получает вид d₁₁ = 0; d₂₃ = 5; d₃₂ = 0. Начальный план задачи выбора может быть построен тем же способом, что и в транспортной задаче общего вида, причем способ северо-западного угла здесь вырождается в диагональный способ, при котором х_ij = δ_ij = 1 при i = j; х_ij = δ_ij = 0 при i≠ j; δ_ij - дискретная дельта-функция или символ Кронекера.

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

2. Сущность первого этапа заключается в проверке всех элементов выбора d_ij эквивалентной матрицы, полученной на предварительном этапе. Если все d_ij = 0, то план оптимален и ему соответствует наибольшее значение линейной формы Q*= 0 (при любом другом плане это значение будет отрицательным). Если же некоторые d_ij < 0, то значение функции цели можно увеличить путем перехода на 2-м этапе к новому улучшенному плану.

3. Основным содержанием 2-го этапа. является переход к новому опорному плану, для которого значение линейной формы больше. С этой целью по следующему правилу строится так называемая цепочка пересчета:
- начальным узлом цепочки назначается любой ненулевой элемент выбора d'_ij ≠ 0;
- в качестве следующего узла цепочки выбирается нуль в строке d'_ij; и т. д.

Цепочка пересчета построенная на 2-м этапе, может оказаться либо замкнутой, либо разомкнутой. Если цепочка замкнута, то необходимо перейти к новому выбору (а, следовательно, и к новому плану) путем включения в него нулей и исключения ненулевых элементов замкнутой цепочки. В противном случае, когда цепочка пересчета оказалась незамкнутой, следует перейти к 3-му этапу.

4. Сущность третьего этапа состоит в том, что путем эквивалентного преобразования матрицы число нулей возрастает, но при этом по возможности сохраняются нули незамкнутой цепочки, построенной на предыдущем этапе. Чтобы добиться этого, необходимо из строк, содержащих элементы выбора в граничных клетках незамкнутой цепочки пересчета, вычесть максимальные элементы этих же строк. Затем эти же элементы следует добавить к столбцам, содержащим нули незамкнутой цепочки (тем самым общее число нулей в цепочке останется прежним). После завершения 3-го этапа необходимо (в соответствии со структурно-логической схемой алгоритма) вернуться к 1-му этапу, т.е. снова проверить полученный план на оптимальность.

Пример 2. Рассмотрим методику решения венгерским способом одной из распространенных задач, получившей название "задачи о назначениях". Предположим, что на предприятие возникли 4 вакансии В_j, j =1(1)4 на сходные должности. По объявлению о наборе специалистов подали заявление 4-ро претендентов С_i, i =1(1)4.

Предприятие заинтересовано в наиболее рациональном использовании специалистов, поэтому перед назначением они были проверены компетентной комиссией, определившей (методом экспертных оценок) ту условную прибыль d_ij, которую предприятие получит, если i-й специалист будет назначен на j-ю должность (i,j = 1(1)4 ).

Значения d_ij, установленные комиссией, приведены в матрице D_[4,4], а вид решения задается матрицей Х*_[4,4]

Необходимо найти оптимальный план распределения специалистов, при котором они смогут обеспечить предприятию наибольшую прибыль.

Решение. В соответствии с алгоритмом (см. схему) решение задачи заключается в ряде последовательных эквивалентных преобразований матрицы ||d_ij||. Будем исходный план выбирать способом северо-западного угла, а числа p_i и r_j, с помощью которых осуществляются преобразования, записывать около соответствующей строки или столбца матрицы. Тогда цепочка преобразований будет выглядеть следующим образом:

Цепочки в матрицах обозначены пунктиром со стрелками указывающими направление переходов между элементами матриц

Заключение

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

С помощю этого онлайн калькулятора можно решить задачу о назначениях (задачу о выборе) венгерским методом. Для решения задачи о назначениях задайте размерность матрицы, выберите из вариантов "максимальная прибыль" и "минимальные расходы". Затем введите данные в ячейки и нажимайте на кнопку "Вычислить". Теоретическую часть смотрите ниже.

Предупреждение

Задача о назначениях − теория

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

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

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

При решении задачи о назначениях применяется венгерский метод, что существенно упрощает решение задачи.

Венгерский метод

Сделаем несколько определений.

1. Нулевые элементы квадратной матрицы S будем называть независимыми нулями , если столбец и строка, в которых находится данный нулевой элемент не содержат другого нулевого элемента.

2. Две прямоугольные матрицы и порядка mxn называются эквивалентными, если , , .

Решение задачи имеет подголовительную и итерационную части.

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

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

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

Вариант 1. Строка, содержащая невыделенный нуль содержит также нуль со звездой. В этом случае ставим над найденным нулем знак °, выделяем строку, содержащую этот нуль, снимаем выделение из столбца, на пересечении которой с только что выделенной строкой находится нуль со звездой. Далее, если обнаруживается невыделенный нуль, переходим к этапу 1. Если невыделенных нулей нет, то переходим к этапу 3.

Вариант 2. Строка, содержащая невыделенный нуль не содержит нуль со звездой. В этом случае отмечаем этот нуль знаком ° и переходим к этапу 2.

Этап 2. Исходя из нуля со знаком °, в строке которой нет нуля со звездой (вариант 2) строим следующую цепочку элементов матрицы C: Исходный 0° − 0* (лежащий в одном столбце (если существует)) − 0° (лежащей в одной строке с предшествующим 0* и т.д. Цепочка имеет вид 0°−0*−0°−. и обязательно заканчивается 0°. Там, где 0°, заменяем на 0*, а на четных позициях уничтожаем знак * над нулями. Далее уничтожаем все ° над нулями и снимаем выделения из столбцов и строк. Число независимых нулей увеличился на единицу. Переходим к этапу 1.

Этап 3. К этому этапу переходим после завершения этапа 1, когда независимых нулей нет.

Среди невыделенных элементов находим минимальный q>0. Далее величину q вычитаем из всех элементов матрицы C расположенных на невыделенных строках, и прибавляем ко всем элементам на выделенных столбцах (можно и так: величину q вычитаем из всех невыделенных элементов матрицы C и прибавляем ко всем элементам, находящимся на пересечении выделенных строк и столбцов). В полученной матрице появятся невыделенные нули поэтому переходим к этапу 1.

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

Читайте также: