Aula 5 - Planejamento e distribuição de recursos

Prévia do material em texto

©2000-2001 Prof.ª Gladys Castillo
1
Problema de designação
Planejamento e distribuição de recursos
Iniciaremos às 08:00 Hs
Administração da Produção – Prof. Me – Ricardo Reiff
©2000-2001 Prof.ª Gladys Castillo
2
O Problema de designação
Suponha n trabalhadores a distribuir por n tarefas de forma a que cada trabalhador execute apenas uma tarefa, e que cada tarefa seja executada apenas por um trabalhador. 
Conhecendo os custos da realização de cada tarefa por cada trabalhador: 
 designar os trabalhadores às tarefas de forma a 
 minimizar os custos
O problema de designação é um problema de dimensão (n x n), em que:
as variáveis de decisão xij podem tomar valores 0 ou 1;
Administração da Produção – Prof. Me – Ricardo Reiff
2
©2000-2001 Prof.ª Gladys Castillo
3
Número de Possíveis Soluções
O Problema de designação envolve a determinação de n! possíveis soluções.
Exemplo:
para um problema com 5 trabalhadores e 5 tarefas o número de soluções possíveis é igual a 5 ! = 120.
para um problema com 10 trabalhadores e 10 tarefas o número de soluções é igual a 10 ! = 3 628 800.
Obter a solução ótima por tentativa é DIFÍCIL !
Administração da Produção – Prof. Me – Ricardo Reiff
3
©2000-2001 Prof.ª Gladys Castillo
4
Destino
Origem
 
1 2 … n
Oferta
1
2
.
.
.
.
.
.
.
.
.
.
.
.
Procura
 
1
 
 
 
 
… 
… 
 
 
 
 
c
c
11
11
c
c
12
12
c
c
1n
1n
c
c
21
21
c
c
22
22
c
c
2n
2n
c
c
m1
n1
c
c
m2
n2
c
c
mn
nn
x
x
11
11
x
x
12
12
x
x
1n
1n
…
…
x
x
21
21
x
x
22
22
x
x
2n
2n
…
…
x
x
n1
x
x
x
x
…
…
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
n2
nn
1
1
1
1
1
Problema de designação Formulação
n
Administração da Produção – Prof. Me – Ricardo Reiff
4
©2000-2001 Prof.ª Gladys Castillo
5
Minimizar
sujeito a:
 cada trabalhador é designado a uma só tarefa
cada tarefa é executada apenas por um trabalhador
Problema de designação Formulação
Administração da Produção – Prof. Me – Ricardo Reiff
©2000-2001 Prof.ª Gladys Castillo
6
 
 
Resolução do Problema de Designação
Método Húngaro
Este método consiste em adicionar ou subtrair valores de forma adequada às linhas e às colunas da matriz de custos de dimensão nn para obter um problema equivalente com n zeros enquadrados na matriz de custos
Uma vez transformada a matriz de custos numa matriz com n zeros enquadrados, esses zeros correspondem à designação ótima, tomando:
xij = 1, para os zeros enquadrados da matriz de custos transformada
xij = 0, para os restantes valores 
Administração da Produção – Prof. Me – Ricardo Reiff
6
©2000-2001 Prof.ª Gladys Castillo
7
Resolução do problema de designação
Método Húngaro - Exemplo
Considere que existem 5 trabalhadores que devem ser designados a 5 tarefas. A matriz dos custos associados à realização de cada tarefa por cada trabalhador é a seguinte:
		1	2	3	4	5
	1	17,5	15	9	5,5	12
	2	16	16,5	10,5	5	10,5
	3	12	15,5	14,5	11	5,5
	4	4,5	8	14	17,5	13
	5	13	9,5	8,5	12	17,5
Administração da Produção – Prof. Me – Ricardo Reiff
7
©2000-2001 Prof.ª Gladys Castillo
8
Resolução do problema de Designação
Método Húngaro
Início: Redução da Matriz de Custos.
1º. Subtrair aos elementos de cada coluna da matriz de custos o mínimo dessa coluna.
2º. Na matriz resultante, subtrair a cada linha o respectivo mínimo.
Iteração: 
1º. Desenhar o número mínimo de traços que cobrem todos os 
 zeros da matriz
2º. Critério de parada:
 o número mínimo de traços é igual a n?.
Sim – enquadrar n zeros, um por linha e um por coluna,
 a solução é ótima. FIM.
Não – passar a 3.
3º.  Redução da matriz de custos.
Determinar o menor valor não riscado .
Subtrair  a todos os elementos não riscados e somar  a todos os elementos duplamente riscados.
Considerar de novo todos os zeros livres e voltar a 1 (Iteração)
Administração da Produção – Prof. Me – Ricardo Reiff
8
©2000-2001 Prof.ª Gladys Castillo
9
 
 
 
1
 
 
 
 
 
 
2 
 
 3 
 
 
 4 
 
 
 
 
 5
1
2
3
4
5
13
7
0.5
0.5
6.5
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
 
 
1
 
 
 
 
 
 
2 
 3 
 
 
 4 
 
 
 
 
 5
1
1
2
3
4
5
17.5
15
9
5.5
12
16
12
4.5
13
16.5
10.5
15.5
14.5
8
9.5
14
8.5
5
11
17.5
12
10.5
5.5
13
17.5
1º: Subtrair o menor elemento de cada coluna de todos os elementos dessa coluna
 17.5 - 4.5 = 13 
 16 - 4.5 = 11.5 
 12 - 4.5 = 7.5 
 4.5 - 4.5 = 0 
 13 - 4.5 = 8.5 
menor elemento da coluna 1
Método Húngaro. Exemplo.
Início: Redução da Matriz de Custos.
Administração da Produção – Prof. Me – Ricardo Reiff
9
©2000-2001 Prof.ª Gladys Castillo
10
 
 
 
1
1
 
 
 
 
 
 
2 
2 
 
 
 3 
 3 
 
 
 4 
 4 
 
 
 
 
 5
 5
1
1
2
2
3
3
4
4
5
5
12.5
6.5
0
0
6
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
2º: Subtrair o menor elemento de cada linha de todos os elementos dessa linha
 
 
 
1
 
 
 
 
 
 
2 
 
 3 
 
 
 4 
 
 
 
 
 5
1
2
3
4
5
13
7
0.5
0.5
6.5
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
Existe empate na escolha do menor elemento da linha 1 (igual a 0.5).
 Nas linhas restantes o mínimo é zero, sendo que as linhas restantes não vão ser alteradas
 13 - 0.5 = 12.5 
 7 - 0.5 = 6.5 
 0.5 - 0.5 = 0 
6.5 - 0.5 = 6 
Método Húngaro. Exemplo.
Início: Redução da Matriz de Custos.
Administração da Produção – Prof. Me – Ricardo Reiff
10
©2000-2001 Prof.ª Gladys Castillo
11
 
 
 
1
 
 
 
 
2 
 
 
 3 
 
 
 4 
 
 
 
 
 5
1
1
2
3
3
4
4
5
5
12.5
6.5
0
0
6
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
Método Húngaro. Iteração: 
Critério de parada.
1º. Desenhar o número mínimo de traços que cobrem todos os 
 zeros da matriz.
2º. Critério de parada: o número mínimo de traços é igual a 5?.
 Não – passar a 3.
Administração da Produção – Prof. Me – Ricardo Reiff
11
©2000-2001 Prof.ª Gladys Castillo
12
 
 
1
 
 
 
 
 
 
2 
 
 
 3 
 
 
 4 
 
 
 
 
 5
1
2
3
3
4
4
5
12.5
6.5
0
0
6
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3
4
12.5
6.5
0
0
6
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
11.5
7.5
0
8.5
8.5
2
7.5
6
0
1.5
5.5
0
0
6
12.5
7
5
0
7.5
12
1º. min {elementos da submatriz dos 
 elementos não riscados } = 1.5
4º. Os restantes elementos não são alterados.
2º. Subtrair 1.5 a todos os elementos não riscados.
3º. Somar 1.5 aos elementos na intersecção dos traços.
 
 
 
1
 
 
 
 
 
 
2 
 
 
 3 
 
 
 4 
 
 
 
 
 5
1
2
3
4
5
11
5
0
0
4.5
10
7.5
0
7
7
2
7.5
7.5
0
0
7
0
0
7.5
14
7
3.5
0
7.5
10.5
Método Húngaro. Exemplo.
Iteração: Redução da Matriz de Custos.
Administração da Produção – Prof. Me – Ricardo Reiff
12
©2000-2001 Prof.ª Gladys Castillo
13
 
 
 
1
 
 
 
 
 
2 
 
 
 3 
 
 
 4 
 
 
 
 
 5
1
2
3
4
5
11
5
0
0
4.5
10
7.5
0
7
7
2
7.5
7.5
0
0
7
0
0
7.5
14
73.5
0
7.5
10.5
1º. Desenhar o número mínimo de traços que cobrem todos os 
 zeros da matriz.
2º. Critério de parada: o número mínimo de traços é igual a 5?.
 Sim – enquadrar 5 zeros, um por linha e um por coluna,
 a solução é ótima. FIM
Método Húngaro. Iteração: 
Critério de parada.
Administração da Produção – Prof. Me – Ricardo Reiff
13
©2000-2001 Prof.ª Gladys Castillo
14
 
 
1
 
 
 
 
 
 
2 
 
 
 3 
 
 
 4 
 
 
 
 
 5
1
2
3
4
5
17.5
15
9
5.5
12
16
12
4.5
13
16.5
10.5
15.5
14.5
8
9.5
14
8.5
5
11
17.5
12
10.5
5.5
13
17.5
Matriz inicial de custos
Método Húngaro. Exemplo: Solução Ótima.
solução ótima é : x13 = 1 , x24 = 1, x35 = 1, x41 = 1 , x52 = 1 
 com um custo total : 9 + 5 + 5.5 + 4.5 + 9.5 = 33.5
Administração da Produção – Prof. Me – Ricardo Reiff
14
å
=
=
n
j
ij
x
1
1
1
,
0
=
ij
x
n
i
,...,
2
,
1
 
,
=
n
j
,...,
2
,
1
 
,
=
n
j
,...,
2
,
1
 
,
=
å
=
=
n
i
ij
x
1
1
n
i
,...,
2
,
1
 
,
=
å
=
=
n
j
i
ij
ij
x
c
C
1
,