PROBLEMAS DE ALOCAO

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Problemas de Alocação
MATÉRIA: PESQUISA OPERACIONAL
PROFESSOR: ODIVANEY RAMOS PEDRO
UNA
Problema de Alocação
	O Problema de Alocação é um caso específico do Problema de Transporte, que por sua vez é um caso específico de um Problema de Programação Linear. Sendo assim o Problema de Alocação é um caso de Programação Linear.
2
Problema de Alocação
	O objetivo básico do Problema é a Alocação de cada uma das Origens aos Destinos, de maneira ótima.
3
Problema de Alocação
Exemplos:
4
Exemplo...
	Designar 4 operários [ I, II, III, IV ] para executar 4 tarefas (A, B, 
C, D) de maneira que o tempo total para o término de todas as 
tarefas seja o menor possível. Conhece-se o tempo que cada 
operário gasta para desempenhar cada uma das 4 tarefas:
5
Exemplo...
Modelo em Redes
6
Problema de Alocação
Considerações
Utiliza-se variáveis de decisão binárias (Xij).
Possui dimensão (n x n).
O problema tem n! possíveis soluções.
Resolver por enumeração.
7
Formulação Matemática
8
Formulação Completa
Variável de decisão:
Matriz de Custos:
9
Exemplo
Designação Viável
Custo total igual a ... 52
10
Formulação Completa
Função Objetivo:
11
Formulação Completa
Restrições:
12
Método Húngaro
	O algoritmo Húngaro foi proposto por Harold Kuhn na década de 1950 para resolver problemas de redes. Facilmente aplicado para resolver problemas de alocação de recursos.
13
Método Húngaro ou de Rotulação
Exemplo
	Os três filhos de Francisco (Zezé, Luciano e Marcelinho) estão precisando de dinheiro, e pediram a seu pai. O Sr. Franciso escolheu três tarefas para que eles faça e assim possam receber o dinheiro:
	1 – Cantar.
	2 – Tocar violão.
	3 – Compor. 
14
Método Húngaro
Exemplo
	Para evitar a concorrência prevista entre os irmãos, ele pediu que seus filhos apresentassem propostas (fechadas) do que eles consideravam que fosse um pagamento justo para cada uma das três tarefas. 
15
Método Húngaro
Exemplo
	Ficou combinado que os três concordariam com a decisão do pai sobre quem executaria qual tarefa. A Tabela a seguir resume as propostas recebidas. Com base nessas informações, como o Sr. Francisco deve designar as tarefas?
16
Método Húngaro
Exemplo
Problema de designação do Sr. Francisco
			 Cantar	 Tocar	Compor 
Zezé		 $ 15	 $ 10	$ 9
Marcelinho $ 9	 $ 15	$ 10
Luciano	 $ 10	 $ 12	$ 8
O Método Húngaro
Passos
1º - Ajustando linhas
	A- determinar o menor valor da linha (ML).
	B- Subtrair ML de todos os valores da linha.
2º - Ajustando colunas
	A- determinar o menor valor da coluna (MC).
	B- Subtrair MC de todos os valores da coluna.
3° - Rotular minimamente os 0’s (zeros) da Matriz.
Método Húngaro
Exemplo – Passo 1
Cantar
Tocar
Compor
Zezé
15
10
9
Marcelinho
9
15
10
Luciano
10
12
8
Método Húngaro
Exemplo – Passo 1
Cantar
Tocar
Compor
Zezé
6
1
0
Marcelinho
0
6
1
Luciano
2
4
0
Método Húngaro
Exemplo – Passo 2
Cantar
Tocar
Compor
Zezé
6
1
0
Marcelinho
0
6
1
Luciano
2
4
0
Método Húngaro
Exemplo – Passo 2
Cantar
Tocar
Compor
Zezé
6
0
0
Marcelinho
0
5
1
Luciano
2
3
0
Método Húngaro
Exemplo – Passo 3
Cantar
Tocar
Compor
Zezé
6
0
0
Marcelinho
0
5
1
Luciano
2
3
0
Método Húngaro
Resposta
		A resposta encontrada tem um custo de 10+9+8 =$27,00. 
		O resultado sempre será igual à
	 (ML1+ML2+ML3) + (MC1+MC2+MC3) = 		 (9+9+8) + (0+1+0)= 
				$27,00.
Método Húngaro
	As etapas do método húngaro apresentadas funcionam bem no exemplo precedente porque as entradas zero na matiz final produzem uma designação viável (no sentido de que uma tarefa distinta é designada a cada filho). Em alguns casos, os zeros criados pelas etapas 1 e 2 podem não resultar em uma solução viável diretamente e serão necessárias mais etapas para achar a designação ótima (viável).
25
Método Húngaro
Exemplo
	 Considere que Wellignton também pediu dinheiro ao sr Francisco, sendo assim ele arrumou mais uma tarefa para dividir para os quatro filhos.
26
Método Húngaro
Exemplo
Cantar
Tocar
Compor
Dançar
Zezé
15
10
9
12
Marcelinho
9
15
10
8
Luciano
10
12
8
10
Wellington
11
8
13
9
Método Húngaro
Exemplo – Passo 1
Cantar
Tocar
Compor
Dançar
Zezé
15
10
9
12
Marcelinho
9
15
10
8
Luciano
10
12
8
10
Wellington
11
8
13
9
Método Húngaro
Exemplo – Passo 1
Cantar
Tocar
Compor
Dançar
Zezé
6
1
0
3
Marcelinho
1
7
2
0
Luciano
2
4
0
2
Wellington
3
0
5
1
Método Húngaro
Exemplo – Passo 2
Cantar
Tocar
Compor
Dançar
Zezé
6
1
0
3
Marcelinho
1
7
2
0
Luciano
2
4
0
2
Wellington
3
0
5
1
Método Húngaro
Exemplo – Passo 2
Cantar
Tocar
Compor
Dançar
Zezé
5
1
0
3
Marcelinho
0
7
2
0
Luciano
1
4
0
2
Wellington
2
0
5
1
Método Húngaro
Exemplo – Passo 3
Cantar
Tocar
Compor
Dançar
Zezé
5
1
0
3
Marcelinho
0
7
2
0
Luciano
1
4
0
2
Wellington
2
0
5
1
Método Húngaro
Passos
4º - Determinar o menor valor (MV) NÃO riscado da matriz. 
5° - Diminuir MV de todos os valores NÃO RISCADOS e somá-lo a todos os cruzados por DOIS riscos.
 Retornar ao passo 3; 
33
Método Húngaro
Exemplo – Passo 4
Cantar
Tocar
Compor
Dançar
Zezé
5
1
0
3
Marcelinho
0
7
2
0
Luciano
1
4
0
2
Wellington
2
0
5
1
Método Húngaro
Exemplo – Passo 5
Cantar
Tocar
Compor
Dançar
Zezé
4
1
0
2
Marcelinho
0
7
2
0
Luciano
0
4
0
1
Wellington
1
0
5
0
Método Húngaro
Exemplo – Passo 5
Cantar
Tocar
Compor
Dançar
Zezé
4
1
0
2
Marcelinho
0
8
3
0
Luciano
0
4
0
1
Wellington
1
0
5
0
Método Húngaro
Exemplo – Passo 3
Cantar
Tocar
Compor
Dançar
Zezé
4
1
0
2
Marcelinho
0
8
3
0
Luciano
0
4
0
1
Wellington
1
0
5
0
Método Húngaro
Exemplo
Cantar
Tocar
Compor
Dançar
Zezé
4
1
0(1)
2
Marcelinho
0
8
3
0(3)
Luciano
0(2)
4
0
1
Wellington
1
0(4)
5
0
Método Húngaro
Exemplo
Cantar
Tocar
Compor
Dançar
Zezé
15
10
9
12
Marcelinho
9
15
10
8
Luciano
10
12
8
10
Wellington
11
8
13
9
Exemplo 2
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
94
1
54
68
Máquina 2
74
10
88
82
Máquina 3
62
88
8
76
Máquina 4
11
74
81
21
Exemplo 2 – Passo 1
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
94
1
54
68
Máquina 2
74
10
88
82
Máquina 3
62
88
8
76
Máquina 4
11
74
81
21
Exemplo 2 – Passo 1
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
93
0
53
67
Máquina 2
64
0
78
72
Máquina 3
54
80
0
68
Máquina 4
0
63
70
10
Exemplo 2 – Passo 2
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
93
0
53
67
Máquina 2
64
0
78
72
Máquina 3
54
80
0
68
Máquina 4
0
63
70
10
Exemplo 2 – Passo 2
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
93
0
53
57
Máquina 2
64
0
78
62
Máquina 3
54
80
0
58
Máquina 4
0
63
70
0
Exemplo 2 – Passo 3
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
93
0
53
57
Máquina 2
64
0
78
62
Máquina 3
54
80
0
58
Máquina 4
0
63
70
0
Exemplo 2 – Passo 4
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
93
0
53
57
Máquina 2
64
0
78
62
Máquina 3
54
80
0
58
Máquina 4
0
63
70
0
Exemplo 2 – Passo 5
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
40
0
0
4
Máquina 2
11
0
25
9
Máquina 3
54
80
0
58
Máquina 4
0
63
70
0
Exemplo 2 – Passo 5
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
40
0
0
4
Máquina 2
11
0
25
9
Máquina 3
54
133
0
58
Máquina 4
0
116
70
0
Exemplo 2 – Passo 3
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
40
0
0
4
Máquina 2
11
0
25
9
Máquina 3
54
133
0
58
Máquina 4
0
116
70
0
Exemplo 2 – Passo 4
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
40
0
0
4
Máquina 2
11
0
25
9
Máquina 3
54
133
0
58
Máquina 4
0
116
70
0
Exemplo 2 – Passo 5
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
36
0
0
0
Máquina 2
7
0
25
5
Máquina 3
50
133
0
54
Máquina 4
0
116
70
0
Exemplo 2 – Passo 5
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
36
0
0
0
Máquina 2
7
0
25
5
Máquina 3
50
133
0
54
Máquina 4
0
120
74
0
Exemplo 2 – Passo 3
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
36
0
0
0
Máquina 2
7
0
25
5
Máquina 3
50
133
0
54
Máquina 4
0
120
74
0
Exemplo 2 – 
encontrando a solução
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
36
0
0
0 (3)
Máquina 2
7
0 (1)
25
5
Máquina 3
50
133
0 (2)
54
Máquina 4
0 (4)
120
74
0
Exemplo 2
Tarefa 1
Tarefa
2
Tarefa
3
Tarefa 4
Máquina 1
94
1
54
68
Máquina 2
74
10
88
82
Máquina 3
62
88
8
76
Máquina 4
11
74
81
21