Prévia do material em texto

Lista 5 - Pesquisa Operacional
1 Método de Resolução para Problemas de Designação
Para a resolução dos problemas de designação, a função objetivo deve ser de minimização. Para
transformar um problema de maximização em minimização,
• Passo1: Encontre o custo de maior valor CMAX da matriz de custos;
• Passo2: Calcule a diferença CMAX − cij para todos os outros custos da matriz.
Para a resolução do problema de Designação:
• Passo1: Redução de Linhas. Para cada linha i, encontre o menor custo CMINi e calcule a
diferença CMINi − cij, para todo j.
• Passo2: Redução de Colunas. Para cada coluna j, encontre o menor custo CMINj e calcule
a diferença CMINj − cij, para todo i.
• Passo3: Determine o menor número de linhas horizontais e verticais para "capturar" todos
os zeros da matriz de custo.
Se essa quantidade é maior ou igual o número de linhas ou colunas do problema, determine
a solução do problema de modo que o zero no campo (i, j) equivalha a xij = 1 e de modo a
atender as restrições.
Se essa quantidade é menor que o número de linhas ou colunas do problema, aplicar o método
Húngaro. Neste método, encontre o menor custo CMIN dos campos "não-traçados" na
matriz. Para todos os campos "não traçados", calcule a diferença CMIN − cij. Para todos
os campos "traçados" e com cruzamento, calcule a soma CMIN + cij. Para todos os campos
"traçados" e sem cruzamento, copie os custos.
Repita esta etapa até encontrar um número de traços que cobrem os zeros igual ou maior ao
número de linhas ou colunas do problema.
1
2 Exercícios
1. Considere que os valores na matriz de custos dada a seguir sejam na verdade lucro, então
você deve encontrar a designação que maximize o lucro total.
40 80 70 70
70 55 60 40
35 90 45 60
55 40 30 80
Solução:
Transformar um problema de maximização em um de minimização
O maior custo encontrado é CMAX = 90, na linha 3 e coluna 2. Assim, ao calcular
CMAX − cij = 90− cij, temos:
50 10 20 20
20 35 30 50
55 0 45 30
35 50 60 10
Table 1: Problema com custos alterados para um problema de minimização.
Redução de linha
No quadro 1, na linha 1, o menor custo é CMIN1 = 10. Na linha 2, CMIN2 = 20. Na linha
3, CMIN3 = 0. Na linha 4, CMIN4 = 10. Assim, a matriz de custos �ca:
40 0 10 10
0 15 10 30
55 0 45 30
25 40 50 0
Table 2: Matriz de custos atualizada na etapa da redução de linha.
2
Redução de coluna
A partir do quadro 2, na coluna 1, o menor custo é CMIN1 = 0. Na coluna 2, CMIN2 = 0.
Na coluna 3, CMIN3 = 10. Na linha 4, CMIN4 = 0. Assim, a matriz de custos �ca:
40 0 0 10
0 15 0 30
55 0 35 30
25 40 40 0
Table 3: Matriz de custos atualizada na etapa da redução de coluna.
Temos elementos nulos em todas as linhas e colunas e precisamos de 4 traços para "cobrir"
os zeros. Como isso ocorre, a solução encontrada é factível.
Figure 1: Avaliando a matriz de custos para ver se encontramos a solução.
São nos elementos nulos na matriz de custo que designamos origem para destinos. Isto é, re-
solvemos o problema de designação sabendo que somente as variáveis x12, x13, x21, x23, x32, x44
podem ser iguais a 1.
Considerando as restrições, a solução ótima encontrada está apresentada nos no quadro
seguinte, com valor de função objetivo
z∗ = 70 + 70 + 90 + 80 = 310
0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1
Table 4: Solução ótima encontrada de valor função objetivo z∗ = 310.
3
2. Resolva o problema de minimazação a seguir por Designação e, se necessário, utilize o método
Húngaro.
A1 A2 A3 A4
R1 3 8 2 10
R2 8 7 3 9
R3 6 4 2 7
R4 8 4 3 3
R5 9 6 6 9
Solução:
Como temos 5 elementos na linha e 4 na coluna, precisamos criar uma variável DUMMY
que será a quinta coluna, com custos nulos, já que estamos trabalhando com um problema
de minimização. Feito isso, a próxima etapa é a redução de linha e, em seguida, a redução
de colunas.
Preparação da matriz de custos
3 8 2 10 0
8 7 3 9 0
6 4 2 7 0
8 4 3 3 0
9 6 6 9 0
Table 5: Matriz de custos atualizada para a resolução do problema.
Redução de linha
Como acrescentamos uma coluna de valores nulos na matriz de custos, esta etapa pode
ser pulada porque o custo mínimo de cada linha CMINi = 0 e calculando as diferenças
CMINi − cij, a matriz atualizada será igual a do quadro 5.
Redução de coluna
Na primeira coluna, o menor custo é CMIN1 = 3. na segunda coluna, CMIN2 = 4. Já
na terceira coluna, CMIN3 = 2 e na quarta coluna, CMIN4 = 3. Na última coluna,
CMIN5 = 0. Daí, a matriz atualizada de custos �ca
0 4 0 7 0
5 3 1 6 0
3 0 0 4 0
5 0 1 0 0
6 2 4 6 0
Table 6: Matriz de custos atualizada após a redução de colunas.
4
Método Húngaro
Quando cobrimos os zeros, vemos que só precisamos de 4 traços para isso, conforme a �gura
2.
Figure 2: Avaliando a matriz de custos para ver se encontramos a solução.
Neste caso, precisamos aplicar o método Húngaro. Na �gura, podemos ver que na linha 2 e
na linha 5, da coluna 1 até a coluna 4 os campos não estão traçados. Dentre estes 8 valores,
temos o menor custo CMIN = 1.
Para estes 8 campos não traçados, vamos subtrair CMIN destes custos. Para os campos
traçados e com cruzamento, vamos somar CMIN . Para os campos traçados e sem cruza-
mento, o valor do custo não muda. Veja um resumo desta etapa na �gura 3.
Figure 3: Resumo do Método Húngaro.
Após essa etapa, a matriz de custos atualizada é:
5
0 4 0 7 1
4 2 0 5 0
3 0 0 4 1
5 0 1 0 1
6 1 3 5 0
Table 7: Matriz de custos atualizada após o traçado para cobrir os zeros.
A �gura seguinte mostra que o número de traços para cobrir os zeros é igual ao número de
linhas e colunas do problema de designação.
Figure 4: Resumo do Método Húngaro.
O próximo passo é fazer a atribuição das variáveis e teremos
z∗ = 3 + 3 + 4 + 3 + 0 = 13
1 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 1
Table 8: Solução ótima encontrada, com z∗ = 13.
6