Buscar

Método Simplex para Resolução de PLs

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

1
Resolução de PLs
� O método de enumeração de soluções básicas 
é muito ineficiente.
� O número de possíveis bases pode ser enorme
� Para encontrar a solução associada a cada base é
preciso resolver um sistema linear
� O método simplex resolve ambos os problemas
� Só considera um número relativamente pequeno de 
bases
� Não é necessário resolver um sistema linear inteiro 
para encontrar a solução associada a cada base
2
Pesquisa Operacional I
Método Simplex
Prof.: Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI/
3
Exemplo: Problema de Mix de Produção
x15 10 15
x
2
5
1
0
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 ≤ 24
3,0 x1 + 1,5 x2 ≤ 21
1,0 x1 + 1,0 x2 ≤ 8
x1 , x2 ≥ 0
4
Método Simplex
O método exige que o PL esteja no formato padrão.
Introduzir variáveis de folga
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 ≤ 24
3,0 x1 + 1,5 x2 ≤ 21
1,0 x1 + 1,0 x2 ≤ 8
x1 , x2 ≥ 0
5
PL no formato padrão.
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 + 1 x3 = 24
3,0 x1 + 1,5 x2 + 1 x4 = 21
1,0 x1 + 1,0 x2 + 1 x5 = 8
x1 , x2 , x3 , x4 , x5 ≥ 0
Método Simplex
6
As variáveis de folga formam uma base que é uma matriz 
identidade => a solução básica viável associada é facilmente 
encontrada
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 + 1 x3 = 24
3,0 x1 + 1,5 x2 + 1 x4 = 21
1,0 x1 + 1,0 x2 + 1 x5 = 8
x1 , x2 , x3 , x4 , x5 ≥ 0
Método Simplex
7
Reescrever o sistema isolando as variáveis básicas do lado 
esquerdo das equações. As variáveis não-básicas e o termo 
constante ficam do lado direito. A variável z (valor da função 
objetivo) também é representada por uma equação;
x3 = 24 – 1,5 x1 – 4,0 x2
x4 = 21 – 3,0 x1 – 1,5 x2
x5 = 8 – 1,0 x1 – 1,0 x2
z = 4,0 x1 + 6,0 x2
Método Simplex
8
Reescrever o sistema isolando as variáveis básicas do lado 
esquerdo das equações. As variáveis não-básicas e os 
termos constantes ficam do lado direito. A variável z (valor 
da função objetivo) também é representada:
x3 = 24 – 1,5 x1 – 4,0 x2
x4 = 21 – 3,0 x1 – 1,5 x2
x5 = 8 – 1,0 x1 – 1,0 x2
z = 4,0 x1 + 6,0 x2
Método Simplex
A solução básica é:
x1 = 0 x2 = 0
x3 = 24 x4 = 21
x5 = 8
Valor da FO para essa solução:
z = 0
9
Dicionário 
Um PL reescrito de forma a que as variáveis de uma solução 
básica viável fiquem isoladas no seu lado esquerdo está em 
forma de “dicionário”
x3 = 24 – 1,5 x1 – 4,0 x2
x4 = 21 – 3,0 x1 – 1,5 x2
x5 = 8 – 1,0 x1 – 1,0 x2
z = 4,0 x1 + 6,0 x2
10
Dicionário 
Essa representação é muito conveniente, porque o valor das 
variáveis básicas já é dado pelas constantes (não é
necessário resolver o sistema BxB = b ).
x3 = 24 – 1,5 x1 – 4,0 x2
x4 = 21 – 3,0 x1 – 1,5 x2
x5 = 8 – 1,0 x1 – 1,0 x2
z = 4,0 x1 + 6,0 x2
11
x15 10 15
x
2
5
1
0
x1 = 0 x2 = 0
x3 = 24 x4 = 21
x5 = 8
z = 0
Solução atual
12
Melhorando a solução atual
Escolher uma variável não-básica (do lado direito do 
dicionário) para ter seu valor aumentado, de forma a 
também aumentar o valor da função objetivo.
x3 = 24 – 1,5 x1 – 4,0 x2
x4 = 21 – 3,0 x1 – 1,5 x2
x5 = 8 – 1,0 x1 – 1,0 x2
z = 4,0 x1 + 6,0 x2
13
Escolher uma variável não-básica (do lado direito do 
dicionário) para ter seu valor aumentado, de forma a 
também aumentar o valor da função objetivo.
x3 = 24 – 1,5 x1 – 4,0 x2
x4 = 21 – 3,0 x1 – 1,5 x2
x5 = 8 – 1,0 x1 – 1,0 x2
z = 4,0 x1 + 6,0 x2
Escolhemos x2. O maior valor que x2
pode ter sem que alguma variável básica 
fique com valor negativo é dado por:
2
24 21 8
min , , 6
4 1,5 1
x
 
= = 
 
Nesse momento já sabemos que a nova 
solução vai ter z=36. A variável que 
passou a valer 0 após o crescimento de 
x2 foi x3.
Melhorando a solução atual
14
Montando o novo dicionário
O sistema é reescrito de forma a que x2 fique isolada no lado 
esquerdo e x3 vá para o lado direito.
3 1 2
2 1 3
2 1 3
324 4
2
34 24
2
3 16
8 4
x x x
x x x
x x x
= − −
= − −
= − −
Primeiro reescrevemos a
única equação em que x2 e
x3 aparecem
15
Substituindo a equação para x2 nas equações restantes, 
todo o sistema é atualizado:
2 1 3
4 1 1 3
5 1 1 3
1 1 3
3 16
8 4
3 3 121 3 6
2 8 4
3 18 1 1 6
8 4
3 14 6 6
8 4
x x x
x x x x
x x x x
z x x x
= − −
 
= − − − − 
 
 
= − − − − 
 
 
= + − − 
 
Montando o novo dicionário
16
Novo dicionário
Dizemos que a variável x3 saiu da base e a variável x2 entrou 
na base.
2 1 3
4 1 3
5 1 3
1 3
3 16
8 4
39 312
16 8
5 12
8 4
7 336
4 2
x x x
x x x
x x x
z x x
= − −
= − +
= − +
= + −
17
Novo dicionário
2 1 3
4 1 3
5 1 3
1 3
3 16
8 4
39 312
16 8
5 12
8 4
7 336
4 2
x x x
x x x
x x x
z x x
= − −
= − +
= − +
= + −
A nova solução básica viável é:
x1 = 0 x2 = 6
x3 = 0 x4 = 12
x5 = 2
Esta solução aumentou a função 
objetivo:
z = 36
Dizemos que a variável x3 saiu da base e a variável x2 entrou 
na base.
18
Nova solução básica viável
x15 10 15
x
2
5
1
0
:
x1 = 0 x2 = 6
x3 = 0 x4 = 12
x5 = 2
z = 36
19
Melhorando a solução
Ainda é possível aumentar o valor de z?
2 1 3
4 1 3
5 1 3
1 3
3 16
8 4
39 312
16 8
5 12
8 4
7 336
4 2
x x x
x x x
x x x
z x x
= − −
= − +
= − +
= + −
20
Melhorando a solução
Ainda é possível aumentar o valor de z? Sim.
2 1 3
4 1 3
5 1 3
1 3
3 16
8 4
39 312
16 8
5 12
8 4
7 336
4 2
x x x
x x x
x x x
z x x
= − −
= − +
= − +
= + −
21
Melhorando a solução
2 1 3
4 1 3
5 1 3
1 3
3 16
8 4
39 312
16 8
5 12
8 4
7 336
4 2
x x x
x x x
x x x
z x x
= − −
= − +
= − +
= + −
Aumentando x1 sem fazer que uma 
variável básica fique com valor 
negativo. O maior valor para x1 é:
1
6 12 2 16
min , ,3 39 5 58 16 8
x
 
 
= = 
  
Nesse momento já sabemos que a nova 
solução vai ter z=36+7/4.16/5=41,6. A 
variável que passou a valer 0 após o 
crescimento de x1 foi x5.
22
Montando o novo dicionário
Seguindo o mesmo procedimento da iteração anterior, o 
dicionário é atualizado através da 3ª equação do dicionário 
anterior.
x1 entra na base (vai pro lado esquerdo) e x5 sai da base (vai 
para o lado direito).
1 3 5
1 3 5
5 12
8 4
16 2 8
5 5 5
x x x
x x x
= + −
= + −
23
Novo dicionário
Substituindo x1 nas equações restantes do dicionário 
anterior, tem-se o seguinte dicionário atualizado:
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4 14
5 5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
24
Novo dicionário
Substituindo x1 nas equações restantes do dicionário 
anterior, tem-se o seguinte dicionário atualizado:
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4 14
5 5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
A solução básica viável é:
x1 = 16/5 x2 = 24/5
x3 = 0 x4 = 21/5
x5 = 0
Esta solução resulta em:
z = 208/5
25
x1 = 16/5 =3,2
x2 = 24/5 = 4,8
x3 = 0
x4 = 21/5 = 4,2
x5 = 0
z = 208/5 = 41,6
x15 10 15
x
2
5
1
0
Nova solução básica viável
26
Novo dicionário
Ainda é possível aumentar o valor da função objetivo?
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4 14
5 5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
27Solução ótima
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4 14
5 5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
Não existem variáveis não-básicas 
que, quando aumentadas, 
resultem em aumento no valor da 
função objetivo.
Logo, a solução básica mostrada 
nesse sistema é ótima.
28
1. Montar um dicionário inicial
2. Olhando a equação do z, escolha uma variável não-
básica xin cujo aumento melhoraria a solução corrente 
do dicionário (coeficiente negativo se for minimização, 
positivo se for maximização). Se não houver tal 
variável, a solução corrente é ótima.
3. Calcule o máximo valor para que xin que não torne 
uma variável básica negativa. Se esse valor for infinito, 
o PL é ilimitado. Caso contrário, escolha uma variável 
xout que bloqueou o crescimento de xin.
4. A variável xin entra na base, xout sai da base. Atualize o 
dicionário colocando xin isolado do lado esquerdo, xout
vai pro lado direito. Volte para o Passo 2.
Método Simplex
29
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e foi criado a partir das 
notas do Prof. Rodrigo A. Scarpel do ITA 
(www.mec.ita.br/~rodrigo) e não pode ser 
reproduzido sem autorização prévia de ambos os 
autores. Quando autorizado, seu uso é exclusivo 
para atividades de ensino e pesquisa em 
instituições sem fins lucrativos.

Outros materiais