Aula Designação de Tarefas - solução

Prévia do material em texto

Universidade Presbiteriana Mackenzie
Pesquisa Operacional Aplicada
Designação de Tarefas
Método Húngaro
Solução dos exercícios
Faculdade de Computação e Informática
Prof. Gastón A.C. Henriquez
Modelagem Matemática I
Exercícios: Nos exercícios abaixo, fazer o modelo matemático e 
resolver os problemas pelo Método Húngaro. Determine a designação 
e o custo do processo.
1) Designar 4 operários para realizarem 4 tarefas de maneira que o tempo
total para o término de todas as tarefas seja mínimo. Na tabela abaixo
temos os tempos de realização de cada tarefa por funcionário.
Modelo Matemático:
Variáveis de decisão: xij representam se o diretor i será transferido 
para a filial j: xij ={0, 1}, com i, j = 1, 2 , 3 ou 4
Função objetivo:
min 𝑐 = 5𝑥11 + 24𝑥12 + 13𝑥13 + 7𝑥14 + 10𝑥21 + 25𝑥22 + 3𝑥23 + 23𝑥24 +
28𝑥31 + 9𝑥32 + 8𝑥33 + 5𝑥34 + 10𝑥41 + 17𝑥42 + 15𝑥43 + 3𝑥44
Restrições:
𝑠. 𝑎. :
𝑥11 + 𝑥12 + 𝑥13 + 𝑥14 = 1
𝑥21 + 𝑥22 + 𝑥23 + 𝑥24 = 1
𝑥31 + 𝑥32 + 𝑥33 + 𝑥34 = 1
𝑥41 + 𝑥42 + 𝑥43 + 𝑥44 = 1
𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 = 1
𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 = 1
𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 = 1
𝑥14 + 𝑥24 + 𝑥34 + 𝑥44 = 1
Método Húngaro
Fase 1:
1) Matriz de custos:
5 24
10 25
13 7
3 23
28 9
10 17
8 5
15 3
2) Subtrair menor de cada linha:
0 19
7 22
8 2
0 20
23 4
7 14
3 0
12 0
3) Subtrair o menor de cada coluna:
0 15
7 18
8 2
0 20
23 0
7 10
3 0
12 0
4) Designar:
0 15
7 18
8 2
0 20
23 0
7 10
3 ∅
12 0
Designação: Op1 ⟶ Tar1
Op2 ⟶ Tar3
Op3 ⟶ Tar2
Op4 ⟶ Tar4
Custo da designação: c = 5 + 3 + 9 + 3 = 20
2) Considere a matriz abaixo:
Considerando que os números da matriz acima representam o rendimento de 
cada jogador em cada posição, sendo que quanto menor o número, pior o 
rendimento. Se você fosse um técnico de um time com salários atrasados e 
quisesse sabotar o time. Como escalar um time para que ele tivesse a maior 
chance de perder.
Modelo Matemático:
Variáveis de decisão: xij representam se a tarefa i será feita na 
máquina j: xij ={0, 1}, com i, j = 1, 2 ou 3
Função objetivo:
min 𝑐 = 4𝑥11 + 2𝑥12 + 4𝑥13 + 2𝑥21 + 2𝑥22 + 3𝑥23 + 3𝑥31 + 1𝑥32 + 5𝑥33
Restrições:
𝑠. 𝑎. :
𝑥11 + 𝑥12 + 𝑥13 = 1
𝑥21 + 𝑥22 + 𝑥23 = 1
𝑥31 + 𝑥32 + 𝑥33 = 1
𝑥11 + 𝑥21 + 𝑥31 = 1
𝑥12 + 𝑥22 + 𝑥32 = 1
𝑥13 + 𝑥23 + 𝑥33 = 1
Método Húngaro
Fase 1:
1) Matriz de custos:
4 2 4
2 2 3
3 1 5
2) Subtrair menor de cada linha:
2 0 2
0 0 1
2 0 4
3) Subtrair o menor de cada coluna:
2 0 1
0 0 0
2 0 3
4) Designar:
2 0 1
0 ∅ ∅
2 ∅ 3
Não foi possível designar.
Fase 2:
1) Marcar linha não designada:
2 0 1
0 ∅ ∅
2 ∅ 3
2) Marcar coluna com zero não designado na linha marcada:
2 0 1
0 ∅ ∅
2 ∅ 3
v
v
v
3) Na coluna marcada, marcar linha com zero nela designado:
Fase 3:
1) Riscar linhas não marcadas e colunas marcadas:
2 0 1
0 ∅ ∅
2 ∅ 3
2) Subtrair o menor valor não riscado, dos números não riscados e
somar esse valor nos cruzamentos de linha:
1 0 0
0 1 0
1 0 2
2 0 1
0 ∅ ∅
2 ∅ 3 v
v
v
3) Designar:
1 ∅ 0
0 1 ∅
1 0 2
Designação: Jog1 ⟶ Pos3
Jog2 ⟶ Pos1
Jog3 ⟶ Pos2
Custo da designação: c = 4 + 2 + 1 = 7
3) Designar 4 operários para trabalhar em 4 máquinas, sabendo que qualquer
operário pode trabalhar em qualquer máquina, porém com custos diferentes. Os
custos para cada operário trabalhar em cada máquina estão dispostos na tabela
abaixo:
Determine qual operário deve trabalhar em qual máquina de modo que o custo 
total seja mínimo. Qual o custo mínimo?
Modelo Matemático:
Variáveis de decisão: xij representam se o diretor i será transferido 
para a filial j: xij ={0, 1}, com i, j = 1, 2 , 3 ou 4
Função objetivo:
min 𝑐 = 4𝑥11 + 2𝑥12 + 8𝑥13 + 4𝑥14 + 6𝑥21 + 8𝑥22 + 2𝑥23 + 12𝑥24 +
2𝑥31 + 4𝑥32 + 12𝑥33 + 10𝑥34 + 2𝑥41 + 6𝑥42 + 6𝑥43 + 14𝑥44
Restrições:
𝑠. 𝑎. :
𝑥11 + 𝑥12 + 𝑥13 + 𝑥14 = 1
𝑥21 + 𝑥22 + 𝑥23 + 𝑥24 = 1
𝑥31 + 𝑥32 + 𝑥33 + 𝑥34 = 1
𝑥41 + 𝑥42 + 𝑥43 + 𝑥44 = 1
𝑥11 + 𝑥21 + 𝑥31 + 𝑥41 = 1
𝑥12 + 𝑥22 + 𝑥32 + 𝑥42 = 1
𝑥13 + 𝑥23 + 𝑥33 + 𝑥43 = 1
𝑥14 + 𝑥24 + 𝑥34 + 𝑥44 = 1
Método Húngaro
Fase 1:
1) Matriz de custos:
4 2
6 8
8 4
2 12
2 4
2 6
12 10
6 14
2) Subtrair menor de cada linha:
2 0
4 6
6 2
0 10
0 2
0 4
10 8
4 12
3) Subtrair o menor de cada coluna:
2 0
4 6
6 0
0 8
0 2
0 4
10 6
4 10
4) Designar:
2 ∅
4 6
6 0
0 8
0 2
∅ 4
10 6
4 10
Não foi possível designar a linha 4.
Fase 2:
1) Marcar linha não designada:
2 ∅
4 6
6 0
0 8
0 2
∅ 4
10 6
4 10 v
2) Marcar coluna com zero não designado na linha marcada:
2 ∅
4 6
6 0
0 8
0 2
∅ 4
10 6
4 10
3) Marcar linha com zero designado nessa coluna marcada:
2 ∅
4 6
6 0
0 8
0 2
∅ 4
10 6
4 10
Fase 3:
1) Riscar linhas não marcadas e colunas marcadas:
2 ∅
4 6
6 0
0 8
0 2
∅ 4
10 6
4 10
v
v
v
v
v
2) Subtrair o menor valor não riscado, dos números não riscados e somar
esse valor nos cruzamentos de linha:
3) Designar:
4 ∅
6 6
6 0
0 8
∅ 0
0 2
8 4
2 8
Designação: Op1 ⟶ Maq4
Op2 ⟶ Maq3
Op3 ⟶ Maq2
Op4 ⟶ Maq1
Custo da designação: c = 4 + 2 + 4 + 2 = 12
4 0
6 6
6 0
0 8
0 0
0 2
8 4
2 8