Método húngaro: em que consiste, exemplo - Ciência - 2023

science
Método húngaro: em que consiste, exemplo - Ciência
Método húngaro: em que consiste, exemplo - Ciência

Contente

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 atribuindo várias pessoas a várias atividades com base no menor custo. Cada atividade deve ser atribuída a uma pessoa diferente.

Um problema de alocação é um tipo especial de problema de programação linear, em que o objetivo é minimizar o custo ou o tempo de conclusão de uma série de tarefas por várias pessoas.

Uma das características importantes do problema de alocaçã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 o método húngaro para problemas de atribuição. É também conhecido como algoritmo de alocação de Kuhn-Munkres.


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

- Com a primeira fase, são realizadas reduções de linha e reduções de 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 alocação ideal seja encontrada.

Uma matriz quadrada de ordem n por n é considerada como dado de entrada, que deve conter apenas elementos não negativos.

Para um determinado problema, se o número de linhas da matriz não for igual ao número de colunas, deve-se adicionar uma linha fictícia ou uma coluna fictícia, dependendo do caso. Os custos de alocação para essas células dummy são sempre alocados como zero.

Etapa 1: subtraia os mínimos de cada linha

Para cada linha na 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 item com o valor mais baixo é selecionado para cada coluna e subtraído de cada item dessa coluna.

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

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

Se um total de n linhas forem necessárias para cobrir todos os zeros, onde n é igual ao tamanho n vezes n da matriz, haverá uma alocação ótima entre os zeros e, portanto, o algoritmo para.

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

Etapa 4: crie zeros extras

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 k é 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, você retornará à etapa 3.

Alocação ótima

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

Se neste 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 removidos, repetindo o mesmo para as outras atribuições.

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

Todas as linhas ou colunas fictícias que foram adicionadas são removidas. Os zeros escolhidos nesta matriz final correspondem, portanto, à atribuição ideal exigida na matriz original.

Exemplo

Consideremos uma empresa onde existem 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 designar um determinado trabalhador para uma determinada atividade. O objetivo é minimizar o custo total da tarefa composta por essas quatro atividades.

Etapa 1: subtraia os mínimos de cada linha

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

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 demais elementos dessa coluna, obtendo-se a seguinte matriz:

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

Agora iremos determinar o número mínimo de linhas (horizontais ou verticais) que são necessárias para cobrir todos os zeros na matriz. Todos os zeros podem ser cobertos com 3 linhas:

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

Etapa 4: crie zeros extras

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

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

Etapa 3 (repetir)

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

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

Alocação ótima

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

Esta seleção de zeros corresponde à seguinte alocação ótima na matriz de custo original:

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

Referências

  1. Algoritmo Húngaro (2019). O algoritmo húngaro. Retirado de: hungarianalgorithm.com.
  2. Study (2019). Usando o algoritmo húngaro para resolver problemas de atribuição. Retirado de: study.com.
  3. Wisdom Jobs (2018). Método Húngaro para Resolver Problema de Atribuição - Técnicas Quantitativas de Gestão. Retirado de: swordjobs.com.
  4. Geeks for Geeks (2019). Algoritmo Húngaro para o Problema de Atribuição. Retirado de: geeksforgeeks.org.
  5. Karleigh Moore, Nathan Landman (2019). Algoritmo de correspondência máxima húngara. Brilhante. Retirado de: brilhante.org.