Aula Designação de Tarefas

Prévia do material em texto

Universidade Presbiteriana Mackenzie
Pesquisa Operacional Aplicada
Designação de Tarefas
Método Húngaro 
Faculdade de Computação e Informática
Prof. Gastón A.C. Henriquez
Modelagem Matemática I
O Problema da Designação de Tarefas
• Apesar de não parecer o problema é bem semelhante ao
problema de transportes, com algumas modificações.
• Suponhamos que uma quantidade de m tarefas (ou
trabalhadores) devem ser alocadas em n máquinas. Cada
tarefa i (I = 1, 2, ..., m) alocada a uma máquina j (j = 1, 2, ..., n)
tem um custo cij
• Objetivo: Designar para cada máquina a tarefa adequada de
modo a minimizar o custo total.
• Caso alguma tarefa não possa ser feita em alguma máquina, o
custo correspondente deve ser arbitrado em um valor “muito
alto”, de modo a impedir essa designação.
2
Considerações:
• Todas as tarefas devem ser feitas e só podem ser feitas uma
vez (sem retrabalho).
• Todas as máquinas devem ser usadas e também só podem
ser usadas uma vez.
• Como todas as tarefas devem ser feitas só uma vez e como
as máquinas tem que ser usadas uma vez, significa que o
número de tarefas deve ser igual ao número de máquinas,
ou seja, n = m.
• Assim, antes de modelar, devemos tornar m = n, ou seja,
introduzir máquinas ou tarefas , o que for necessário.
Representação geral:
c11 c12 c1n
c21 c22 c23
cm1 cm2 cmn
Modelo Matemático:
Variáveis de decisão: xij representam se a tarefa i será feita na 
máquina j: xij ={0, 1}
Função objetivo:
min 𝑐 = σ𝑖σ𝑗
𝑐𝑖𝑗 . 𝑥𝑖𝑗 = 𝑐11𝑥11 + 𝑐12𝑥12 + …+ 𝑐1𝑛𝑥1𝑛 +
𝑐21𝑥21 + 𝑐22𝑥22 + …+ 𝑐2𝑛𝑥2𝑛 +
…
𝑐𝑛1𝑥𝑛1 + 𝑐𝑛2𝑥𝑛2 +⋯+ 𝑐𝑛𝑛𝑥𝑛𝑛
Restrições:
𝑠. 𝑎. :
𝑥11 + 𝑥12 +⋯𝑥1𝑛 = 1
𝑥21 + 𝑥22 +⋯𝑥2𝑛 = 1…
𝑥11 + 𝑥21 +⋯𝑥𝑛1 = 1
𝑥12 + 𝑥22 +⋯𝑥𝑛2 = 1
…
EXEMPLO 1: Três tarefas devem ser designadas a três máquinas, todas as 
tarefas podendo ser feitas em todas as máquinas, mas com custos diferentes. 
Veja a situação inicial:
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 𝑐 = 2𝑥11 + 4𝑥12 + 3𝑥13 + 1𝑥21 + 3𝑥22 + 2𝑥23 + 5𝑥31 + 2𝑥32 + 4𝑥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
Solução: Método Húngaro
Fase 1
1) Transformar a tabela de custos em uma matriz:
2 4 3
1 3 2
5 2 4
2) Subtrair de todos os elementos de cada linha o seu menor
elemento:
0 2 1
0 2 1
3 0 2
3) Subtrair de todos os elementos de cada coluna o seu menor
elemento:
0 2 0
0 2 0
3 0 1
4) Tentar achar uma designação da seguinte maneira:
a. Para cada linha, ou coluna, marcar um zero e riscar os restantes dos
zeros na mesma linha ou coluna.
b. Fazer isso para todas as linhas e colunas, de modo que não fique mais
de um zero marcado em cada linha ou coluna.
c. Se for possível marcar um zero em cada linha, foi obtida a designação
ótima com custo mínimo. Se não for possível, passar à fase 2.
Na matriz obtida acima é possível obter uma designação, qual seja:
∅ 2 [0]
[0] 2 ∅
3 [0] 1
• Designação: Onde podemos ver que a tarefa 1 será designada para a
máquina 3, a tarefa 2 para a máquina 1 e a tarefa 3 para a máquina 2.
• O custo dessa designação é: C = 3 + 1 + 2 = 6
• Observação: A designação ótima nem sempre é única. Pode-se obter outra
com o mesmo custo. No exemplo acima, uma outra designação possível
seria: Tarefa 1 na máquina 1, tarefa 2 na máquina 3 e tarefa 3 na máquina 2.
O que daria o mesmo custo, 6.
• Nem sempre é possível fazer a designação apenas com os passos da fase
1.
• Nesse caso a solução ótima se obtém em 3 fases.
EXEMPLO 2: O presidente de uma empresa deseja transferir 4 de seus diretores 
para 4 filiais diferentes. Quais diretores ele deve mandar para quais lugares de 
modo a minimizar o custo da transferência. A tabela abaixo mostra o custo de 
transferência de cada diretor para cada lugar. 
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 𝑐 = 2𝑥11 + 1𝑥12 + 4𝑥13 + 2𝑥14 + 3𝑥21 + 4𝑥22 + 1𝑥23 + 6𝑥24 +
1𝑥31 + 2𝑥32 + 6𝑥33 + 5𝑥34 + 1𝑥41 + 3𝑥42 + 3𝑥43 + 7𝑥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
Solução: Método Húngaro
Fase 1
1) Transformar a tabela de custos em uma matriz:
2 1
3 4
4 2
1 6
1 2
1 3
6 5
3 7
2) Subtrair de todos os elementos de cada linha o seu menor elemento:
1 0
2 3
3 1
0 5
0 1
0 2
5 4
2 6
3) Subtrair de todos os elementos de cada coluna o seu menor elemento:
1 0
2 3
3 0
0 4
0 1
0 2
5 3
2 5
4) Tentar achar uma designação da seguinte maneira:
a. Para cada linha, ou coluna, marcar um zero e riscar os restantes dos
zeros na mesma linha ou coluna.
b. Fazer isso para todas as linhas e colunas, de modo que não fique mais
de um zero marcado em cada linha ou coluna.
c. Se for possível marcar um zero em cada linha, foi obtida a designação
ótima com custo mínimo. Se não for possível, passar à fase 2.
1 ∅
2 3
3 [0]
[0] 4
[0] 1
∅ 2
5 3
2 5
Não foi possível achar uma designação, pois o diretor 4 não foi designado para 
nenhum local. 
Devemos passar à fase 2.
Fase 2
1) Marca linha sem designação:
1 ∅
2 3
3 [0]
[0] 4
[0] 1
∅ 2
5 3
2 5
2) Na linha marcada, marca coluna com zero nessa linha:
1 ∅
2 3
3 [0]
[0] 4
[0] 1
∅ 2
5 3
2 5
٧
٧
٧
3) Na coluna marcada, marcar linha com zero designado nessa coluna:
1 ∅
2 3
3 [0]
[0] 4
[0] 1
∅ 2
5 3
2 5 ٧
٧
٧
4) Repetir os passos 2) e 3) até não conseguir marcar mais nenhuma
linha ou coluna.
Neste caso, não há como marcar mais nenhuma linha ou coluna.
Vamos então à fase 3.
Fase 3
1) Traçar uma reta sobre as linhas não-marcadas e sobre as colunas
marcadas:
1 0
2 3
3 0
0 4
0 1
0 2
5 3
2 5
2) Subtrair os elementos não riscados pelo valor do menor elemento não
riscado e somar esse mesmo valor aos elementos de cruzamento das
linhas. Manter os outros valores:
2 0
3 3
3 0
0 4
0 0
0 1
4 2
1 4
v
v
v
3) Obter uma designação:
2 ∅
3 3
3 [0]
[0] 4
∅ [0]
[0] 1
4 2
1 4
Designação: O diretor 1 vai para a filial 4, o diretor 2 vai para a filial 3, o diretor 
3 vai para a filial 2 e o diretor 4 vai para a filial 1.
Custo da designação: C = 2 + 1 + 2 + 1 = 6 
Obs: Geralmente começamos a fazer a designação pela linha que não tinha 
conseguido ser designada, no caso acima, a linha 4.
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.
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.
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?