Otimização Linear Inteira

Prévia do material em texto

Modelagem com variáveis binárias 
Um grande número de problemas de otimização linear inteiro envolve a 
ocorrência ou não de um evento, e a decisão entre duas alternativas. 



=
ocorrenãoeventoose0
ocorreeventoose1
x
Decisão sobre uma atitude (fazer ou não fazer, comprar ou 
não comprar...).
Custo fixo (um exemplo)
A produção de um item implica em um custo fixo, por 
exemplo, de preparação da máquina .
Nos modelos de produção dados anteriormente 
tínhamos:
xj=Quantidade produzida de um item.
Para o item j, a função custo, designada por cj(xj) ,
traduz os custos incorridos quando se produzem xj itens do tipo j.
(não linear devido a descontinuidade no ponto x=0). Como Modelar de forma linear?
Seja uma variável binária yj, tal que yj vale 1 se xj>0 e yj vale 0 caso contrário


 >
=
cc
xse
y jj 0
01
jj cxsyK +=
Como associar x e y ?
Considerando M um limite superior para a produção do item (xj) podemos escrever:
jj Myx ≤
Podemos formular matematicamente um problema de planejamento da 
produção da seguinte maneira
Considere uma situação em que, se o produto 1 é fabricado, 
então o produto 2 também deve ser fabricado. Sejam
1x =quantidade produzida do item 1. 
2x =quantidade produzida do item 2. 
As condições são expressas por:
Podemos ter a condição de que 1 1y = implica que 2 0x > . Isto é obtido por meio 
da desigualdade 2 1x ny≥ , onde n é o limitante para a produção do item 2 
Suponha que quatro itens podem ser produzidos em uma máquina denotada por k,
e se o item 1 é produzido na máquina k, 
então os outros itens:2, 3 e 4 não podem ser processados em k e 
são processados em outras máquinas.
então se 1 1kx = implica que 2 3 4 0k k kx x x= = = . 
Como as variáveis são binárias, pode-se expressar esta condição como:
1 0kx > então 2 3 4 0k k kx x x+ + ≤ , ou 2 3 4 0k k kx x x− − − ≥ . 
Seja a desigualdade 1( , , ) 0nf x x ≤L 
Definindo: 
1 se f 0
0
y
cc
≤
= 

 
Podemos expressar esta implicação como: 
1( , , ) (1 )nf x x M y≤ −L 
Onde M é um número grande. Note que se y=0, a restrição é desativada, isto é, 
1( , , )nf x xL pode assumir qualquer valor até seu limite superior M. 
Considere as desigualdades: 
1( , , ) 0nf x x ≤L (4) 
e 
1( , , ) 0ng x x ≤L (5) 
Deseja-se que somente uma das desigualdades esteja ativada. 
Definindo 
1 se f 0
0 g 0
y
se
≤
=  ≤
 
Isto pode ser representando por: 
 
1( , , ) (1 )nf x x M y≤ −L 
1( , , )ng x x My≤L 
O acréscimo de um número M grande do lado
direito das restrições faz com que a restrição
seja transladada paralelamente no quadrante 
superior. As linhas pontilhadas indicam a 
translação mínima das duas retas de forma
que somente uma das restrições seja ativada.
yxx
yxx
M
xxxx
xxxx
12010052
)1(1208024
120}100,120max{
2005210052
200248024
21
21
2121
2121
+≤+
−+≤+
==
=+→=+
=+→=+
Suponha que existam cinco tipos de investimento financeiro e seja xj a variável 
binária de decisão tal que 
1 se o investimento j é selecionad
0j
o
x
cc

= 

 
Considere as seguintes restrições e situações: 
1) No máximo três investimentos são selecionados 
1 2 3 4 5 3x x x x x+ + + + ≤ 
2) Exatamente um investimento é selecionado 
1 2 3 4 5 1x x x x x+ + + + = 
3) O investimento 1 ou o investimento 2 é selecionado 
1 2 1x x+ ≥ 
4) Se o investimento 2 é selecionado, então o investimento 1 é selecionado 
2 1x x≤ 
5) Se os investimentos 2, 3 ou 4 são selecionados, então o investimento 1 é 
selecionado. 
Duas formas: 
2 1x x≤ 
3 1x x≤ 
4 1x x≤ 
ou 
2 3 4 13x x x x+ + ≤ 
Qual é o melhor?
Relaxação linear???
Relaxação linear???
}4,1,10,3{ 14321 L=≤≤≤++= ixxxxxX i
}4,1,10,,,{ 1413122 L=≤≤≤≤≤= ixxxxxxxX i
2
11432
12
satisfazemnão mas
satisfazem
3
1
,
4
1
,
2
1pois
X
Xxxxx
XX
====
⊂
12 relaçãoempreferido XX
Considere o problema de localização de armazéns cujo objetivo é escolher os 
armazéns que devem ser instalados para servir um conjunto de clientes.
Neste modelo existem uma capacidade associada a cada local possível e uma 
procura associada a cada cliente. 
A procura dos clientes associados a um certo armazém não pode exceder a sua capacidade. 
O objetivo do problema é ainda satisfazer os pedidos a um custo global mínimo, 
que envolve os custos mensais da renda dos armazéns
e os custos de transporte da mercadoria entre os armazéns e os clientes. 
Considere 4 possíveis armazéns (A,B,C e D) 
com capacidades de 35, 28, 22 e 28 respectivamente e com as rendas mensais indicadas 
na tabela. 
Existe um conjunto de 5 clientes (a,b,c,d, e e) que representam as 
procuras de 14, 12, 10, 12 e 8, respectivamente. 
Os custos de transporte unitários entre cada possível armazém e 
cada cliente são indicados na tabela.
Exemplo
� Formule um modelo de programação inteira que lhe permita determinar qual 
o conjunto ótimo de armazéns a selecionar. Considere as variáveis a 
quantidade a ser transportada do armazém i até o cliente j. As variáveis 
binárias assumem o valor 1 se o armazém i é selecionado e 0, caso contrário. 
Para o problema é necessário respeitar as seguintes restrições:
� Dos locais C e D, exatamente 1 deve ser selecionado
� A seleção do local A ou do local B implica na exclusão do local C.
� A seleção do local A ou do local B implica a seleção do local D