Método húngaro: o que é, exemplo

O método húngaro é um algoritmo usado em problemas de alocação quando você deseja minimizar o custo. Ou seja, é usado para encontrar o custo mínimo designando várias pessoas para várias atividades com base no menor custo. Cada atividade deve ser atribuída a uma pessoa diferente.

Um problema de atribuição é um tipo especial de problema de programação linear, em que o objetivo é minimizar o custo ou o tempo de conclusão de vários trabalhos por várias pessoas.

Método húngaro: o que é, exemplo 1

Fonte: pixabay.com

Uma das características importantes do problema de atribuição é que apenas um trabalho (ou trabalhador) é atribuído a uma máquina (ou projeto).

Este método foi desenvolvido pelo matemático húngaro D. Konig. Por esse motivo, é conhecido como método húngaro para problemas de atribuição. Também é conhecido como algoritmo de atribuição Kuhn-Munkres.

Qualquer problema de atribuição pode ser facilmente resolvido aplicando este método que consiste em duas fases:

– Com a primeira fase, são feitas reduções de linha e coluna.

– Na segunda fase, a solução é otimizada de forma iterativa.

Qual é o método húngaro?

O método húngaro consiste em quatro etapas. As duas primeiras etapas são executadas apenas uma vez, enquanto as etapas 3 e 4 são repetidas até que uma atribuição ideal seja encontrada.

É considerado como entrada para uma matriz quadrada da ordem n por n, que deve conter apenas elementos não negativos.

Para um determinado problema, se o número de linhas na matriz não for igual ao número de colunas, uma linha fictícia ou uma coluna fictícia deverá ser adicionada, dependendo do caso. Os custos de alocação para essas células simuladas são sempre atribuídos como zero.

Etapa 1: subtrair os mínimos de cada linha

Para cada linha da matriz, o elemento com o valor mais baixo é selecionado e subtraído de cada elemento nessa linha.

Etapa 2: subtrair os mínimos de cada coluna

Da mesma forma, o elemento com o valor mais baixo é selecionado para cada coluna e subtraído de cada elemento nessa coluna.

Etapa 3: cubra todos os zeros com um número mínimo de linhas

Todos os zeros na matriz resultantes da etapa 2 devem ser cobertos usando um número mínimo de linhas horizontais e verticais, por linhas ou colunas.

Se um total de n linhas for necessário para cobrir todos os zeros, com n sendo igual ao tamanho n por n da matriz, uma alocação ideal será feita entre os zeros e, portanto, o algoritmo será interrompido.

Caso contrário, se menos de n linhas forem necessárias para cobrir todos os zeros na matriz, continue na etapa 4.

Etapa 4: criar zeros adicionais

O menor elemento da matriz (chamado k) que não é coberto por uma das linhas feitas na etapa 3 é selecionado.

O valor de k é subtraído de todos os elementos que não são cobertos por linhas. Posteriormente, o valor de ka é adicionado a todos os elementos que são cobertos pela interseção de duas linhas.

Os itens cobertos por uma única linha são deixados como estão. Depois de executar esta etapa, retorne à etapa 3.

Alocação ideal

Depois que o algoritmo é parado na etapa 3, um conjunto de zeros é escolhido para que cada linha e cada coluna tenha apenas um zero selecionado.

Se nesse processo de seleção não houver um único zero em uma linha ou coluna, um desses zeros será escolhido. Os zeros restantes nessa coluna ou linha são eliminados, repetindo o mesmo para as outras atribuições.

Se não houver uma única alocação de zeros, significa que existem várias soluções. No entanto, o custo permanecerá o mesmo para os diferentes conjuntos de atribuições.

Qualquer linha ou coluna fictícia adicionada foi excluída. Os zeros escolhidos nesta matriz final correspondem à alocação ideal necessária na matriz original.

Exemplo

Considere uma empresa em que há quatro atividades (A1, A2, A3, A4) que devem ser realizadas por quatro trabalhadores (T1, T2, T3, T4). Uma atividade deve ser atribuída por trabalhador.

A matriz a seguir mostra o custo de atribuir um trabalhador específico a uma determinada atividade. O objetivo é minimizar o custo total da tarefa composta por essas quatro atividades.

Método húngaro: o que é, exemplo 2

Etapa 1: subtrair os mínimos de cada linha

Começa subtraindo o elemento com o valor mínimo de cada linha dos outros elementos dessa linha. Por exemplo, o menor elemento na primeira linha é 69. Portanto, 69 de cada elemento na primeira linha é subtraído. A matriz resultante é:

Método húngaro: o que é, exemplo 3

Etapa 2: subtrair os mínimos de cada coluna

Da mesma forma, o elemento com o valor mínimo de cada coluna é subtraído dos outros elementos dessa coluna, obtendo a seguinte matriz:

Método húngaro: o que é, exemplo 4

Etapa 3: cubra todos os zeros com um número mínimo de linhas

O número mínimo de linhas (horizontais ou verticais) necessárias para cobrir todos os zeros na matriz será agora determinado. Todos os zeros podem ser cobertos usando 3 linhas:

Método húngaro: o que é, exemplo 5

Como o número de linhas necessárias é três e é menor que o tamanho da matriz (n = 4), a etapa 4 continua.

Etapa 4: criar zeros adicionais

O menor elemento não coberto pelas linhas é selecionado, cujo valor é 6. Esse valor é subtraído de todos os elementos não cobertos e esse mesmo valor é adicionado a todos os elementos cobertos pela interseção de duas linhas. Isso resulta na seguinte matriz:

Método húngaro: o que é, exemplo 6

Conforme indicado no método húngaro, a etapa três deve ser executada novamente.

Etapa 3 (repetir)

Novamente, é determinado o número mínimo de linhas necessárias para cobrir todos os zeros na matriz. Nesta ocasião, são necessárias quatro linhas:

Método húngaro: o que é, exemplo 7

Como o número de linhas necessárias é 4, igual ao tamanho da matriz (n = 4), há uma alocação ideal entre os zeros na matriz. Portanto, o algoritmo para.

Alocação ideal

Como o método indica, a seleção feita dos seguintes zeros corresponde a uma alocação ideal:

Método húngaro: o que é, exemplo 8

Essa seleção de zeros corresponde à seguinte alocação ideal na matriz de custos original:

Método húngaro: o que é, exemplo 9

Portanto, o trabalhador 1 deve executar a atividade 3, trabalhador 2, atividade 2, trabalhador 3, atividade 1 e o trabalhador 4 deve executar a atividade 4. O custo total dessa alocação ideal é 69 + 37 + 11 + 23 = 140.

Referências

  1. Algoritmo húngaro (2019). O algoritmo húngaro. Retirado de: hungarianalgorithm.com.
  2. Estudo (2019). Usando o algoritmo húngaro para resolver problemas de atribuição. Retirado de: study.com.
  3. Empregos de sabedoria (2018). Método Húngaro para Resolução de Problemas de Atribuição – Técnicas Quantitativas de Gerenciamento. Retirado de: truthjobs.com.
  4. Geeks para Geeks (2019). Algoritmo húngaro para problemas de atribuição. Retirado de: geeksforgeeks.org.
  5. Karleigh Moore, Nathan Landman (2019). Algoritmo de correspondência máxima húngaro. Brilhante Retirado de: shiny.org.

Deixe um comentário

Este site usa cookies para lhe proporcionar a melhor experiência de usuário. política de cookies, clique no link para obter mais informações.

ACEPTAR
Aviso de cookies