Prévia do material em texto

Introdução Big M Simplex 2 fases Caso especial
Método simplex
Big M e 2 Fases
André Gustavo dos Santos1
1Departamento de Informática
Universidade Federal de Viçosa
INF280 - 2019/1
André Gustavo UFV Método simplex INF280 - 2019/1 1 / 26
Introdução Big M Simplex 2 fases Caso especial
Conteúdo
1 Introdução
2 Big M
3 Simplex 2 fases
4 Caso especial
André Gustavo UFV Método simplex INF280 - 2019/1 2 / 26
Introdução Big M Simplex 2 fases Caso especial
Problema com a solução inicial
Modelo
max 3x1 + 5x2
s.a.
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≥ 18
x1, x2 ≥ 0
Modelo na forma padrão
max 3x1 + 5x2
s.a.
x1 + f1 = 4
2x2 + f2 = 12
3x1 + 2x2 − f3 = 18
x1, x2, f1, f2, f3 ≥ 0
Este quadro não representa uma
solução viável! (f3 = −18)
A base trivial, com f1, f2, f3, é inviável
Não podemos começar por esse quadro
Quadro simplex
x1 x2 f1 f2 f3
−z 3 5 0 0 0 0
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 -1 18
André Gustavo UFV Método simplex INF280 - 2019/1 3 / 26
Introdução Big M Simplex 2 fases Caso especial
Como encontrar uma solução inicial viável?
Uma alternativa é acrescentar uma
variável artificial
O quadro inicial usa esta variável no
lugar da variável de folga negativa
Base inicial: (f1, f2, a) = (4, 12, 18)
Isso aumenta a dimensão do problema,
mas a solução inicial é viável
Forma padrão com variável artificial
max 3x1 + 5x2
s.a.
x1 + f1 = 4
2x2 + f2 = 12
3x1 + 2x2 − f3 +a = 18
x1, x2, f1, f2, f3, a ≥ 0
O problema é que ela é viável neste
modelo, mas não no original!
(x1, x2, f1, f2, f3) = (0, 0, 4, 12, 0) não
atende às restrições originais
E se a variável artificial for, em algum
momento, retirada da base?
Fora da base vale 0, e o modelo seria
equivalente ao modelo original
Quadro simplex
x1 x2 f1 f2 f3 a
−z 3 5 0 0 0 0 0
f1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 3 2 0 0 -1 1 18
André Gustavo UFV Método simplex INF280 - 2019/1 4 / 26
Introdução Big M Simplex 2 fases Caso especial
Como retirar a variável artificial da base?
Dois métodos principais
Método Big M
Método simplex 2 fases
André Gustavo UFV Método simplex INF280 - 2019/1 5 / 26
Introdução Big M Simplex 2 fases Caso especial
Método Big M
A base inicial com a variável artificial é viável e pode-se começar o simplex
Mas o modelo com variável artificial só é equivalmente ao original se a = 0
Deve-se garantir que ela saia da base
O método Big M faz isso dando um valor muito ruim para a variável artifical
Por exemplo, considere a função objetivo: max 3x1 + 5x2 − 1000000a
Soluções com a > 0 terão um valor muito ruim de função objetivo
A solução ótima terá a = 0, e também será ótima no modelo original1
Vale ressaltar que o coeficiente de a na função objetivo deve ser suficiente
negativo para garantir que a solução ótima terá a = 0.
Em um problema de minimização, ele deve ser suficiente alto.
Assim, acrescentamos −Ma ou +Ma na função objetivo, dependendo se esta for
max ou min, sendo M uma constante muito grande. Daí o nome Big M.
1 lembre-se que existe a restrição a ≥ 0, portanto a não pode ser negativo.
André Gustavo UFV Método simplex INF280 - 2019/1 6 / 26
Introdução Big M Simplex 2 fases Caso especial
Método Big M - solução do modelo da introdução
Considerando M = 1000, a função objetivo será max 3x1 + 5x2 − 1000a.
E o quadro simplex inicial seria:
x1 x2 f1 f2 f3 a b
−z 3 5 0 0 0 -1000 0
f1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 3 2 0 0 -1 1 18
Mas a variável a está na base, então seu coeficiente na linha z precisa ser zerado.
(neste caso, basta somar à linha z a linha de a× 1000)
x1 x2 f1 f2 f3 a b
−z 3003 2005 0 0 -1000 0 18000
(as demais linhas continuam como estavam)
André Gustavo UFV Método simplex INF280 - 2019/1 7 / 26
Introdução Big M Simplex 2 fases Caso especial
Método Big M - solução do modelo da introdução
x1 x2 f1 f2 f3 a b
−z 3003 2005 0 0 -1000 0 18000
f1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 3 2 0 0 -1 1 18
x1 x2 f1 f2 f3 a b
−z 0 2005 -3003 0 -1000 0 5988
x1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 0 2 -3 0 -1 1 6
x1 x2 f1 f2 f3 a b
−z 0 0 9/2 0 5/2 -2005/2 -27
x1 1 0 1 0 0 0 4
f2 0 0 3 1 1 -1 6
x2 0 1 -3/2 0 -1/2 1/2 3
x1 x2 f1 f2 f3 a b
−z 0 0 0 -3/2 1 -1001 -36
x1 1 0 0 -1/3 -1/3 1/3 2
f1 0 0 1 1/3 1/3 -1/3 2
x2 0 1 0 1/2 0 0 6
x1 x2 f1 f2 f3 a b
−z 0 0 -3 -5/2 0 -1000 -42
x1 1 0 1 0 0 0 4
f3 0 0 3 1 1 -1 6
x2 0 1 0 1/2 0 0 6
Solução ótima:
x1 = 4, x2 = 6
z = 42
André Gustavo UFV Método simplex INF280 - 2019/1 8 / 26
Introdução Big M Simplex 2 fases Caso especial
Método Big M
Se houver mais de uma restrição ≥, acrescentar uma variável artificial para cada
Todas elas devem ter coeficiente M grande
Modelo
max 3x1 + 5x2
s.a.
x1 ≤ 4
2x2 ≥ 12
3x1 + 2x2 ≥ 18
x1, x2 ≥ 0
Forma padrão com variáveis artificiais
max 3x1 + 5x2 − 10000a1 − 10000a2
s.a.
x1 + f1 = 4
2x2 − f2 + a1 = 12
3x1 + 2x2 − f3 + a2 = 18
x1, x2, f1, f2, f3, a1, a2 ≥ 0
André Gustavo UFV Método simplex INF280 - 2019/1 9 / 26
Introdução Big M Simplex 2 fases Caso especial
Método Big M - incovenientes
Desde que M seja suficientemente grande, o método funciona, em teoria
Na prática, pode levar a erros numéricos quando executados por um computador
Será necessário trabalhar simultaneamente com valores muito grandes
(coeficientes na linha z) e valores muito pequenos (note as frações no quadro)
Valores de ponto flutuante no computador têm precisão limitada
são armazenados de forma similar à notação científica, com mantissa e expoente
a quantidade de dígitos armazenados é limitada
por exemplo, um tipo double (precisão dupla) suporta valores de 10−308 a 10308,
aproximadamente, com cerca de 15 dígitos de precisão.
assim, embora seja possível armazenar valores suficientemente grandes e pequenos
para qualquer aplicação do simplex, não são armazenados com precisão total
uma soma 1000000000 + 0.000004, que deveria resultar em 1000000000.000004,
poderia ser arredondada para 1000000000
uma pequena diferença que futuramente poderia ser crucial para determinar se uma
variável deve entrar ou não na base, por exemplo ao subtrair 1000000000 em um
pivoteamento resultaria em 0 em vez de 0.000004
Por isso tal método geralmente não é usado por softwares de programação linear
André Gustavo UFV Método simplex INF280 - 2019/1 10 / 26
Introdução Big M Simplex 2 fases Caso especial
Simplex 2 fases
Fase 1
Objetivo: encontrar uma solução viável
Como? Forçando a saída das variáveis artificiais da base
⇒ Usar uma função objetivo que minimiza o valor das artificiais
Fase 2
Objetivo: encontrar uma solução ótima
Como? Voltar a função objetivo original e continuar o simplex normalmente
O problema com restrições ≥ é não ter uma base trivial viável para iniciar o simplex.
A Fase 1 encontra uma e a Fase 2 é o simplex a partir dela.
André Gustavo UFV Método simplex INF280 - 2019/1 11 / 26
Introdução Big M Simplex 2 fases Caso especial
Simplex 2 fases - exemplo
Modelo
max 3x1 + 5x2
s.a.
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≥ 18
x1, x2 ≥ 0
Forma padrão com artificiais
max 3x1 + 5x2
s.a.
x1 + f1 = 4
2x2 + f2 = 12
3x1 + 2x2 − f3 + a = 18
x1, x2, f1, f2, f3, a ≥ 0
André Gustavo UFV Método simplex INF280 - 2019/1 12 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 1: minq = a
min q = a ⇒ max − q = −a
x1 x2 f1 f2 f3 a b
q 0 0 0 0 0 -1 0
f1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 3 2 0 0 -1 1 18
antes de mais nada, “ajeitamos” a linha da função objetivo,
zerando o coeficiente de a, que está na base (somar linha q com linha de a)
x1 x2 f1 f2 f3 a b
q 3 2 0 0 -1 0 18
f1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 3 2 0 0 -1 1 18
André Gustavo UFV Método simplex INF280 - 2019/1 13 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 1: minq =a
x1 x2 f1 f2 f3 a b
q 3 2 0 0 -1 0 18
f1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 3 2 0 0 -1 1 18
x1 x2 f1 f2 f3 a b
q 0 2 -3 0 -1 0 6
x1 1 0 1 0 0 0 4
f2 0 2 0 1 0 0 12
a 0 2 -3 0 -1 1 6
x1 x2 f1 f2 f3 a b
q 0 0 0 0 0 -1 0
x1 1 0 1 0 0 0 4
f2 0 0 3 1 1 -1 6
x2 0 1 -3/2 0 -1/2 1/2 3
Fim da Fase 1.
Artificial saiu da base.
Solução viável encontrada.
André Gustavo UFV Método simplex INF280 - 2019/1 14 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 2: max z = 3x1 + 5x2
A Fase 2 usa a função objetivo original, e começa da solução viável encontrada na
fase anterior, sem a variável artificial, que não é mais necessária.
x1 x2 f1 f2 f3 b
−z 3 5 0 0 0 0
x1 1 0 1 0 0 4
f2 0 0 3 1 1 6
x2 0 1 -3/2 0 -1/2 3
antes de mais nada, “ajeitamos” a linha de função objetivo,
zerando os coeficientes de x1 e x2, que estão na base.
(neste caso, somar à linha z a linha de x1 ×−3 e de x2 ×−5)
x1 x2 f1 f2 f3 b
−z 0 0 9/2 0 5/2 -27
x1 1 0 1 0 0 4
f2 0 0 3 1 1 6
x2 0 1 -3/2 0 -1/2 3
Quadro inicial da Fase 2.
Continuar o simplex normalmente.
André Gustavo UFV Método simplex INF280 - 2019/1 15 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 2: max z = 3x1 + 5x2
x1 x2 f1 f2 f3 b
−z 0 0 9/2 0 5/2 -27
x1 1 0 1 0 0 4
f2 0 0 3 1 1 6
x2 0 1 -3/2 0 -1/2 3
x1 x2 f1 f2 f3 b
−z 0 0 0 -3/2 1 -36
x1 1 0 0 -1/3 -1/3 2
f1 0 0 1 1/3 1/3 2
x2 0 1 0 1/2 0 6
x1 x2 f1 f2 f3 b
−z 0 0 -3 -5/2 0 -42
x1 1 0 1 0 0 4
f3 0 0 3 1 1 6
x2 0 1 0 1/2 0 6
Fim da Fase 2.
Solução ótima encontrada.
André Gustavo UFV Método simplex INF280 - 2019/1 16 / 26
Introdução Big M Simplex 2 fases Caso especial
Gráfico do exemplo anterior
Fase 1:
O simplex vai de (0, 0) para (4, 0),
diminuindo a inviabilidade na restrição 3
(valor de a) de 18 para 6
Em seguida vai de (4, 0) para (4, 3),
retirando a inviabilidade na restrição 3
(a saiu da base)
Fim da fase 1, solução viável.
Fase 2:
O simplex começa da solução viável
(4, 3), de valor 27, encontrada na fase 1
Desta, vai para (2, 6) de valor 36.
Por fim, para (4, 6), de valor 42.
Fim da fase 2, solução ótima.
André Gustavo UFV Método simplex INF280 - 2019/1 17 / 26
Introdução Big M Simplex 2 fases Caso especial
Exemplo de modelo de minimização
Modelo
min 3x1 + 5x2
s.a.
x1 ≤ 4
2x2 ≥ 12
3x1 + 2x2 ≥ 18
x1, x2 ≥ 0
Modelo na forma padrão
max−3x1 − 5x2
s.a.
x1 + f1 = 4
2x2 − f2 = 12
3x1 + 2x2 − f3 = 18
x1, x2, f1, f2, f3 ≥ 0
André Gustavo UFV Método simplex INF280 - 2019/1 18 / 26
Introdução Big M Simplex 2 fases Caso especial
Exemplo de modelo de minimização
Modelo
min 3x1 + 5x2
s.a.
x1 ≤ 4
2x2 ≥ 12
3x1 + 2x2 ≥ 18
x1, x2 ≥ 0
Forma padrão com artificiais
max−3x1 − 5x2
s.a.
x1 + f1 = 4
2x2 − f2 + a1 = 12
3x1 + 2x2 − f3 + a2 = 18
x1, x2, f1, f2, f3, a1, a2 ≥ 0
André Gustavo UFV Método simplex INF280 - 2019/1 18 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 1: minq = a1 + a2
min q = a1 + a2 ⇒ max − q = −a1 − a2
x1 x2 f1 f2 f3 a1 a2 b
q 0 0 0 0 0 -1 -1 0
f1 1 0 1 0 0 0 0 4
a1 0 2 0 -1 0 1 0 12
a2 3 2 0 0 -1 0 1 18
antes de mais nada, “ajeitamos” a linha de função objetivo,
zerando os coeficientes de a1 e a2, que estão na base
x1 x2 f1 f2 f3 a1 a2 b
q 3 4 0 -1 -1 0 0 30
f1 1 0 1 0 0 0 0 4
a1 0 2 0 -1 0 1 0 12
a2 3 2 0 0 -1 0 1 18
André Gustavo UFV Método simplex INF280 - 2019/1 19 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 1: minq = a1 + a2
x1 x2 f1 f2 f3 a1 a2 b
q 3 4 0 -1 -1 0 0 30
f1 1 0 1 0 0 0 0 4
a1 0 2 0 -1 0 1 0 12
a2 3 2 0 0 -1 0 1 18
x1 x2 f1 f2 f3 a1 a2 b
q 3 0 0 1 -1 -2 0 6
f1 1 0 1 0 0 0 0 4
x2 0 1 0 -1/2 0 1/2 0 6
a2 3 0 0 1 -1 -1 1 6
x1 x2 f1 f2 f3 a1 a2 b
q 0 0 0 0 0 -1 -1 0
f1 0 0 1 -1/3 -1/3 0 1/3 2
x2 0 1 0 -1/2 0 1/2 0 6
x1 1 0 0 1/3 -1/3 -1/3 1/3 2
Fim da Fase 1.
Artificiais saíram da base.
Solução viável encontrada.
André Gustavo UFV Método simplex INF280 - 2019/1 20 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 2: min z = 3x1 + 5x2
Transformando a função objetivo em max , para manter o padrão adotado no simplex:
min z = 3x1 + 5x2 ⇒ max − z = −3x1 − 5x2
x1 x2 f1 f2 f3 b
z -3 -5 0 0 0 0
f1 0 0 1 -1/3 -1/3 2
x2 0 1 0 -1/2 0 6
x1 1 0 0 1/3 -1/3 2
antes de mais nada, “ajeitamos” a linha de função objetivo,
zerando os coeficientes de x1 e x2, que estão na base.
x1 x2 f1 f2 f3 b
z 0 0 0 -3/2 -1 36
f1 0 0 1 -1/3 -1/3 2
x2 0 1 0 -1/2 0 6
x1 1 0 0 1/3 -1/3 2
Fim da Fase 2.
Nenhuma variável
entra na base.
A solução já é ótima.
André Gustavo UFV Método simplex INF280 - 2019/1 21 / 26
Introdução Big M Simplex 2 fases Caso especial
Gráfico do exemplo anterior
Fase 1:
O simplex vai de (0, 0) para (0, 6),
retirando a inviabilidade na restrição 2
(a1 saiu da base)
Em seguida vai de (0, 6) para (2, 6),
retirando a inviabilidade na restrição 3
(a2 saiu da base)
Fim da fase 1, solução viável.
Fase 2:
O simplex começa da solução viável
(2, 6), encontrada na fase anterior
Coincidentemente, ela já é ótima.
Fim da fase 2, solução ótima.
André Gustavo UFV Método simplex INF280 - 2019/1 22 / 26
Introdução Big M Simplex 2 fases Caso especial
Exemplo de caso especial
Modelo
max 3x1 + 5x2
s.a.
x1 ≥ 4
2x2 ≥ 12
3x1 + 2x2 ≤ 18
x1, x2 ≥ 0
Forma padrão com artificiais
max 3x1 + 5x2
s.a.
x1 − f1 + a1 = 4
2x2 − f2 + a2 = 12
3x1 + 2x2 + f3 = 18
x1, x2, f1, f2, f3, a1, a2 ≥ 0
André Gustavo UFV Método simplex INF280 - 2019/1 23 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 1: minq = a1 + a2
min q = a1 + a2 ⇒ max − q = −a1 − a2
x1 x2 f1 f2 f3 a1 a2 b
q 0 0 0 0 0 -1 -1 0
a1 1 0 -1 0 0 1 0 4
a2 0 2 0 -1 0 0 1 12
f3 3 2 0 0 1 0 0 18
antes de mais nada, “ajeitamos” a linha de função objetivo,
zerando os coeficientes de a1 e a2, que estão na base
x1 x2 f1 f2 f3 a1 a2 b
q 1 2 -1 -1 0 0 0 16
a1 1 0 -1 0 0 1 0 4
a2 0 2 0 -1 0 0 1 12
f3 3 2 0 0 1 0 0 18
André Gustavo UFV Método simplex INF280 - 2019/1 24 / 26
Introdução Big M Simplex 2 fases Caso especial
Fase 1: minq = a1 + a2
x1 x2 f1 f2 f3 a1 a2 b
q 1 2 -1 -1 0 0 0 16
a1 1 0 -1 0 0 1 0 4
a2 0 2 0 -1 0 0 1 12
f3 3 2 0 0 1 0 0 18
x1 x2 f1 f2 f3 a1 a2 b
q 1 0 -1 0 0 0 -1 4
a1 1 0 -1 0 0 1 0 4
x2 0 1 0 -1/2 0 0 1/2 6
f3 3 0 0 1 1 0 -1 6
x1 x2 f1 f2 f3 a1 a2 b
q 0 0 -1 -1/3 -1/3 0 -2/3 2
a1 0 0 -1 -1/3 -1/3 1 1/3 2
x2 0 1 0 -1/2 0 0 1/2 6
x1 1 0 0 1/3 1/3 0 -1/3 2
Fim da Fase 1.
Mas a1 não saiu da base!
Modelo inviável
André Gustavo UFV Método simplex INF280 - 2019/1 25 / 26
Introdução Big M Simplex 2 fases Caso especial
Exemplo de caso especial
O simplex vai de (0, 0) para (0, 6),
retirando a inviabilidade na restrição 2
(a2 saiu da base)
Em seguida vai de (0, 6) para (2, 6),
diminuindo a inviabilidade na restrição 1
(a1 diminuiu de 4 pra 2)
Mas não há como retirar a inviabilidade
da restrição 1 sem inviabilizar outra (a1
não sai da base)
Fim da fase 1, o simplex descobre que o
modelo é inviável
André Gustavo UFV Método simplex INF280 - 2019/1 26 / 26
	Introdução
	Big M
	Simplex 2 fases
	Caso especial