Alocação de Tarefas e Método Húngaro

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. Egerváry. Por tratarse de um método discreto de otimização, baseado na manipulação de matrizes, no qual não é necessário o uso de cálculo Diferencial e Integral, os pré-requisitos são mínimos, o que torna sua compreensão e utilização extremamente acessíveis. Em nossa sociedade, é muito frequente depararmos com problemas que requerem tomadas de decisões visando a melhoria da relação custo-benefício por meio da maximização ou minimização de elementos do problema. Esse tipo de problema forma uma classe especial de problemas de otimização, ou seja, problemas cuja solução consiste em maximizar ou minimizar uma função numérica de um determinado número de variáveis (ou funções), estando estas sujeitas a certas restrições. Por exemplo, o problema pode ser encontrar a melhor distribuição de trabalhadores em empregos, jogadores de um esporte em posições no campo, maquinário em locais de construção e assim por diante.
O problema da alocação de tarefas requer que haja o mesmo número de instalações e tarefas, digamos n. Neste caso, há exatamente n! maneiras distintas de alocar univocamente as tarefas às instalações. Isto ocorre pois há n maneiras de alocar a primeira tarefa, n −1 maneiras de alocar a segunda, n – 2 maneiras de