O Método Húngaro
Um dos problemas fundamentais da pesquisa operacional é a alocação ótima de recursos, que consiste em atribuir tarefas a facilidades (ou recursos) de forma a minimizar (ou maximizar) uma determinada medida de desempenho, como custo ou lucro.
O problema clássico de atribuição pressupõe um número igual de tarefas e facilidades. Dado \( n \) tarefas e \( n \) facilidades, o número total de atribuições possíveis é \( n! \). Por exemplo, para \( n = 3 \), existem \( 3! = 6 \) combinações distintas, mas nem todas representam uma solução ótima.
Uma abordagem ingênua seria testar todas as combinações e selecionar a melhor. No entanto, para valores elevados de \( n \), essa estratégia de força bruta torna-se computacionalmente inviável. Para \( n = 20 \), por exemplo, teríamos \( 20! \approx 2.43 \times 10^{18} \) possibilidades. O Método Húngaro surge como uma alternativa eficiente para resolver este problema de forma exata e com esforço polinomial.
Vale notar que, em matrizes de custo \( C \) de ordem \( m \times n \) com \( m < n \), a enumeração exaustiva pode ainda ser considerada, dependendo das dimensões. No entanto, o foco deste trabalho é apresentar aplicações do Método Húngaro, sem compará-lo detalhadamente com outras técnicas.
Fundamentação do Método
O Método Húngaro é aplicado a problemas de alocação onde os recursos são indivisíveis (variáveis inteiras) e busca determinar a distribuição que otimiza o custo total.
Seja \(c_{ij}\) o custo associado à atribuição da tarefa \( i \) à facilidade \( j \), para \( i, j = 1, 2, \ldots, n \). A matriz \(C \) com entradas \(c_{ij}\) onde \(i,j=1, 2, \ldots,n \) é denominada matriz de custos.
Uma alocação viável é um conjunto de \( n \) elementos \( c_{ij} \) da matriz tal que não há dois elementos na mesma linha ou coluna – garantindo que cada tarefa seja designada a exatamente uma facilidade e vice-versa. A soma desses \( n \) elementos constitui o custo da alocação. Uma alocação é ótima se seu custo é o mínimo possível (para um problema de minimização).
Princípio Teórico
O método baseia-se em uma propriedade fundamental de transformação da matriz de custos:
“Se um mesmo valor k for adicionado ou subtraído de todos os elementos de uma linha (ou coluna) da matriz de custos \(C\), a alocação ótima para a nova matriz resultante também será ótima para a matriz original \(C\).”
Explorando essa propriedade, o Método Húngaro opera por meio de transformações sistemáticas na matriz \(C\), gerando uma matriz equivalente com elementos não-negativos e zeros em posições estratégicas, a partir da qual uma atribuição de custo mínimo pode ser identificada.
Para resolver um problema de maximização, por exemplo, de lucro ou eficiência, basta converter o problema em um de minimização, definindo uma nova matriz \( C’ = -C\) e então aplicar o método padrão.
Clique no link a seguir para praticar com alguns exemplos. Ir para a teoria e exemplos