PUC-Rio Pesquisa Operacional - PO B Met Gr e Sp 2013.2

Prévia do material em texto

Pesquisa Operacional. 
 Método Gráfico. 
 Método Simplex. 
9 
PO - PESQUISA OPERACIONAL Profa. Léa Benatti 
 Continuação 
 
CONSTRUÇÃO DE MODELOS: 
Discriminar as variáveis do problema: X1, ..., Xn; 
Definir a função objetivo; 
Definir as restrições do problema; 
Marcar restrições de não-negatividade. 
 
Para determinar as variáveis de decisão e o valor da função objetivo: 
 Método Gráfico; 
 Método Simplex; 
 Uso do Excel: SOLVER (ou outros programas computador). 
 
2.3 – Método Gráfico para Resolução de Modelos de Programação Linear 
 
Método Gráfico: Técnica de solução para modelos de programação linear 
com duas variáveis de decisão (2D). 
 
 
Consiste em representar num sistema de eixos ortogonais o 
conjunto das possíveis soluções do problema: pontos (X1, X2). 
 
Conjunto de pontos (X1, X2): obedecem ao grupo de restrições impostas 
pelo sistema em análise. 
 
Representação gráfica de equação Linear com 2 variáveis: Reta. 
 
Representação gráfica de inequação Linear com 2 variáveis: um dos 
semiplanos definidos pela reta correspondente a equação. 
 
OBS.: Duas variáveis de decisão: não causam poluição visual (2D). 
Três variáveis de decisão: sistema tridimensional (3D). 
 
Problemas com muitas variáveis de decisão: uso de computadores. 
 
 
 
 
 10
Exemplo 1: (Método Gráfico) (P. O. – Medeiros Silva – pg. 28) 
Resolver graficamente o problema de programação linear: 
 
 Minimizar Z = 2X1 + 3X2 
 
Sujeito as X1 + X2 ≥ 5 
restrições: 5X1 + X2 ≥ 10 
 X1 ≤ 8 
 X1, X2 ≥ 0 restrição de não negatividade 
 
Solução: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Solução Ótima: encontra-se em um dos pontos extremos (vértices). 
 
* Qualquer ponto dentro da área permissível satisfaz as restrições 
 
1a restrição: X1 + X2 = 5 X1 = 0, X2 = 5 
 X2 = 0, X1 = 5 
 
2a restrição: 5X1 + X2 = 10 X1 = 0, X2 = 10 
 X2 = 0, X1 = 2 
 
3a restrição: X1 = 8 
 
4a e 5a restrições: não negatividade – solução no 1º quadrante do gráfico. 
10 
5 
5 10 2 8 
1a 
3a 
X1 = 8 
2a 
 
D 
A B 
C 
ZONA 
PERMISSÍVEL 
X1 
X2 
X1+X2=5 
5X1+X2=10 
A, B, C, D: 
Pontos extremos da 
zona permissível. 
 
X1, X2: variáveis 
de decisão. 
 11
Coordenadas dos pontos extremos: 
A = (8, 0) 
B = (5, 0) 
C = ? interseção das retas limites das 1a e 2a restrições. 
D = (0, 10) 
 
Coordenada de C: 
 X1 + X2 = 5 x (5) 
 5X1 + X2 = 10 
 
 5X1 + 5X2 = 25 
 5X1 + X2 = 10 
 
 
 
 
C = (1,25; 3,75) 
 
Substituindo coordenadas dos pontos na função objetivo: 
 
Ponto X1 X2 
F. objetivo: Z = 2X1+3X2 
 (minimizar) 
A 8 0 16 
B 5 0 10 (Solução ótima) 
C 1,25 3,75 13,75 
D 0 10 30 
 
Solução Ótima: encontra-se no ponto B (X1 = 5, X2 = 0) e Z = 10. 
 (Minimizar: menor valor obtido) 
 
Outra forma de avaliar o valor mínimo: através de retas paralelas com valor 
arbitrário da F. objetivo. 
Arbitrar valores para Z: 
 
 Z = 2X1+3X2 = 12 
 Z = 2X1+3X2 = 18 
 
 
 
Usa-se igualdade, pois estamos no 
limite de mínimo. 
- 
75,3
4
15X 2 ==
25,1
5
)75,310(X 1 =
−
=
 4X2 = 15 
Preferência usar múltiplos de 2 
e 3: facilita o cálculo. 
 12
Se Z = 12: Z = 2X1+3X2 = 12 
 
 
Se Z = 18: Z = 2X1+3X2 = 18 
 
 
No gráfico já traçado: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exemplo 2: (Método Gráfico) (P. O. – Medeiros Silva – pg. 29) 
Resolver o problema de programação linear: 
 
 Maximizar L = 2X1 + 3X2 
 
Sujeito as 4X1 + 6X2 ≤ 60 
restrições: X1 + X2 ≥ 12 
 X1, X2 ≥ 0 restrição de não negatividade 
 
 
 
X1 = 0, X2 = 4 
X2 = 0, X1 = 6 
 
X1 = 0, X2 = 6 
X2 = 0, X1 = 9 
 
10 
5 
5 10 2 8 
1a 
3a 
X1 = 8 
2a 
 
D 
A B 
C 
ZONA 
PERMISSÍVEL 
X1 
X2 
Minimizar Z: cada vez 
mais próximo da origem. 
 
Zmin: pto B (5, 0) 
Zmin = 2 (5) + 3 (0) = 10 
 (Solução Ótima) 
9 6 
4 
6 
Z = 12 
Z = 18 
Zmin 
Zmin: última reta que toca 
a área permissível. 
 13
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1a rest.: 4X1 + 6X2 = 60 X1 = 0, X2 = 10 
 X2 = 0, X1 = 15 
 
2a rest.: X1 + X2 = 12 X1 = 0, X2 = 12 
 X2 = 0, X1 = 12 
 
3a rest.: condição de não negatividade. 
 
Coordenadas dos pontos: R = (12, 0), Q = (15, 0) 
P = ? interseção das retas limites da 1a e 2a restrições. 
Coordenada do ponto P: 
 4X1 + 6X2 = 60 
 X1 + X2 = 12 x (4) 
 
 4X1 + 6X2 = 60 
 4X1 + 4X2 = 48 
 
 
P = (6, 6) 
 
 
15 
X2 
5 
5 10 
10 
12 
12 
X1 
Zona Permissível 
P 
R Q 
1a 
2a 
X1 + X2 = 12 
4X1 + 6X2 = 60 
Solução Ótima: nos ptos 
extremos da zona permissível. 
- 
6
2
12X 2 ==
6)612(X1 =−=
 2X2 = 12 
 14
Substituindo coordenadas dos pontos na função objetivo: 
 
Ponto X1 X2 F. objetivo: L = 2X1+3X2 (maximizar) 
P 6 6 30 (Solução ótima) 
Q 15 0 30 (Solução ótima) 
R 12 0 24 
 
A solução ótima se encontra nos pontos P e Q: sobre a reta PQ 
(Solução Múltipla). 
(Maximizar: maior valor obtido) 
 
Avaliando valor máximo de L por retas paralelas: 
 
 L = 2X1 + 3X2 = 24 X1 = 0, X2 = 8 
 X2 = 0, X1 = 12 
 
 L = 2X1 + 3X2 = 45 X1 = 0, X2 = 15 
 X2 = 0, X1 = 22,5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Zmax 
15 
X2 
5 
5 10 
10 
12 
12 
X1 
Zona Permissível 
P 
R Q 
1a 
2a 
20 22,5 
15 
8 
 15
Z = 2X1 + 3X2 = 30 X1 = 0, X2 = 10 
 X2 = 0, X1 = 15 
 
 
 
Logo, todos os pontos do segmento PQ são soluções ótimas do modelo 
(solução múltipla). 
 
Exemplo 3: (Método Gráfico) (Puccini – pg. 44) 
Resolver o problema de programação linear: 
 
 Maximizar Z = 5X1 + 2X2 
 
Sujeito as 
restrições: 
 
 
 
 
Solução: 
 
 
 
 
 
 
 
 
 
 
 
 
1a rest.: X1 = 3 
2a rest.: X2 = 4 
3a rest.: X1 + 2X2 = 9 
 
 
Reta PQ 
denegatividanãoderestrição0X,X
9X2X
4X
3X
21
21
2
1
≥
≤+
≤
≤
Colocar no quadro. Deixar para os 
alunos fazerem em casa. 
9X,0X
5,4
2
9X,0X
12
21
==
===
* Qualquer ponto do trapézio ABCDE 
satisfaz todas as restrições. 
 
* Trapézio: é o conjunto de soluções 
permissíveis para este modelo. 
10 
4,5 
4 
3 5 10 9 
2a rest. 
1a rest. 
3a rest. 
Zona Permissível 
B A 
E D 
C 
X1 
X2 
 16
Coordenadas dos pontos: A (0, 0); B (3, 0); E (0,4); 
 
Coordenada de C: X1 + 2X2 = 9 
 X1 = 3 
 C = (3, 3) 
 
 Coordenada de D: X1 + 2X2 = 9 , X1 = 9 – 8 = 1X2 = 4 
 
 D = (1, 4) 
 
Substituindo coordenadas dos pontos na função objetivo: 
 
Ponto X1 X2 
F. objetivo: Z = 5X1+2X2 
 (maximizar) 
A 0 0 0 
B 3 0 15 
C 3 3 21 (Solução ótima) 
D 1 4 13 
E 0 4 8 
 
 
Avaliando valor máximo de Z por retas paralelas: 
 L = 5X1 + 2X2 = 0 X1 = 0, X2 = 0 
 X2 = 0, X1 = 0 
 
 
 
 
 
 
 L = 5X1 + 2X2 = 10 X1 = 0, X2 = 5 
 X2 = 0, X1 = 2 
 
 
 
 
 
 
3
2
39X, 2 =
−
=
Difícil para traçar retas paralelas: 
sugestão do Puccini 
10: é múltiplo de 5 e 
de 2. 
 17
 
 
 
 
 
 
 
 
 
 
 
 
 
EXERCÍCIOS PROPOSTOS: 
P. O. – Medeiros da Silva (Lista 2 – pg. 31). 
 
EXERCÍCIOS: D. M. – Daniel Moreira 
 
EXEMPLOS: Puccini – pg. 52 
EXEMPLOS - Puccini 
• Pg. 50 – ex. Atividades – Const. Modelos. 
• Pg. 52 – ex. Dieta – Const. Modelos. 
• Pg. 54 – ex. Investimentos Const. Modelos 
• Pg. 56 – exercícios propostos – não resolvi; (Resolução na pg. 219) 
 
2.4 – Solução Básica e Solução Básica Possível de um Sistema de 
Equações Lineares 
 
Definição: (Pg. 35 – P. O. – Medeiros) 
 
R: Conjunto dos números reais; 
 
R2: Conjunto dos pares ordenados de nos reais: 
 (3, 5), (6, -2), ... 
 
R3: Conjunto das ternas ordenadas de nos reais: 
 (1, 3, 8), (2, 4, 0), ... 
... 
Rn: Conjunto das n-uplas (ênuplas) ordenadas de nos reais: (X1, X2, ..., Xn) 
onde Xj é um no real qualquer. 
Resolvidos no 
Livro. 
Cada conjunto: 
Espaço Vetorial. 
 
Cada elemento dos 
conjuntos: 
Vetores. 
10 
4,5 
4 
3 5 10 9 
2a rest. 
1a rest. 
3a rest. 
Zona Permissível 
B A 
E D 
C 
X1 
X2 
2 
Zmax: Ponto C 
 X1 = 3, X2 = 3 
 
Zmax = 5 (3) + 2 (3) = 21 
Zmax Z = 10 
 18
 
 
Exemplo: (2, 3): Vetor do R2 (espaço bi-dimensional – dois elementos). 
 
 
Vetor coluna: 3 - Vetor do R2 (espaço bi-dimensional). 
 5 
 
Vetor linha: (2, -1, 0) - Vetor do R3 (espaço tri-dimensional). 
 
 
 
 
 
 
 
a) Combinação Linear de Vetores (Pg. 36 – P. O. – Medeiros) 
 
Dado um grupo de vetores de um espaço, pode-se multiplicar cada um deles 
por um numero qualquer e em seguida somar os resultados. O vetor obtido 
nessa operação é uma combinação linear dos vetores dados. 
 
Ex.: Mostrar que o vetor (11, 18) pode ser escrito como combinação linear 
dos vetores (3, 4) e (1, 2). 
 
Solução: 
 
 
 
 
X (3, 4) + Y (1, 2) = (11, 18) 
 



→=+
−→=+
⇒





=





+





)3(x18Y2X4
)4(x11YX3
18
11
Y
2
1
X
4
3
 
 
-12X – 4Y = - 44 
 12X + 6Y = 54 
 
 2Y = 10 Y = 5 
 X = 2 
OBS.: Vetor no plano: Ponto inicial fixo na origem (0, 0). 
 Ponto final: determina o vetor no plano 
 P(a, b): vetor no plano. 
 
 Livro: Álgebra Linear (pg. 99) 
 Autor: Boldrini / Costa 
 Figueiredo / Wetzler a 
b 
P 
+ 
Substituir na 1a equação 
Nos que definem a combinação linear dos vetores 
dados que resulta o vetor (11, 18). 

Y
X
 19
 
Logo: 2(3, 4) + 5(1, 2) = (11, 18) 
 
O vetor (11, 18) pode ser escrito como combinação linear dos vetores (3, 4) e 
(1, 2), com coeficientes X = 2 e Y = 5. 
 
b) Base de um Espaço Vetorial (Pg. 38 – P. O. – Medeiros) 
 
Base do espaço Rn é um conjunto de n vetores do Rn, linearmente 
independentes. 
 
VETORES LINEARMENTE INDEPENDENTES: 
São vetores que não podem ser escritos como combinação linear de um grupo 
de vetores. 
 
Sabe-se que: 
Base R2: conjunto de 2 vetores de R2, independentes. 
Base R6: conjunto de 6 vetores de R6, independentes. 
 
� A “base de um espaço vetorial” é um “gerador do espaço”, isto é, qualquer 
vetor do espaço pode ser obtido como combinação linear dos vetores da 
base. 
 
� A combinação linear para gerar um vetor a partir da base resulta num 
sistema de equações que tem sempre solução única (qualquer que seja a 
combinação linear a solução é única). 
 
2.4.1 – Solução Básica de um Sistema de Equações Lineares 
 (Pg. 38 – P. O. – Medeiros) 
Observe o sistema linear de equações: 
 
 
 
 
 
Que pode ser escrito na forma: 
 
 
 
 
Colunas: vetores de R2 (base R2: constituída de 2 vetores independentes). 



=+−+
=−++
5K2ZYX2
10KZ4Y3X 2 eq.: R2. 
4 variáveis: X, Y, Z, K. 
4 – 2 = 2 variáveis nulas. 






=




−
+





−
+





+





5
10
K
2
1
Z
1
4
Y
1
3
X
2
1
 20
 
Solução básica: obtida zerando-se 2 variáveis, isto é, reduz o sistema a uma 
base de 2 vetores. 
 
Se Z = K = 0: 
 
Solução básica: X = 1, Y = 3 
 Z = K = 0 
 
Se X = Z = 0: 
 
 
 
 
 
Solução básica: Y = 75/21, K = 5/7 
 X = Z = 0 
 
Total de Soluções básicas contidas neste exemplo: 6 
 
1) X = Y = 0 
2) X = Z = 0 
3) X = K = 0 
4) Y = Z = 0 
5) Y = K = 0 
6) Z = K = 0 
 
2.4.2 – Solução Básica de um Sistema de Inequações Lineares 
 (Pg. 40 – P. O. – Medeiros). 
 
 
Maximizar Z = 2X + 3Y
 
 
Sujeito as X + 5Y ≤ 20 
restrições: 2X + Y ≤ 10 
 X, Y ≥ 0 restrições de não negatividade 
 
a) Construir a região de soluções do modelo usando Método Gráfico; 
 




===+
=−
7
5K,
21
75Y5K2Y
10KY3
OBS.: Variável básica: ≠ 0 
 Variável não básica: = 0 
 Obtêm-se várias soluções básicas. 
 Método Simplex: busca solução básica possível ótima. 
Restrições (≤≤≤≤): SOMAR variáveis de folga. 
 
OBS.: Se (≥≥≥≥), SUBTRAIR variáveis de 
folga. 



===+
=+
3Y,1X5YX2
10Y3X
 21



==
==
=+
20X,0Y
4Y,0X
20Y5X



==
==
=+
5X,0Y
10Y,0X
10YX2
b) Transformar o sistema de inequações num sistema de equações com 
variáveis não negativas (usam-se variáveis de folga); 
 
c) Mostrar que as soluções básicas do sistema de equações obtido são os 
vértices da região de soluções do modelo. 
 
Solução: 
 
a) 1a restrição: 
 
 
 
 2a restrição: 
 
Método gráfico: 
 
 
 
 
 
 
 
 
 
 
 
 
b) Transformar as Inequações em Equações 
 
 
 
 
 
 
 
 
 
5 
4 
10 15 20 
5 
10 
A 
C 
D B 
1a rest. 
2a rest. 
Zona 
Permissível 
X 
Y 
Vértices da região: são as soluções 
básicas do sistema de equações. 
⇒
Sistema de Inequação Sistema de Equação 
Variáveis não 
negativas 



≤+
≤+
10YX2
20Y5X



=++
=++
10SYX2
20SY5X
2
1
0S,0S
0Y,0X
:Sendo
algfodeVariáveis
S
S
21
2
1
≥≥
≥≥
→



 22
 
 
 
 
 
 
 
 
c) Soluções básicas: são vértices do polígono de soluções do método gráfico.X, Y ≥ 0, S1, S2 ≥ 0: variáveis não negativas 
 
 2 eq. 
 4 incog. 
 
 
Espaço vetorial: base R2, conjunto de 2 vetores linearmente independente. 
 
1a solução básica: 
X = Y = 0, base (1, 0) e (0, 1) 
 
 





=





+





10
20
S
1
0
S
0
1
21 
 
 
 
 
Solução básica: 
X = Y = 0, S1 = 20, S2 = 10: Vértice A 
 
2a solução básica: 
X = S1 = 0, base (5, 1) e (0, 1) 
 
 
 
 
 
 
 



=+++→=++
=+++→=++
10SS0YX210SYX2
20S0SY5X20SY5X
212
211
4 – 2 = 2 
(2 incógnitas nulas). 



==→=+
=+
10S,20S10S1S0
20S0S1
2121
21 Solução única p/ esta base 
sendo dado (20, 10) → vetor 
formado pela base. 



==→=+
=+
6S,4Y10S1Y
20S0Y5
22
2
→ Vetores que a partir de 
combinação linear geram 
outro vetor. 





=





+





10
20
S
1
0
Y
1
5
2
Variáveis de Folga ≥ 0 
Disponibilidade 
de recursos 
Recursos incluídos no 1º termo da equação 
de forma que este se iguale ao 2º termo: 
X + 5Y ≤ 20 
 
1o termo 2o termo 
 23
Solução básica: 
X = S1 = 0, Y = 4, S2 = 6: Vértice B 
 
3a solução básica: 
X = S2 = 0, base (5, 1) e (1, 0) 
 
 
 
 
 
 
 
 
Solução básica: X = S2 = 0, S1 = - 30, Y = 10 
 
4a solução básica: 
Y = S1 = 0, base (1, 2) e (0, 1) 
 
 
 
 
 
 
 
 
Solução básica: 
Y = S1 = 0, X = 20, S2 = - 30 
 
5a solução básica: 
Y = S2 = 0, base (1, 2) e (1, 0) 
 
 
 
 
 
 
Solução básica: Y = S2 = 0, X = 5, S1 = 15: Vértice C 
 
 






=





+





10
20
S
0
1
Y
1
5
1



<−==→=+
=+
030S,10Y10S0Y
20S1Y5
11
1
 ↓↓↓↓ 
Indica ponto fora da região de solução: Ponto (X, Y), 
isto é ponto (0, 10) - Solução básica não possível. 






=





+





10
20
S
1
0
X
2
1
2



−==→=+
=+
30S,20X10SX2
20S0X
22
2
Ponto fora da área permissível 



==→=+
=+
15S,5X10S0X2
20S1X
11
1






=





+





10
20
S
0
1
X
2
1
1
 24
6a solução básica: 
S1 = S2 = 0, base (1, 2) e (5, 1) 
 
 
 
 
 2X + 10Y = 40 
 2X + Y = 10 
 9Y = 30 Y = 30/9 
 X = 30/9 
 
Solução básica: 
S1 = S2 = 0, X = 30/9, Y = 30/9: Vértice D 
Logo, solução básica do sistema de equações com variáveis não negativas 
são os vértices da região de soluções do modelo. 
 
Valor ótimo da solução: ocorre no vértice do polígono de soluções do 
modelo (satisfaz restrições e alcança a função objetivo). 
 
 
Caso de inequação do tipo (≥≥≥≥): 
 
Deve-se subtrair a variável de folga S para que seu valor fique não negativo. 
 
Ex.: Restrição: 2X + 4Y ≥ 12 (inequação) 
 2X + 4Y = S + 12 (equação) 
 2X + 4Y – S = 12 (equação) 
 
 Neste caso, a variável S passa a se chamar variável de excesso. 
O que excede do lado esquerdo para se igualar ao lado direito. 
 
 
 
 
 
 
 
 
 
 



=+
=+
10YX2
)2(x20Y5X
- 
Substituir na 2a equação 
OBS.: 
2.4 – Sol. Básica e Sol. Básica Possível de um Sistema de Equações Lineares. 
2.4.1 – Sol. Básica de um Sistema de Equações Lineares. 
2.4.2 – Sol. Básica de um Sistema de Inequações Lineares. 
2.4.3 – Solução Básica e Soluções Básicas Possíveis (Programação Linear). 
 25
2.4.3 – Soluções Básicas e Soluções Básicas Possíveis (abordagem resumida) 
 (D. Moreira – pg. 54 - Programação Linear). 
 
São acrescentadas variáveis de folga a cada restrição Inequações se 
transformam em equações (restrições). 
 
Ex.: Problema de Maximização: 
F. Objetivo: Max. Z = 4000X + 5000Y 
Restrições: 5X + 10Y ≤ 100 
 9X + 6Y ≤ 108 
 Y ≤ 8 
 X, Y ≥ 0 (restrição de não negatividade) 
Solução: 
F. Objetivo: Z = 4000X + 5000Y + 0S1 + 0S2 + 0S3 
Restrições: 5X + 10Y + S1 = 100 
 9X + 6Y + S2 = 108 
 Y + S3 = 8 
 X, Y ≥ 0 (restrição de não negatividade) 
 S1, S2, S3 ≥ 0 (restrição de não negatividade) 
Variáveis de folga: representa disponibilidade (recursos não usados). 
 
Valores das variáveis de folga: 
Ponto X Y S1 S2 S3 
A 
B 
C 
D 
E 
0 
12 
8 
4 
0 
0 
0 
6 
8 
8 
 100 108 8 
 40 0 8 
 0 0 2 
 0 24 0 
 20 60 0 
 
 
 
 
Espaço Vetorial: R3, 3 vetores independentes. 
5 incógnitas – 3 eqs. = 2 variáveis nulas em cada ponto extremo (ver tabela 
acima). 
 
Pontos extremos: Soluções básicas possíveis. 
 
Variáveis de folga 
“adicionadas” (≤) 
5 incógnitas e 3 eqs. 
(Sistema indeterminado) 
Para cada 
vértice, 2 
variáveis 
nulas. 
S1, S2, S3: 
determinados 
através das 
restrições. Vértices: 
Solução 
Básica 
Possível. 
X, Y: 
determinados 
pelo método 
gráfico. 
S1, S2, S3: determinados 
com substituição dos 
valores X e Y nas eqs. de 
restrições. 
 26
PROPRIEDADE: (D. Moreira – pg. 56). 
 
“Dado um problema de programação linear com P incógnitas e m equações 
(após a introdução das variáveis de folga), nos pontos extremos da região 
possível terão (P–m) incógnitas com valores iguais a zero”. 
 
Sendo: (P-m) variáveis: Solução não básica (valores nulas). 
 m variáveis: Solução básica (valores diferentes de zero). 
 
Solução básica possível: os valores das variáveis satisfazem às restrições 
originais. 
Procedimento: 
a) Fazem-se conjuntos ≠s de (P-m) incógnitas nulas (tentativas). 
 
b) Determinam-se soluções básicas e, dentre elas, as soluções básicas 
possíveis. 
 
c) Substituir os valores das variáveis (tomadas como soluções básicas 
possíveis) na função objetivo. 
 
d) Obtém-se a solução ótima. 
 
Problemas com várias variáveis: a determinação das soluções básicas como 
apresentado acima requer um grande esforço de cálculo. 
 
Como evitar: Método Simplex – reduz consideravelmente o numero de 
soluções básicas a calcular (elimina soluções básicas não possíveis). 
 
Resolução com muitas variáveis: 
Uso de programas computacionais (ex.: Excel: uso do SOLVER). 
 
Resolução analítica para problemas de Programação Linear: 
MÉTODO SIMPLEX. 
 
2.5 – Método Simplex (D. Moreira - pg. 58, P. O. (Medeiros) – pg. 46) 
 
 Algoritmo para a solução de problemas de programação linear. 
 
Procura encontrar a “Solução Ótima”. 
 
É formado por um grupo de critérios para escolha de soluções básicas que 
melhoram o desempenho do modelo, e é também de um teste de otimalidade. 
 
Uso de computadores facilita o trabalho de cálculo e elimina a possibilidade 
de erros quando se trata de problemas com grandes números de variáveis. 
 27
 
Procedimento do Método Simplex: 
 
1 – Estabeleça uma tabela inicial. Formule a função objetivo e as restrições. Entre com as 
variáveis de decisão, variáveis na solução, valores de solução (bj - termos 
independentes das restrições), Ci (contribuição da variável - coeficientes), Z (custode 
introdução da variável) e (C – Z) (contribuição líquida). 
 
2 – Selecione a coluna-chave (coluna pivô). É a coluna que apresenta o coeficiente de 
maior valor positivo na linha (C – Z). A variável referente a esta coluna se torna a 
nova variável em solução. 
 
3 – Selecione a linha-chave (linha principal). É a linha com o menor valor obtido pela 
divisão do valor de solução (bj) pelo correspondente valor na coluna-chave. Use 
somente números positivos (abandonar números negativos ou indeterminados). Isso 
identifica a variável que deixa a solução (ou a base). 
 
4 – Marque o número-chave (pivô). Faça um círculo no número encontrado na intersecção 
da linha e coluna-chave. 
 
5 – Converta o número-chave (pivô) em 1. Faça isso dividindo cada valor na linha principal 
pelo pivô (Nova Linha Principal). Entre com essa nova linha em uma nova tabela. 
 
6 _ Gere outras linhas para a nova tabela com zeros na coluna-chave. Isso é feito pela 
multiplicação da Nova Linha Principal pelo valor encontrado na intersecção da coluna-
chave e a linha a ser convertida. Subtraia este resultado da linha antiga considerada. 
Entre com a linha revisada na nova tabela e continue com esse procedimento para as 
demais linhas na seção central da tabela (as que correspondem às restrições). 
 
7 – Teste a otimalidade. Compute os valores de Z e (C – Z). Os valores Z para cada coluna 
são ∑(elementos da coluna x Ci). Se todos os valores da linha (C – Z) são ≤ zero, a 
solução é ótima. Leia os valores para as variáveis em solução (na coluna de valores de 
solução – coluna bj) e o valor da função objetivo na linha Z (na coluna de valores da 
solução (coluna bj)). 
 
 
Exemplo 1: (D. M. – pg. 58) 
 
Maximizar Z = X + 3Y 
Sujeito a: 5X + 6Y ≤ 60 
 X + 2Y ≤ 16 
 X ≥ 0, Y ≥ 0 (condição de não negatividade) 
Solução: 
Transformar inequações lineares em equações lineares. 
Acrescentar “Variáveis de Folga” S1 e S2 (duas restrições, acrescentar duas 
variáveis de folga, uma para cada restrição): 
 28
 
Forma Genérica do Problema: 
Maximizar Z = X + 3Y + 0S1 + 0S2 
 
Obs.: coeficientes das variáveis de folga na Função Objetivo são nulos. 
 
Sujeito a: 5X + 6Y + 1S1 + 0S2 = 60 
 X + 2Y + 0S1 + 1S2 = 16 
 
 X, Y ≥ 0, S1, S2 ≥ 0 (cond. não negatividade) 
1a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 3 0 0 (Linha objetivo) 
Ci 
V. na 
Solução X Y S1 S2 bj bj/aij bj/aij 
0 S1 5 6 1 0 60 60/6 10 
0 S2 1 2 0 1 16 16/2 8 
Z 0 0 0 0 0 
(C-Z) 1 3 0 0 
 
 
 
 
 
Onde: Xi: variável de decisão (i = 1, ..., 3) 
 Sj: variável de folga (j = 1, ..., 3) 
 
Pivô: número que aparece na intersecção da coluna da variável que entra 
com a linha da variável que sai da base →→→→ 2. 
 
Ci: coeficientes das “variáveis na solução” na função objetivo. 
 
Inicialmente igual à zero (se for variável de folga, mas se for variável 
artificial é ≠ zero) →→→→ coeficiente das variáveis de folga na função objetivo. 
 
Tem-se ainda que: S1 = 60, S2 = 16 
X = Y = 0 
 
 
Linha Z: decréscimo na função objetivo se 1 unidade da variável fosse 
acrescentada à solução (para cada coluna). 
 
Inicialmente, a prioridade de formar a 
base são das variáveis de folga. 
Variável que entra na base: Y. 
Sai 
(LP) 
Linha (C-Z) é descrita em termos de variáveis não básicas 
 (neste caso: X, Y) → F. obj. 
 29
Linha (C-Z): acréscimo na função objetivo se 1 unidade da variável fosse 
acrescentada à solução (para cada coluna). 
 
 
 
 
 
 
 
Valores da linha Z: 
 
 
 
 
 
 Ci X Y S1 S2 bj 
 0 5(0) 6(0) 1(0) 0(0) 60(0) + 
 0 1(0) 2(0) 0(0) 1(0) 16(0) 
 Z 0 0 0 0 0 
 
 
 
 
Valores da linha (C-Z): 
 
 
 
 
 
Variável: X Y S1 S2 
 Coef: 1 3 0 0 - 
 Linha Z: 0 0 0 0 
 Linha (C-Z): 1 3 0 0 
 
 
 
Solução Ótima: encontrada quando na linha (C-Z) todos os valores são ou 
negativos ou nulos. 
 
OBS.: * Controlar os acréscimos e decréscimos 
 X Y S1 S2 da F. obj. na procura da solução ótima. 
 1X 3Y 0S1 0S2 
1(1) 3(1) 0(1) 0(1) 1 unidade da variável é acrescentada. 
 1 3 0 0 
 
Acréscimo na F. obj. → própria F. obj. (decréscimo = zero) 
 
Valor da F. O. associado à 1a tabela 
X = 0, Y = 0: variáveis não básicas – origem para solução Gráfica. 
Valores > zero → melhorar 
Para cada coluna.

 

 Coefs. das variáveis na 
função objetivo (F. O.) - (Valor Z correspondente) 
  
 
 
 
 
 
 
 


 x Ci →→→→ Para cada coluna. Coeficientes e lados direitos (bj) das restrições 
 
Soma-se os produtos 
 30
OBS.: Linha Z, linha (C-Z): decréscimo pode ocorrer, pois estamos 
maximizando. Acréscimo não pode ocorrer, logo parar o algoritmo 
quando (C-Z) for nulo ou negativo. 
 (Não pode ocorrer acréscimo, isto é (C-Z) > 0). 
 
Montagem da 2a Tabela: 
 
Na linha (C-Z), selecionar o maior coeficiente: 3 (maior contribuição que uma 
variável isolada pode trazer à F. O.). 
 
- Variável que entra na base: Y 
 
 
- Variável que sai da base: 
 
 
 
Menor valor de indica variável que sai: S2. 
 
 
OBS.: Usa-se Ycorrespondente, pois a variável que entra é Y. 
 
Linha Principal (LP): Linha da variável que sai. 
 
Pivô: no de intersecção da coluna da variável que entra com a linha da 
variável que sai da base → 2. 
 
- Determinar novos valores da linha principal (LP): 
 
 
 
 
Variável X Y S1 S2 bj 
Antiga LP 
Nova LP 
 1 2 0 1 16 
 ½ 1 0 1/2 8 
 
- Determinar novas linhas restantes: 
 (neste caso a linha de S1) 
� Selecionar o valor da intersecção dessa linha com a coluna da 
variável que entra (Y): 6 
Pivô
Antiga
Linha
÷




 * Buscar a base para a 
entrada de Y: (0,1) 






=
=
8
2
16
:linha2
10
6
60
:linha1
Y
b
a
a
entecorrespond
j
entecorrespond
j
Y
b
 31
 
� Multiplicar cada valor da nova linha principal (NLP) pelo número 
acima selecionado. 
 
Variável X Y S1 S2 bj 
NLP x no 
NLP x 6 
1/2(6) 1(6) 0(6) 1/2(6) 8(6) 
 3 6 0 3 48 
 
� Subtrair esse resultado da linha antiga: 
 
Variável 
Linha antiga S1 
NLP x no 
 X Y S1 S2 bj 
 5 6 1 0 60 - 
 3 6 0 3 48 
Nova linha S1 2 0 1 -3 12 
 
- Cálculo da linha Z: 
 
Ci 
0 
3 
 X Y S1 S2 bj 
 2 (0) 0 (0) 1(0) -3 (0) 12 (0) + 
 ½ (3) 1 (3) 0 (3) ½ (3) 8 (3) 
 Z
 
 3/2 3 0 3/2 24 
 
- Cálculo da linha (C-Z): 
 
Variável 
Coef. F. O. 
Linha Z 
 X Y S1 S21 3 0 0 - 
 3/2 3 0 3/2 
(C-Z)
 
 -1/2 0 0 -3/2 
 
 
 
 
 
 
 
 
 
Todos os valores da linha (C-Z) são ou negativos ou nulos. 
 
Solução Ótima encontrada. 
 32
2a tabela: 
 
 Variáveis de decisão (título da tabela) 
 1 3 0 0 (L. objetivo) 
 
Ci 
V. na 
Solução X Y S1 S2 bj bj/aij 
0 S1 2 0 1 -3 12 
3 Y ½ 1 0 1/2 8 
Z 3/2 3 0 3/2 24 
(C-Z) -1/2 0 0 -3/2 
 
 
 
 
 Observar base formada nas colunas das variáveis Y e S1: interseção linha 
/coluna de cada variável básica é “1” e “zero” nos demais campos da coluna 
da variável em análise. 
 
Tem-se então que: 
 
 
 
 
Função Objetivo: 1X + 3Y = 1 (0) + 3 (8) = 24 
 
1a restrição: 5X + 6Y = 5 (0) + 6 (8) = 48 ≤ 60 ok 
Sobram: 60 – 48 = 12 unidades de recurso sem utilização. 
 S1 = 12 
 S2 não comparece na restrição (coef. nulo). 
 
2a restrição: 1X + 2Y = 1 (0) + 2 (8) = 16 ≤ 16 ok 
 S1 não comparece na restrição (coef. nulo). 
 S2 = 0 (S2 não comparece na solução → var. não básica). 
 
Solução básica possível: 
 Variáveis básicas: S1 = 12, Y = 8 
 Variáveis não básicas: S2 = 0, X = 0 
 
 Z = 24 (função objetivo atingida (maximizada)). 
 



=
=
8Y
),bemcomparecenão(0X j X = 0: variável não 
básica 
Valor final de F. O. 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: X, S2) → F. obj. 
Solução Ótima 
 33
Exemplo 2: (P. O. –Medeiros da Silva – pg. 46) 
Resolver, pelo método Simplex, o seguinte modelo de programação linear: 
 
Maximizar Z = 3X + 5Y 
 
Sujeito a: 2X + 4Y ≤ 10 
 6X + Y ≤ 20 
 X - Y ≤ 30 
 X ≥ 0, Y ≥ 0 (condição de não negatividade) 
 
Bibliografia usada na elaboração do material do curso. 
 
BIBLIOGRAFIA PRINCIPAL (BP): (Normas ABNT) 
 
/1/ - ‘Pesquisa Operacional na Tomada de Decisões – Modelagem em Excel – Para Cursos de 
Administração, Economia e Ciências Contábeis’, Gerson Lachtermacher – Editora Campus – Rio de 
Janeiro, 2002. 
 
BIBLIOGRAFIA COMPLEMENTAR (BC): (Normas ABNT) 
 
/1/ - ‘Administração da Produção e Operações’, Daniel Augusto Moreira – 3a Edição – Livraria Pioneira 
Editora – São Paulo, 1998. 
 
/2/ - ‘Pesquisa Operacional’, Ermes Medeiros da Silva / Elio Medeiros da Silva / Valter Gonçalves / 
Afrânio Carlos Murilo – 3a Edição - Editora Atlas S. A. – São Paulo, 1998. 
 
/3/ - ‘Introdução à Programação Linear’, Abelardo de Lima Puccini – Livros Técnicos e Científicos Editora 
S. A. – Rio de Janeiro, 1981 (última reimpressão). 
 
/4/ - ‘Introdução à Pesquisa Operacional’, Hillier / Lieberman - Editora Campus Ltda – Editora da 
Universidade de São Paulo – São Paulo, 1998. 
 
/5/ - ‘Pesquisa Operacional’, Richard Bronson – McGraw-Hill do Brasil – São Paulo, 1985. 
 
/6/ - ‘Modelos de Programação Linear’, Mário Jorge Braga / Mihail Lermontov / Maria Augusta Machado 
– Imprensa Naval – Rio de Janeiro, 1985. 
 
/7/ - ‘Pesquisa Operacional’, Harvey M. Wagner – Prentice/Hall do Brasil – Rio de Janeiro, 1986. 
 
/8/ - ‘Pesquisa Operacional – Técnicas de Otimização Aplicadas a Sistemas Agroindustriais’, José Vicente 
Caixeta-Filho - Editora Atlas S.A. – São Paulo, 2001. 
 
/9/ - ‘Introdução à Pesquisa Operacional – Métodos e Modelos para Análise de Decisões’, Eduardo 
Leopoldino de Andrade – 3a ed. - Editora LTC – Rio de Janeiro, 2002.