Faculdade de Engenharia - Campus de Guaratinguetá
Pesquisa Operacional
Livro: Introdução à Pesquisa Operacional
Capítulo 5 – Modelo da Designação
Fernando Marins – [email protected]
Departamento de Produção
1
Sumário
Introdução
Modelo da Designação
Método Húngaro
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
2
Introdução
Problema: alocação de recursos disponíveis para atividades de
interesse de forma a otimizar alguma medida de efetividade do
sistema.
Exemplos de aplicações
RECURSO
ATIVIDADE
CRITÉRIO
Operários
Tarefas
Tempo de execução
Caminhões
Rotas
Custo de transporte
Máquinas
Vendedores
Locais
Regiões
Operacionalidade
Volume de vendas
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
3
Introdução
Trata-se de um caso particular do Modelo de Transporte Simples
com ai= bj = 1.
Pode ser resolvido pelo Método Simplex ou pelo
“Stepping Stone Method”.
Será apresentado um algoritmo mais eficiente que explora suas
características particulares: Algoritmo Húngaro.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
4
Modelo da Designação
Seja a matriz C = (cij ) de ordem m x m, onde cada valor cij corresponde
ao custo da alocação do recurso i à atividade j.
1, recurso i alocado à atividade j
Variáveis de decisão: xij = 

0, caso contrário
Função objetivo:
Minimização de CT = custo total de designação
Min CT =   C ij X ij
i
j
Restrições:
sujeito
 Xij = 1,  j 1, 2, ..., m (Toda atividade recebe um recurso)
a:  i
 Xij = 1,  i  1, 2, ..., m (Cada recurso designado a uma atividade)
J
Xij {0,1} para todo i = 1, 4 e j = 1, 4 (binárias)
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
5
Modelo da Designação - 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:
[ I
II III IV ]
 A   5 24 13 7 
 B  10 25 3 23
 

C   28 9 8 5 
 

 D  10 17 15 3 
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
6
Modelo em Redes
1
5
A
24
7
10
1
B
1
C
10
1
D
1
II
1
III
1
IV
1
13
25
3
23
28
I
9
8
5
17
15
3
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
7
Modelo da Designação - Exemplo
Como exemplo, uma designação viável pode ser identificada da forma abaixo :
[ I II III IV ]
A 
B 
 
C 
 
D 
Neste caso a matriz
corresponde a:
X=
5 24

10 25
 28  9

10 17
13
3
8
15
7 
 23
5 

3 
X associada com os valores das variáveis básicas Xij
1

0
0

0
0 0 0

0 0 1
1 0 0

0 1 0
O valor do tempo total de designação associado a esta solução é calculado por:
CT =   C ij . X ij = 5 . 1 + 9 . 1 + 15 . 1 + 23 . 1 = 52
i
J
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
8
Modelo completo para o exemplo dos operários e tarefas
Variáveis de decisão: i = 1, 4
e
j = 1,4
1, se a tarefa i for para operário j
Xij = 
0, caso contrário
Função objetivo:
Min T = tempo total execução das tarefas
Min T = 5X11 + 24X12 + 13X13 + 7X14 + 10X21 + 25X22 +
+ 3X23 + 23X24 + 28X31 + 9X32 + 8X33 + 5X34 +
+ 10X41 + 17X42 + 15X43 + 3X44
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
9
Modelo completo para o exemplo dos operários e tarefas
Restrições:
sujeito a
X11 + X12 + X13 + X14 = 1
X21 + X22 + X23 + X24 = 1
X31 + X32 + X33 + X34 = 1
X41 + X42 + X43 + X44 = 1
X11 + X21 + X31 + X41 = 1
X12 + X22 + X32 + X42 = 1
X13 + X23 + X33 + X43 = 1
X14 + X24 + X34 + X44 = 1
(para as tarefas)
(para os operários)
Xij {0,1} para todo i = 1, 4 e j = 1, 4
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
(binárias)
10
Método Húngaro para Resolução
Fase 1: Redução de linhas e colunas da matriz C
Objetivo é facilitar a identificação das melhores opções de designação
(associados com os custos nulos existentes na matriz reduzida). Ir para a
Fase 2.
Fase 2: Identificação de uma Solução Ótima
Tentar achar uma Designação Completa que utilize as alocações de
recursos à atividades associadas aos custos nulos existentes na matriz
reduzida.
Se não for obtida uma Designação Completa: ir para a Fase 3.
Fase 3: Alterações adicionais na matriz C
Necessária se não for obtida uma designação completa na Fase 2.
Voltar à Fase 2.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
11
Aplicação do Método Húngaro ao exemplo dos operários e
tarefas
Fase 1: fazendo a redução das linhas:
I
II
III
IV
Menor
A
5
24
13
7
5
B
10
25
3
23
3
C
28
9
8
5
D
10
17
15
5
3
3
Fase 1: fazendo a redução das colunas:
I
A
0
II
19
B
7
22
0
20
C
23
4
3
0
D
Menor
7
0
14
4
12
0
0
0
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
III
8
IV
2
12
Aplicação do Método Húngaro ao exemplo
dos operários e tarefas
Fase 2: Procurando identificar uma designação completa:
I
II
III
IV
A
[0]
15
8
2
B
7
18
[0]
20
C
23
[0]
3
0
D
7
10
12
[0]
A solução ótima será dada por:
X11 = 1  tarefa A para o operário I
X23 = 1  tarefa B para o operário III
X32 = 1  tarefa C para o operário II
X44 = 1  tarefa D para o operário IV
Tempo ótimo de execução das tarefas (ver na matriz original as posições designadas):
T* = 5 + 3 + 9 + 3 = 20
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
13
Algoritmo Húngaro completo
Fase 1: Redução de Linhas e Colunas – Obter a Matriz C Reduzida
(I) Subtrair o elemento mínimo de cada linha (e coluna) de todos os elementos
daquela linha (e coluna).
Ir à Fase 2 (Etapa (II)).
Fase 2: Identificação de Designação Ótima na Matriz C Reduzida
(II) Examinar linhas e colunas sucessivamente.
Para cada linha (coluna) com exatamente um zero não reservado ([0]) ou
eliminado () reservar esta posição para uma designação e eliminar os demais
zeros da coluna (linha) correspondente.
Repetir este processo para as linhas e colunas sem posições reservadas até que
todos os zeros tenham sido reservados ([0]) ou eliminados ().
Se as posições reservadas formarem uma designação completa 
Solução Ótima foi obtida. Parar!
Caso contrário  ir a Fase 3 (etapas (III) e (IV))
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
14
Algoritmo Húngaro completo
Fase 3: Etapa (III) – Proteger os zeros essenciais na Matriz C reduzida
(A)Marcar com um asterisco ao lado da tabela todas as linhas sem zeros
reservados;
(B) Em linhas marcadas, marcar com um asterisco ao lado da tabela todas as
colunas que tenham zeros (reservados ou eliminados);
(C) Em colunas marcadas, marcar com um asterisco ao lado da tabela todas as
linhas que tenham zeros reservados;
(D) Repetir
adicionais
(B) e (C) até não se conseguir marcar linhas ou colunas
(E) Cobrir com uma reta cada linha não marcada e cada coluna marcada
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ir à Fase 3 – Etapa (IV)
15
Algoritmo Húngaro completo
Fase 3: Etapa (IV) - Redução adicional na Matriz C Reduzida
(IV) Examinar os elementos não cobertos por retas na etapa (III) e
identificar o elemento mínimo.
Subtrair este elemento mínimo de todos os elementos não cobertos por
retas
Somar este elemento mínimo a todos os elementos cobertos por mais de
uma reta (nas intersecções de duas retas)
Manter os demais elementos da matriz como são.
Retornar à Fase 2.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
16
Comentários gerais
• O número mínimo de retas necessárias para cobrir
todos os zeros da Matriz de Custos Reduzida = número
máximo de designações possível com os zeros
disponíveis.
• Designações impossíveis: bloquear a posição (colocar
um custo muito alto na Função Objetivo) associada à
designação impossível na Matriz C original
• Matriz de custos não é quadrada: adicionar linhas ou
colunas fictícias e custos nulos.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
17
Comentários gerais
• Problema de maximização:
Multiplicar todos os elementos da matriz C por (-1)
Identificar o elemento de maior valor em módulo
Somar o elemento de maior módulo a todos os elementos
da nova matriz de custos (já multiplicada por (-1))
Resolver como se fosse de minimização
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
18
Exemplo de Minimização
O presidente de uma empresa está estudando a transferência de
quatro diretores para quatro locais de trabalho diferentes. Foram
feitas estimativas dos custos envolvidos na transferência de cada
diretor para cada novo local de trabalho. Estes custos são dados a
seguir:
Local
DIRETOR
1
2
3
4
A
2
1
4
2
B
3
4
1
6
C
1
2
6
5
D
1
3
3
7
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
19
Exemplo
Obter a designação de diretores para locais de trabalho de menor
custo.
Fase 1: Reduzindo as linhas da matriz C
1
2
3
4
Menor
A
2
1
4
2
1
B
3
4
1
6
1
C
1
2
6
5
1
D
1
3
3
7
1
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
20
Exemplo
Resolução do exemplo dos diretores e locais
Fase 1: Reduzindo as colunas da matriz C – Etapa I
1
2
3
4
A
1
0
3
1
B
2
3
0
5
C
0
1
5
4
D
0
2
2
6
Menor
0
0
0
1
Ir para Fase 2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
21
Exemplo
Fase 2: Tentando identificar uma designação completa – Etapa II
1
2
3
4
A
1
[0]
3

B
2
3
[0]
4
C
[0]
1
5
3
D

2
2
5
Não foi obtida uma designação completa  Ir para a Fase 3.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
22
Exemplo
Fase 3: Etapa (III) - Proteger os Zeros
(A): Marcar linha sem Designação
1
2
3
4
A
1
[0]
3

B
2
3
[0]
4
C
[0]
1
5
3
D

2
2
5
Marca
*
Marca
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
23
Exemplo
Fase 3: Etapa (III) - Proteger os Zeros
(B): Em linha marcada, marcar coluna com zero
1
2
3
4
A
1
[0]
3

B
2
3
[0]
4
C
[0]
1
5
3
D

2
2
5
Marca
*
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Marca
*
24
Exemplo
Fase 3: Etapa (III) - Proteger os Zeros
( C): Em coluna marcada, marcar linha com zero designado
1
2
3
4
A
1
[0]
3

B
2
3
[0]
4
C
[0]
1
5
3
*
D

2
2
5
*
Marca
*
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Marca
25
Exemplo
Fase 3: Etapa (III) - Proteger os Zeros
(D): Repetir (A), (B) e (C)
• Não há como marcar novas colunas, pois a coluna 1 já foi
marcada na iteração anterior.
• Finalizadas as Etapas de (A) – (D)
• Ir Para Fase 3 – (E)
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
26
Exemplo
Fase 3: Etapa (III) – Proteger os zeros
Fase (E): traçar reta sobre linha não marcada e sobre coluna
marcada
1
2
3
4
Marca
A
1
[0]
3

B
2
3
[0]
4
C
[0]
1
5
3
*
D

2
2
5
*
Marca
*
Fase 3 - Etapa (IV): O menor elemento não coberto por alguma reta é =
1, na posição (C, 2).
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
27
Fase 3 – Etapa IV
Fase 3 – Etapa IV: Modificações adicionais na Matriz C Reduzida:
subtrair 1 dos números não cobertos por alguma reta e somar 1 aos
que estão no cruzamento de 2 retas. Os demais não mudam.
1
2
3
4
A
2
0
3
0
B
3
3
0
4
C
0
0
4
2
D
0
1
1
4
Voltar à Fase 2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
28
Fase 2 – Etapa II
Fase 2: Identificação de uma Designação Ótima
1
2
3
4
A
2

3
[0]
B
3
3
[0]
4
C

[0]
4
2
D
[0]
1
1
4
Foi obtida uma solução ótima: Diretor A vai para Local 4, Diretor
B vai para o Local 3, Diretor C vai para o Local 2 e o Diretor D vai
para o Local 1.
Custo ótimo = soma dos custos originais para as designações
ótimas = 2 + 1 + 2 + 1 = 6
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
29
Exercícios
1. O Diretor de uma escola deseja inscrever quatro alunos num
concurso de matemática que engloba os seguintes assuntos:
Álgebra, Cálculo I, Linguagens de Computação e Cálculo II.
Somente um aluno pode ser inscrito em cada assunto e nenhum
aluno pode ser inscrito em mais de um assunto porque as provas
do concurso ocorrerão simultaneamente. Para isso ele seleciona
seus quatro melhores alunos, A, B, C, D e lhes aplica testes
cobrindo as quatro áreas do concurso. O quadro abaixo indica o
número de pontos que cada aluno obteve em cada uma das áreas
no exame simulado.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
30
Exercícios
A
B
C
D
Álgebra
Cálculo I
Computação
Cálculo II
7
8
4
5
10
7
9
4
8
8
3
6
3
1
5
9
Qual aluno deve ser selecionado para cada um dos assuntos do
concurso, sendo que o Diretor resolveu que o aluno B não deverá
fazer a prova de Cálculo II?
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
31
Exercícios
2.
Uma empresa vende produtos em quatro regiões e possui quatro
vendedores que devem atender quatro regiões diferentes, sendo
um vendedor para cada região.
As regiões não são igualmente ricas e apresentam o seguinte
potencial de venda (em $):
Região I: 60.000
Região II: 50.000
Região III: 40.000
Região IV:30.000
Os vendedores por outro lado, não são igualmente hábeis e as suas
eficiências, que refletem a capacidade de atingir o mercado
potencial da região, são dados pelo quadro que se segue:
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
32
Exercícios
Vendedor
A
B
C
D
I
0,7
0,8
0,5
1,0
II
0,7
0,8
0,5
0,4
Região
III
0,7
0,8
0,5
1,0
IV
1,0
1,0
1,0
0,4
Pede-se determinar, empregando o modelo da designação e o
algoritmo húngaro, como enviar os vendedores às regiões para que
o volume de vendas total das quatro regiões seja o maior possível.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
33
Exercícios
3. Uma Empresa necessita desenvolver um plano de produção para
iniciar a fabricação de três novos produtos.
A Empresa dispõe de cinco máquinas e apenas três destas
deverão ser escolhidas para manufaturar os novos itens, sendo
um produto por máquina.
Os custos de produção e os custos de distribuição para todas as
combinações produto-máquina são fornecidos a seguir:
Custos de Produção ($/unidade):
1
1 20
Produto 2 8
3 5
2
23
29
8
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Máquina
3
4
38
15
6
35
3
4
5
35
35
7
34
Exercícios
Custos de Distribuição ($/unidade):
1
1 20
2 7
3 5
2
50
90
5
Máquina
3
4
20 10
8 35
4 15
5
13
80
6
De acordo com os planos atuais é necessário manter uma determinada produção
anual por item para haver demanda pelos preços unitários planejados, estes dados são
fornecidos adiante:
Produto
Produção Planejada
Preços Planejados
1
35000
US$ 55
2
160000
US$ 50
3
54000
US$ 30
Formule um modelo da designação para tratar este problema e resolva-o pelo Algoritmo
Húngaro.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
35