Volvismo

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1705 palavras )
  • Download(s) : 0
  • Publicado : 14 de setembro de 2012
Ler documento completo
Amostra do texto
O MÉTODO HÚNGARO APLICADO À ALOCAÇÃO DE RECURSOS
GOVERNAMENTAIS
Sérgio Antônio Martini Bortolin Júnior

Resumo
O algoritmo Húngaro foi proposto por Harold Kuhn na década de 1950 para resolver
problemas de emparelhamento máximo em grafos bipartidos. Desde esta época, tem sido
largamente implementado em diversos projetos. Neste trabalho ele será aplicado na redução
de custos do governo.Abstract
The Hungarian algorithm was proposed by Harold Kuhn in the 1950´s decade, to
solve troubles of max mating in bipartite graphs. Since this time, it has been widely
implanted in many projects. In this paper it will be applied for the reduction of government
costs.

1. Introdução
O problema da alocação de tarefas, também conhecido como “Casamento Mínimo
Perfeito”, pode ser aplicado àsmais diversas áreas, com o objetivo de minimizar ou
maximizar valores de uma matriz de custos. Para resolução de sistemas desse tipo usamos
um algoritmo eficiente, conhecido como “Método Húngaro”, com o qual é possível
encontrar a alocação ótima (Rorres, 2000).

2. Um Problema Simples de Alocação de Tarefas
Dado um problema do mundo real, precisamos interpretá-lo matematicamente pararepresentar em forma de notação matricial. Primeiramente, consideramos o seguinte
problema fictício: O governo estadual sancionou uma lei de apoio ao desenvolvimento da
metade sul do Estado do Rio Grande do Sul, na qual todas as cidades devem ser atendidas
num determinado setor de carência de investimentos e que o governo não pode investir em
dois setores iguais. Os orçamentos estão dispostos natabela a seguir, onde as linhas
correspondem à cidade e as colunas, ao setor.

Tabela 1 – Orçamento de 3 cidades
Saúde

Moradia

Educação

Alegrete

10000,00 R$

37000,00 R$

15000,00 R$

Uruguaiana

8000,000 R$

30000,00 R$,

19000,00 R$

Bagé

12000,00 R$

32000,00 R$

14000,00 R$

Devido a uma série de despesas que devem ser pagas, o governo decide minimizar aomáximo a verba destinada à metade sul.
Podemos resolver tal problema por inspeção, sem recorrer ao método húngaro, já que
é uma matriz 3 X 3, existem apenas 6 (3!) possibilidades de alocação. Vejamos:

P1 = a11 + a22 + a33 = 10000,00 + 30000,00 + 14000,00 = 54000,00
P2 = a11 + a23 + a32 = 10000,00 + 19000,00 + 32000,00 = 61000,00
P3 = a12 + a21 + a33 = 37000,00 + 8000,00 + 14000,00 =59000,00
P4 = a13 + a21 + a32 = 15000,00 + 8000,00 + 32000,00 = 55000,00
P5 = a12 + a23 + a31 = 37000,00 + 19000,00 + 12000,00 = 68000,00
P6 = a13 + a22 + a31 = 10000,00 + 10000,00 + 10000,00 = 57000,00

Dessa forma, o governo adotaria a primeira possibilidade, P1, transferiria 10000,00
R$ para Alegrete em saúde, 30000,00 R$ para Uruguaia na em moradia, e 14000,00 R$
para Bagé em educação,somando-se um total de 54000,00 R$.
Essa resolução se tornaria inviável quando o número de linhas ou colunas da matriz
cresce, pois se faria muito dispendioso encontrar as 120 possibilidades de uma matriz 5 x 5,
por exemplo.

3. Aplicando o Método Húngaro
Com base em problemas de alocação mais complexos, recorremos ao algoritmo
húngaro, onde, com uma pequena seqüência de passos a ser seguida,encontramos
facilmente a alocação ótima de valores. Para dificultar o problema, suponhamos agora que

mais dois setores devem ser atendidos: Alimentação e Segurança, e também mais uma
cidade, Rosário do Sul.

Tabela 2 – Orçamento de 5 cidades
Saúde

Moradia

Educação

Alimentação Segurança

Alegrete

10000,00 R$ 37000,00 R$ 15000,00 R$ 18000,00R$

11000,00R$

Uruguaiana8000,000 R$ 30000,00 R$ 19000,00 R$ 21000,00R$

9000,00R$

Bagé

12000,00 R$ 32000,00 R$ 14000,00 R$ 20000,00R$

9000,00R$

Rosário do Sul 10000,00R$

35000,00R$

14000,00R$ 22000,00R$

10000,00R$

Surge um novo problema: o número de cidades é diferente da quantidade de setores,
dessa forma a matriz é 4 x 5, então, não é uma matriz quadrada, assim o algoritmo húngaro
não pode ser...
tracking img