Aula Forma Padrao

Prévia do material em texto

Forma-padrão
PROGRAMAÇÃO LINEAR - ENP153
Alexandre Xavier Martins
Departamento de Engenharia de Produção, UFOP
LASOS - Laboratório de Simulação e Otimização de Sistemas
16 de março de 2015
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 1 / 13
Forma-padrão
Introdução
Forma-padrão
Como a solução dos problemas de programação linear se dão através de um
computador, não podemos inserir os modelos de qualquer maneira. Nesta
seção mostraremos a forma-padrão que utilizaremos ao longo do curso e
também como transformar qualquer problema de programação linear, seja ele
como for, em um problema na forma-padrão.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 2 / 13
Forma-padrão
Introdução
Forma-padrão
Um Problema de Programação Linear (PPL) se encontra na forma-padrão se
ele está como segue:
Forma algébrica
Minimize Q(x) =
n∑
j=1
cjxj
Sujeito a:
n∑
j=1
aijxj = bi, ∀ i = {1, . . . ,m}
xj ≥ 0, ∀ j = {1, . . . , n}
Sendo bi ≥ 0 para todo i = 1, . . . ,m.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 3 / 13
Forma-padrão
Introdução
Forma-padrão
Um Problema de Programação Linear (PPL) se encontra na forma-padrão se
ele está como segue:
Forma algébrica
Minimize Q(x) =
n∑
j=1
cjxj
Sujeito a:
n∑
j=1
aijxj = bi, ∀ i = {1, . . . ,m}
xj ≥ 0, ∀ j = {1, . . . , n}
Sendo bi ≥ 0 para todo i = 1, . . . ,m.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 3 / 13
Forma-padrão
Introdução
Forma-padrão
Um Problema de Programação Linear (PPL) se encontra na forma-padrão se
ele está como segue:
Forma matricial
Minimize Q(x) = ctx
Sujeito a:
Ax = b
x ≥ 0
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 4 / 13
Forma-padrão
Introdução
Forma-padrão
Um Problema de Programação Linear (PPL) se encontra na forma-padrão se
ele está como segue:
Forma matricial
Minimize Q(x) = ctx
Sujeito a:
Ax = b
x ≥ 0
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 4 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
Situações que podemos encontrar em um PPL
a. Há restrição do tipo menor ou igual (≤)
b. Há restrição do tipo maior ou igual (≥)
c. Existe bi < 0
d. Existem variáveis negativas
e. Existem variáveis livres
f. O PPL é de maximização
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 5 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[a.] Há restrição do tipo menor ou igual (≤)
Exemplo: 2x1 + 3x2 ≤ 5
Neste caso, basta adicionar ao primeiro membro da restrição uma variável de
folga não-negativa. Exemplo: 2x1 + 3x2 ≤ 5→ 2x1 + 3x2 + x3 = 5. Onde a
variável de folga x3 ≥ 0. Repare que em 2x1 + 3x2 + x3 = 5, se x3 = 0, então
2x1 + 3x2 = 5, se x3 > 0, então 2x1 + 3x2 ≤ 5, o que respeita a restrição
original nos dois casos.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 6 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[a.] Há restrição do tipo menor ou igual (≤)
Exemplo: 2x1 + 3x2 ≤ 5
Neste caso, basta adicionar ao primeiro membro da restrição uma variável de
folga não-negativa. Exemplo: 2x1 + 3x2 ≤ 5→ 2x1 + 3x2 + x3 = 5. Onde a
variável de folga x3 ≥ 0. Repare que em 2x1 + 3x2 + x3 = 5, se x3 = 0, então
2x1 + 3x2 = 5, se x3 > 0, então 2x1 + 3x2 ≤ 5, o que respeita a restrição
original nos dois casos.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 6 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[b.] Há restrição do tipo maior ou igual (≥)
Exemplo: 2x1 + 3x2 ≥ 5
Neste caso, basta subtrair do primeiro membro da restrição uma variável de
folga (excesso) não-negativa. Exemplo:
2x1 + 3x2 ≥ 5→ 2x1 + 3x2 − x3 = 5. Onde a variável de folga x3 ≥ 0.
Partindo-se do raciocínio adotado anteriormente podemos ver que a nova
restrição também respeita a restrição original em todos os casos.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 7 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[b.] Há restrição do tipo maior ou igual (≥)
Exemplo: 2x1 + 3x2 ≥ 5
Neste caso, basta subtrair do primeiro membro da restrição uma variável de
folga (excesso) não-negativa. Exemplo:
2x1 + 3x2 ≥ 5→ 2x1 + 3x2 − x3 = 5. Onde a variável de folga x3 ≥ 0.
Partindo-se do raciocínio adotado anteriormente podemos ver que a nova
restrição também respeita a restrição original em todos os casos.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 7 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[c.] Existe bi < 0
Exemplo: 2x1 − 3x2 = −5
Neste caso, basta multiplicar a restrição por (−1). Exemplo:
2x1 − 3x2 = −5→ −2x1 + 3x2 = 5.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 8 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[c.] Existe bi < 0
Exemplo: 2x1 − 3x2 = −5
Neste caso, basta multiplicar a restrição por (−1). Exemplo:
2x1 − 3x2 = −5→ −2x1 + 3x2 = 5.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 8 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[d.] Existem variáveis negativas
Exemplo: xk ≤ 0
Seja xk ≤ 0. Neste caso, basta criar uma variável x′k ≥ 0 tal que x
′
k = −xk e
então, substituímos xk por −x′k no modelo original. Exemplo: 2x1 + 3x2 = 5,
onde x1 ≤ 0, fazemos x′1 = −x1, com x
′
1 ≥ 0, e fazemos a substituição,
obtendo −2x′1 + 3x2 = 5.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 9 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[d.] Existem variáveis negativas
Exemplo: xk ≤ 0
Seja xk ≤ 0. Neste caso, basta criar uma variável x′k ≥ 0 tal que x
′
k = −xk e
então, substituímos xk por −x′k no modelo original. Exemplo: 2x1 + 3x2 = 5,
onde x1 ≤ 0, fazemos x′1 = −x1, com x
′
1 ≥ 0, e fazemos a substituição,
obtendo −2x′1 + 3x2 = 5.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 9 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[e.] Existem variáveis livres
Uma variável xk é dita livre se pode assumir qualquer valor real (−, 0,+).
Neste caso, basta substituir xk por x
′
k − x
′′
k , isto é, fazer: xk = x
′
k − x
′′
k onde
x
′
k ≥ 0 e x
′′
k ≥ 0.
Se x
′
k > x
′′
k , xk > 0.
Se x
′
k < x
′′
k , xk < 0.
Se x
′
k = x
′′
k , xk = 0.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 10 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[e.] Existem variáveis livres
Uma variável xk é dita livre se pode assumir qualquer valor real (−, 0,+).
Neste caso, basta substituir xk por x
′
k − x
′′
k , isto é, fazer: xk = x
′
k − x
′′
k onde
x
′
k ≥ 0 e x
′′
k ≥ 0.
Se x
′
k > x
′′
k , xk > 0.
Se x
′
k < x
′′
k , xk < 0.
Se x
′
k = x
′′
k , xk = 0.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 10 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[e.] Existem variáveis livres
Uma variável xk é dita livre se pode assumir qualquer valor real (−, 0,+).
Neste caso, basta substituir xk por x
′
k − x
′′
k , isto é, fazer: xk = x
′
k − x
′′
k onde
x
′
k ≥ 0 e x
′′
k ≥ 0.
Se x
′
k > x
′′
k , xk > 0.
Se x
′
k < x
′′
k , xk < 0.
Se x
′
k = x
′′
k , xk = 0.
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 10 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[f.] O PPL é de maximização
Teorema:
SejaM = {x ∈ Rn|Ax = b; x ≥ 0} e o PPL
Max Q(x) = ctx
Sujeito a:
Ax ∈ M
então max Q(x) = min −Q(x).
Prova:
Seja max Q(x) = Q(x∗). Logo Q(x) ≤ Q(x∗) para todo x ∈ M. Multiplicando
por (−1) temos: −Q(x) ≥ −Q(x∗) para todo x ∈ M. Logo min
−Q(x) = −Q(x∗) e max Q(x) =min −Q(x).
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 11 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
[f.] O PPL é de maximização
Teorema:
Seja M = {x ∈ Rn|Ax = b; x ≥ 0} e o PPL
Max Q(x) = ctx
Sujeito a:
Ax ∈ M
então max Q(x) = min −Q(x).
Prova:
Seja max Q(x) = Q(x∗). Logo Q(x) ≤ Q(x∗) para todo x ∈ M. Multiplicando
por (−1) temos: −Q(x) ≥ −Q(x∗) para todo x ∈ M. Logo min
−Q(x) = −Q(x∗) e max Q(x) =min −Q(x).
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 11 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
Exemplo:
Max Q(x) = x1 + 2x2 + 3x3
Sujeito a:
x1 − x2 ≤ 5
3x1 − 4x2 ≥ 7
x2 − 2x3 ≥ −6
x1 ≥ 0, x2 ≤ 0, x3 livre
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 12 / 13
Forma-padrão
Redução de um PPL qualquer à forma-padrão
Exercício:
Maximize Q(x) = 3x1 + x2
Sujeito a:
x1 − 2x2 ≤ −4
x1 + x2 ≤ 6
x2 = 1
x1 ≥ 0, x2livre
xmartins@decea.ufop.br (LASOS) PROGRAMAÇÃO LINEAR - ENP153 16 de março de 2015 13 / 13
	Forma-padrão