Matemática discreta e a
solução de problemas de
otimização
Socorro Rangel
Departamento de Ciências da Computação e Estatística
e-mail: [email protected]
Apoio
:
http://www.dcce.ibilce.unesp.br/~socorro/
O Problema da mochila
maxz  v1 x1  v2 x2  ... vn xn
Sujeito a p x  p x  ... p x  C
1 1
2 2
n n
x j  0 / 1 j  1,...,n
2
n possíveis soluções! Como
encontrar a solução ótima?
Enumerar as Soluções: é Sempre Possível?
n
3
5
10
100
2n
O que fazer
8
então?
32
1024
30
1.26 x 10
Computador:
1 solução
1s
1.26x1030 soluções
~4 x 1022 anos!!!!
O Problema do Caixeiro Viajante
• elementos conhecidos:
– um conjunto de cidades
– custo da viagem entre cada par de cidades
• elementos desconhecidos: um roteiro de viagem que inclua todas as
cidades apenas uma vez, e que comece e termine na mesma cidade.
• objetivo encontrar o roteiro de menor custo possivel
Be
Sal
Circuito Hamiltoniano
Ma
RJ
Go
SP
Quantos roteiros
existem?
• Se o problema considerar n cidades teremos
que o número total de roteiros é (n-1)!
n
n!
Tempo
8
40320
1s
10
3628800
54s
11
39916800
12 min
12
479001600
1h 25 min
30
2 . 1032*
9 . 1021 milênios*
*Da ordem de
50
3 . 1064*
9 . 1053 milênios*
Assim, fica inviável analisar todos
os circuitos manualmente!
Métodos de Solução
Como podemos ver, tentar resolver esta classe de problemas
pelo método de enumeração completa é inviável
Precisamos de técnicas mais avançadas:
• Particionar e limitar (branch and bound)
• Geração de Colunas (variáveis)
• Planos de corte poliédricos (restrições)
• Heurísticas
• Combinação dos Métodos acima (branch-cut- and price).
Problemas Práticos
• Problemas de Corte e empacotamento
(Cutting and Packing Problems)
• Problemas Integrados de dimensionamento de lotes
(Lot-scheduling Problems)
O Problema de Corte de Estoque
Unidimensional
L = 200
(1)
(1)
(3)
(4)
33
33
40
90
l1 = 33
l2 = 87
l3 = 40
l4 = 90
x j  númerode vezesque o item j é cortado
x1 = 2
x2 = 0
x3 = 1
x4 = 1
Restrição Física: 33x1 + 87x2 + 40x3 + 90x4  200
Perda = 4
}
33
33 2x33
40
90
196  200
Problemas de dimensões maiores
corte
bidimensional
Empacotamento
Tridimensional
Planejamento da Produção: Corte de
Matéria Prima na Indústria de Móveis
410 x 383 x 03 (3)
600 x 440 x 15 (2)
370 x 110 x 12
(3)
450 x 132 x 15 (3)
388 x 377 x 03 (3)
390 x 110 x 12 (6)
445 x 213 x 03 (4)
Restrições do equipamento de corte
Nº de faixas distintas:
A cada largura distinta é necessário o ajuste do
batente que determina a largura da faixa a ser
cortada
Capacidade da Seccionadora: Quantidade de objetos que a seccionadora
corta simultaneamente
Solução Modelo de Otimização Discreta
Solução da Indústria
Planejamento da Produção: Dimensionamento e
sequenciamento de lotes na Indústria de
Bebidas
• Várias linhas de produção
• Vários tanques para armazenamento de
líquido
• Garrafas recicláveis e descartáveis
• Refrigerantes em diversos sabores
Uma linha de produção
(Empresa de Médio porte na região de S. J. do Rio Preto)
• Esteira rolante
• Máquinas alinhadas em série
• lavar garrafas
• encher
• fechar
• rotular
• empacotar
A unidade de produção
Determinar a
quantidade e a
ordem de produção
de refrigerantes de
forma a satisfazer a
demanda do
mercado, com
objetivo de
minimizar os custos
de
produção,
armazenamento e
preparo de
máquinas.
Desafio: Sincronia no Processo de Produção
Estágio I
Estágio II
Tanque (Preparo do xarope para produção do refrigerante)
Linha (Envase de refrigerantes)
Não sincronizado
k para l
Tanque
a
m
Tempo
b
troca
Subp. 1
c
Subp. 2
Subp. 3
2
3
c
Subp. 4
d
d
Subp. 5
Subp. 6
i para j
Linha
1
4
3
5
m
Sincronizado
(Solução Viável)
Tanque
a
b
c
c
d
d
Subp. 3
Subp. 4
Subp. 5
Subp. 6
3
3
m
Subp. 1
Linha
m
1
Atraso da linha
Subp. 2
2
4
Atraso do tanque
5
Projeto de Pesquisa
(CNPq)
• Familiarização com as características do sistema
produtivo de empresas de pequeno, médio e
grande porte de diversos setores industriais, tais
como, os setores de fundição, bebidas e moveis.
• Propor e Analisar a eficiência de algoritmos
baseados em métodos de solução exatos e
heurísticos
para
resolver
problemas
de
planejamento da produção.
Publicações Selecionadas
Rangel, S. (2005) Introdução á contrução de modelos de otimização linear
e inteira. 1. ed. São Carlos-SP: Sociedade Brasileira de Matemática
Aplicada e Computacional-SBMAC, 2005. v. único. 82 p.
Ferreira, D., Morábito R., Rangel, S. (2005). Aplicação de um modelo de
otimização mulit-item multi-máquinas na programação da produção de
uma fábrica de bebidas. Anais do XXXVII Simpósio Brasileiro de
Pesquisa Operacional, Gramado-RS.
Figueiredo, A. , Rangel, S. (2005). Aplicações de Modelos 2-estágios e 1grupo na geração de padrões de corte na indústria moveleira. Anais do
XXVIII CNMAC, São Paulo, SP, setembro.
Cavali, R. e S. Rangel (2004). Production Planning: A Cutting Stock
Problem In The Furniture Industry, trabalho aceito para o XII Congreso
Latino-Iberoamericano de Investigación de Operaciones y Sistemas CLAIO a ser realizado em Havana, Cuba de 04 a 08 de outubro.
Rangel, S. e Ferreira, D. (2003). Um modelo de dimensionamento de lote
para uma fábrica de refrigerantes. Tema Têndencias Em Matemática
Aplicada e Computacional, São José do Rio Preto - SP, v. 4, n. 2, p.
237-246.
.
Grupo de Pesquisa:
Modelagem e Otimização de
Sistemas
• Socorro Rangel
• Geraldo Nunes Silva
• Silvio Alexandre de Araujo
http://www.dcce.ibilce.unesp.br/otimiza/riopreto.html