Álg
eb
ra L
inear
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Álg
eb
ra L
inear
UNIVERSIDADE FEDERAL FLUMINENSEUNIVERSIDADE FEDERAL FLUMINENSE
Por:Por:Viviane LiriaViviane Liria
O Problema da O Problema da Alocação deAlocação de
TarefasTarefas
Professora:Professora:Ana IsabelAna Isabel
Álg
eb
ra L
inear
Álg
eb
ra L
inear
O Problema da Alocação de O Problema da Alocação de TarefasTarefas
O que é alocação de tarefas?
Problema de distribuição de um número n de instalações para um número n de tarefas, buscando um custo mínimo. Para este problema há exatamente n! maneiras diferentes de alocar as tarefas. Uma alocação com custo mínimo é denominada alocação ótima.
Custo – unidade utilizada para definir a tarefa a ser otimizada. Pode ser reais, quilômetros, horas, etc.
Cij – custo de alocar a i-ésima tarefa à j-ésima instalação.
C11C11 C12C12 ...... C1nC1n
C21C21 C22C22 ...... C2nC2n
...... ...... ...... ......
Cn1Cn1 Cn2Cn2 CnnCnn
C = Matriz-custo
Álg
eb
ra L
inear
Álg
eb
ra L
inear
O Problema da Alocação de O Problema da Alocação de TarefasTarefas
Exemplo1
Uma faculdade pretende instalar ar-condicionado em três de seus prédios num período de uma semana e convida três firmas para
submeter orçamentos para cada um dos prédios. Na tabela 1 aparecem os orçamentos em unidades de 1000 reais.
Prédio 1Prédio 1 Prédio 2Prédio 2 Prédio 3Prédio 3
Firma 1Firma 1 5353 9696 3737
Firma 2Firma 2 4747 8787 4141
Firma 3Firma 3 6060 9292 3636
Álg
eb
ra L
inear
Álg
eb
ra L
inear
O Problema da Alocação de O Problema da Alocação de TarefasTarefasExemplo1
A matriz custo para este problema é a matriz 3x3:
5353 9696 3737
4747 8787 4141
6060 9292 3636
C = Matriz-custo
Como só há seis (3!) alocações possíveis, podemos resolver este problema calculando o custo de cada uma
delas e calculamos sua soma:
Álg
eb
ra L
inear
Álg
eb
ra L
inear
O Problema da Alocação de O Problema da Alocação de TarefasTarefas
5353 9696 3737
4747 8787 4141
6060 9292 3636
• 53 + 87 + 36 = 176
• 53 + 92 + 41 = 186
• 47 + 96 + 36 = 179
• 47 + 92 + 37 = 176
• 60 + 96 + 41 = 197
• 60 + 87 + 37 = 184
O resultado nos dá duas opções de alocação de tarefas com custo
mínimo.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
00 55 00 33
00 44 22 55
66 00 77 77
77 99 00 00
O Método Húngaro
No exemplo anterior conseguimos rapidamente encontrar uma solução, pois a matriz-custo só permitia 6 formas diferentes de
alocação. Porém, quando encontramos um problema mais complexo, o método utilizado torna-se impraticável.
Vamos descrever, agora um método mais prático para resolução de problemas maiores:
Suponhamos que a matriz custo de um problema seja:
Note que todas as entradas são não-negativas e que ela contém
muitos zeros.
Nesta matriz é possível encontrar facilmente uma alocação composta
apenas por zero. Esta alocação deve ser ótima, pois seu custo é
zero.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
O Método Húngaro
Teorema:
Se um número é somado ou subtraído de todas as entradas
de uma linha ou coluna de uma matriz-custo, então uma
alocação de tarefas ótima para a matriz-custo resultante
também é uma alocação ótima para a matriz-custo original.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de TarefasO Método Húngaro
Exemplo 2:
Matriz-custo:
9090 7575 7575 8080
3535 8585 5555 6565
125125 9595 9090 105105
4545 110110 9595 115115
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de TarefasO Método Húngaro
9090 7575 7575 8080
3535 8585 5555 6565
125125 9595 9090 105105
4545 110110 9595 115115
Passo 1: Subtraímos a menor entrada de cada linha
1515 00 00 55
00 5050 2020 3030
3535 55 00 1515
00 6565 5050 7070
Passo 2: As três primeiras colunas da matriz já contém entradas zero, portanto, só precisamos subtrair da quarta coluna.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de TarefasO Método Húngaro
Passo 3: Riscamos as entradas zero utilizando um número mínimos de traços.
3535 00 00 55
00 3030 00 55
5555 55 00 1010
00 4545 3030 4545
Passo 4: Como o número de traços ainda é inferior a 4, subtraímos a menor entrada da matriz de todas as entradas não riscadas e somamos a todas as entradas riscadas por 2.
1515 00 00 00
00 5050 2020 2525
3535 55 00 1010
00 6565 5050 6565
Passo 5: Repetiremos o passo 3.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de TarefasO Método Húngaro
Passo 3: Como as entradas zero não podem ser riscadas com menos de 4 traços, a matriz encontrada deve conter uma alocação ótima de zeros.
3535 00 00 55
00 3030 00 55
5555 55 00 1010
00 4545 3030 4545
Encontramos, portanto, duas opções para alocação de tarefas.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
O Método Húngaro
Restrições para resolução através do método húngaro:
•O problema deve ser de minimização de custo;
•A matriz custo deve ser quadrada
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de TarefasO Problema de Alocação de Tarefas de Carlos Alberto ParreiraO Problema de Alocação de Tarefas de Carlos Alberto Parreira
KakáKaká RenatoRenato AdrianoAdriano Juninho P.Juninho P. CicinhoCicinho Zé RobertoZé Roberto
Roque Jr.Roque Jr.
LúcioLúcio
MarcosMarcos
Ronaldo G.Ronaldo G.
RobinhoRobinho
??
??
????
??
EmersonEmerson
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Roque Jr.Roque Jr.
LúcioLúcio
MarcosMarcos
Ronaldo G.Ronaldo G.
RobinhoRobinho
33
22
11
44
55
KakáKaká RenatoRenato AdrianoAdriano Juninho P.Juninho P. CicinhoCicinho Zé RobertoZé Roberto
EmersonEmerson
Álg
eb
ra L
inear
Álg
eb
ra L
inear
KakáKaká RenatoRenato AdrianoAdriano Juninho P.Juninho P. CicinhoCicinho Zé RobertoZé Roberto
Posição 1Posição 1 1515 77 2121 1414 1414 2121
Posição 2Posição 2 1818 88 2323 1616 77 2323
Posição 3Posição 3 1414 99 2020 1414 1919 2121
Posição 4Posição 4 1414 77 1919 1313 1313 1919
Posição 5Posição 5 1717 55 2020 1616 2121 2020
Posição 6Posição 6 00 00 00 00 00 00
Quantos gols fez a seleção nos últimos dez jogos em que cada um desses jogadores jogou nessas posições?
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
1515 77 2121 1414 1414 2121
1818 88 2323 1616 77 2323
1414 99 2020 1414 1919 2121
1414 77 1919 1313 1313 1919
1717 55 2020 1616 2121 2020
00 00 00 00 00 00
-15-15 -7-7 -21-21 -14-14 -14-14 -21-21
-18-18 -8-8 -23-23 -16-16 -7-7 -23-23
-14-14 -9-9 -20-20 -14-14 -19-19 -21-21
-14-14 -7-7 -19-19 -13-13 -13-13 -19-19
-17-17 -5-5 -20-20 -16-16 -21-21 -20-20
00 00 00 00 00 00
Como temos 6 jogadores e apenas cinco posições, vamos inserir uma linha com todas as entradas zero que representará o banco de reservas.
Para transformar o problema de maximização em um problema de minimização, multiplicaremos todas as entradas por (-1).
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
66 1414 00 77 77 00
55 1515 00 77 1616 00
77 1212 11 77 22 00
55 1212 00 55 66 00
44 1616 11 55 00 11
00 00 00 00 00 00
-15-15 -7-7 -21-21 -14-14 -14-14 -21-21
-18-18 -8-8 -23-23 -16-16 -7-7 -23-23
-14-14 -9-9 -20-20 -14-14 -19-19 -21-21
-14-14 -7-7 -19-19 -14-14 -13-13 -19-19
-17-17 -5-5 -20-20 -16-16 -21-21 -20-20
00 00 00 00 00 00
Nessa matriz, subtrai-se a menor entrada de cada linha.
Na matriz obtida, não é preciso subtrair a menor entrada nas colunas pois já temos pelo menos uma entrada zero em cada.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
44 1212 00 55 55 00
33 1313 00 55 1414 00
55 1010 11 55 00 00
33 1010 00 33 44 00
44 1616 33 55 00 33
00 00 22 00 00 22
66 1414 00 77 77 00
55 1515 00 77 1616 00
77 1212 11 77 22 00
55 1212 00 55 66 00
44 1616 11 55 00 11
00 00 00 00 00 00
Agora, temos que riscar todas as entradas zero utilizando o menor número de traços possível.
Como o número de traços utilizados foi menor do que 6, devemos subtrair a menor entrada de todas as entradas não riscadas e somar a menor entrada a todas as entradas riscadas por 2 traços.
Na matriz obtida, vamos repetir os passos anteriores.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
11 99 00 22 55 00
00 1010 00 22 1414 00
22 77 11 22 00 00
00 77 00 00 44 00
11 1313 33 22 00 33
00 00 55 00 33 55
Como não é possível riscar todas as entradas zero com menos de 6 traços, essa matriz deve conter uma alocação ótima de zeros. Obtivemos, portanto o resultado do problema.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Alocação de TarefasAlocação de Tarefas
KakáKaká RenatoRenato AdrianoAdriano Juninho P.Juninho P. CicinhoCicinho Zé RobertoZé Roberto
Posição 1Posição 1 11 99 00 22 55 00
Posição 2Posição 2 00 1010 00 22 1414 00
Posição 3Posição 3 22 77 11 22 00 00
Posição 4Posição 4 00 77 00 00 44 00
Posição 5Posição 5 11 1313 33 22 00 33
Posição 6Posição 6 00 00 55 00 33 55
As entradas zero representam o melhor desempenho de cada jogador.
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Posição 1Posição 1
Posição 2Posição 2
Posição 3Posição 3
Posição 4Posição 4
Posição 5Posição 5
Posição 6Posição 6
Alocação de TarefasAlocação de Tarefas
KakáKaká RenatoRenato AdrianoAdriano Juninho P.Juninho P. CicinhoCicinho Zé RobertoZé Roberto
Quantos gols fez a seleção nos últimos dez jogos em que cada um desses jogadores jogou nessas posições?
AdrianoAdriano
AdrianoAdriano
AdrianoAdriano
KakáKaká
KakáKaká
KakáKaká RenatoRenato
Juninho P.Juninho P.
Juninho P.Juninho P.
CicinhoCicinho
CicinhoCicinho
Zé RobertoZé Roberto
Zé RobertoZé Roberto
Zé RobertoZé Roberto
Zé RobertoZé Roberto
XX
XX
XX
XXXX
XX
XX
XX
XX
Álg
eb
ra L
inear
Álg
eb
ra L
inear
Posição 1Posição 1
Posição 2Posição 2
Posição 3Posição 3
Posição 4Posição 4
Posição 5Posição 5
Posição 6Posição 6
Alocação de TarefasAlocação de Tarefas
KakáKaká RenatoRenato AdrianoAdriano Juninho P.Juninho P. CicinhoCicinho Zé RobertoZé Roberto
Quantos gols fez a seleção nos últimos dez jogos em que cada um desses jogadores jogou nessas posições?
AdrianoAdriano
KakáKaká
RenatoRenato
Juninho P.Juninho P.
CicinhoCicinho
Zé RobertoZé Roberto
Álg
eb
ra L
inear
Álg
eb
ra L
inear
KakáKaká
RenatoRenato
AdrianoAdrianoJuninho P.Juninho P.
CicinhoCicinhoZé RobertoZé Roberto
Roque Jr.Roque Jr.
LúcioLúcio
MarcosMarcos
Ronaldo G.Ronaldo G.
RobinhoRobinho
EmersonEmerson