simplex

Prévia do material em texto

Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 1
Método Simplex
Prof. DSc. George Dantzig
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 2
Vimos que o modelo de programação linear reduz um 
sistema real a um conjunto de equações (ou 
inequações) onde pretendemos otimizar uma funfunçção ão 
objetivoobjetivo.
Como fazemos para resolver este problema ?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 3
Veremos, um método capaz de realizar tal 
resolução:
O SimplexSimplex !!!!!
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 4
x1
x2
x1
x2
Sabemos que a solução ótima (desde de que exista) será encontrada 
num ponto extremo do conjunto das soluções viáveis.
Solução Exata para os Modelos de PL
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 5
Dificuldades:
� O número de pontos extremos (vértices) é, em geral, 
exponencialmente proporcional ao número de variáveis.
Solução Exata para os Modelos de PL
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 6
Dificuldades:
� Para resolver um sistema indeterminado de equaequaçções ões 
lineares lineares (PPL na forma padrão), devemos:
� Obter soluções básicas viáveis para o sistema.
� Evitar o teste de todas as soluções básicas 
viáveis para garantir a otimização do sistema.
Solução Exata para os Modelos de PL
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 7
Solução:
� Usar o algoritmo simplexsimplex que é...
� Extremamente eficiente para a resolução do 
sistema
� Adaptável ao cálculo computacional
Solução Exata para os Modelos de PL
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 8
Algoritmo SimplexAlgoritmo Simplex
Este algoritmo foi uma das grandes 
contribuições à Programação Matemática 
ocorrida no século XX.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 9
O SimplexSimplex é:
� Um algoritmo que emprega ferramental da Álgebra Linear
� Método iterativo
� Eficiente
Fundamentos Teóricos do SimplexSimplex
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 10
A concepção geral do SimplexSimplex é a seguinte:
� Iniciar numa solução básica viável do sistemas de equações 
formado pelas restrições do PPL
� Identificar novas soluções viáveis melhores ou iguais à
corrente
� Identificar se uma dada solução viável é, ou não, um 
vértice ótimo
Fundamentos Teóricos do SimplexSimplex
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 11
n
Otimizar [Max/Min] Q(X) = Σ cj.xjj=1
sujeito a
n
Σ aij . xj ≥ di i = 1, 2, ..., mj=1
xj ≥ 0 j = 1, 2, ..., n
M = {1, 2, ... , m }, o conjunto dos índices das restrições
N = {1, 2, ..., n }, conjunto dos índices das variáveis
Formulação Algébrica Geral
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 12
– Forma Canônica
– Forma Padrão
– Forma Matricial
Formulações Equivalentes
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 13
PadrãoPadrão
CanônicaCanônica
MatricialMatricial
Todas as formulações são 
equivalentes !
Formulações Equivalentes
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 14
Otimizar [MIN] Q(X) = C.X
sujeito a
A . X = B, B ≥≥≥≥ 0
X ≥≥≥≥ 0
Forma Padrão
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 15
Qualquer PPL pode ser escrito numa das formas anteriores por meio das 
seguintes operações:
�� OperaOperaçção 1ão 1: Mudança de critério de otimização
Maximizar 
Q(X)
Minimizar 
-Q(X)
Minimizar
Q(X)
Maximizar 
-Q(X)
Operações Elementares
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 16
�� OperaOperaçção 2ão 2: Transformação de termo independente 
negativo bi ≤≤ 00
Basta multiplicar toda a restrição por –1.
Operações Elementares
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 17
�� OperaOperaçção 3ão 3: Transformação de desigualdades em 
igualdades (e vice-versa)
x1 + x2 + ... + xn ≤≤ b (inequação original)
x1 + x2 + ... + xn + xn+1 = b
Variável de folga
Operações Elementares
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 18
�� OperaOperaçção 4ão 4: Transformação de desigualdades em 
igualdades (e vice-versa)
x1 + x2 + ... + xn ≥≥ b (inequação original)
x1 + x2 + ... + xn - xn+1 = b
Variável de excesso
Operações Elementares
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 19
�� OperaOperaçção 5ão 5: Transformação de uma variável livre em 
variável não-negativa, ou seja, uma variável é substituída 
por duas variáveis auxiliares, ambas positivas
xn = xn
´´
– xn
´
Xn´´ ≥ 0 , xn´ ≥ 0
Operações Elementares
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 20
�� OperaOperaçção 6ão 6: Transformação de uma variável negativa em 
variável não-negativa, ou seja, uma variável é substituída 
por uma auxiliar, positiva
xn = – xn
´
xn
´ ≥ 0
Operações Elementares
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 21
Min Q(X) = 2x1 + 5x2
sujeito a 
-x1 - 2x2 ≤ -18
x1 + x2 ≥ 6
x1 , x2 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 22
Min Q(X) = 2x1 + 5x2
sujeito a 
-x1 - 2x2 ≤≤≤≤ -18
x1 + x2 ≥≥≥≥ 6
x1 , x2 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 23
� Multiplicar a restrição -x1 - 2x2 ≤ -18 por (-1) 
x1 + 2x2 ≥ 18
� Adicionar uma variável de excesso, x3:
x1 + 2x2 - x3 = 18; x3 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 24
� Introduzir uma variável de excesso em x1 + x2 ≥ 6
x1 + x2 – x4 = 6 x4 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 25
Min Q(X) = 2x1 + 5x2 (Forma Padrão Forma Padrão -- MinMin)
sujeito a 
x1 + 2x2 - x3 = 18 
x1 + x2 – x4 = 6 
x1 , x2 , x3 , x4 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 26
Max Q(X) = -2x1 - 5x2 (Forma Padrão Forma Padrão -- MaxMax)
sujeito a 
x1 + 2x2 - x3 = 18 
x1 + x2 – x4 = 6 
x1 , x2 , x3 , x4 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 27
Obtenha a forma padrão associada:
Max Q(X) = x1 + 2x2 - 3x3
sujeito a 
2x1 + 3x2 - x3 = 6
3x1 - x2 + 2x3 ≤ 9
- x1 + x2 - 2x3 ≥ -3
x1 ≤ 0 , x2 ≥ 0
Exercício
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 28
MIN Q(X) = C.X
s. a
A . X = B
X ≥ 0
Onde:
A é a matriz dos coeficientes das variáveis nas restrições
X é a matriz das variáveis (coluna)
C é a matriz dos coeficientes das variáveis na FO (linha)
B é a matriz dos termos independentes
Forma Matricial
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 29
Escreva a forma padrão abaixo na notação matricial.
Min Q(X) = 2x1 + 5x2
s. a 
x1 + 2x2 - x3 = 18 
x1 + x2 – x4 = 6 
x1 , x2 , x3 , x4 ≥ 0
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 30
MIN Q(X) = C.X
s. a
A . X = B
X ≥ 0
Onde:
Exemplo 1
[ ]0052=C












=
4
3
2
1
x
x
x
x
X 





−
−
=
1011
0121
A 





=
6
18
B
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 31
Exemplo 1
[ ]0052=C












=
4
3
2
1
x
x
x
x
X
41 x
C
14 x
X [ ] 11 x=
21
52 xx +=
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 32
Exemplo 1












=
4
3
2
1
x
x
x
x
X






−
−
=
1011
0121
A 





==
6
18
B
14 x
X
42 x
A 12 xB[ ] == 12 x






=−++
=+−+
=
60
1802
4321
4321
xxxx
xxxx
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 33
Exercício
Escreva a forma matricial associada a forma padrão obtida no 
exercício anterior.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 34
Método Simplex
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 35
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = 5x1 + 3x2
s.a
3x1 + 5x2 ≤≤≤≤ 15
5x1 + 2x2 ≤≤≤≤ 10
xi ≥≥≥≥ 0, i = 1,2
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 36
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
A B 
C 
D 
A (0,0) 
B (2,0) 
C (20/19,45/19) 
D (0,3) 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 37
Max Q´(X) = -5x1 -3x2
s.a
3x1 + 5x2 + x3 =15
5x1 + 2x2 + x4 = 10
xi ≥≥≥≥ 0, i = 1,2,3,4
1) Obter Forma Padrão
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 38
2) Colocar o PPL no Quadro Simplex
Q´(X)00-3-5
101025
150153
x4x3x2x1
Variáveis
Restrições
FO
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 39
Q´(X)00-3-5
101025x4
150153x3
x4x3x2x1VB
3) Determinar as variáveis básicas e uma solução 
básica viável inicial
Básicas
Variáveis básicas são aquelas cujas colunas têm 1 numa 
posição e 0 nas demais.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 40
No Simplex as Variáveis Não Básicas (VNB) sempre valem 0: 
x1 = 0; x2 = 0
Logo, as Variáveis Básicas (VB) valem: x3 = 15; x4 = 10
Corresponde ao vértice A (0,0,15,10).
Valor da função objetivo (F.O.) nesta base: 
Q(X) = -5x1 -3x2 + 0.x3 + 0.x4 = -5 . 0 -3 . 0 + 0 . 15 + 0 . 10 = 0
3) Determinar as variáveis básicas e uma solução 
básica viável inicial
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 41
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
A 
A (0,0) 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 42
Q´(X)00-3-5
101025x4
150153x3
x4x3x2x1VB
4) Essa solução é ótima?
Este quadro não é ótimo pois existem variáveis com 
coeficientes negativos na linha da FO.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 43
Fazendo uma mudança de base.
Para isso precisamos definir quem entra e quem sai da base.
5) Como encontrar um novo vértice?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 44
Qual, entre as variáveis não básicas, deve entrar para a base ?
Resposta: 
Deve entrar para a base a variável que possuir o COEFICIENTE 
MAIS NEGATIVO na linha da FO. 
Se duas ou mais variáveis têm o mesmo coeficiente negativo, você 
pode escolher qualquer uma delas.
5.1) Quem Entra?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 45
Resposta (continuação): 
Se todas as variáveis tiverem coeficientes positivos então 
atingimos o ponto de ÓTIMO da função objetivo e, 
conseqüentemente, o processo do Método Simplex chegou ao seu 
final. 
Os valores assumidos pelas variáveis são os que corresponderão 
ao ótimo da F.O. 
5.1) Quem Entra?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 46
Q´(X)00-3-5
101025x4
150153x3
x4x3x2x1VB
X1 entra na base pois é a que tem o coeficiente mais negativo 
na linha da FO.
5.1) Quem entra na base?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 47
5.2) Quem sai da base?
Resposta: 
Deve sair da base a variável cujo coeficiente RHS (termo 
independente), em relação à variável que está entrando para a 
base, for MÍNIMO.
O coeficiente RHS somente pode ser calculado se o mesmo for 
resultar em número positivo pois caso contrário teremos uma 
inconsistência ou seja uma variável assumindo um valor 
negativo.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 48
Q´(X)00-3-5
101025x4
150153x3
x4x3x2x1VB
x3 x4
Min {15/3,10/5} = 10/5, logo x4 sai da base
5.2) Quem sai da base?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 49
Denominamos de pivô ao elemento que se encontra na interseção 
entre a linha da variável que irá sair da base e a coluna da 
variável que deverá entrar para a base ou ao denominador do 
menor quociente. Na linha do pivô temos a variável que deixa a 
base.
Assim temos que...
5.3) Determinando o elemento pivô da base atual
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 50
Q´(X)00-3-5
10102x4
150153x3
x4x3x2x1VB
5.3) Determinando o elemento pivô da base atual
Elemento pivô
5
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 51
Q´(X)00-3-5
101025x4
150153x3
x4x3x2x1VB
5.4) Realizando o pivoteamento da base atual
Como X1 entra na base no lugar de X4, X1 deve passar a fazer o papel que 
era de X4. Portanto a coluna de X1 deve se transformar na coluna de X4. 
Logo no lugar do pivô deve aparecer 1 e nas demais posições 0. Para 
efetuarmaos a mudança de base devemos fazer operações elementares.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 52
Operações Elementares
Linha do Pivô:
Lpivô←←←← 1 / pivô * Lpivô;
Demais Linhas:
Lj←←←← Lj – (elemento que queremos zerar na linha) / pivô * Lpivô;
5.4) Realizando o pivoteamento da base atual
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 53
Q´(X)00-3-5
10102x4
150153x3
x4x3x2x1VB
5.4) Realizando o pivoteamento da base atual
5
Operações Elementares: L2← 1/5 L2; L1← L1 - 3/5 L2; 
L3← L3 – (-5)/5 L2
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 54
Q´(X)+1010-10
21/502/51x1
9-3/510x3
x4x3x2x1VB
5.4) Realizando o pivoteamento da base atual
(2,0,9,0) – Não é ótimo! Corresponde ao Vértice B.
Operações Elementares: L1← 1/(19/5) L1; 
L2← L2 – (2/5)/(19/5) L1; L3← L3 – (-1)/(19/5) L1
19/5
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 55
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
A B 
A (0,0) 
B (2,0) 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 56
Q´(X) +
235/19
16/195/1900
20/195/19-2/1901x1
45/19-3/195/1910x2
x4x3x2x1VB
Quadro Ótimo – Solução Única!
(20/19,45/19,0,0) – Ótimo! Corresponde ao vértice C.
Q´(X*) = -235/19 ∴∴∴∴ Q(X*) = 235/19
(não existem mais variáveis com coeficientes negativos na FO)
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 57
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
B 
C 
B (2,0) 
C (20/19,45/19) 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 58
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
B 
C 
A 
A (0,0) 
B (2,0) 
C (20/19,45/19) 
 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 59
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
B 
C 
A 
A (0,0) 
B (2,0) 
C (20/19,45/19) 
 ÓTIMO! 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 60
Visualizando Graficamente
 
 
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
X1
X2 
Região 
 Viável 
B 
C 
A 
A (0,0) 
B (2,0) 
C (20/19,45/19) 
 ÓTIMO! 
D 
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 61
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = 6x1 + 10x2
s.a
3x1 + 5x2 ≤≤≤≤ 15
5x1 + 2x2 ≤≤≤≤ 10
xi ≥≥≥≥ 0, i = 1,2
Exemplo 2
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 62
Q´(X) +300200
41-2/5019/5x4
301/513/5x2
x4x3x2x1VB
Quadro Ótimo – Infinitas Soluções!
(0,3,0,4) – Ótimo! Q´(X*) = -30 ∴∴∴∴ Q(X*) = 30
(como existe uma VNB com coeficiente nulo na FO, o PPL tem 
INFINITAS SOLUÇÕES)
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 63
Q´(X) +300200
20/195/19-2/1901x1
45/19-3/195/1910x2
x4x3x2x1VB
(20/19,45/19,0,0) – Ótimo! Q´(X*) = -30 ∴∴∴∴ Q(X*) = 30
Quadro Ótimo – Infinitas Soluções!
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 64
Como expressar as infinitas soluções ótimas?
Fazendo uma combinação linear convexa entre os dois 
vértices ótimos encontrados.
30*)(
}1,0;1;0,0,
19
45
,
19
29)4,0,3,0(),,,{(
4321
=
≤≤=+




+==
XQ
xxxxS βαβαβα
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 65
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = 2x1 + 2x2
s.a
x1 - x2 ≥≥≥≥ -1
-1/2 x1 + x2 ≤≤≤≤ 2
xi ≥≥≥≥ 0, i = 1,2
Exemplo 3
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 66
Q´(X) +
10
8-600
22-201x1
32-110x2
x4x3x2x1VB
Quadro Simplex – Solução Ilimitada!
Como todos os candidatos a pivô são negativos, concluímos que 
o PPL tem solução ilimitada. Pois a FO pode decrescer 
indefinidamente.
?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 67
Utilizado quando não temos uma solução básica viável 
inicial.
Para cada restriçãoi do tipo = introduzimos uma variável 
artificial positiva xia.
Para cada restrição i do tipo ≥ introduzimos, além da variável 
de folga, uma variável artificial positiva acompanhada de 
coeficiente positivo xia.
Método Simplex das Duas Fases
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 68
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = 6x1 - x2
s.a
4x1 + x2 ≤ 21
2x1 + 3x2 ≥ 13
x1 - x2 = -1
xi ≥≥≥≥ 0, i = 1,2
Exemplo 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 69
Max Q(X) = 6x1 - x2
s.a
4x1 + x2 ≤ 21
2x1 + 3x2 ≥ 13
x1 - x2 = -1
xi ≥≥≥≥ 0, i = 1,2
Forma Padrão
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 70
Min Q´(X) = -6x1 + x2
s.a
4x1 + x2 + x3 = 21
2x1 + 3x2 – x4 = 13
-x1 + x2 = 1
xi ≥≥≥≥ 0, i = 1,2,3,4
Forma Padrão
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 71
1001-1
Q´(X)001-6
13-1032
210114x3
x4x3x2x1VB
Quadro Simplex
Não conseguimos identificar uma base inicial!
?
?
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 72
Min Q´(X) = -6x1 + x2
s.a
4x1 + x2 + x3 = 21
2x1 + 3x2 – x4 + x1a = 13
-x1 + x2 + x2a = 1
x1,x2,x3,x4,x1
a
,x2
a ≥≥≥≥ 0
Inclusão das Artificiais
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 73
0
0
1
0
x1
a
0
1
0
0
x2
a
1001-1x2a
Q´(X)001-6
13-1032x1a
210114x3
x4x3x2x1VB
Quadro Simplex
Qa(X) = Σxia
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 74
Qa(X)110000
0
0
1
0
x1
a
0
1
0
0
x2
a
1001-1x2a
Q´(X)001-6
13-1032x1a
210114x3
x4x3x2x1VB
Quadro Simplex -1a FASE
O objetivo da 1a FASE é minimizar Qa(X). Ao acrescentarmos a 
linha de Qa(X) perdemos a base canônica.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 75
Qa(X)110000
0
0
1
0
x1
a
0
1
0
0
x2
a
1001-1x2a
Q´(X)001-6
13-1032x1a
210114x3
x4x3x2x1VB
Quadro Simplex -1a FASE
Para recuperarmos a base canônica devemos fazer a seguinte 
operação elementar: a linha da FO Artificial recebe ela mesma 
menos as linhas onde aparecem artificiais na base.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 76
Qa(X)110000
0
0
1
0
x1
a
0
1
0
0
x2
a
1001-1x2a
Q´(X)001-6
13-1032x1a
210114x3
x4x3x2x1VB
Quadro Simplex -1a FASE
L5← L5 – L2 – L3
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 77
Qa(X)-140010-4-1
0
0
1
0
x1
a
0
1
0
0
x2
a
1001-1x2a
Q´(X)001-6
13-1032x1a
210114x3
x4x3x2x1VB
Quadro Simplex -1a FASE
Recuperamos a base canônica. Agora podemos dar início a 1a
FASE do método.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 78
Qa(X)-140010-4-1
0
0
1
0
x1
a
0
1
0
0
x2
a
100-1x2a
Q´(X)001-6
13-1032x1a
210114x3
x4x3x2x1VB
Quadro Simplex -1a FASE
1
L1← L1 – L3; L2← L2 – 3L3; L4← L4 – L3; L5← L5 – (-4)L3
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 79
Qa(X)-1040100-5
0
0
1
0
x1
a
-1
1
-3
-1
x2
a
1001-1x2
Q´(X)-1000-5
10-100x1a
200105x3
x4x3x2x1VB
Quadro Simplex -1a FASE
5
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 80
Qa(X)110000
1
1/5
1/5
-1
x1
a
-4
2/5
-3/5
2
x2
a
1-1/5010x2
Q´(X)+9-1000
10-1/5001x1
201100x3
x4x3x2x1VB
Quadro Simplex -1a FASE
Quadro Ótimo!
X1a = x2a = 0 ; Qa(X*)=0
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 81
Qa(X)110000
1
1/5
1/5
-1
x1
a
-4
2/5
-3/5
2
x2
a
1-1/5010x2
Q´(X)+9-1000
10-1/5001x1
201100x3
x4x3x2x1VB
Quadro Simplex -1a FASE
Como as variáveis artificiais se anularam e elas não tem qualquer 
significado real, podemos eliminar do quadro simplex as colunas 
das variáveis artificiais e a linha da FO Artificial.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 82
1-1/5010x2
Q´(X)+9-1000
10-1/5001x1
20100x3
x4x3x2x1VB
Quadro Simplex -2a FASE
O Objetivo da 2a FASE é minimizar a FO Original.
1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 83
501/510x2
Q´(X)+190100
401/501x1
101100x4
x4x3x2x1VB
Quadro Simplex -2a FASE
(4,5,0,10) ; Q´(X*) = -19 ∴ Q(X*) = 19
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 84
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = x1 + x2
s.a
x1 + 4x2 ≥ 4
3x1 + x2 = 1
xi ≥≥≥≥ 0, i = 1,2
Exemplo 2
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 85
Qa(X)501011
0
0
1
x1
a
1
1
-4
x2
a
1013x2
Q´(X)+1002
0-10-11x1a
x3x2x1VB
Quadro Simplex – Fim da 1a FASE
Quadro Ótimo! x1a = x2a = 0 ; Qa(X*)=0
Porém x1a permanece na base. Para excluir a coluna de x1a, 
primeiro devemos retirá-la da base.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 86
Qa(X)501011
0
0
1
x1
a
1
1
-4
x2
a
1013x2
Q´(X)+1002
0-10-11x1a
x3x2x1VB
Quadro Simplex – Fim da 1a FASE
No entanto a coluna de x2a e alinha de Qa(X) podem ser excluídas
do quadro simplex.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 87
0
0
1
x1
a
1013x2
Q´(X)+1002
0-10-11x1a
x3x2x1VB
Quadro Simplex – Candidatos a Pivô
Esse é o único momento do simplex em que podemos escolher um
candidato a pivô negativo. Observe que o termo independente 
associado a x1a vale 0.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 88
0
0
1
x1
a
1013x2
Q´(X)+1002
00-11x1a
x3x2x1VB
Quadro Simplex – Retirada de Artificial da 
BASE
-1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 89
0
0
-1
x1
a
1013x2
Q´(X)+1002
01011x3
x3x2x1VB
Quadro Simplex – Retirada de Artificial da 
BASE
Agora podemos excluir a coluna de x1a.
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 90
1013x2
Q´(X)+1002
01011x3
x3x2x1VB
Quadro Simplex – 2a Fase
Quadro Ótimo!
(0,1,0) Q´(X*) = -1∴ Q(X*) = 1
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 91
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = x1 + x2
s.a
2x1 + 3x2 = 5
-6x1 - 9x2 = -15
-x1 + x2 ≤ 0
xi ≥≥≥≥ 0, i = 1,2
Exemplo 3
Pesquisa Operacional 
Prof. Luciano Lessa Lorenzoni 92
Resolva o seguinte PPL por meio do emprego do Método Simplex:
Max Q(X) = x1 + 3x2
s.a
- x1 - x2 ≥ 1
xi ≥≥≥≥ 0, i = 1,2
Exemplo 4