O método húngaro é um algoritmo que permite minimizar custos em um problema de otimização baseado em programação linear.
O objetivo do método húngaro é encontrar o custo mínimo de um conjunto de tarefas que devem ser realizadas pelas pessoas mais adequadas.
Ele usa programação linear (PL) para realizar uma série de etapas que podem ser automatizadas. Assim, ferramentas como o software estatístico R (entre outros) possuem vários pacotes muito úteis para esses problemas de otimização.
Origem do método húngaro
Seu criador foi o matemático húngaro (daí seu nome) Harold W. Kuhn em 1955. Outro matemático, James Munkres, o revisou em 1957. Com essa evolução, ele recebeu outros nomes, como algoritmo de alocação de Munkres ou Kuhn-Munkres.
Por outro lado, esse método tem precedente em dois autores, Dénes König e Jenő Egerváry, judeus e húngaros. O primeiro desenvolveu a teoria dos grafos na qual este algoritmo se baseia. O segundo teorema de König generalizado e permitiu a Kuhn desenvolver o método.
Passos do método húngaro
Os passos a seguir permitem realizar o método húngaro de forma simples através de uma planilha. Além disso, este esquema que mostramos nos permitirá ver de forma global o processo que iremos desenvolver em detalhes no exemplo final.
- Como etapas preliminares, você deve atribuir pessoas (linhas) a uma série de projetos (colunas). Além disso, é necessário calcular os diferentes custos de cada projeto em função de quem o realiza e construir uma matriz (C) com essas informações.
- Na matriz (C) procuramos o valor mínimo de cada linha. Subtraímos isso de todos os elementos na linha e executamos a mesma operação com as colunas. Uma nova matriz (C`) aparecerá com os resultados das operações anteriores.
- A seguir, criamos o «gráfico de igualdades», que nos permite escolher as tarefas e projetos com o menor custo. O ótimo seriam aqueles elementos cujo resultado fosse zero. Se for verdade que não há nenhum elemento com valor zero atribuído a mais de uma linha, o algoritmo termina.
- Caso contrário, uma nova atribuição deve ser feita. É feita uma nova matriz na qual uma série de modificações são aplicadas, como veremos no exemplo. Recriamos o gráfico e continuamos até que tenhamos uma matriz que tenha pelo menos um zero em cada linha e em posições não repetitivas.
- Com esta informação já temos as pessoas e projetos atribuídos (os zeros) que otimizam o problema. Se uma tarefa já foi atribuída em uma linha anterior, ela será descartada na próxima. Para calcular o custo mínimo, somamos os custos da matriz inicial que aparecem na posição desses zeros.
Exemplo de método húngaro
Vejamos um exemplo simples do método húngaro de. Vamos imaginar que temos três trabalhadores e eles devem ser atribuídos a três projetos. Criamos a matriz inicial (C) e os valores de custo em cada célula. Para isso você deve utilizar as informações disponíveis na empresa. Assim que tivermos tudo isso, começamos o processo. Uma planilha pode ajudar.
Calculamos os mínimos de cada linha e os subtraímos dos elementos dessa linha e fazemos o mesmo com as colunas (etapas 1 e 2). Na matriz resultante (C`), desenhamos linhas de forma que cobrem todos os zeros e, por sua vez, se cruzam (etapa 3). Vemos que existem duas linhas, mas o maior valor do número de linhas ou colunas é três. Temos que continuar.
Agora escolhemos o menor dos números descobertos, neste exemplo é dois (azul escuro). Nós o subtraímos dos anteriores e o adicionamos àqueles que estão localizados onde as linhas se cruzam. No nosso caso são mais dois (E3, T1). Ficamos com uma nova matriz (etapa 4). Nós redesenhamos as linhas e contamos. Existem três linhas, igual ao número de linhas ou colunas. O algoritmo foi concluído.
Começamos com a linha ou coluna com o menor número de zeros (E1, T1). Se uma tarefa já foi atribuída, ela não pode ser reatribuída, por exemplo, com E2 você não pode usar o primeiro zero de T1, pois esta tarefa foi atribuída a E1. O custo total, no método húngaro, será a soma dos custos da matriz original (Etapa 1) localizada na mesma posição dos zeros escolhidos (etapa 5).