Buscar

PUC-Rio Pesquisa Operacional - PO C Met Sp e Cs Esp 2013.2

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 21 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 21 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 21 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

Pesquisa Operacional. 
 Simplex (Casos Especiais). 
34 
PO - PESQUISA OPERACIONAL 
 Continuação 
Profa. Léa Benatti 
Exemplo 2: (P. O. –Medeiros da Silva – pg. 46) 
 
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) 
 
Solução: 
Transformar inequações lineares em equações lineares: 
Acrescentar “Variáveis de Folga”. 
Maximizar Z = 3X + 5Y + 0S1 + 0S2 + 0S3 
Sujeito a: 2X + 4Y + 1S1 + 0S2 + 0S3 = 10 
 6X + Y + 0S1 + 1S2 + 0S3 = 20 
 X - Y + 0S1 + 0S2 + 1S3 = 30 
 X, Y ≥ 0; S1, S2, S3 ≥ 0 (cond. não negatividade) 
 
1a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 3 5 0 0 0 (Linha objetivo) 
Ci 
V. na 
Solução X Y S1 S2 S3 bj bj/aij bj/aij 
0 S1 2 4 1 0 0 10 10/4 2,5 
0 S2 6 1 0 1 0 20 20/1 20 
0 S3 1 -1 0 0 1 30 30/(-1) -30 
 Z 0 0 0 0 0 0 
 (C-Z) 3 5 0 0 0 
 
 
 
Valores da linha Z: 
 
 
 
 
 
Forma genérica 
do problema. 
Exemplo resolvido / para treino 
dos alunos → três restrições 
Sai 
(LP) 
Linha (C-Z): em termos de variáveis não básicas ( X, Y) → F. obj. 
entra 
( ) ij Cx
produtososseSoma
restriçõesdasbdireitos
ladoseesCoeficient





−








→→→→ Para cada coluna. 
 
 35









−=
−
=
→=
)considerarnão(30)1(
30
:linha3
20
1
20
:linha2
valormenor5,2
4
10
:linha1
Y
b
a
a
a
.corresp
j
Então: 
 Ci X Y S1 S2 S3 bj 
 0 2(0) 4(0) 1(0) 0(0) 0(0) 10(0) + 
 0 6(0) 1(0) 0(0) 1(0) 0(0) 20(0) 
 0 1(0) -1(0) 0(0) 0(0) 1(0) 30(0) 
 Z 0 0 0 0 0 0 
 
 
 
 
Valores da linha (C-Z): 
 
 
 
 
 
Variável: X Y S1 S2 S3 
 Coef F. O. 3 5 0 0 0 - 
 Linha Z: 0 0 0 0 0 
 Linha (C-Z): 3 5 0 0 0 
 
 
 
Valores da linha (C-Z) > zero (ou positivos) → melhorar 
 
Solução Ótima: encontrada quando os valores da linha (C-Z) são negativos 
ou nulos. 
 
2a Tabela: 
Linha (C-Z): maior valor: 5 (referente a Y). 
 
- Variável que entra: Y 
 
 
 
- Variável que sai: 
 
 
 
( )
.colunacada/p
entecorrespondZValor
.)O.F(objetivofunção
naiávelvarda.Coefs
−





Maior valor da linha (C-Z) → variável que entra: Y 
Z = 0 – 1a tabela: linha Z nula (var. folga somente). 
X = Y = 0: origem para solução Gráfica. 
 
 36
 
 
 
 
Menor valor de : variável que sai - S1. 
 
 
Linha Principal (LP): 1a linha (referente à variável que sai – S1) 
 
Pivô: no de intersecção da coluna da variável que entra com a linha da 
variável que sai da base → 4. 
 
- Determinar a Nova Linha Principal (NLP): 
 
 
 
 
Variável X Y S1 S2 S3 bj 
Antiga LP 
Nova LP 
 2 4 1 0 0 10 
 1/2 1 1/4 0 0 2,5 
 
- Determinar novas linhas restantes: 
� Valor de intersecção da linha com a coluna da variável que entra 
(Y): 2a linha → 1 
 3a linha → -1 
 
� Multiplicar cada valor da nova linha principal (NLP) pelos 
números acima selecionados. 
 
� Subtrair esses resultados das linhas antigas: 
 
2a linha: Nova S2 
Variável X Y S1 S2 S3 bj 
Ant. S2 
NLP x no 
NLP x no 
Nova S2 
 6 1 0 1 0 20 
1/2(1) 1(1) 1/4(1) 0(1) 0(1) 2,5(1) 
 1/2 1 1/4 0 0 2,5 
11/2 (=5,5) 0 -1/4 1 0 35/2 (=17,5) 
 
 
.corresp
j
Y
b
Não se consideram valores menores que zero (ou indeterminados). 
 
Implica em valor negativo para a próxima base, o que não é possível. 
÷ 4 
Pivô
Antiga
Linha
÷





 
 37
3a linha: Nova S3 
Variável X Y S1 S2 S3 bj 
 Ant. S3 
NLP x no 
NLP x no 
Nova S3 
 1 -1 0 0 1 30 
1/2(-1) 1(-1) 1/4(-1) 0(-1) 0(-1) 2,5(-1) 
 -1/2 -1 -1/4 0 0 -2,5 (= - 5/2) 
 3/2 0 1/4 0 1 65/2 (=32,5) 
 
- Cálculo da linha Z: 
Ci 
 5 
 0 
 0 
 X Y S1 S2 S3 bj 
 1/2(5) 1(5) 1/4(5) 0(5) 0(5) 5/2(5) + 
11/2(0) 0(0) -1/4(0) 1(0) 0(0) 35/2(0) 
 3/2(0) 0(0) ¼(0) 0(0) 1(0) 65/2(0) 
 Z
 
 5/2 5 5/4 0 0 25/2 
 
- Cálculo da linha (C-Z): 
Variável 
Coef. F. O. 
Linha Z 
 X Y S1 S2 S3 
 3 5 0 0 0 - 
 5/2 5 5/4 0 0 
(C-Z)
 
 1/2 0 -5/4 0 0 
 
 
2a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 3 5 0 0 0 (Linha objetivo) 
Ci 
V. na 
Solução X Y S1 S2 S3 bj bj/aij bj/aij 
5 Y ½ 1 ¼ 0 0 5/2 5/2 ÷ 1/2 5 
0 S2 11/2 0 -1/4 1 0 35/2 35/2 ÷ 11/2 3,18 
0 S3 3/2 0 ¼ 0 1 65/2 65/2 ÷ 3/2 21,67 
 Z 5/2 5 5/4 0 0 25/2 
 (C-Z) ½ 0 -5/4 0 0 
 
 
3a Tabela: 
Maior valor positivo em (C-Z) = 1/2 → coeficiente da variável X. 
 
� Variável que entra na base: X. 
≥≥≥≥ zero - melhorar 
Sai 
(LP) 
Linha (C-Z): em termos de variáveis não básicas ( X, S1) → F. obj. 
 
 38
� Variável que sai da base: 
 S2 → Linha Principal (menor valor de bj/aij = 3,18). 
 
� Pivô = 11/2 = 5,5 
 
- Determinar novos valores da linha principal (LP): 
 
 
 
 
 
 
- Determinar novas linhas restantes: 
� Valor de intersecção da linha com a coluna da variável que entra 
(X): 1a linha → 1/2 
 3a linha → 3/2 
 
� Multiplicar cada valor da Nova Linha Principal (NLP) pelos 
números acima selecionados. 
 
� Subtrair esses resultados das linhas antigas: 
 
1a linha: 
Variável X Y S1 S2 S3 bj 
Ant. Y
 
NLP x no 
NLP x no 
Nova Y
 
 1/2 1 1/4 0 0 5/2 
1(1/2) 0(1/2) -1/22(1/2) 2/11(1/2) 0(1/2) 35/11(1/2) 
 1/2 0 -1/44 1/11 0 35/22 
 0 1 3/11 -1/11 0 10/11 
 
3a linha: 
Variável X Y S1 S2 S3 bj 
Ant. S3 
NLP x no 
NLP x no 
Nova S3 
 3/2 0 1/4 0 1 65/21(3/2) 0(3/2) -1/22(3/2) 2/11(3/2) 0(3/2) 35/11(3/2) 
 3/2 0 -3/44 3/11 0 105/22 
 0 0 7/22 -3/11 1 305/11=(27,73) 
 
 
 
Variável X Y S1 S2 S3 bj 
Antiga LP 
Nova LP 
11/2 0 -1/4 1 0 35/2 
 1 0 -1/22 2/11 0 70/22 = 35/11 
÷ 11/2 
Pivô
Antiga
Linha
÷





 
 39
- Cálculo da linha Z: 
Ci 
 5 
 3 
 0 
 X Y S1 S2 S3 bj 
 0(5) 1(5) 3/11(5) -1/11(5) 0(5) 10/11(5) + 
 1(3) 0(3) -1/22(3) 2/11(3) 0(3) 35/11(3) 
 0(0) 0(0) 7/22(0) -3/11(0) 1(0) 305/11(0) 
 Z
 
 3 5 297/242=1,23 1/11 0 155/11 
 
- Cálculo da linha (C-Z): 
Variável 
Coef. F. O. 
Linha Z 
 X Y S1 S2 S3 
 3 5 0 0 0 - 
 3 5 297/242 1/11 0 
(C-Z)
 
 0 0 -297/242 -1/11 0 
 
 
 
3a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 3 5 0 0 0 (L. objetivo) 
Ci 
V. na 
Solução X Y S1 S2 S3 bj bj/aij 
5 Y 0 1 3/11 -1/11 0 10/11 
3 X 1 0 -1/22 2/11 0 35/11 
0 S3 0 0 7/22 -3/11 1 305/11 
 Z 3 5 297/242=1,23 1/11=0,09 0 155/11 
 (C-Z) 0 0 -297/242 -1/11 0 
 
Linha (C-Z): valores menores ou iguais a zero – Solução Ótima 
 
Logo: 
Variáveis básicas: X = 35/11 = 3,18 Z = 155/11 = 14,09 
 Y = 10/11 = 0,91 
 S3 = 305/11 = 27,73 
 
Variáveis não básicas: S1 = S2 = 0 
 
 
Ok - Valores ≤ zero - Solução Ótima. 
 
 40
Exercícios Propostos: 
 
Exemplo 3: (D. M. – Daniel Moreira – pg. 65) 
 
Maximizar Z = 2X + 5Y 
 
Sujeito a: 12X + 40Y ≤ 2400 
 5X + 10Y ≤ 810 
 X ≥ 0, Y ≥ 0 (condição de não negatividade) 
 
Exemplo 4: (P. O. – Medeiros da Silva – pg. 52) 
 
Maximizar Z = 2X1 + 3X2 + X3 
 
Sujeito a: X1 + X2 + X3 ≤ 40 
 2X1 + X2 –X3 ≤ 20 
 3X1 + 2X2 – X3 ≤ 30 
 X1 ≥ 0, X2 ≥ 0, X3≥ 0 (condição de não negatividade) 
 
 
 
 
 
 
 
 
 
 
 
 
Fazer a lista de exercícios propostos no livro P. O. - Medeiros da Silva – pg. 56 – respostas 
na pg. 58. 
 
Puccini – pg. 65. 
 Exercícios na pg. 66: Resolvido item 3.3.2 – Solução algébrica. 
 Resolvido item 3.3.3 – Solução usando quadros (pg. 71). 
 Problemas propostos (pg. 91): resolução na pg. 222. 
 
 
 
 
 
Exercício resolvido no livro P. O. – Medeiros da Silva – pg. 52. 
Sua forma de montar a solução é um pouco diferente de Daniel Moreira (abordada 
neste curso), mas leva à mesma resposta. 
Exercício resolvido no livro P. O. – Medeiros da Silva. 
Além da forma de montar a solução ser diferente da apresentada aqui, a tabela possui 
formatação diferente. Neste caso, deve-se ter o cuidado de, antes de iniciar a resolução 
do modelo, verificar se a variável desejada está na base. Caso não esteja, coloca-la na 
base através de programação linear. 
 
 41
2.5.1 – Casos Especiais (D. M. – Daniel Moreira) 
 
a) Problema de Minimização 
Viu-se até então: Problemas de Maximização; 
 Restrições (≤). 
 
Problema de minimização →→→→ Problema de Maximização 
 
 
 
 
• Valores finais das variáveis de decisão estarão corretos. 
 
• Valor final da “função objetivo”: linha Z, coluna bj, com o “sinal trocado”. 
 
OBS.: Restrições →→→→ conservadas como as originais. 
 
Ex.: Problema de Minimização: (P. O. (Medeiros)– pág. 58) 
F. Objetivo: Minimizar L = 3X - 4Y + Z 
Restrições: X + Y + Z ≤ 10 
 2X + Y - Z ≤ 20 
 X, Y, Z ≥ 0 (restrição de não negatividade) 
 
Modelo Equivalente: 
F. Objetivo: Maximizar (-L) = -3X + 4Y - Z 
Sujeito a: X + Y + Z ≤ 10 
 2X +Y – Z ≤ 20 
 X, Y, Z ≥ 0 (restrição de não negatividade) 
 
Resolvido o “modelo equivalente”, tem-se a solução do “modelo original” 
com troca do sinal do valor de L e valores das variáveis básicas sem 
alteração. 
 
b) Problema de variável livre (P. O. – pág. 59) 
Caso de alguma variável do modelo não possuir a condição de não 
negatividade 
 
 
 
Multiplicar todos os coeficientes da “Função Objetivo” por (-1). 
Substituí-la pela diferença de duas outras variáveis “não negativas”. 
 
 42
Ex.: Max. Z = X1 + 2X2 + X3 
 Sujeito a: X1 + X2 + X 3 ≤ 10 
 2X1 + 3X2 ≤ 20 
 X1, X 3 ≥ 0, X2 → livre 
 
Modelo Equivalente: 
Faz-se: X2 = X4 –X5; com X4 ≥ 0 e X5 ≥ 0 
 
Max. Z = X1 + 2X4 – 2X5 + X3 
 
 
Sujeito a: X1 + X4 – X5 + X3 ≤ 10 
 2X1 + 3X4 – 3X5 ≤ 20 
 X1, X4, X5, X3 ≥ 0 
A solução deste modelo resolve o anterior. 
 
Nomenclaturas de mesmo significado: 
Variável livre; sem restrição de sinal, variável qualquer. 
 
c) Empate na Entrada da Base (Puccini – pág. 77) 
Caso de empate na entrada (duas ou mais variáveis de mesmo valor positivo 
na linha (C-Z)): escolher arbitrariamente uma delas para entrar na base. 
 
Implicação da escolha: caminho mais longo ou mais curto para chegar à 
solução ótima. 
 
d) Empate na saída da Base (Puccini – pág. 77, P. O. – pág 73) 
Método Simplex: a linha principal é a restrição que apresenta o menor 
quociente, não negativo, na divisão dos termos independentes (bj) pelos 
coeficientes correspondentes da variável que entra na base. 
 
Variável que sai da base: variável correspondente à Linha Principal. 
 
Caso de empate na saída: escolher arbitrariamente uma das variáveis para sair 
da base. 
 
Ex.: Caso de empate na saída das variáveis X3 e X5. 
Escolha: X3: sai da base; 
 X5 é nula (variável que fica na base). 
 
Se X3 for nula no passo seguinte: solução compatível básica DEGENERADA. 
(Duas variáveis nulas no passo) 
 
Artifício Matemático 
2X2 
 
 43
Problemas de Degeneração: eventualmente se entra em circuitos fechados 
intermináveis à procura da solução ótima. 
 
 
 
 
 
e) Caso de Soluções Múltiplas (Puccini – pág. 79, P. O. – pág 73) 
Na linha (C-Z) do Algoritmo Simplex, os valores dos coeficientes 
das variáveis não básicas são diferentes de Zero →→→→ para cada solução, 
inclusive para a solução ótima. 
 
Se na solução ótima o coeficiente de uma variável não básica na linha (C-Z) 
for zero, essa variável poderá entrar na base sem alterar o valor do objetivo, 
gerando outra solução ótima. Neste caso, qualquer combinação linear dessas 
duas soluções também será solução ótima. 
 
Exercício: (Exemplo de soluções Múltiplas) (Puccini – pg. 79) 
Maximizar Z = X + 2Y 
 Sujeito a: X ≤ 3 
 Y ≤ 4 
 X + 2Y ≤ 9 
 X ≥ 0, Y ≥ 0 (condição de não negatividade) 
 
a) Resolver pelo Método Gráfico. 
b) Resolver pelo Método Simplex. 
 
Solução: 
a) Solução Gráfica: 
3a restrição:X = 0, Y = 9/2 = 4,5 
Y = 0, X = 9 
 
 
 
 
 
 
 
 
 
 
Caso raro (existem maneiras para solucionar: nível 
de exposição sem interesse nessa disciplina). 
Zona 
Permissível 
X + 2Y = 9 (sobre a linha) 
Y = 4 
X = 3 
X 
Y 
9,0 
B (3, 0) A (0, 0) 
C (3, 3) 
D (1, 4) 
E (0, 4) 
4,5 
3,0 
 
 44
 
Pontos X Y Z = X + 2Y (Max.) 
A 0,0 0,0 0,0 
B 3,0 0,0 3,0 
C 3,0 3,0 9,0 
D 1,0 4,0 9,0 
E 0,0 4,0 8,0 
 
b) Solução pelo Método Simplex: 
Solução: 
 
Transformar inequações lineares em equações lineares. 
Acrescentar “Variáveis de Folga”: 
 
Maximizar Z = X + 2Y + 0S1 + 0S2 + 0S3 
Sujeito a: X + 0Y + 1S1 + 0S2 + 0S3 = 3 
 0X + Y + 0S1 + 1S2 + 0S3 = 4 
 X + 2Y + 0S1 + 0S2 + 1S3 = 9 
 X, Y ≥ 0; S1, S2, S3 ≥ 0 (cond. não negatividade) 
 
1a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 1 2 0 0 0 (Linha objetivo) 
Ci 
V. na 
Solução X Y S1 S2 S3 bj bj/aij bj/aij 
0 S1 1 0 1 0 0 3 Indet. indet. 
0 S2 0 1 0 1 0 4 4/1 4 
0 S3 1 2 0 0 1 9 9/2 4,5 
 Z 0 0 0 0 0 0 
 (C-Z) 1 2 0 0 0 
 
 
 
 
Onde: Xi: variável de decisão (i = 1, ..., 2) 
 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 → 1. 
 
Forma genérica 
do problema 
Solução ótima (encontra-se no 
ponto C e D): sobre a reta CD. 
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. 
 
 45
Linha Z: inicialmente com valores iguais l à zero (somente variáveis de 
folga na base) → coeficientes das variáveis de folga na função objetivo 
inicial. 
 
Se, além de usar variáveis de folga, for necessário usar também variável 
artificial (ai), isto é, quando se tem restrições com sinais (≥), aparecerá 
na linha Z valores diferentes de zero. 
 
Valores da linha Z: 
 
 
 
 
 
 
 Ci X Y S1 S2 S3 bj 
 0 1(0) 0(0) 1(0) 0(0) 0(0) 3(0) + 
 0 0(0) 1(0) 0(0) 1(0) 0(0) 4(0) 
 0 1(0) 2(0) 0(0) 0(0) 1(0) 9(0) 
 Z 0 0 0 0 0 0 
 
 
 
 
 
Valores da linha (C-Z): 
)entecorrespondZValor(
.)O.F(tivofunçãoobje
alniávevarda.Coefs
−





 
 
 
Variável: X Y S1 S2 S3 
 Coef F. Obj.: 1 2 0 0 0 - 
 Linha Z: 0 0 0 0 0 
 Linha (C-Z): 1 2 0 0 0 
 
 
 
 
 
 
( ) ij Cx
produtososseSoma
restriçõesdasbdireitos
ladoseesCoeficient





−








→→→→ Para cada coluna. 
Valores > zero → melhorar. 
Variável que entra: Y. 
(Para cada coluna) 
Valor da F. O. associado à 1a tabela (Z = 0,0). 
X = 0, Y = 0: variáveis não básicas – origem p/ solução Gráfica. 
 
 46
Montagem da 2a Tabela: 
Na linha (C-Z), selecionar o maior valor (coeficiente): 2 (maior contribuição 
que uma variável isolada pode trazer à F. O.). 
 
- Variável que entra na base: Y (var. que corresponde ao maior coeficiente). 
 
- Variável que sai da base: 
 
 
5,4
2
9
:linha3
)S:sai.(varvalormenor:4
1
4
:linha2
)esquecer(adominerdetin
0
3
:linha1
a
2
a
a
=
=
=
 
 
OBS.: Usa-se Ycorrespondente, pois a variável que entra é Y. 
 
Linha Principal (LP): Linha da variável que sai (2a linha, referente a S2). 
 
- Determinar novos valores da nova linha principal (NLP): 
 
 
 
 
 
Variável X Y S1 S2 S3 bj 
Antiga LP 
Nova LP 
 0 1 0 1 0 4 
 0 1 0 1 0 4 
 
- Determinar novas linhas restantes: (neste caso a linha de S1 e S3) 
1a linha: (no = Zero) 
Variável X Y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova S1 
 1 0 1 0 0 3 
 0(0) 1(0) 0(0) 1(0) 0(0) 4(0) - 
 1 0 1 0 0 3 
 
3a linha: (no = 2) 
Variável X Y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova S3 
 1 2 0 0 1 9 
 0(2) 1(2) 0(2) 1(2) 0(2) 4(2) - 
 1 0 0 -2 1 1 
Ycorrespondente
bj
Pivô
Antiga
Linha
÷





1 
* Buscar a base para a 
entrada de Y: (0,1) 
 
 47
 
- Cálculo da linha Z: 
Ci 
 0 
 2 
 0 
 X Y S1 S2 S3 bj 
 1(0) 0(0) 1(0) 0(0) 0(0) 3(0) 
 0(2) 1(2) 0(2) 1(2) 0(2) 4(2) + 
 1(0) 0(0) 0(0) -2(0) 1(0) 1(0) 
 Z
 
 0 2 0 2 0 8 
 
- Cálculo da linha (C-Z): 
Variável 
Coef. F. O. 
Linha Z 
 X Y S1 S2 S3 
 1 2 0 0 0 - 
 0 2 0 2 0 
(C-Z)
 
 1 0 0 -2 0 
 Linha (C-Z) apresenta coef. > zero (melhorar). 
 
2a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 1 2 0 0 0 (Linha objetivo) 
Ci 
V. na 
Solução X Y S1 S2 S3 bj bj/aij bj/aij 
0 S1 1 0 1 0 0 3 3/1 3 
2 Y 0 1 0 1 0 4 4/0 indet. 
0 S3 1 0 0 -2 1 1 1/1 1 
 Z 0 2 0 2 0 8 
 (C-Z) 1 0 0 -2 0 
 
 
 
 
 
Montagem da 3a Tabela: 
Linha (C-Z), maior valor: 1 (maior contribuição que uma variável isolada 
pode trazer à F. O.) – coef. da variável X. 
 
- Variável que entra na base: X 
 
- Variável que sai da base (S3) – menor valor de 
(LP) 
 
 Xcorrespondente
bj
Variável que entra na base: X (maior coef. (+)). 
Sai 
(LP) 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: X, S2) → F. obj. Pivô: 1 
 
 48
- Determinar novos valores da nova linha principal (NLP): 
 
 
 
 
 
Variável X Y S1 S2 S3 bj 
Antiga LP 
Nova LP 
 1 0 0 -2 1 1 
 1 0 0 -2 1 1 
 
- Determinar novas linhas restantes: (neste caso a linha de S1 e Y) 
 
1a linha: (no = 1) 
Variável X Y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova S1 
 1 0 1 0 0 3 
 1(1) 0(1) 0(1) -2(1) 1(1) 1(1) - 
 0 0 1 2 -1 2 
 
2a linha: (no = zero) 
Variável X Y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova Y
 
 0 1 0 1 0 4 
 1(0) 0(0) 0(0) -2(0) 1(0) 1(0) - 
 0 1 0 1 0 4 
 
- Cálculo da linha Z: 
Ci 
 0 
 2 
 1 
 X Y S1 S2 S3 bj 
 0(0) 0(0) 1(0) 2(0) -1(0) 2(0) 
 0(2) 1(2) 0(2) 1(2) 0(2) 4(2) + 
 1(1) 0(1) 0(1) -2(1) 1(1) 1(1) 
 Z
 
 1 20 0 1 9 
 
- Cálculo da linha (C-Z): 
Variável 
Coef. F. O. 
Linha Z 
 X Y S1 S2 S3 
 1 2 0 0 0 - 
 1 2 0 0 1 
(C-Z)
 
 0 0 0 0 -1 
Linha (C-Z) apresenta coefs. ≤ zero. (Solução Ótima encontrada) 
 
 
Pivô
Antiga
Linha
÷





1 
* Buscar a base para a 
entrada de X: (1,0) 
 
 49
3a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 1 2 0 0 0 (Linha objetivo) 
Ci V. na 
Solução X Y S1 S2 S3 bj bj/aij bj/aij 
0 S1 0 0 1 2 -1 2 
2 Y 0 1 0 1 0 4 
1 X 1 0 0 -2 1 1 
 Z 1 2 0 0 1 9 
 (C-Z) 0 0 0 0 -1 
 
 
 
 
 
Variáveis Básicas: Variáveis não básicas: F. Objetivo: 
X = 1,0 S2 = S3 = 0,0 Z = 9,0 
Y = 4,0 
S1 = 2,0 
 
Solução Ótima: pto D(1,4) da região permissível. 
 
Coeficiente da variável não básica S2 é zero na linha (C-Z). 
 
Logo, S2 poderá entrar na base sem alterar o valor do objetivo: gera outra 
solução ótima. 
 Z = 0S2 –1S3 + 9 (S2 e S3: variáveis não básicas) 
(Coeficientes da linha (C-Z) (Z modificado) e 
Valor de Z (da linha Z) correspondente ao termo 
independente bj). 
 
Montagem da 4a Tabela: 
- Variável que entra na base: S2 (depois de encontrada solução ótima, variável 
não básica de coeficiente nulo na linha (C-Z)). 
 
- Variável que sai da base (S1) – menor valor (LP) 
 
Variável que entra na base: S2 (coef. = zero). 
Sai 
(LP) 
Linha (C-Z) é descrita em termos de variáveis não 
básicas (neste caso: S2, S3) → F. obj. 
Pto D(1,4) 
(sol. Graf.) 
Solução 
Múltipl
a 
S2 correspondente
bj
 
 50
 
)esquecer(
2
1
2
1
:linha3
4
1
4
:linha2
saique.Var1
2
2
:linha1
a
a
a
−=
−
=
=
 
 
Linha principal: referente à linha de S1. 
Pivô: 2 
 
- Determinar novos valores da nova linha principal (NLP): 
 
 
 
 
Variável X Y S1 S2 S3 bj 
Antiga LP 
Nova LP 
 0 0 1 2 -1 2 
 0 0 1/2 1 -1/2 1 
 
- Determinar novas linhas restantes: (neste caso a linha de X e Y) 
 
2a linha: (no = 1) 
Variável X Y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova Y
 
 0 1 0 1 0 4 
 0(1) 0(1) 1/2(1) 1(1) -1/2(1) 1(1) - 
 0 1 -1/2 0 1/2 3 
 
3a linha: (no = -2) 
Variável X Y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova X
 
 1 0 0 -2 1 1 
 0(-2) 0(-2) 1/2(-2) 1(-2) -1/2(-2) 1(-2) - 
 1 0 1 0 0 3 
 
- Cálculo da linha Z: 
Ci 
 0 
 2 
 1 
 X Y S1 S2 S3 bj 
 0(0) 0(0) 1/2(0) 1(0) -1/2(0) 1(0) 
 0(2) 1(2) -1/2(2) 0(2) 1/2(2) 3(2) + 
 1(1) 0(1) 1(1) 0(1) 0(1) 3(1) 
 Z
 
 1 2 0 0 1 9 
 
Pivô
Antiga
Linha
÷





2 
 
 51
- Cálculo da linha (C-Z): 
Variável 
Coef. F. O. 
Linha Z 
 X Y S1 S2 S3 
 1 2 0 0 0 - 
 1 2 0 0 1 
(C-Z)
 
 0 0 0 0 -1 
Linha (C-Z) apresenta coefs. ≤ zero. (Outra Solução Ótima encontrada) 
 
4a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 2 0 0 0 (Linha objetivo) 
Ci V. na 
Solução X Y S1 S2 S3 bj bj/aij bj/aij 
0 S2 0 0 1/2 1 -1/2 1 
2 Y 0 1 -1/2 0 1/2 3 
1 X 1 0 1 0 0 3 
 Z 1 2 0 0 1 9 
 (C-Z) 0 0 0 0 -1 
 
 
Variáveis básicas: Variáveis não básicas: F. Objetivo: 
X = 3 S1 = S3 = 0,0 Z = 9,0 
Y = 3 
S2 = 1 Ponto C(3, 3) da solução gráfica. 
 
 O coeficiente de S1 (variável não básica) na linha (C-Z) é zero. Se S1 
entrar na base retornamos à 3a tabela, ou seja, ao ponto D. Sendo assim, 
qualquer combinação linear das soluções da tabela 3 e 4, isto é, qualquer 
ponto de CD, também será uma solução ótima para o modelo em questão. 
 
 
f) Como Trabalhar com Restrições do tipo (=) e (>): (P. O. – Pág. 60, Puccini – Pág. 81) 
 
 Modelos resolvidos até o presente momento pelo Algoritmo Simplex: 
 - Restrições são do tipo (≤); 
 - Termos da direita bj positivos (bj > 0). 
 
Se bj for negativo: multiplicar por (-1) toda a restrição. 
 (O sinal da inequação deve ser invertido). 
 
Variável que entra na base: S1 (coef. = zero). 
Sai 
(LP) 
Linha (C-Z): descrita em termos de vars não básicas (neste caso: S1, S3) → F. obj. 
Pto C(3,3) 
(sol. Graf.) 
Solução 
Múltipla 
 
 52
Ex.: Restrição: X – 2Y ≤ - 3 → x (-1) 
-X + 2Y ≥ 3 → restrição do tipo (≥). 
 
� Trabalha-se com problemas de Maximização (caso de problemas de 
Minimização: transforma-lo em problema de Maximização). 
 
f.1) Restrição do tipo (=): (Daniel Moreira – pág. 65) 
 
 Usa-se variável artificial (ou fictícia, ou fantasma) a. 
 
Obs.: Artifício de cálculo: a → variável incluída por meio de obter a solução. 
Na verdade seu valor é nulo (lado direito = lado esquerdo). 
 
Ex.: Restrições: 7X + 3Y = 13 (a1) 
2X – Y = 2 (a2) 
Logo: 
7X + 3Y + 1a1 + 0a2 =13 
2X – Y + 0a1 + 1a2 = 2 
 
Função objetivo: usar coeficientes negativos de grande valor absoluto: - M 
 (M de grande valor absoluto). 
 
 
 
 
 
 
Ex.: Maximizar 12X + 5Y Maximizar 12X + 5Y - M1a1 –M2a2 
 
Obs.: a1, a2, ..., → depende do número de restrições tipo (=); 
 Usar: M1 = M2 = .... = M (facilitará os cálculos). 
 
f.2) Restrição do tipo (≥≥≥≥): (D. M. – pág. 65) 
 
Usam-se variáveis artificiais (ou fictícias, ou fantasmas) a e variáveis de 
folga S (as últimas com sinais negativos). 
 
Ex.: Restrições: 3X + 2Y ≥ 18 
 
3X + 2Y – 1S1 + 1a1 = 18 
 
Este procedimento assegura que as variáveis fictícias 
não participarão da solução. (D. M. – pág 64) 
-S: o que falta no lado direito para igualar 
ao lado esquerdo. Daí o sinal (-). 
 3X + 2Y + 1a1 = 18 +S1 
 3X + 2Y – S1 + 1a1 = 18 
 
 
 53
Função objetivo: usam-se variáveis de folga e artificiais (com coeficiente 
nulo e com coeficiente negativo de grande valor absoluto (-M), 
respectivamente). 
 
Ex.: Minimizar Z = 4X + 3Y 
 
 
 Maximizar (-Z) = - 4X - 3Y 
 Maximizar (-Z) = - 4X - 3Y - 0S1 - Ma1 
 
Obs.: a1, a2, ..., 
 S1, S2, ..., 
 
Exemplos: (P. O. –pág. 60) 
Maximizar Z = X + Y + Z 
Sujeito a: 2X + Y – Z ≤ 10 (variável de folga: S1) 
 X + Y + 2Z ≥ 20 (variável folga (-): -S2 / fict.: a2) 
 2X + Y + 3Z = 60 (variável fictícia: a3) 
 X, Y, Z ≥ 0 (cond. não negatividade) 
 
Problema Equivalente: 
Maximizar Z = X + Y + Z + 0S1 – 0S2 – M2a2 – M3a3 
Sujeito a: 2X + Y – Z + S1 = 10X + Y + 2Z – S2 + a2 = 20 
 2X + Y + 3Z + a3 = 60 
 X, Y, Z ≥ 0 (cond. não negatividade) 
 S1, S2, a2, a3 ≥ 0 (cond. não negatividade) 
 
À medida que a função Z é maximizada, as variáveis a2 e a3 deixam a base 
devido ao grande valor de seus coeficiente M2 e M3, respectivamente. 
 
 
 
 
 
Para montagem do quadro do Simplex, tem-se: 
Maximizar L = X + Y + Z + 0S1 – 0S2 – M2a2 – M3a3 
Sujeito a: 2X + Y – Z + S1 + 0S2 + 0a2 + 0a3 = 10 
 X + Y + 2Z + 0S1 – S2 + a2 + 0a3 = 20 
 2X + Y + 3Z + 0S1 + 0S2 + 0a2 + a3 = 60 
 X, Y, Z ≥ 0 (cond. não negatividade) 
→ dependem do número de restrições tipo (≥). 
Obs.: a2 = a3 = zero, linha (C-L): C - L → -M + kM 
 (-M) (-kM) (kM > M) 
Variável correspondente a kM entra na base. 
 
 54
 S1, S2, a2, a3 ≥ 0 (cond. não negatividade) 
 
 Usar na resolução: M1 = M2 = .... = M (facilitará os cálculos). 
 
g) Problema de solução Ilimitada: (P. O. – pág. 73) 
 Ocorre quando a variável que entra na base não possui em sua coluna 
nenhum coeficiente positivo. Os programas de computadores, neste caso, 
apresentam a última solução básica antes que a solução se torne ilimitada. 
 
Exercícios: resolvidos e propostos, quando se têm problemas abordados nos casos speciais 
(item 2.5.1). 
 
Daniel Moreira: (pág. 65) - exercícios resolvidos; (pág. 71) - exercícios propostos. 
 
Medeiros (P. O.) – exercícios resolvidos, principalmente para restrições do tipo (=) e (≥). 
 
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.

Outros materiais