Cientista

Universidade Federal de Alfenas - UNIFAL–MG

O Problema de Alocação de Tarefas – Método Húngaro

César Henrique Valentino
Mariana Frontelli

Poços de Caldas – 2013

César Henrique Valentino
Mariana Frontelli

O Problema de Alocação de Tarefas – Método Húngaro

Trabalho apresentado à unidade curricular Álgebra Linear do ICT da UNIFAL –MG sob orientação do Professor Dr. Mayk Coelho.

Poços de Caldas – 2013

Sumário
1) Introdução ............................................................................................................. 4
2) Exercício 1 do livro. ............................................................................................ 11
3) Exercício 2 do livro. ............................................................................................ 15
4) Exercício 3 do livro. ............................................................................................ 17
5) Exercício 5 do livro. ............................................................................................ 19
6) Discussão e Conclusão ...................................................................................... 23

4

1) Introdução
Pode parecer simples à primeira vista a resolução de um problema como o abaixo: Um homem deseja comprar ingressos para assistir 3 jogos de futebol, um comerciante, amigo do homem, para testar a inteligência de seu amigo faz três propostas sobre o preço de venda de cada ingresso e pede para o homem escolher qual proposta ele quiser para pagar no ingresso de cada jogo. A única regra, é que o homem só pode escolher uma proposta para cada jogo, e se o homem fosse capaz de fazer a escolha em que economizasse a maior quantidade de dinheiro, o negociante ainda lhe daria um bom desconto na compra. O negociante mostrou ao amigo a seguinte tabela de preços.

Quais propostas o homem deve escolher para cada jogo de modo a diminuir ao mínimo o valor total que pagará ao negociante e ganhar e