Álgebra Linear
UNIVERSIDADE FEDERAL FLUMINENSE
O Problema da
Alocação de Tarefas
Por:
Viviane Liria
Professora:
Ana Isabel
Álgebra Linear
O Problema da Alocação de Tarefas
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.
C11
C12
...
C1n
C21
C22
...
C2n
C=
Matriz-custo
...
...
Cn1
Cn2
...
...
Cnn
Álgebra Linear
O Problema da Alocação de Tarefas
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 1
Prédio 2
Prédio 3
Firma 1
53
96
37
Firma 2
47
87
41
Firma 3
60
92
36
Álgebra Linear
O Problema da Alocação de Tarefas
Exemplo1
A matriz custo para este problema é a matriz 3x3:
53
C=
96
37
47
87
41
60
92
36
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:
Álgebra Linear
O Problema da Alocação de Tarefas
53
96
37
47
87
41
60
92
36
• 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.
Álgebra Linear
Alocação de Tarefas
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:
0 5 0 3
0 4 2 5
6 0 7 7
7 9 0 0
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.
Álgebra Linear
Alocaçã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.
Álgebra Linear
Alocação de Tarefas
O Método Húngaro
Exemplo 2:
Matriz-custo:
90
75
75
80
35
85
55
65
125
95
90
105
45
110
95
115
Álgebra Linear
Alocação de Tarefas
O Método Húngaro
90
75
75
80
35
85
55
65
125
95
90
105
45
110
95
115
15
0
0
5
0
50
20
30
35
5
0
15
0
65
50
70
Passo 1: Subtraímos a menor entrada
de cada linha
Passo 2: As três primeiras colunas da
matriz já contém entradas zero,
portanto, só precisamos subtrair da
quarta coluna.
Álgebra Linear
Alocação de Tarefas
O Método Húngaro
15
0
0
0
0
50
20
25
35
5
0
10
0
65
50
65
35
0
0
5
0
30
0
5
55
5
0
10
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.
0
45
30
45
Passo 5: Repetiremos o passo 3.
Passo 3: Riscamos as entradas zero
utilizando um número mínimos de
traços.
Álgebra Linear
Alocação de Tarefas
O Método Húngaro
35
0
0
5
0
30
0
5
55
5
0
10
0
45
30
45
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.
Encontramos, portanto, duas opções para alocação de
tarefas.
Álgebra Linear
Alocaçã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
Álgebra Linear
Alocação de Tarefas
O Problema de Alocação de Tarefas de Carlos Alberto Parreira
Kaká
Renato
Adriano
Juninho P.
Cicinho
Zé Roberto
?
?
Robinho
Roque Jr.
Marcos
?
Emerson
Ronaldo G.
Lúcio
?
?
Álgebra Linear
Kaká
Renato
Adriano
Juninho P. Cicinho Zé Roberto
1
4
Robinho
Roque Jr.
Marcos
2
Emerson
Ronaldo G.
Lúcio
5
3
Álgebra Linear
Quantos gols fez a seleção nos últimos dez jogos em que cada um desses
jogadores jogou nessas posições?
Kaká
Renato
Adriano
Juninho P.
Cicinho
Zé Roberto
Posição 1
15
7
21
14
14
21
Posição 2
18
8
23
16
7
23
Posição 3
14
9
20
14
19
21
Posição 4
14
7
19
13
13
19
Posição 5
17
5
20
16
21
20
Posição 6
0
0
0
0
0
0
Álgebra Linear
Alocação de Tarefas
15
7
21
14
14
21
18
8
23
16
7
23
14
9
20
14
19
21
14
7
19
13
13
19
17
5
20
16
21
20
0
0
0
0
0
0
-15
-7
-21
-14
-14
-21
-18
-8
-23
-16
-7
-23
-14
-9
-20
-14
-19
-21
-14
-7
-19
-13
-13
-19
-17
-5
-20
-16
-21
-20
0
0
0
0
0
0
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).
Álgebra Linear
Alocação de Tarefas
-15
-7
-21
-14
-14
-21
-18
-8
-23
-16
-7
-23
-14
-9
-20
-14
-19
-21
-14
-7
-19
-14
-13
-19
-17
-5
-20
-16
-21
-20
0
0
0
0
0
0
6
14
0
7
7
0
5
15
0
7
16
0
7
12
1
7
2
0
5
12
0
5
6
0
4
16
1
5
0
1
0
0
0
0
0
0
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.
Álgebra Linear
Alocação de Tarefas
6
14
0
7
7
0
5
15
0
7
16
0
7
12
1
7
2
0
5
12
0
5
6
0
4
16
1
5
0
1
0
0
0
0
0
0
4
12
0
5
5
0
3
13
0
5
14
0
5
10
1
5
0
0
3
10
0
3
4
0
4
16
3
5
0
3
0
0
2
0
0
2
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.
Álgebra Linear
Alocação de Tarefas
1
9
0
2
5
0
0
10
0
2
14
0
2
7
1
2
0
0
0
7
0
0
4
0
1
13
3
2
0
3
0
0
5
0
3
5
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.
Álgebra Linear
Alocação de Tarefas
As entradas zero representam o melhor desempenho de cada jogador.
Kaká
Renato
Adriano
Juninho P.
Cicinho
Zé Roberto
Posição 1
1
9
0
2
5
0
Posição 2
0
10
0
2
14
0
Posição 3
2
7
1
2
0
0
Posição 4
0
7
0
0
4
0
Posição 5
1
13
3
2
0
3
Posição 6
0
0
5
0
3
5
Álgebra Linear
Alocação de Tarefas
Quantos gols fez a seleção nos últimos dez jogos em que cada um desses
jogadores jogou nessas posições?
Kaká
Renato
Adriano
Juninho P.
Cicinho
X
Posição 1
Adriano
Zé Roberto
X
Posição 2
Kaká
X
Zé Roberto
Adriano
X
Posição 3
Cicinho
Posição 4
X
X
Adriano
Kaká
Cicinho
X
Kaká
Renato
X
Juninho P.
Zé Roberto
X
Zé Roberto
Juninho P.
Posição 5
Posição 6
Zé Roberto
Álgebra Linear
Alocação de Tarefas
Quantos gols fez a seleção nos últimos dez jogos em que cada um desses
jogadores jogou nessas posições?
Kaká
Renato
Adriano
Juninho P.
Cicinho
Zé Roberto
Posição 1
Adriano
Posição 2
Kaká
Posição 3
Zé Roberto
Posição 4
Juninho P.
Posição 5
Cicinho
Posição 6
Renato
Álgebra Linear
Renato
Adriano
Juninho P.
Robinho
Roque Jr.
Marcos
Emerson
Kaká
Ronaldo G.
Lúcio
Cicinho
Zé Roberto