PROGRAMAÇÃO INTEIRA
27 de maio de 2014
PROGRAMAÇÃO INTEIRA
É um caso particular da Programação Linear em que todas as
variáveis são restritas a valores inteiros.
5
4
3
x2
2
1
0
0
1
2
3
4
5
x1
Aplicações em problemas envolvendo número de itens, como
televisores, automóveis, número de estágios...
Na resolução desses problemas, além da Função Objetivo e das
restrições, são acrescentadas
Condições de Integralidade
Max f = 3 x1 + 4 x2
s.a.: 2 x1 + x2  6
2 x1 + 3 x2  9
x1 ≥ 0 (inteiro)
x2 ≥ 0 (inteiro)
Há problemas, no entanto, em que apenas algumas variáveis são
restritas a valores inteiros. Nesse caso, as condições de
integralidades são acrescentadas apenas para estas.
Max f = 3 x1 + 4 x2
s.a.: 2 x1 + x2  6
2 x1 + 3 x2  9
x1 ≥ 0 (inteiro)
x2 ≥ 0
Temos, então a Programação Linear com Inteiros
No decorrer da resolução dos problemas de Programação Inteira, aparecem
os seguintes tipos de soluções intermediárias:
- soluções inteiras: todas as variáveis exibem valores inteiros.
- soluções não-inteiras: pelo menos uma variável exibe um valor não-inteiro.
As soluções não-inteiras são eliminadas passo-a-passo restando ao final a
solução inteira ótima.
A estratégia de resolução consiste em:
1. Aplicar o SIMPLEX ao problema original com as condições de
integralidade relaxadas Se coincidir desta solução ser inteira, ela é a solução
do problema.
2. Formular e resolver sucessivos problemas de Programação Linear. Em cada
problema é acrescentada um nova restrição a uma variável não-inteira,
convergindo-se, assim, para a solução inteira ótima.
Essa estratégia pode ser aplicada com o auxílio do Método de Branch-andBound, que consta de duas operações básicas:
bifurcação (“branch”) e limitação (“bound”).
P
xj  [xj*]
xj
100
xj
xj ≥ [xj*] + 1
SP1
SP2
80
inteira
70
não-inteira
não bifurcável
Guardada
xj
A bifurcação gera novos problemas restritos.
A limitação evita a resolução de problemas cujas soluções se mostram,
antecipadamente, piores (economiza esforço computacional).
Eliminação de Intervalo
Numa solução intermediária não-inteira, deve haver pelo menos uma variável xj cujo
valor xj* é não-inteiro.
Seja [xj*] a parte inteira de xj.
Então, a condição necessária para que xj seja inteiro é
xj  [xj*] ou xj ≥ [xj*] + 1
Ou seja: o intervalo [xj*] < xj < [xj*] + 1 deve ser eliminado da busca
5
4
Exemplo: x2* = 2,6
[x2*] = 2
Intervalo eliminado
2 < x2 < 2 + 1
3
x2
2
1
0
0
1
2
3
x1
4
5
Eliminação de Intervalo: Bifurcação (“branch”)
Ao dar continuidade à resolução, parte-se da solução intermediária não-inteira
P
xj  [xj*]
FP
xj
xj ≥ [xj*] + 1
Problema de Máximo
SP1
FSP1 < FP
SP2
FSP2 < FP
e criam-se dois sub-problemas (bifurcação) com as devidas restrições:
Sub-problema 1:
xj  [ xj* ]
Sub-problema 2:
xj ≥ [ xj* ] + 1
A solução de qualquer Sub-Problema é mais restrita do que a do Problema que a
originou. Portanto, a sua solução é necessariamente pior do que a do Problema.
Este fato não preocupa porque faz parte do caminho de busca de uma solução inteira.
Heurística: havendo mais de uma variável com valor não-inteiro, deve-se selecionar,
para bifurcação, aquela mais afastada do valor inteiro (mais próxima de 0,5).
LIMITAÇÃO (“Bound”)
Ao se chegar a uma primeira solução inteira, esta não é necessariamente a ótima
porque outras soluções inteiras ainda podem ser encontradas no processo de
bifurcação.
O valor (F) da Função Objetivo desta primeira solução inteira serve de limite (“bound”)
para as soluções seguintes.
Em Problemas de Mínimo  limite superior.
Em Problemas de Máximo  limite inferior.
Qualquer outra solução inteira posteriormente encontrada com um valor melhor do
que F, deve ser adotada como solução ótima provisória. Se pior, deve ser descartada.
Qualquer solução não-inteira com um valor pior do que F, não deve ser bifurcada: as
soluções bifurcadas são necessariamente piores.
P
xj  [xj*]
xj
SP1
FSP1 < FP
inteira
FP
xj
Exemplo
Problema de Máximo
xj ≥ [xj*] + 1
xj  [xj*]
P
100
xj
xj ≥ [xj*] + 1
SP1
SP2
FSP2 < FSP1
80
inteira
não-inteira
não bifurcável
Guardada
70
não-inteira
não bifurcável
SP2
xj
xj
xj
EXEMPLO
5
Max f = 3 x1 + 4 x2
s.a.: 2 x1 + x2  6
2 x1 + 3 x2  9
x1 ≥ 0 (inteiro)
x2 ≥ 0 (inteiro)
4
inviável
Problema
Relaxado
3
x2
2
f = 12,75
1
1
0
0
1
2
3
x1
f = 12,5
4
5
x1 = 1,5
x2 = 2
x1  2
f = 11,50
x1  1
5
f = 12,33
x2  3
inviável
f = 12,00
7
x1 = 0
x2 = 3
SOLUÇÃO
Duas soluções piores...
x2  1
x2  2
3
x1 = 2,25
x2 = 1,50
4
2
x1 = 2,5
x2 = 1
Não-inteira não-bifurcável: pior que a outra
x1 = 1
x2 = 2,33
x2  2
f = 11,00
6
x1 = 1
x2 = 2
PROGRAMAÇÃO 0 - 1
Caso particular da Programação Inteira em que as variáveis inteiras só podem assumir
os valores 0 e 1.
É a parte da Programação Inteira de interesse na Engenharia de Processos.
Min f = 2 x1 – 3 y1 – 2y2 – 3y3
s.a.: x1 + y1 + y2 + y3 ≥ 2
10 x1 + 5 y1 + 3 y2 + 4 y3  10
x1 ≥ 0
y1 , y2 , y3 = 0, 1
f= -6,8
0
[0,6; 1; 1]
y1 = 1
y1 = 0
f= -5
1
[0; 1; 1]
f= - 6,667
[1; 0,333; 1]
2
y2 = 0
f= -6
3
y1 = 1
[1; 0; 1]
f= - 6,5
y3 = 0
f= - 5
5
[1; 1; 0]
4
[1; 1; 0,5]
y3 = 1
6
Inviável (pq?)
Na Engenharia de Processos, o problema central é a criação de
um fluxograma de processo. Neste problema, há variáveis
inteiras e variáveis contínuas.
As variáveis inteiras binárias correspondem à presença (1) ou
não (0) de um equipamento.
As variáveis contínuas correspondem às variáveis de processo
(vazões, temperaturas, concentrações, dimensões).
Temos, então, a
Programação Linear Inteira Mista (PLIM)
“Mixed Integer Linear Programming” (MILP).
ea
Programação Não-Linear Inteira Mista (PNLIM)
“Mixed Integer Nonlinear Programming” (MINLP).
6.5.4 Resolução por Super-estruturas
T
DS
RM
R
A,B
A
A
A
(7)
DE
Escrevem-se os modelos dos equipamentos e conexões.
A cada equipamento é associada uma variável binária. Na solução:
(1) equip. presente; (0) equip. ausente.
RM
P,A
RT
R
DS
P
Resolve-se um problema de programação não-linear com inteiros:
geradas e analisadas diversas estruturas..