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.
Aplicações em problemas envolvendo número de itens, como televisores, automóveis, número de estágios...
1 2 3 4 500
1
2
3
4
5
x1
x2
Na resolução desses problemas, além da Função Objetivo e das restrições, são acrescentadas
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.
Temos, então a Programação Linear com Inteiros
Max f = 3 x1 + 4 x2
s.a.: 2 x1 + x2 6 2 x1 + 3 x2 9 x1 ≥ 0 (inteiro) x2 ≥ 0 (inteiro)
Max f = 3 x1 + 4 x2
s.a.: 2 x1 + x2 6 2 x1 + 3 x2 9 x1 ≥ 0 (inteiro) x2 ≥ 0
Condições de Integralidade
No decorrer da resolução dos problemas de Programação Inteira, aparecem os seguintes tipos de soluções intermediárias:
As soluções não-inteiras são eliminadas passo-a-passo restando ao final a solução inteira ótima.
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.
- 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.
A estratégia de resolução consiste em:
Essa estratégia pode ser aplicada com o auxílio do Método de Branch-and-Bound, que consta de duas operações básicas: bifurcação (“branch”) e limitação (“bound”).
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).
P xj
SP1
xj [xj*]
SP2
xj ≥ [xj*] + 1100
80
inteira
Guardada
70 não-inteiranão bifurcável
xj xj
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
Exemplo: x2* = 2,6
[x2*] = 2
Intervalo eliminado2 < x2 < 2 + 1
Ou seja: o intervalo [xj*] < xj < [xj
*] + 1 deve ser eliminado da busca
1 2 3 4 500
1
2
3
4
5
x1
x2
Eliminação de Intervalo: Bifurcação (“branch”)
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.
P xj
SP1
xj [xj*]
SP2
xj ≥ [xj*] + 1FP
FSP1 < FP FSP2 < FP
Ao dar continuidade à resolução, parte-se da solução intermediária não-inteira
Este fato não preocupa porque faz parte do caminho de busca de uma solução inteira.
Problema de Máximo
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.
xjxj
P xj
SP1
xj [xj*]
SP2
xj ≥ [xj*] + 1FP
FSP1 < FP
inteira
FSP2 < FSP1 não-inteiranão bifurcável
P xj
SP1
xj [xj*]
SP2
xj ≥ [xj*] + 1100
80
inteira
Guardada
70 não-inteiranão bifurcável
xj xj
ExemploProblema de Máximo
EXEMPLO
1
f = 12,75
x1 = 2,25x2 = 1,50
3f = 12,5x1 = 1,5x2 = 2
2f = 11,50x1 = 2,5x2 = 1
x2 2 x2 1
4f = 12,33
x1 = 1x2 = 2,33
x1 2 x1 1
7f = 12,00 x1 = 0x2 = 3
6f = 11,00x1 = 1x2 = 2
x2 3 x2 2
Max f = 3 x1 + 4 x2
s.a.: 2 x1 + x2 6 2 x1 + 3 x2 9 x1 ≥ 0 (inteiro) x2 ≥ 0 (inteiro)
1 2 3 4 500
1
2
3
4
5
x1
x2
5
inviável
inviávelProblema Relaxado
Duas soluções piores...
Não-inteira não-bifurcável: pior que a outra
SOLUÇÃO
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.
5 6f= - 5 [1; 1; 0]
y3= 0 y3= 1
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
0f= -6,8 [0,6; 1; 1]
21 f= - 6,667f= -5 [0; 1; 1] [1; 0,333; 1]
y1 = 0
y1 = 1
3 4f= - 6,5 [1; 1; 0,5]
y2= 0
y1 = 1
f= -6 [1; 0; 1]
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.
Temos, então, a Programação Linear Inteira Mista (PLIM)
“Mixed Integer Linear Programming” (MILP).
As variáveis contínuas correspondem às variáveis de processo (vazões, temperaturas, concentrações, dimensões).
e a Programação Não-Linear Inteira Mista (PNLIM)
“Mixed Integer Nonlinear Programming” (MINLP).
DE
DS
RT
RM
T
R
A
6.5.4 Resolução por Super-estruturas
DS
RM
R
A
A,B
P,A
P
A
(7)
Resolve-se um problema de programação não-linear com inteiros: geradas e analisadas diversas estruturas..
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.