Otimização Matemática e
Aplicações
Socorro Rangel
Departamento de Ciências da Computação e Estatística
e-mail: [email protected]
Sumário
• Problemas de Otimização
• Aplicações:
– Indústria de Móveis
– Indústria de Refrigerantes
• Ferramentas Computacionais
Motivação
"Existem duas maneiras de aumentar a eficiência de
uma loja, empresa, ou indústria. Uma delas requer
a melhoria tecnológica, isto é, atualização dos
equipamentos, mudança no processo tecnológico,
descoberta de novos e melhores tipos de matéria
prima. A outra maneira, até hoje muito menos
utilizada, envolve melhorias na organização do
planejamento e da produção. Isto é, melhorias no
processo de distribuição do trabalho entre as
máquinas da empresa, distribuição de matéria
prima, combustível, entre outros fatores."
(Kantorovich (1939) in Dantzig, 1963, pg 22)
Motivação
 Por que usar modelos matemáticos para
auxiliar a tomada de decisão?
– Solução matemática X solução impírica
– Melhor entendimento da empresa
– Ferramenta de apoio a tomada de decisão
Elementos de um modelo de otimização
DECISÕES
Identificar as possíveis soluções (decisões)
Definir Variáveis de Decisão
OBJETIVOS
Definir critérios de avaliação capazes de indicar que uma decisão é preferível
a outras
Definir Função Objetivo
RESTRIÇÕES
Identificar quais as restrições que limitam as decisões a serem tomadas
Definir Conjunto de Equações ou Inequações
Forma Geral de um Modelo de Otimização
min ou max
(função objetivo)
sujeito a
(restrições principais - equações ou inequações)
(tipo das variáveis de decisão)
Classes de Modelos de Otimização
•
•
•
•
Linear contínuo
Linear Inteiro
Não linear
Misto
Modelo de Otimização Linear
Inteiro Misto
min( ou max) z  c1 x1  c2 x2  ...  cn xn
sujeito a
a11 x1  a12 x2  ...  a1 p x p  ...  a1n xn ~ b1
a22 x1  a22 x2  ...  a2 p x p  ...  a2 n xn ~ b2
...
am1 x1  am 2 x2  ...  amp x p  ...  amn xn ~ bm
x1 , x2 ,...xn  0
, x1 , x2 ,...x p , inteiras
onde ~ pode ser , , ou 
O Problema da Mochila
•
elementos conhecidos:
– um conjunto de itens
– peso e valor de de cada item
– Capacidade da Mochila (peso
máximo)
•
•
elementos desconhecidos: um
subconjunto de itens a serem
incluidos na mochila cuja soma dos
pesos é menor ou igual que a
capacidade da mochila
Objetivo: encontrar o subconjunto
de itens com
o maior valor
possível
Modelo de Otimização Inteira
maxz  40x1  10x2  10x3
Sujeito a
3x1  5x2  4 x3  10
x1, x2 , x3  0 ou1
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!!!!
Métodos de Solução de problemas de
Otimização Inteira Mista
Como podemos ver, tentar resolver os problemas de
otimização inteira pelo método de enumeração completa é
inviável.
Precisamos de técnicas mais avançadas:
• Enumeração implícita (branch and bound)
• Geração de Colunas (inclusão de variáveis)
• Planos de corte poliédricos (inclusão de inequações)
• Heurísticas
• Combinação dos Métodos acima (branch-cut- and price).
Aplicações
Problemas de Corte e empacotamento
(Cutting and Packing Problems)
Planejamento da Produção: Corte de
Matéria Prima na Indústria de Móveis
Panorama da indústria moveleira
•
Forte dispersão geográfica, porém concentrada em pólos regionais
localizados principalmente nas regiões Sul e Sudeste do país
•Pólo de Votuporanga-SP: empresas de pequeno e médio porte,
móveis
retilineos.
• Matéria prima principal: painéis de madeira - compensados, aglomerados e
chapas de fibras comprimidas (MDF- Médium-Density Fiberboard)
O processo de produção de um móvel
1 – Corte da matéria prima: problema de corte de estoque bidimensional
410 x 383 x 03 (3)
600 x 440 x 15 (2)
item
objetos
450 x 132 x 15 (3)
370 x 110 x 12
(3)
388 x 377 x 03 (3)
390 x 110 x 12 (6)
445 x 213 x 03 (4)
2 - furação, colagem, pintura
3 – Os itens são agrupados, empacotados e aramazenados
-Armazenamento de itens cortados deve ser evitado
- Espaço
limitado para armazenar produto final.
Tipo de Corte
Guilhotinado ortogonal em até três estágios
1º
2º
3º
A serra
Ajuste de acordo com
a largura da faixa
Capacidade da serra – corte de varios
objetos simultaneamente (até 60mm de
espessura)
ajuste de acordo
com o comprimento
do item
Solução clássica
•
Sistema Cortebi - Método Simplex com geração de colunas; Padrões de corte em dois
estágios de Gilmory e Gomory (1965).
•
Se mostrou útil como um sistema de apoio a decisão devido a rapidez e qualidade da
solução
•
Resolveu exemplares do problema com até 20 itens em menos que dois segundos e com
perda total entre 3,07% e 5,27% . A indústria aceita até 6%.
Rejeitado (perda 4,19%)
Aceito (perda 2,73%)
Padrões de corte n-grupos
•As faixas obtidas no primiro estágio são agrupadas e cortadas simultaneamente no
segundo estágio
Padrão Tabuleiro
(ou 1-grupo)
1o estágio - faixas
2o estágio – faixas são
cortadas simultaneamente
•Os padrões 1-grupo posuem baixo custo operacional e podem ser identificados
como subpadrões nos padrões de corte utilizados pela indústria.
Padrão de corte da indústria
Subpadrão tabuleiro
Heuristica para gerar padrões tabuleiros compostos
Passo 1 - Leia a dimensão do objeto e dos itens ( L,W ) , ( (li , wi ) i  1... m , rotação e ordenação
dos itens ( wi  wi1 , i  1...p ).
Passo 2 - Use o item k (item pivô), k  1...p , para criar até duas faixas de largura wk :
homogênea maximal e se possível uma faixa heterogênia (o item pivô e itens j tais que
w j  wk ). Seja S o conjunto de itens incluídos em cada faixa.
Passo 3- Para cada
faixas criadas no Passo 2, (área B) inclua o item
( L  l j )  li , i : wi  wk .
i se
jS
A
1
2
2
B
1
2
2
B
1
2
2
B
Remoção
de
faixas
A
1
2
2
B
Passo 4 - Para cada faixa criada Etapa 1, gere um padrão tabuleiro usando W wk  faixas.
Passo 5 - Para cada padrão tabuleiro criado no Passo 4 crie K padrões de corte derivados
removendo faixas do padrão. Se um padrão tabuleiro possuir t faixas, podem ser construídos até
(t-1) padrões derivados. A área ociosa associada às faixas removidas será considerada um novo
objeto (área A). Gere um padrão tabuleiro para o subobjeto (L, WA).
Passo 6 - Resolva o problema do corte de estoque bidimensional considerando o pool de padrões
gerados nos passos 2-5. O pool irá conter até 2p(K+1) padrões de corte diferentes.
Estudo Computacional
Máquina: PC AMD-Athlon 2200, 256 RAM
Software: XPressMP Suite
Exemplares: Produtos fabricados com itens (objetos) de
diferentes espessuras (3, 6, 15,18, 20, e 25mm). Um problema de
corte de estoque para cada tipo de objeto.
Resultados 1: Padrões de corte para P1
Gerados pela heuristica
Usados pela Industria
Resultados 2: 1 lote de cada produto
Heuristica
Industria
Produto
Nr.
Pad.
Nr.
Obj
perda
Nr.
Pad.
Nr.
Obj
perda
P1
8
142
4,2%
6
143,5
4,3%
P2
16
240
4,3%
12
240
4,5%
P3
33
236
4,9%
27
240
4,9%
Total
57
618
4,5%
45
624
4,6%
Aplicações
Problemas Integrados de dimensionamento e sequenciamento de lotes
(Lot-scheduling Problems)
Planejamento da Produção 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 e
tamanhos
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
Linha de produção 1
Linha de produção 2
...
..
. de produção m
Linha
água
Tanque
Propocionador
(Bebida)
Concentrados,
aromas,
essências e
sucos
Estágio I – Xaroparia
Estágio II - Envase
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
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
Atraso do tanque
4
5
Modelo Dois Estágios Multi-Máquinas
(P2EMM - Otimização Inteira Mista)
Elementos Conhecidos
•Demanda dos refrigerantes (itens);
•Tempos de produção;
•Tempos de troca de itens nas linhas de produção;
•Capacidade das Máquinas;
•Tempos de troca de xarope no tanque;
•Capacidade dos tanques;
•Quantidade de xarope utilizada em cada item;
•Custos: estoque, troca de item, troca de xarope;
Critério de Otimização
•Minimizar os custos de
estoque, atraso, custo de
troca de itens nas linhas e
xarope nos tanques;
Restrições
•Fornecimento dos xaropes necessários para produção;
•Capacidade dos tanques;
•Estágio I – xaroparia: 8 classes
•Troca de xarope nos tanques;
de restrições
• troca de itens nas linhas;
•Estágio II – envase: 8 classes
•Capacidade da linha (tempo de produção);
•de restrições
•Atendimento da demanda;
•Sincronia entre preparo de xarope e envase do líquido
Estudo Computacional
•Computador: Pentium 4, 1.0 Gb de RAM, 3.2 Ghz 256 Mb
•Software: AMPL/CPLEX 10.0.
• 15 exemplares (2 linhas de envase, 2 máquinas, 23 tipos de itens, 18 tipos de
xaropes)
•Total de variáveis
86.359
variáveis binárias restrições
4.575
86.140
•Métodos de solução
•Branch and cut (CPLEX)
•Estratégia de Decomposição (ED)
•Estratégia de Relaxação (ER)
•Heuristica relax and fix (RF)
Resultados
• O modelo P2EMM mostrou-se útil na representação do
problema de programação da produção de refrigerantes.
• A resolução de exemplares deste modelo mostrou as
limitações dos sistemas de última geração disponíveis
atualmente (Gap > 98% , 4 horas de cpu)
• Necessidade de se buscar métodos específicos de solução
que explorem a estrutura combinatória do problema.
• Combinação ER + RF gerou soluções melhores que a
fornecida pela Fábrica (26,3%).
Ferramentas Computacionais
• Comerciais - Versão de estudante
XPRESS: http://www.dashoptimization.com/
MPL: http://www.maximal-usa.com/
AMPL: http:www.ampl.com/
(acompanha sistema de resolução: e.g. CPLEX,
LINDO)
•Não Comerciais
CLP (COIN-OR Linear Program Solver)
http://www.coin-or.org/Clp/
LPSOLVE - http://lpsolve.sourceforge.net/5.5/
ZIMPL - http://www.zib.de/koch/zimpl/
Publicações Selecionadas
1.
2.
3.
4.
5.
RANGEL, S. . Introdução à construçã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. 82 p.
RANGEL, S. ; LEMOS, Renato Brigido . Manual do sistema CorteBI
- Interface Gráfica. São José do Rio Preto,: Departamento de
Ciências de Computação e Estatística - DCCE/UNESP, 2007
(Relatório Técnico).
RANGEL, S. ; FIGUEIREDO, A. . O problema de corte de estoque
em indústrias de móveis de pequeno e médio porte 2007 (Relatório
Técnico - Submetido para publicação).
MOSQUERA, Gabriela Perez ; RANGEL, S. . Minimização do
número de ciclos da serra no problema de corte de estoque 2007
(Relatório Técnico - Submetido para publicação).
FERREIRA, D. ; MORABITO, R. ; RANGEL, S. . Abordagens de
solução para o problema integrado de dimensionamento e
sequenciamento de lotes de produção de refrigerantes com dois
estágios e múltiplas máquinas 2007 (Relatório Técnico - Submetido
para publicação).