Algoritmo húngaro, ou como a matemática ajuda na atribuição de tarefas

Olá amigos! Neste artigo, gostaria de falar sobre um algoritmo interessante da disciplina “Pesquisa Operacional”, especificamente sobre o método húngaro e como resolver problemas de atribuição com sua ajuda. Vou abordar a teoria sobre em quais casos e para quais tarefas esse algoritmo é aplicável, analisarei passo a passo no meu exemplo inventado e compartilharei meu modesto esboço do código para sua implementação na linguagem R. Vamos começar!

Algumas palavras sobre o método

Para não pintar muita teoria com termos e definições matemáticos, proponho considerar algumas opções para construir o problema de atribuição, e acho que você entenderá imediatamente em que casos usaremos o método húngaro:

• A tarefa de nomear funcionários para cargos. É necessário distribuir os trabalhadores para os cargos, de modo a obter a máxima eficiência ou o custo mínimo do trabalho.
• Atribuindo máquinas às seções de produção. A distribuição das máquinas para que, durante a operação, a produção seja o mais lucrativa possível, ou o custo de manutenção delas seja mínimo.
• Estima-se a seleção de candidatos para várias vagas. Vamos analisar este exemplo abaixo.

Como você pode ver, existem muitas opções para as quais o método húngaro é aplicável, e tarefas semelhantes surgem em muitas áreas de atividade.

Como resultado, a tarefa deve ser resolvida para que um artista (pessoa, máquina, ferramenta, ...) possa executar apenas um trabalho e cada trabalho seja realizado por apenas um artista.

Uma condição necessária e suficiente para resolver um problema é o seu tipo fechado. I.e. quando o número de artistas = o número de obras (N = M). Se essa condição não for atendida, você poderá adicionar artistas fictícios ou trabalho fictício, cujos valores na matriz serão zero. Isso não afetará a solução do problema, apenas fornecerá o tipo fechado necessário.

Algoritmo passo a passo por exemplo

Declaração do problema: planeje uma importante conferência científica. Para conduzi-lo, é necessário configurar som, luz, imagens, registrar convidados e preparar-se para intervalos entre as apresentações. Existem 5 organizadores para esta tarefa. Cada um deles tem certas estimativas do desempenho de um trabalho específico (suponha que essas estimativas sejam definidas como a média aritmética das revisões de seus funcionários). É necessário distribuir os organizadores para que sua pontuação total seja máxima. A tarefa tem o seguinte formato:


Se o problema for resolvido no máximo (como no nosso caso), em cada linha da matriz é necessário encontrar o elemento máximo, subtraí-lo de cada elemento da linha correspondente e multiplicar a matriz inteira por -1. Se o problema for resolvido no mínimo, esta etapa deverá ser ignorada.


Em cada linha e em cada coluna, deve haver apenas um zero selecionado. (ou seja, quando o zero foi escolhido, os zeros restantes nesta linha ou nesta coluna não são mais considerados). Nesse caso, isso não pode ser feito:


( Se o problema for resolvido ao mínimo, você precisará começar com esta etapa ). Continuamos a solução ainda mais. Redução de matriz por linhas (procure o elemento mínimo em cada linha e subtraia-o de cada elemento, respectivamente):


Porque Como todos os elementos mínimos são zero, a matriz não mudou. Realizamos a redução em colunas:


Novamente, procuramos que em cada coluna e em cada linha haja apenas um zero selecionado. Como pode ser visto abaixo, neste caso é impossível de fazer. Apresentei duas opções de como escolher zeros, mas nenhuma delas deu o resultado desejado:


Continuamos a decisão ainda mais. Cruze linhas e colunas que contêm zero elementos ( IMPORTANTE! O número de cruzamentos deve ser mínimo ). Entre os elementos restantes, procuramos o mínimo, subtraí-lo dos elementos restantes (que não são riscados) e adicionamos aos elementos que estão localizados na interseção das linhas e colunas cruzadas (o que é marcado em verde é subtraído ali; o que é marcado em dourado é resumido lá; depois, o que não está pintado - não toque):


Como você pode ver agora, em cada coluna e linha há apenas um zero selecionado. Concluímos a solução do problema!


Substitua na tabela inicial a localização dos zeros selecionados. Assim, obtemos o plano ideal, ou ideal, no qual os organizadores são distribuídos entre o trabalho e a soma das estimativas acabou sendo máxima:


Se você resolver o problema e ainda for impossível escolher zeros para que haja apenas um em cada coluna e linha, repetimos o algoritmo a partir do local em que a redução por linhas foi realizada (o elemento mínimo em cada linha).

Implementação da linguagem de programação R

O algoritmo húngaro é implementado usando recursões. Espero que meu código não cause dificuldades. Primeiro você precisa compilar três funções e depois iniciar os cálculos.

Os dados para resolver o problema são obtidos do arquivo example.csv, que tem o formato:



O resultado do programa:

Em conclusão

Muito obrigado por ler o meu artigo. Vou fornecer todos os links usados ​​abaixo. Espero que você tenha aprendido algo novo para si mesmo ou atualizado seus conhecimentos antigos. Todo o sucesso, boa e boa sorte!

Recursos utilizados

1. Wikipedia invadida
2. E outros bons sites
3. Estressei por mim mesmo algumas informações deste artigo.