Apostila Pesquisa Operacional P2

Prévia do material em texto

08/10/2017
1
11
Professor – Paulo Amorim
Disciplina: Pesquisa Operacional
NP2
2
Problema de Designação
Um caso especial do Modelo de Transportes é aquele em que
cada origem tem 1 unidade disponível e cada destino também
necessita de apenas 1 unidade. Ex: escalar vendedores para
regiões de vendas, produtos para fábricas, etc.
Esse também é um problema de Programação Linear, e tem
aplicação direta na Logística.
Porém, devemos fazer a seguinte consideração: Cada origem
deve ser designada para exatamente 1 destino (e vice-versa).
Assim como no algoritmo de transporte, há um custo associado
em designar a origem para o destino.
O objetivo é determinar como todas as designações devem ser
realizadas afim de minimizar o custo (ou maximizar o “lucro”).
Para encontrar a solução ótima, pode-se utilizar o algoritmo de
transportes. Contudo, como é permitido somente 1 designação
(alocação) em cada linha e coluna, trata-se de um problema
degenerado, sendo assim a performance cai muito.
08/10/2017
2
3
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;
Problema de Designação
4
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 !
Problema de Designação
08/10/2017
3
5
Formulação



n
j
ijx
1
1
1,0ijx
ni ,...,2,1 , 
nj ,...,2,1 , 
Minimizar
sujeito a:
cada trabalhador 
é designado a 
uma só tarefa
nj ,...,2,1 , 



n
i
ijx
1
1
cada tarefa é 
executada apenas 
por um 
trabalhador
ni ,...,2,1 , 



n
ji
ijijxcC
1,
Problema de Designação
6
Depois de montado o quadro contendo as origens, destinos e
seus respectivos custos, efetua-se os cálculos:
Passo 1:
Subtrair o menor elemento de cada linha. Em seguida, fazer o
mesmo para cada coluna. Isso deverá gerar pelo menos 1
elemento nulo em cada linha/coluna
Passo 2:
Traçar o menor número de retas possível afim de cobrir todos os
zeros. Retas diagonais não são permitidas.
Passo 3:
Se o número de retas for igual ao número de linhas ou colunas,
estamos na solução ótima (basta fazer a designação). Caso
contrário, vá para o passo 4.
Método Simplex de Designação - Minimização
Problema de Designação
08/10/2017
4
7
Passo 4:
a) Escolhe-se o menor elemento NÃO COBERTO por nenhuma
reta. Subtrai-se este elemento
de todos os demais NÃO COBERTOS pelas retas
b) Soma-se este elemento a todos os elementos que se
encontram na INTERSECÇÃO das retas
c) Todos os demais elementos PERMANECEM INALTERADOS.
d) Voltar ao passo 2.
Método Simplex de Designação - Minimização
Problema de Designação
8
O quadro representa custos de envio de veículos da locadora
para os destinos onde deverão ser entregues. Designar um
veículo para cada destino com o menor custo total possível (caso
de minimização):
Método Simplex de Designação - Exemplo
Problema de Designação
08/10/2017
5
9
Método Simplex de Designação - Exemplo
Problema de Designação
10
Método Simplex de Designação - Exemplo
Problema de Designação
08/10/2017
6
11
Método Simplex de Designação - Exemplo
Problema de Designação
A designação não se completou 
devido a origem 3 e o destino 3
Cobrir os zeros com o menor 
número de linhas possíveis
12
Método Simplex de Designação - Exemplo
Problema de Designação
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;
- os outros elementos 
permanecem iguais.
08/10/2017
7
13
Método Simplex de Designação - Exemplo
Problema de Designação
Solução: Designação
L1 -> F1 Custo 10; L3 -> F4 Custo 15
L2 -> F2 Custo 12; L4 -> F3 Custo 13
Total Custo 50
Fazer nova designação
14
Exercício1:
Problema de Designação
Um encarregado necessita designar 4 tarefas distintas para 4
operadores, sabe-se que qualquer um dos operadores (P, A, M, e G)
são capazes de efetuar as 4 tarefas. Porem, devido à experiência, o
tempo médio gasto (em dias) que cada operador levaria para realizar
cada tarefa está descrito no quadro.
O encarregado deseja otimizar a distribuição das tarefas
minimizando o tempo de preparação.
P
A
M
G
08/10/2017
8
15
Exercício1: Problema de Designação
16
Exercício1: Problema de Designação
08/10/2017
9
17
Resultado
Problema de Designação
P
A
M
G
Planejamento:
Prof. P ficará com a disciplina 3
Prof. A ficará com a disciplina 2
Prof. M ficará com a disciplina 4
Prof. G ficará com a disciplina 1
18
Problema de Designação (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 %
08/10/2017
10
19
Problema de Designação (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 %
20
Problema de Designação (Maximização)
08/10/2017
11
21
Problema de Designação (Maximização)
22
Problema de Designação (Maximização)
08/10/2017
12
23
Problema de Designação (Maximização)
24
Exercício 2:
Problema de Designação (Maximização)
Uma empresa tem disponível nos fornecedores quatro tipos de robôs que fazem uma
seqüência de operações padronizadas. Um estudo feito em colaboração com os
fornecedores revelou os lucros anuais gerados pela instalação de um robô em cada
uma das três unidades produtoras da empresa, após descontados os custos de
instalação, manutenção e depreciação dos equipamentos (em 1.000 u.m.).
A empresa deseja adquirir um tipo de robô para cada instalação produtora, de modo a
maximizar o lucro total no ano devido a essa operação.
08/10/2017
13
25
Exercício 3:
Problema de Designação (Minimização)
Quatro encomendas (A,B,C,D) podem ser feitas por 4 funcionários (I,II,III,IV) . Cada
funcionário pode fazer apenas 1 encomenda e todasdevem ser feitas ao mesmo
instante. O tempo que cada funcionário leva para fazer cada encomenda está na tabela:
Quantos minutos são gastos, no mínimo, par que sejam feitas todas as encomendas?
Qual a relação funcionário x encomenda reflete esse tempo mínimo?
A B C D
I 30 10 40 30
II 20 50 30 50
III 30 15 50 30
IV 50 30 40 20
26
O Problema de Fluxo Máximo (The Maximum 
Flow Problem)
Considere uma rede direcionada (dígrafo) conectada, com 2 nós
especiais denominados Origem e Destino e ainda, associado a
cada arco, uma distância não-negativa. O objetivo é encontrar o
fluxo máximo na rede.
Exemplos de Aplicações:
1)Maximizar o fluxo de uma rede de distribuição (suprimentos) de
uma companhia a partir de suas fábricas (fornecedores) para os
seus (suas) clientes (fábricas).
2)Maximizar o fluxo de óleo (água) através de um sistema de
oleodutos (aquedutos).
3)Maximizar o fluxo de veículos através de uma rede de
transporte.
08/10/2017
14
27
O Problema de Fluxo Máximo (The Maximum 
Flow Problem)
28
Algoritmo de Fluxo Máximo
08/10/2017
15
29
Exemplo de problema de Fluxo Máximo
30
Exemplo de problema de Fluxo Máximo
Caminhos saturados por uma outra ordem
08/10/2017
16
31
Fluxos Negativos
32
Fluxos Negativos
08/10/2017
17
33
Teorema de Fluxo Máximo – Corte Mínimo
34
Teorema de Fluxo Máximo – Corte Mínimo
08/10/2017
18
35
Teorema de Fluxo Máximo – Exercício
O cálculo do fluxo máximo consiste em analisar todos os caminhos possíveis
entre a origem (A) e o destino (C), determinando o fluxo máximo que pode
percorrer cada caminho. Começamos por analisar o caminho com o maior fluxo
máximo.
36
Teorema de Fluxo Máximo – Exercício
08/10/2017
19
37
Teorema de Fluxo Máximo – Exercício
38
Teorema de Fluxo Máximo – Exercício 1
08/10/2017
20
39
Teorema de Fluxo Máximo – Exercício 2
40
Teorema de Fluxo Máximo – Exercício 3
Considere um sistema viário de uma zona urbana entre os pontos X e P. A tabela 1
apresenta a capacidade de tráfego em viaturas/horas nos pontos A, B e C. Deve-se
obedecer um sentido obrigatório de trânsito que são entre os pontos A, B e C e os
pontos D, E e F e as capacidade de tráfego são indicados na tabela 2. Em seguida, a
capacidade de tráfego em viaturas/horas nos pontos D, E e F são apresentadas na
tabela 3.