Programação Linear e Problemas de Produção

Prévia do material em texto

Programação Inteira/Otimização discreta
Exemplo
Deseja-se produzir dois diferentes produtos, Mesas e Cadeiras usando as peças 
disponíveis (matéria-prima):
� 6 peças grandes
� 8 peças pequenas
� Especificação do produto:
� Mesa : 2 peças grandes
2 peças pequenas
� Cadeira : 1 peça grande
2 peças pequenas
Pendegraft, 1997
Objetivo 
Encontrar uma combinação de produtos (mesas e cadeiras) que dê o
maior lucro possível, considerando:
Preço de venda : Mesa $ 16
Cadeira $ 10
Modelagem do Problema
Max 16 m + 10 c
s.a 2 m + 2 c ≤ 8 (disp. Peças pequenas)
2 m + c ≤ 6 (disp. Peças grandes)
Variáveis: m – número de mesas
c – número de cadeiras
Solução Gráfica
cadeiras
mesas
Peças pequenas
Peças 
Grandes
4
4
3
6
Solução Ótima 
(c=2,m=2)
Soluções Viáveis
Solução Gráfica (motivação)
E se tivéssemos disponíveis 9 peças pequenas, qual seria a 
melhor solução pelo método gráfico?
cadeiras
mesas
Peças pequenas
Peças 
Grandes
4.5
4.5
3
6
Solução Ótima (3 
cadeiras e 1.5 mesas)
Soluções Viáveis
Não é inteiro. Faz sentido???
Modelos de Programação Linear
� ZPL = Max cx + dy
� Sujeito a:
� Ax+Dy ≤ b
� x≥0 e y≥0 
n
n
+
+
ℜ∈
ℜ∈
y
x
Problema da mistura, dieta, planejamento de projetos, problema do transporte e outros.
Programação (Linear) Inteira 
Mista (PIM)
� ZPIM = Max cx + dy
� Sujeito a:
� Ax+Dy ≤ b
� x≥0 e inteiro e y≥0 
n
nZ
+
+
ℜ∈
∈
y
x
Problema de planejamento da produção e outros.
Problema de PI (programação 
inteira)
� ZPI = Max cx + dy
� Sujeito a:
� Ax+Dy ≤ b
� x≥0 e inteiro e y≥0 e inteiro
n
n
Z
Z
+
+
∈
∈
y
x
Se X e Y assumir somente valores 0-1?
Problema de programação 0-1 
(binária)
� Z = Max cx
� Sujeito a:
� Ax ≤ b
� x∈{0,1} ou x ∈B2
Problema da mochila, do caixeiro viajante, de localização de facilidades e outros.
Problema de programação 0-1 
(binária)
Exemplo
})1,0{,}1,0{(
1086
..
32max
21
2
21
21
∈∈∈
≤+
+=
xxouBx
xx
as
xxZ
(0,1)}(1,0),{(0,0),X
FactívelRegião
=
Qual a solução ótima?
)inteiroe0(
554
4559
..
610max
2
21
21
21
≥∈
≤+−
≤+
+=
+ i
PI
xouz
xx
xx
as
xxZ
x
Região Factível
)}0,5(),1,4(),0,4(),3,3(),2,3(
),1,3(),0,3(),2,2(),1,2(),0,2(
),1,1(),0,1(),1,0(),0,0{(=x
Qual a solução ótima? X=(5,0), ZPI=50
1
2
1
1
21
21
21
,
554
4559
..
610max
++ ∈ℜ∈
≤+−
≤+
+=
Zxx
xx
xx
as
xxZPIM
Região Factível: Quatro segmentos de reta
}
9
300),3,{(
}
9
350),2,{(
}
9
400),1,{(
}50),0,{(
114
113
112
111
≤≤=
≤≤=
≤≤=
≤≤=
xx
xx
xx
xx
x
x
x
x
Qual a solução ótima? X=(10/3,3), ZPIM=154/3 ≅51,33
1
2
1
1
21
21
21
,
554
4559
..
610max
++ ℜ∈ℜ∈
≤+−
≤+
+=
xx
xx
xx
as
xxZPL
Qual a solução ótima? ZPL=670/13≅51,58
A solução relaxada pode estar bem distante da solução ótima
Mais que isso: em problemas grandes, pode ser difícil, por meio do 
arredondamento, obter uma solução factível
A relaxação tem um papel chave nos principais algoritmos de 
resolução de PI e PIM.
Idéia: ela fornece um limitante
•Em geral, não faz sentido resolver a relaxação linear e arredondar a solução ótima obtida. 
A solução arredondada pode nem sequer ser factível ou pode estar muito afastada da solução ótima.
•Há circunstâncias práticas em que o arredondamento pode fazer sentido, tendo-se a consciência de 
que está obtendo uma solução que pode não ser ótima 
(por exemplo, na prática será muito diferente x=1999.5 ou x=2000?).
•Um problema PI é muito mais difícil de resolver do que o PL
(perdeu-se a convexidade do conjunto de soluções factíveis...).
Para PI não são conhecidas condições necessárias nem suficientes de otimalidade: dada uma 
solução factível, a única forma de determinar se ela é ótima ou não é demonstrar que não existe 
nenhuma solução factível com melhor valor.
Intervalo (gap) de integralidade (gráfico problema maximização)
* *
RL PI
*
PI
Z - Z
relativo = 
Z
Soluções 
factíveis 
para o PI
Soluções 
factíveis 
para o RL
GAP