INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Método Simplex

É um procedimento algébrico utilizado para resolução de problemas de programação linear, com base
numa interpretação geométrica,cuja compreensão facilita a sua utilização e evidencia as razões da sua
simplicidade e eficácia.


(0,9)
(2,6)
(0,6)
Maximizar Z = 3x1 + 5x2
s.a.:
x1
4
2x2  12
2x1 + 3x2 18
Xi  0
(4,6)


(4,3)
Região
Admissível
(0,0)
Cecília Rocha # 1

(4,0)
(6,0)
Neste problema, cada restrição é representada por uma linha que
limita a região admissível.
Os pontos de intersecção das linhas de restrição são Soluções em
Pontos de Quebra (SPQ) do problema.
Estas SPQ podem ser SPQ Admissíveis – caso dos pontos (0,0)
(4,0) (4,3) (2,6) e (0,6) – ou SPQ Não Admissíveis (6,0) (4,6) e (0,9).
Para qualquer problema de programação linear com n variáveis de
decisão, diz-se que 2 SPQ Admissíveis são adjacentes se partilham
n-1 restrições. As 2 SPQ Admissíveis estão ligadas por um
segmento de recta que se situa nas restrições comuns. Esse
segmento denomina-se limite da região admissível.
Neste caso como n = 2, as SPQA partilham 1 restrição
Teste de Optimização
Considere um problema de programação linear que tem pelo menos
uma solução óptima. Se uma SPQA não tem SPQA adjacentes que
sejam melhores (considerando Z) então será uma Solução Óptima.
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Procedimentos do Método Simplex

Início


Teste de Optimização

(0,9)

(2,6)
2
(4,6)
3


(4,3)
Região
Admissível
(0,0)
1
(4,0)
Cecília Rocha # 2
(6,0)
Concluir que o ponto (0,0) não é a Solução Óptima (os pontos adjacentes levam a uma
melhor solução)
Iterações

(0,6)
1 Escolher o ponto (0,0) como SPQA inicial

1ª Iteração
 Dos 2 limites que partem de (0,0) escolher a direcção x2 – dado que tem maior
parâmetro em Z, pelo que se chegará mais rapidamente à solução óptima.
 Parar no próximo limite da região admissível
 2 Resolver para a intersecção das duas restrições  ponto (0,6)
Teste de Optimização
 Concluir que o ponto (0,6) não é a Solução Óptima
2ª Iteração
 Dos 2 limites que partem de (0,6) escolher a direcção paralela a x1 – dado que a
outra direcção levaria à uma diminuição do valor de Z
 Parar no próximo limite da região admissível
 3 Resolver para a intersecção das duas restrições  ponto (2,6)
Teste de Optimização
 Concluir que o ponto (2,6) é a Solução Óptima
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Metodologia do Método Simplex

1º Conceito de Solução


O método simplex só analisa Soluções em Pontos de Quebra (SPQ). Para qualquer problema com pelo menos
uma solução óptima, só é necessário encontrar a melhor SPQ.
2º Conceito de Solução

O método simplex é um procedimento iterativo com a seguinte sequência:
Inicialização
início das iterações e procura da SPQ inicial
Teste de Optimização
Será a SPQ actual a Solução Óptima?
Não
STOP
Iteração

Fazer uma iteração para procurar uma SPQ melhor.
3º Conceito de Solução

Cecília Rocha # 3
Sim
Sempre que possível, a inicialização do método simplex é feita na Origem (todas as variáveis de decisão iguais a
zero), o que evita a necessidade de calcular algebricamente o valor das variáveis.
2001/2002
INVESTIGAÇÃO OPERACIONAL
4ª Aula (cont.)


Metodologia do Método Simplex

4º Conceito de Solução


(0,9)

5º Conceito de Solução

TC = 3
2
TC  0
(0,6)
(2,6)
(4,6)
3
(0,0)
TC  0
TC = 5


(4,3)
1
TC = 3
Cecília Rocha # 4
(4,0)
(6,0)
O método simplex analisa os limites da Região Admissível que partem da SPQ
actual e levam às SPQ adjacentes, identificando a taxa de crescimento de Z que
será obtida pela movimentação em cada limite. Das taxas de crescimento positivas,
o método simplex escolha a maior.
TC (4,0) = 3 e TC (0,6) = 5  próxima SPQ = (0,6)
6º Conceito de Solução

Região
Admissível
Cada vez que o método simplex realiza uma iteração para se aproximar de uma
SPQ melhor, escolhe sempre uma SPQ adjacente e nunca nenhuma das outras
ainda disponíveis. Assim, o percurso percorrido para atingir a solução óptima será ao
longo dos limites da Região Admissível.
(0,0)  SPQ adjacentes (4,0) e (0,6)

A existência de uma taxa de crescimento positiva em Z indica que há uma SPQ
adjacente melhor que a actual, enquanto que uma taxa de crescimento negativa
indica uma SPQ pior que a actual. Então, o teste de optimização consiste em
verificar se a taxa de crescimento em Z para cada um dos limites que saem da SPQ
actual é positiva. Se não existir nenhuma positiva então a SPQ é a Solução Óptima.
TC (4,3)  0 e TC (0,6)  0  Solução Óptima SPQ = (2,6)
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Preparação do Método Simplex

Procedimento Algébrico


Envolve a resolução de sistemas de equações, pelo que será necessário converter as restrições sob a forma de
desigualdade em igualdade. Esta conversão é feita pela introdução de Variáveis de Folga.
Retomando o mesmo exemplo:
Problema Inicial
Maximizar Z = 3x1 + 5x2
s.a.:
x1
4
2x2  12
3x1 + 2x2  18
xi  0
Cecília Rocha # 5
Forma Aumentada do Problema
Introduzir Variáveis de Folga
(x3, x4, x5)
Maximizar Z = 3x1 + 5x2
s.a.:
x1
+ x3
=4
2x2
+ x4
= 12
3x1 + 2x2
+ x5 = 18
xi  0

A Forma Aumentada do Problema é constituída pelas Variáveis de Decisão e pelas Variáveis de Folga

Uma Solução Básica (SB) é uma solução em ponto de quebra aumentada

Uma Solução Básica Admissível (SBA) é uma solução em ponto de quebra admissível aumentada
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Preparação do Método Simplex

A Solução Básica Admissível (SBA) é constituída por:



Uma Solução Básica tem as seguintes propriedades






Cecília Rocha # 6
Variáveis básicas – VB
Variáveis não básicas – VNB (são iguais a zero)
Cada variável é designada por VB ou VNB;
O número de VB é igual ao número de restrições e o número de VNB é igual ao número de
variáveis menos o número de restrições;
As VNB são iguais a zero;
Os valores das VB são obtidos pela resolução do sistema de equações das restrições;
Se as VB satisfazem a restrição de não- negatividade, a SB é uma SBA.
Duas Soluções Básicas Admissíveis (SBA) são adjacentes se todas menos uma das VNB são as
mesmas. Assim, todas menos uma das VB também são as mesmas, embora possam ter valores
numéricos diferentes.
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exemplo de Aplicação do Método Simplex – Resolução Algébrica

Inicialização
Maximizar Z = 3x1 + 2x2
s.a.:
x1
4
x1 + 3x2  15
2x1 + x2  10
xi  0

Solução Básica Admissível Inicial


Resolução do sistema na Forma Aumentada

Se x1 = 0 e x2 = 0  x3 = 4; x4 = 15 e x5 = 10

SBA inicial (0, 0, 4, 15, 10)
Teste de Optimização


Cecília Rocha # 7
Adicionar
Variáveis de Folga
Maximizar Z = 3x1 + 2x2
s.a.:
x1
+ x3
=4
x1 + 3x2
+ x4
= 15
2x1 + x2
+ x5 = 10
Taxas de crescimento em x1 e x2 (são ambas positivas)

TC (x1) = 3

TC (x2) = 2
Determinação da direcção do movimento

Como a Taxa de Crescimento em x1 é superior, x1 deixará de ser VNB e passará a variável básica de entrada
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exemplo de Aplicação do Método Simplex – Resolução Algébrica (cont.)

1ª Iteração

Determinar a VB que passará a Variável Básica de Saída (VBS), ou seja, qual a VB que tomará o valor zero em
primeiro lugar
Se x2 = 0, então
x1 + x3 = 4

x3 = 4 – x1  0
 x1  4
mínimo
x1 + 3x2 + x4 = 15

x4 = 15 – x1  0
 x1  15
2x1 + x2 + x5 = 10

x5 = 10 – 2x1  0
 x1  5
O teste do rácio mínimo indica que a VBS será x3
Encontrar a nova SBA

Se x2 = 0 e x3 = 0, então (para anular x1 em todas as equações menos uma)


(0)
(1)
(2)
(3)

Z – 3x1 – 2x2 = 0
x1
+ x3
=4
x1 + 3x2
+ x4
= 15
2x1 + x2
+ x5 = 10
Realizando as operações indicadas à esquerda, obtemos:
(0)+3(1)
(1)
(2)-(1)
(3)-2(1)
Cecília Rocha # 8
Z – 3x1 – 2x2 + 3(x1 + x3) = 0 + 3*4
(1º)
x1
+ x3
=4
(3º)
x1 + 3x2
+ x4 - (x1 + x3) = 15 – 4
(4º)
2x1 + x2
+ x5 – 2(x1 + x3) = 10 – 2*4
(2º)
Z
- 2x2 + 3x3
= 12

x1
+ x3
=4

3x2 – x3 + x4
= 11

- x2 - 2 x3
+ x5 = 2
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exemplo de Aplicação do Método Simplex – Resolução Algébrica (cont.)


Teste de Optimização



Encontrar a nova SBA

Se x2 = 0 e x3 = 0 então x1 = 4; x4 = 11; x5 = 2 e Z = 12

SBA intermédia (4, 0, 0, 11, 2)
Taxas de crescimento em x2 e x3

TC (x2) = 2

TC (x3) = -3
Determinação da direcção do movimento

Como a Taxa de Crescimento em x2 é positiva, x2 deixará de ser VNB e passará a variável básica de entrada
2ª Iteração

Determinar a VB que passará a Variável Básica de Saída (VBS), ou seja, qual a VB que tomará o valor zero em
primeiro lugar
Se x3 = 0, então
x1
+ x3
=4

x1 = 4  0
 x1 = 
3x2 – x3 + x4
= 11

x4 = 11 – 3x2  0
 x2  11/3
x2 – 2x3
+ x5 = 2

x5 = 2 – x2  0
 x2  2
mínimo

Cecília Rocha # 9
O teste do rácio mínimo indica que a VBS será x5
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exemplo de Aplicação do Método Simplex – Resolução Algébrica (cont.)

Encontrar a nova SBA

Se x3 = 0 e x5 = 0, então (para anular x2 em todas as equações menos uma)
(0)
(1)
(2)
(3)

- 2x2 + 3x3
= 12
x1
+ x3
=4
3x2 – x3 + x4
= 11
- x2 - 2 x3
+ x5 = 2
Realizando as operações indicadas à esquerda, obtemos:
(0)+2(3)
(1)-0(3)
(2)-3(3)
(3)


(2º)
Z
(3º)
(4º)
(1º)
– 2x2 + 3x3 + 2(-x2 – 2x3 + x5) = 12 + 2*2
x1
+ x3
=4
x1 + 3x2
+ x4 - 3(-x2 –2x3 + x5) = 11 – 3*2
- x2 + 2x3
+ x5 = 2




Z
– x3
+ 2x5 = 16
x1 + x3
=4
5x3 + x4 – 3x5 = 5
x2 – 2x3
+ x5 = 2
Encontrar a nova SBA

Se x3 = 0 e x5 = 0 então x1 = 4; x2 = 2; x4 = 5 e Z = 16

SBA intermédia (4, 2, 0, 5, 0)
Teste de Optimização


Cecília Rocha # 10
Z
Taxas de crescimento em x3 e x5

TC (x3) = 1

TC (x5) = -2
Determinação da direcção do movimento

Como a Taxa de Crescimento em x3 é positiva, x3 deixará de ser VNB e passará a variável básica de entrada
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exemplo de Aplicação do Método Simplex – Resolução Algébrica (cont.)

3ª Iteração

Determinar a VB que passará a Variável Básica de Saída (VBS), ou seja, qual a VB que tomará o valor zero em
primeiro lugar
Se x5 = 0, então
x1 + x3
=4

x1 = 4 - x3  0
 x3  4
5x3 + x4 – 3x5 = 5

x4 = 5 – 5x3  0
 x3  1
mínimo
x2 – 2x3
+ x5 = 2

x2 = 2 – 2x3  0
 x3  2
O teste do rácio mínimo indica que a VBS será x4
Encontrar a nova SBA

Se x4 = 0 e x5 = 0, então (para anular x3 em todas as equações menos uma)


(0)
(1)
(2)
(3)

– x3
+ 2x5 = 16
x1
+ x3
=4
5x3 + x4 – 3x5 = 5
x2 – 2x3
+ x5 = 2
Realizando as operações indicadas à esquerda, obtemos:
(0)+(2)
(1)-(2)
(2)5
(3)+2(2)
Cecília Rocha # 11
Z
(2º)
(3º)
(1º)
(1º)
Z
– x3 + 2x5 + (x3 + 1/5x4 – 3/5x5) = 16 + 1
 Z
+ 1/5x4 + 7/5x5 = 17
x1
+ x3 – (x3 + 1/5x4 – 3/5x5) = 4 – 1

x1
- 1/5x4 + 3/5x5 = 4
x3 + 1/5x4 – 3/5x5 = 1

x3 + 1/5x4 – 3/5x5 = 1
- x2 + 2x3
+ x5 + 2(x3 + 1/5x4 – 3/5x5) = 2 + 2*1 
x2
+ 2/5x4 – 1/5x5 = 4
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exemplo de Aplicação do Método Simplex – Resolução Algébrica (cont.)


Encontrar a nova SBA

Se x4 = 0 e x5 = 0 então x1 = 3; x2 = 4; x3 = 1 e Z = 17

SBA intermédia (3, 4, 1, 0, 0)
Teste de Optimização


Taxas de crescimento em x4 e x5

TC (x4) = - 1/5

TC (x5) = - 7/5
Determinação da direcção do movimento

Como as Taxas de Crescimento são negativas, já temos a solução óptima pois qualquer incremento nas VNB
vai levar à diminuição do valor da função objectivo.

Cecília Rocha # 12
Solução Final ( 3, 4, 1, 0, 0 )  Z = 17
2001/2002
INVESTIGAÇÃO OPERACIONAL

4ª Aula (cont.)

Exercício Proposto
Considere o seguinte problema:
Maximizar Z = x1 + 2x2
s.a.:
x1
2
x2  2
x1 + x2  3
xi  0
a) Resolva graficamente e marque todas as soluções em ponto de quebra admissíveis
b) Introduza variáveis de folga para escrever a forma aumentada do problema
c) Para cada SPQ Admissível, identifique a SB Admissível calculando o valor das variáveis de folga. Para cada SBA utilize os
valores das variáveis para identificar as VB e as VNB
d) Resolva este problema, pelo método simplex, utilizando a resolução algébrica
e) Confirme o resultado pelo SOLVER - Excel
Cecília Rocha # 13
2001/2002