Universidade Federal Rural de Pernambuco
Bacharelado em Sistemas de Informação
Álgebra Vetorial e Linear para Computação

O problema da Alocação de
Tarefas

Discentes: Bruno Roberto
Leonardo Pontes
Docente: Marcelo Gama

Recife, Novembro de 2014

O PROBLEMA DA ALOCAÇÃO DE TAREFAS

Apresentação
A álgebra linear tem um amplo campo de aplicações. Por meio de uso da teoria de matrizes, é possível calcular parâmetros adicionais, como os preços e níveis de produção para satisfazer um objetivo economicamente desejado.
Neste trabalho, apresentamos o estudo de um algoritmo de otimização, para encontrar uma alocação de tarefas de custo mínimo. O algoritmo é chamado de
“método Húngaro” e foi criado pelos húngaros D. König e E. …exibir mais conteúdo…

Destacamos as entradas associadas a cada uma das seis alocações e calculamos sua soma.

Observe que os totais de possibilidades variam de um mínimo de R$ 54.000,00 a um máximo de R$ 68.000,00. Como o mínimo total de possibilidades de R$
54.000,00 é atingido pela alocação (a), o governo transferiria verba da seguinte maneira: R$ 10.000,00 para Alegrete em saúde;
R$ 30.000,00 para Uruguaiana em moradia;
R$ 14.000,00 para Bagé em educação.
O método de força bruta usado neste exemplo logo se torna impraticável, à medida que aumenta o tamanho da matriz-custo. Por exemplo, para uma matriz
10×10, há um total de 3.628.800(=10!) alocações possíveis. Iremos descrever agora um método prático para resolver qualquer problema de alocações.

5

O PROBLEMA DA ALOCAÇÃO DE TAREFAS

O Método Húngaro
Esse nome teve origem em 1955 devido a H. W. Kuhn, pesquisador na área de programação linear, que em um de seus trabalhos, fez homenagem aos descobridores do algoritmo em 1931, os húngaros E. Egerváry e D. König, sendo que este último demonstrou um teorema combinatório em 1916 que serviu de base para o algoritmo (Teorema de König).

O Método Húngaro pode ser aplicado em diversos problemas práticos de alocação de tarefas. Suponha que um problema específico de alocação de tarefas tem a matriz-custo:

Podemos notar que todas as entradas desta matriz-custo