DESIGNAÇÃO
Introdução
Um caso especial do modelo de transportes é aquele em que cada origem
tem uma unidade disponível e cada destino necessita também de uma
unidade. É o caso de escalar vendedores para regiões de vendas, máquinas
para diversos locais etc.
Essa característica torna o algoritmo de soluções bastante simples. Antes de
aplicá-lo, devemos verificar se o modelo está equilibrado. No modelo de
designação, o número de origens deve ser igual ao número de destinos
devido a sua característica. Caso isso não ocorra, devemos construir
origens ou destinos auxiliares, com custo de transferência zero.
Exemplo: o quadro representa os custos de transporte de uma máquina dos
locais de depósito para as fábricas onde deverão ser instaladas. Designar
uma máquina para cada fábrica com o menor custo total possível:
F1
F2
F3
F4
L1
10
12
15
16
L2
14
12
13
18
L3
10
16
19
15
L4
14
12
13
15
Descrição do Algoritmo
a. Subtrair de cada linha seu menor valor. Em seguida fazer o mesmo
com as colunas. Cada linha e cada coluna deverá então apresentar
pelo menos um elemento nulo.
Subtrair o menor número de cada linha
F1
F2
F3
F4
L1
0
2
5
6
L2
2
0
1
6
L3
0
6
9
5
L4
2
0
1
3
Pesquisa Operacional
Prof. Célio Moliterno
Subtrair o menor número de cada coluna
F1
F2
F3
F4
L1
0
2
4
3
L2
2
0
0
3
L3
0
6
8
2
L4
2
0
0
0
b. Designar origens para destinos nas células em que aparece o
elemento nulo. Dar preferência a linhas ou colunas que tenham
apenas um zero disponível. Cada designação efetuada invalida os
outros zeros na linha e na coluna da célula designada. Se a
designação se completa, o problema está resolvido.
F1
F2
F3
F4
L1
0
2
4
3
L2
2
0
0
3
L3
0
6
8
2
L4
2
0
0
0
A designação não se completou devido a origem 3 e ao destino 3, então:
c. Cobrir os zeros da tabela com o menor número de linhas possível.
Isto pode ser feito da seguinte forma:
•
•
•
•
marcar as linhas sem designação;
nas linhas marcadas, marcar as colunas com zeros;
nas colunas marcadas, marcar as linhas com designação;
nas linhas marcadas ,voltar a marcar as colunas com zeros até
que não seja possível marcar novas linhas ou colunas;
• riscar as linha não marcadas e as colunas marcadas.
Pesquisa Operacional
Prof. Célio Moliterno
F1
F2
F3
F4
L1
0
2
4
3
L2
2
0
0
3
L3
0
6
8
2
L4
2
0
0
0
d. Encontrar o menor valor dentre os números não cobertos, de todos os
elementos da tabela.
• os elementos não cobertos ficam diminuídos deste número;
• os elementos no cruzamento de coberturas ficam aumentados
desse número;
• ao outros elementos permanecem iguais.
F1
F2
F3
F4
L1
0
0
2
1
L2
4
0
0
3
L3
0
4
6
0
L4
4
0
0
0
e. Fazer nova designação, retornar ao item b.
F1
F2
F3
F4
0
2
1
0
3
6
0
L1
0
L2
4
0
L3
0
4
L4
4
0
Solução: Designação
0
0
L1 -> F1 Custo 10 L3 -> F4 Custo 15
L2 -> F2 Custo 12 L4 -> F3 Custo 13
Total Custo 50
Pesquisa Operacional
Prof. Célio Moliterno
O Caso de Maximização
Caso a tabela de transferência traga retornos que devem ser maximizados, o
modelo deverá ser substituído por outro de minimização. Como no
problema dos transportes, isto pode ser feito multiplicando a função
objetivo por -1, ou transformando o quadro num quadro de perdas
(complemento em relação a um valor fixo).
Exemplo: o quadro representa as eficiências de quatro vendedores,
testados em quatro regiões. Os potenciais de vendas nas regiões são
conhecidos. Designar um vendedor para cada região para maximizar o
valor total das vendas.
Capacidade de cada vendedor de atingir o potencial da região em %
R1
R2
R3
R4
V1
70
60
80
90
V2
70
80
70
90
V3
60
90
60
70
V4
70
80
70
80
Potencial de vendas em milhares de $
R1 = 100 ; R2 = 80 ; R3 = 60 R4 = 90
Solução: Quadro de vendas ou retornos (% x Potencial de Vendas)
R1
R2
R3
R4
V1
70
48
48
81
V2
70
64
42
81
V3
60
72
36
63
V4
70
64
42
72
Pesquisa Operacional
Prof. Célio Moliterno
Quadro de perdas: subtrair de 81
R1
R2
R3
R4
V1
11
33
33
0
V2
11
17
39
0
V3
21
9
45
18
V4
11
17
39
9
Aplicar o algoritmo do caso de minimização
Subtrair o menor número de cada linha
R1
R2
R3
R4
V1
11
33
33
0
V2
11
17
39
V3
12
0
V4
2
8
Subtrair o menor número de cada coluna
R1
R2
R3
R4
V1
9
33
3
0
0
V2
9
17
9
0
36
9
V3
10
0
6
9
30
0
V4
0
8
0
0
Designar origens para destinos ( item b )
R1
R2
R3
R4
V1
9
33
3
0
V2
9
17
9
0
V3
10
0
6
9
V4
0
8
0
0
A designação não se completou, origem 2 destino 3
Cobrir os zeros com o menor número de linhas possível ( item c )
R1
R2
R3
R4
V1
9
33
3
0
V2
9
17
9
0
V3
10
0
6
9
V4
0
8
0
0
Pesquisa Operacional
Prof. Célio Moliterno
Encontrar o menor valor dentre os números não cobertos, de todos os
elementos da tabela ( item d ).
Subtrair 3 da tabela:
R1
R2
R3
R4
V1
6
30
0
0
V2
6
14
6
0
V3
10
0
6
12
V4
0
8
0
3
Fazer nova designação, retornar ao item b.
R1
R2
R3
R4
V1
6
30
00
0
V2
6
14
6
0
V3
10
0
6
12
V4
0
8
0
3
Designação
V1
V2
V3
V4
Vendas (em milhares de $)
R3
R4
R2
R1
Total
48
81
72
70
271
Exercícios:
1. Resolva o problema de designação:
1
2
3
4
1
10
23
8
9
2
4
5
6
7
3
12
10
10
8
4
6
4
9
7
Destinos
Solução
Origem Destino
1
3
2
1
3
4
4
2
Custo 24
Origens
Pesquisa Operacional
Prof. Célio Moliterno
2. Resolva o problema de designação:
1
2
3
4
1
6
8
10
9
2
4
3
6
5
3
7
9
12
6
Origens
Destinos
Solução
Origem Destino
1
1
2
2
3
4
4
3
Custo 15
3. Resolva o problema de designação, onde o símbolo X indica a
impossibilidade da designação da origem para o destino
correspondente:
1
2
3
1
6
X
8
2
4
9
3
3
5
6
4
4
8
10
12
Destinos
Solução
Origem Destino
1
1
2
3
3
2
4
4
Custo 15
Origens
4. Quatro locais, L1, L2, L3, L4 necessitam de um equipamento. Existem
quatro equipamentos disponíveis, um em cada um dos depósitos
D1, D2, D3, D4. A quilometragem entre os locais necessitados e os
depósitos estão no quadro:
L1
L2
L3
L4
D1
100
120
130
140
D2
80
70
120
90
D3
100
80
100
110
D4
90
90
120
80
Solução
Origem Destino
1
1
2
2
3
3
4
4
Km 350
Determine um programa de expedição de quilometragem mínima.
Pesquisa Operacional
Prof. Célio Moliterno