Metodo Simplex

Prévia do material em texto

Investigação Operacional
Tema 3 - O Método Simplex Directo
Curso de Licenciatura em Matemática - 2022
Investigação Operacional
Fundamentação Teórica do Método Simplex
Investigação Operacional
Conceitos básicos: PPL na Forma Padrão
Investigação Operacional
Conceitos básicos: PPL na Forma Padrão
Investigação Operacional
Transformação do PPL na forma padrão
■ Restrições de desigualdade:
➜ Suponha que a restrição i seja dada por
ai1x1 + ai2x2 + . . . + ainxn ≤ bi
Para converter (≤) em (=), basta adicionar uma variável de folga não-
negativa no lado esquerdo da restrição. Ou seja,
ai1x1 + ai2x2 + . . . + ainxn + xk = bi , xk ≥ 0
Por exemplo, para restrição 3x1 + 4x2 − x3 ≤ 7, a forma padrão é:
3x1 + 4x2 − x3+x4 = 7, x4 ≥ 0
➜ Analogamente, se a restrição for da forma
ai1x1 + ai2x2 + . . . + ainxn ≥ bi
Investigação Operacional
Transformação do PPL na forma padrão
basta subtrair uma variável de excesso não-negativa no lado esquerdo da 
inequação para transformá-la em igualdade, ou seja,
ai1x1 + ai2x2 + . . . + ainxn - xk = bi , xk ≥ 0 Por exemplo, para restrição 3x1 + 
4x2 − x3 ≥ 7, tem-se:
3x1 + 4x2 − x3−x4 = 7, x4 ≥ 0
■ Variáveis irrestritas (livres): Se xi é irrestrita de sinal do problema, então
i
′ ′ ′ ′ ′ ′
i i i ix = x − x , com x ≥ 0, x ≥ 0
i i
′ ′
i i■ Variáveis negativas: x ≤ 0 ⇔ x = −x , com x ≥ 
0
■ Função objectivo: Maximizar{F (x )} ⇔ −Minimizar{−F (x )}.
Investigação Operacional
Transformação do PPL na forma padrão
Exemplo: O seguinte PPL:
Maximizar Z = x1 − x3
Sujeito a :
x1 + 2x2 − x3 ≥ 2
x1 − x2 − 3x3 = 1
x2 + x3 ≤ 5
x1 irrestrito, x2 ≥ 0, x3≤ 0,
Investigação Operacional
Transformação do PPL na forma padrão
Exemplo: O seguinte PPL:
Maximizar Z = x1 − x3
Sujeito a :
x1 + 2x2 − x3 ≥ 2
x1 − x2 − 3x3 = 1
x2 + x3 ≤ 5
x1 irrestrito, x2 ≥ 0, x3≤ 0,
é equivalente ao problema na forma padrão:
1
′ ′ ′
1−Minimizar Z = −(x − x ) − x
′
3
Sujeito a :
′
1
′ ′
1
′
32 4x − x + 2x + x − x = 2
′ ′ ′
1 1 2
′
3x − x − x + x = 1
2
′
3 5x − x + x = 5
′ ′ ′ ′
1 1 32 4 5x , x , x , x , x , x 
≥ 0
Investigação Operacional
Conceitos básicos: PPL na Forma Canônica
Investigação Operacional
Conceitos básicos: PPL na Forma Canônica
Investigação Operacional
Conceitos básicos: Conjunto convexo
■ Conjunto convexo: Um conjunto C ⊆ ℝn é convexo sse ∀x, y ∈ C 
,
λx + (1 − λ)y ∈ C, ∀λ ∈ [0, 1]
■ Teorema: O conjunto C das soluções viáveis de um PPL é um conjunto 
convexo.
■ Ponto extremo: u ∈ C é um ponto extremo (ou vértice) do conjunto C de
soluções viáveis de um PPL, se ∄ x, y ∈ C : u = λx + (1 − λ)y, ∀λ ∈ [0, 1].
Ou seja u é ponto extremo se não for um ponto interior de uma linha recta
que conecta x e y .
Investigação Operacional
Conceitos básicos: Solução básica de um PPL
Suponha um PPL na forma padrão:
Minimizar cTx
s.a :
Ax = b
x ≥ 0,
onde A é uma matriz m × n (m < n); x é um vector n−dimensional (nº de 
variáveis); b é um vector m−dimensional (nº de equações).
■ Se igualarmos n−m variáveis zero (denominadas variáveis não básicas), e
depois resolvermos as m equações para as m variáveis restantes
(denominadas variáveis básicas), a solução resultante, se for única é
denominada Solução Básica.
■ Uma solução básica corresponde a um vértice ou ponto extremo (viável ou
não) da região de soluções.
Investigação Operacional
Conceitos básicos: Solução básica de um PPL
Exemplo: Considere o seguinte PPL com duas variáveis:
Maximizar Z = 2x1 + 3x3
s.a
2x1 + x2 ≤ 4
x1 + 2x2 ≤ 5
x1, x2 ≥ 0
Na forma padrão, o problema fica:
Minimizar − Z = −2x1 − 3x3
2x1 + x2 + x3 = 4
s.a x1 + 2x2 + x4 = 5
x1, x2, x3, x4 ≥ 0
O sistema tem m = 2 equações e n = 4 variáveis. Assim, as soluções básicas
(pontos extremos) podem ser determinadas algebricamente igualando n − m
= 4−2 = 2 variáveis em zero e, depois, resolvendo para as m = 2 variáveis
restantes.
Investigação Operacional
Conceitos básicos: Solução básica de um PPL
Representação gráfica da região de soluções para o problema e os lugares 
geométricos (LG) de x 1 = 0, x2 = 0, x3 = 0 e x4 = 0:
■ Por exemplo, se fizermos x1 = 0 e x2 = 0, as equações dão solução (básica) 
única
x3 = 4, x4 = 5
■ Esta solução corresponde ao ponto A na figura acima.
Investigação Operacional
Conceitos básicos: Solução básica de um PPL
■ Um outro ponto pode ser determinado fazendo x3 = 0 e x4 = 0, e então 
resolvendo as duas equações
2x1 + x2 = 4
x1 + 2x2 = 5
o que resulta na solução básica (x1 = 1, x2 = 2), que é o ponto C na figura 
acima.
■ O número máximo de soluções básicas de um PPL é
n
mC =
n!
m!(n − m)!
.
■ Definição: Se todos os valores da solução básica forem não negativos, 
então a solução básica é Solução Básica Viável (SBV).
■ Por exemplo, para determinar o ponto E , fazemos x2 = 0 3 x4 = 0. 
Resolvendo as equações, obtemos a solução básica única (x1 = 5, x3 = −6).
■ Como x3 < 0, então a solução obtida é uma solução básica não viável (não
candidata a solução óptima)
Investigação Operacional
Conceitos básicos: Solução básica viável de um PPL
■ Teorema (Equivalência entre pontos extremos e SBV): Toda SBV do
sistema Ax = b é um ponto extremo (ou vértice) do conjunto C de
soluções viáveis de um PPL.
■ Teorema: A solução óptima de um PPL com um conjunto C de soluções
viáveis será atingida ao menos em um vértice de C (SBV óptima).
■ Trabalho domiciliar:
Considerando o PPL deste exemplo, encontre soluções básicas
correspondentes aos vértices B, D e F , indicando as respectivas
sequências. Identificar as soluções básicas viáveis.
Investigação Operacional
O Algoritmo Simplex
■ Sabe-se que as soluções básicas viáveis (candidatas a soluções óptimas)
de qualquer PPL localizam-se sobre os vértices da região de soluções
viáveis.
■ A idéia básica do algoritmo simplex é: mover-se de um vértice (i.e, um
ponto extremo da região de soluções viáveis) a outro vértice adjacente,
sempre que for possível melhorar o valor da função objectivo, até atingir
a solução óptima (a melhor SBV);
■ Portanto, o método simplex se concentra exclusivamente em SBV. Se o
PPL tem (pelos menos) uma solução óptima, ela é a melhor SBV.
■ Vantagem do método simplex: Na maioria dos casos, o método simplex
não precisará explorar todos os pontos extremos (SBV) para atingir uma
solução óptima.
Investigação Operacional
O Algoritmo Simplex
■ A forma mais conveniente para realizar as operações no método simplex é 
organiza-las em tabelas, chamadas tabelas simplex.
■ Basicamente, a tabela simplex apresenta os coeficientes das variáveis em 
colunas e as restrições e função objectivo em linhas.
RESOLUÇÃO DE UM PPL USANDO A TABELA SIMPLEX
Como exemplo, considere o PPL:
Maximizar Z = 2x1 + 3x2 Sujeito a :
2x1 + x2 ≤ 4 x1 + 2x2 ≤ 5 x1, x2 ≥ 0.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Passo 0: Transformar o PPL na forma canônica 
Para este exemplo, a forma padrão do PPL fica:
Minimizar − Z = −2x1 − 3x2 + 0x3 + 0x4 Sujeito a :
2x1 + x2 + x3 + 0x4 = 4
x1 + 2x2 + 0x3 + x4 = 5
x1, x2, x3, x4 ≥ 0
SObserve que, para S = {3,4} , A =
1 0
0 1
= I e Cs = 0, então o PPL está
na forma canônica em relação a essa sequência.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Passo 0: Transformar o PPL na forma canônica 
Para este exemplo, a forma padrão do PPL fica:
Minimizar − Z = −2x1 − 3x2 + 0x3 + 0x4 Sujeito a :
2x1 + x2 + x3 + 0x4 = 4
x1 + 2x2 + 0x3 + x4 = 5
x1, x2, x3, x4 ≥ 0
SObserve que, para S = {3,4} , A =
1 0
0 1
= I e Cs = 0, então o PPL está
na forma canônica em relação a essa sequência.
■ Passo 1: Encontrar a solução básica inicial e apresenta-la na forma tabular
(tabela simplex inicial)
“Sempre que possível, a inicialização do método simplex opta pela origem
(todas as variáveis de decisão iguais a zero) como a SBV inicial.”(Hillier e
Lieberman, 2013).
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
Assim, para o sistema de equações do exemplo,
2x1 + x2 + x3 + 0x4 = 4
x1 + 2x2 + 0x3 + x4 = 5
x1, x2, x3,x4 ≥ 0,
fixando x1 = 0 e x2 = 0, tem-se x3 = 4 e x4 = 5. Portanto, a SBV inicial (trivial)
é x=(0,0,4,5), resultando no valor da F.O −Z = −2·0−3·0+0·4+0·5 = 0 ⇔ Z =
0. A tabela simplex inicial ficará da seguinte forma:
VB x1 x2 x3 x4 b
x3 2 1 1 0 4
x4 1 2 0 1 5
F.O. -2 -3 0 0 −Z
Note que a equação da função objectivo sempre é escrita em termos das 
variáveis não básicas. Para o exemplo,
−2x1 − 3x2 = −Z,
onde Z é um parâmetro (variável) da função objectivo.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Observe ainda que na tabela acima:
➜ As varáveis de folga (x3 e x4) são as variáveis básicas iniciais (formam 
uma base canônica);
➜ Cada variável básica tem coeficiente +1 em uma equação e 0 nas outras 
(incluindo na função objectivo);
➜ Cada equação possui exatamente uma variável básica com o coeficiente 
+1.
■ Passo 2: Executar um teste de optimalidade: a SBV actual é óptima?
➜ Se todos os coeficientes da função objectivo (última linha) forem não 
negativos (≥ 0), então pare, a SBV actual é óptima;
➜ Caso contrário, realize uma iteração para obter a próxima SBV (Passo 3). 
Significa que a SBV actual pode ser melhorada.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Passo 3: Determinar a variável a entrar na base:
Seleciona-se a variável não básica com coeficiente “mais negativo” (maior
valor absoluto) na função objectivo. A coluna associada a essa variável é
chamada coluna pivô.
VB x1 x2 x3 x4 b
x3 2 1 1 0 4
x4 1 2 0 1 5
F.O -2 -3 0 0 −Z
⇑
■ Passo 4: Determinar a variável que sairá da base aplicando o teste da 
razão mínima (Condição de viabilidade):
O Objectivo do teste é determinar a variável básica cai a zero primeiro, à 
medida que a variável básica que entra é aumentada.
Para o Exemplo: Já que x2 vai tornar-se VB, x1 continuará não básica e igual a 
zero.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
Assim, as equações podem ser vistas como
x2 + x3 = 4 2x2 + x4 = 5
Uma das duas VB (x3 ou x4) deverá tornar-se variável não básica, mas a 
outra não pode ser negativa (Isso garante a viabilidade da próxima solução 
básica). Assim
x3 = 4 − x2 ≥ 0
x4 = 5 − 2x2 ≥ 0
Escrevendo em função de x2, tem-se:
x2 ≤ 4
2x ≤
5
2
Desse modo, x2 pode ser aumentada apenas até 5 , no qual o ponto x4 chega
a 0 e x3 continua positiva. Caso contrário, x4 seria neg
2
ativa, o que violaria a
viabilidade do problema. Assim, x4 é a VB que se torna variável não básica.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Resumindo (Teste da Razão mínima): Esta verificação implica uma escolha
da linha com menor razão entre o lado direito das equações, bj , e o
coeficiente da coluna pivô que seja estritamente positivo (> 0).
A linha associada a variável que sai da base é chamada chamada linha pivô.
O ponto de intersecção da linha pivô com a coluna pivô é conhecido como
elemento pivô
⇐
VB x1 x2 x3 x4 b Razão
x3 2 1 1 0 4 4/1
x4 1 2 0 1 5 5/2 ← mín.
F.O. -2 -3 0 0 −Z
⇑
4 5
1 2
}
■ min , = 5
2
■ Então, x2 substitui x4 como variável básica.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Passo 5: Construir uma nova tabela simplex com a nova SBV
Recolocar o problema na forma canônica usando operações elementares em
linhas, chamadas operações de “pivoteamento” ou, simplesmente, de
eliminação gaussiana.
1) Linha pivô
i) Substituir a variável que sai da base pela variável que entra na base;
ii) Nova linha pivô=Linha pivô actual𝚵 Elemento pivô
2)
Nova Linha =(Linha actual)-(Seu coeficiente de coluna pivô)×(Nova linha 
pivô)
■ Para o exemplo:
➜ Já que x2 substitui x4 como variável básica, inicialmente, divide-se a linha
pivô (linha 2) pelo elemento pivô (2), obtendo-se:
VB x1 x2 x3 x4 b
x2 1/2 1 0 1/2 5/2
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ Continuando:
➜ Na linha 1, devemos encontrar 0 no coeficiente relativo a x2. Operaremos
1 1
′ ′
2com a linha 2, já modificada. Assim, deve-se fazer L = L − L . Encontra-
se, então:
VB x1 x2 x3 x4 b
x3 3/2 0 1 -1/2 3/2
x2 1/2 1 0 1/2 5/2
3➜ Para que o coeficiente de x2 na linha 3 (F.O) seja zero, deve-se fazer L
′ 
= 2L3 + 3L
′
:
VB x1 x2 x3 x4 b
x3 3/2 0 1 -1/2 3/2
x2 1/2 1 0 1/2 5/2
F.O -1/2 0 0 3/2 −Z + 15/2
■ Fim da primeira iteração (vá para o Passo 
1).
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
■ A 2ª iteração começa a partir da última tabela (Passo 
1): VB x1 x2 x3 x4 b
x3 3/2 0 1 -1/2 3/2
x2 1/2 1 0 1/2 5/2
F.O -1/2 0 0 3/2 −Z + 15/2
∃j tal que cj < 0.
■ Passo 2 Teste de optimalidade: há possibilidade de melhorar a F.O? Sim, 
pois
■ Passo 3: A coluna pivô será, obviamente x1;
2 2 2 2
■ Passo 4: Teste da razão mínima - min{ 3 𝚵 3 ; 5 𝚵 1 } = 1. Portanto, x3 sai da
2base (linha pivô). A nova SBV terá sequência {x1, x }.
■ Passo 5: Operações de pivoteamento (eliminação de 
Gauss): VB x1 x2 x3 x4 b
L
′ 
= (2/3)L1
1
L
′ 
= L2 − (1/2)L
′
2 1
x1 
x2
1
0
0
1
2/3
-1/3
-1/3
2/3
1
2
L
′ 
= L3 + (1/2)L
′
3 1 F.O 0 0 1/3 4/3 −Z + 8
■ SBV óptima alcançada: Esta solução é óptima, uma vez que ∀j, cj ≥ 0. O 
valor da função objectivo é 8, pois 0 = −Z + 8.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
Exemplo 2: Usando o método simplex, resolva o seguinte 
PPL: Minimizar Z = −2x1 + x2
Sujeito a :
x1 + x2 ≤ 6 x1 − x2 ≤ 4 x2 ≤ 4
x1, x2 ≥ 0
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
Exemplo 2: Usando o método simplex, resolva o seguinte PPL: Minimizar Z 
= −2x1 + x2
Sujeito a :
x1 + x2 ≤ 6 x1 − x2 ≤ 4 x2 ≤ 4
x1, x2 ≥ 0
■ Escrevendo o PPL na forma padrão:
Minimizar Z = −2x1 + x2 + 0(x3 + x4 + x5) Sujeito a :
x1 + x2 + x3 + 0x4 + 0x5 = 6 x1 − x2 + 0x3 + x4 + 0x5 = 4 0x1 + x2 + 0x3 + 0x4 +
x5 = 4
x1, x2, x3, x4, x5 ≥ 0
Observe que o PPL na forma padrão já está na forma canónica, ou seja, já
temos SBV incial.
Investigação Operacional
O PROCEDIMENTO DO SIMPLEX
Iterações do algoritmo simplex para o PPL do Exemplo 2 :
VB x1 x2 x3 x4 x5 b
x3 1 1 1 0 0 6
x4 1 -1 0 1 0 4
x5 0 1 0 0 1 4
F0 -2 1 0 0 0 Z
x3 0 2 1 -1 0 2
x1 1 -1 0 1 0 4
x5 0 1 0 0 1 4
FO 0 -1 0 2 0 Z + 8
x2 0 1 1/2 -1/2 0 1
x1 1 0 1/2 1/2 0 5
x5 0 0 -1/2 1/2 1 3
FO 0 0 1/2 3/2 0 Z + 9
Solução óptima: x ∗ = (5, 1, 0, 0, 3); Zm∗ ax = −9 
u.m.
Investigação Operacional
CASOS ESPECIAIS DO MÉTODO SIMPLEX
Situações que podem surgir na utilização do método simplex:
■ Empate para a variável não básica que entra
Quando duas ou mais variáveis não-básicas estão empatadas por terem o
mesmo coeficiente “mais negativo” na função objetivo, a escolha da
variável que entra na base é feita de forma arbitrária.
■ Empate para a variável básica que sai (Degeneração)
Quando duas ou mais variáveis básicas são candidatas a variável que sai da
base, isto é, quando ocorre empate na razão mínima, a escolha também é
arbitrária. Quando isto acontece,
➜ no mínimo uma variável básica (aquela não escolhida para sair da base)
terá um valor zero na nova SBV, e diz-se que a nova SBV é degenerada;
➜ O PPL tem, no mínimo, uma restrição redundante (há superdeterminação
de pontos extremos).
Investigação Operacional
CASOS ESPECIAIS DO MÉTODO SIMPLEX
Exemplo:
-1 1 2 3 4
1
2
5
x-axis
Maximizar Z = 3x1 + 9x2
s
x1 + 4x2 ≤ 8
.a x1 + 2x2 ≤ 4
x1, x2 ≥ 0.
y-axis 
3
Investigação Operacional
CASOS ESPECIAIS: DEGENERAÇÃO
TABELA SBV
INICIAL
VB x1 x2 x3 x4 b
x3 
x4
1
1
4
2
1
0
0
1
8
4
F.O -3 -9⇑ 0 0 −Z
L
′
1
L
′
2
= (1/4)L1
= L2 − 2L
′
1
x2 1/4 1 1/4 0 2
x4 1/2 0 -1/2 1 0
L
′
3
= L3 + 9L
′
1 F.O -3/4⇑ 0 9/4 0 −Z + 18
L
′
1
L
′
2
= L1 − (1/4)L
′
2
= 2L2
x2 0 1 1/2 -1/2 2
x1 1 0 -1 2 0
L
′
3
= L3 + (3/4)L
′
2 F.O 0 0 3/2 3/2 −Z + 18
A solução óptima do problema é x ∗ = [0, 2, 0, 0], com Z ∗ = 18.
■ O empate no critério que determina a variável que sai (na tabela inicial), 
leva à degeneração na primeira iteração (x4 = 0);
■ Na solução gráfica, observa-se que três rectas passam pelo vértice óptimo 
(x1 = 0, x2 = 2).
Investigação OperacionalCASOS ESPECIAIS DO MÉTODO SIMPLEX
■ Solução ilimitada (PPL ilimitado): ocorre quando a solução do PPL pode ser
melhorada indefinidamente sem violar nenhuma das restrições. Suponha o
seguinte PPL:
Maximizar Z = x1 + 3x2
s.a. 1 − 3x2 ≤ 3
x1, x2 ≥ 0
x
−2x1 + x2 ≤ 2 R1
R2 R3
Investigação Operacional
CASOS ESPECIAIS: PPL ILIMITADO
Na forma tabular tem-se:
VB x1 x2 x3 x4 b
x3 -2 1 1 0 2
x4 1 -3 0 1 3
F.O -1 -3 0 0 −Z
2/1 = 2
3/(−3) = -1
x2 é a variável que
entrará na base, e
por conseguinte, x1
continuará sendo não
básica (x1 = 0). Para
escolha da variável
que sai da base,
entre x3 e x4,
observa-se o
seguinte:
−2x1 + x2 + x3 = 2 → x3 
= 2 − x2 ≥ 0 → x2 ≤ 1
x1 − 3x2 + x4 = 3 → x4 
= 3 + 3x ≥ 0 → x ≥ 
Investigação Operacional
CASOS ESPECIAIS: PPL ILIMITADO
Desta forma, a partir da SBV inicial:
VB x1 x2 x3 x4 b
x3 -2 1 1 0 2
x4 1 -3 0 1 3
F.O -1 -3⇑ 0 0 −Z
Obtem-se a nova sequência {2,4}
Operações VB x1 x2 x3 x4 b
L
′ 
= L1
1
L
′ 
= L2 + 3L
′
2
1
x2 -2 1 1 0 2
x4 -5 0 3 1 9
L
′ 
= L3 + 3L
′
3
1
F.O -7⇑ 0 3 0 −Z + 6
■ Como o coeficiente de x1 na linha da F.O. é negativo, então há 
possibilidade de melhorar a SBV.
■ No entanto, nenhuma das restrições impõe limites ao crescimento de x1
(coeficientes da coluna pivô negativos);
■ Nenhuma variável básica pode sair da base; O PPL é ilimitado.
Investigação Operacional
CASOS ESPECIAIS DO MÉTODO SIMPLEX
■ Infinitas (Múltiplas) soluções óptimas: Quando a F.O. tem uma direcção
paralela a uma das restrições e seu valor óptimo se encontra exatamente
sobre a recta dessa restrição.
Exemeplo : Minimizar Z = −2x1 − 4x2
s
x1 + 2x2 ≤ 4 R1
.a.
x
−x1 + x2 ≤ 1 R2
1, x2 ≥ 0 R3
Investigação Operacional
CASO DE MÚLTIPLAS SOLUÇÕES ÓPTIMAS
Resolução do PPL usando a tabela simplex:
VB x1 x2 x3 x4 b
x3 1 2 1 0 4
x4 -1 1 0 1 1
F.O -2 -4⇑ 0 0 Z
Usando operações elementares de Gauss, obtem-se:
Operações VB x1 x2 x3 x4 b
L
′
1 = L1 − 2L
′
2 x3 3 0 1 -2 2
L
′
2 = L2 x2 -1 1 0 1 1
L
′
3
= L3 + 3L
′
1 F.O -6⇑ 0 0 4 Z + 4
L
′
1
L
′
2
= (1/3)L1 x1 1 0 1/3 -2/3 2/3
= L2 + L
′
1 x2 0 1 1/3 1/3 5/3
L
′
3
= L3 + 6L
′
1 F.O 0 0 2 0 Z + 8
■ A SBV actual é óptima, x = (2/3, 5/3, 0, 0), Z = −8.
■ Note que, o coeficiente de x4 (não básica) na linha de F.O. é zero; Isto 
significa que existe uma solução óptima alternativa.
Investigação Operacional
CASO DE MÚLTIPLAS SOLUÇÕES ÓPTIMAS
■ Para verificar qual é essa solução, força-se a entrada de x4 na 
base. VB
x1 x2 x3 x4 b
x1
x2
1
0
0
1
1/3
1/3
-2/3
1/3
2/3
5/3
F.O 0 0 2 0⇑ Z + 8
L
′ 
= L1 + (2/3)L
′
1 2
L
′ 
= 3L2
2
x1 
x4
1
0
2
3
1
1
0
1
4
5
L
′ 
= L3
3 F.O 0 0 2 0 Z + 8
■ O método simplex determina apenas os dois pontos extremos:
xA = [2/3, 5/3, 0, 0] e xB = [4, 0, 0, 5];
■ Todas as outras soluções óptimas são obtidas como uma combinação linear 
convexa dessas duas SBV óptimas: x ∗ = αxA + (1 − α)xB, 0 ≤ α ≤ 1.
■ Quando α = 0 ⇒ x ∗ = xB . Se α = 1 ⇒ x ∗ = xA.
■ Para valores de α entre 0 e 1, x ∗ está entre os pontos de xA e xB .
Investigação Operacional
SÍNTESE DO ALGORITMO SIMPLEX
Considere um PPL escrito na forma canônica.
■ Passo 1: Determine uma tabela simplex inicial.
■ Passo 2: Aplique o teste de optimalidade: Se todos os coeficientes da
função objectivo (última linha) forem não negativos (≥ 0), então pare, a
SBV actual é óptima; Caso contrário, vá para o Passo 3.
■ Passo 3: Encontre a variável que entra na base (coluna pivô), selecionando
a variável não básica com coeficiente mais positivo da função objetivo. Se
houver empate na escolha da coluna pivô, a decisão é arbitrária;
Investigação Operacional
SÍNTESE DO ALGORITMO SIMPLEX
■ Passo 4: Aplique o teste da razão mínima para encontrar a variável básica
que sai na base (linha pivô). Escolha a linha com menor razão entre o
lado direito das equações, bj , e o coeficiente da coluna pivô que seja
estritamente positivo (> 0). Se houver empate, a escolha é arbitrária. Se
todos os coeficientes da coluna pivô forem negativos, então pare, o PPL
não tem uma solução óptima, mas sim uma solução ilimitada.
■ Passo 5: Obtenha uma nova tabela simplex (O PPL deverá estar na forma
canônica com nova SBV) usando operações elementares em linha. Então,
retorne ao Passo 2.
Investigação Operacional
FLUXOGRAMA PARA O ALGORITMO SIMPLEX
Não
Sim
Não
Sim
Determine uma tabela 
inicial
coeficiente 
negativo na
linha da 
F.O?
O PPL não 
tem solução 
óptima finita
PARE
Obtenha a coluna pivô
coeficiente 
positivo na 
coluna pivô?
A solução 
actual é 
óptima
PARE
Obtenha a linha pivô
Obtenha uma nova 
tabela aplicando o 
pivoteamento
Investigação Operacional
FIM!