Uma Universidade está querendo pintar quatro dos seus carros, com as cores e os símbolos da universidade. Então, a Universidade faz uma licitação para executar este serviço, onde cada empressa só pode pintar um carro. Dentro das propostas ela seleciona quatro delas, cujos valores são dados segundo tabela abaixo.
carro A
carro B
carro C
carro D
Of.1
3
6
7
5
Of.2
7
7
4
3
Of.3
6
2
6
5
Of.4
5
3
4
7
Então, encontre a melhor proposta para a Universidade.
Passo 1
Este é um problema de atribuição (assignment problem): temos quatro empresas (Of., Of., Of., Of.) e quatro carros (A, B, C, D), cada empresa só pode pintar um carro, e o objetivo é minimizar o custo total. Vamos usar o método húngaro para resolver.
Passo 2
Montamos a matriz de custos e subtraímos de cada linha o seu mínimo:
Em seguida subtraímos de cada coluna o seu mínimo (coluna 3 tinha mínimo 1):
Procuramos uma seleção de zeros tal que cada linha e cada coluna tenha exatamente um zero atribuído. Uma escolha possível é:
Linha 1 to Coluna 1
Linha 2 to Coluna 4
Linha 3 to Coluna 2
Linha 4 to Coluna 3
Isto corresponde a:
Of1 to A, Of2 to D, Of3 to B, Of4 to C
Passo 4
Calculamos o custo total na matriz original:
3;(Of1 em A) +3;(Of2 em D) +2;(Of3 em B) +4;(Of4 em C) =12
Resposta
A melhor proposta é aceitar
Of.1 para pintar o carro A,
Of.2 para pintar o carro D,
Of.3 para pintar o carro B,
Of.4 para pintar o carro C,
com custo total mínimo de ;12;.