PO D Met M e Met W 2013.2

Prévia do material em texto

Pesquisa Operacional . 
 Método de M Grande. 
 Método da Função Objetiva Artificial W. 
55 
PO - PESQUISA OPERACIONAL 
 Continuação 
Profa. Léa Benatti 
2.5.2 – Solução de um Modelo Geral de Programação Linear pelo Método 
Simplex (P. O. – pág. 61) 
 
Retorno ao Modelo Original: 
- Método do M Grande; 
- Método da Função Objetiva Artificial W. 
 
O retorno é realizado com a eliminação das “variáveis artificiais” e a 
manutenção da solução básica. 
 
a) Método de M Grande 
 
M →→→→ coeficiente de grande valor absoluto (usado “negativo” na função 
objetivo). 
 
À medida que a função objetivo Z é maximizada, as variáveis artificiais (ou 
fictícias) deixam a base devido ao grande valor de M. 
 
Resolução do Problema que envolve Variáveis Artificiais 
 (P. O. – pág. 66 (Obs.)) 
a) Eliminar as variáveis artificiais, garantindo o retorno ao problema original: 
 
� Escolher para entrar na base uma variável com qualquer coeficiente na 
linha (C-Z), desde que a entrada dessa variável provoque a saída de uma 
variável artificial. Iniciar o teste com os maiores valores de coeficientes 
positivos na linha (C-Z). 
 
Para isto, procura-se o menor valor positivo de (bj/aij) que será a variável 
artificial básica a ser eliminada. 
Obs.: A variável artificial deixa a base, independente do coeficiente na 
linha (C-Z) da variável que entra. (Ver exemplo na pág. 66 e 67 – P. O.) 
 
� Caso nenhuma das variáveis não básicas possa fazer o papel de expulsar a 
variável artificial da base, o problema não tem solução básica, e, portanto 
não tem solução. 
 
b) Maximizar o objetivo. 
 56
Exercício: Resolver pelo Método de M Grande: (P. O. – pg. 61) 
Maximizar Z = x + y + z 
Sujeito a: 2x + y - z ≤ 10 (var. Folga (+): S1) 
 x + y + 2z ≥ 20 (var. Folga (-): -S2 / artificial: a2) 
 2x + y + 3z = 60 (var. artificial: a3) 
 x, y, z ≥ 0 (condição de não negatividade) 
Solução: 
Transformar inequações lineares em equações lineares. 
Acrescentar variáveis de folga e artificial, conforme a necessidade: 
Maximizar Z = x + y + z + 0S1 - 0S2 – M2a2 – M3a3 
Sujeito a: 
2x + y – z + 1S1 = 10 (S1 = 10; x, y, z =0) 
x + y + 2z + 0S1 - 1S2 + 1a2 = 20 (a2 = 20; x, y, z, S1, S2 = 0) 
2x + y + 3z + 0S1 - 0S2 + 0a2 + 1a3 = 60 (a3 = 60; x, y, z, S1, S2 = 0) 
x, y, z ≥ 0; S1, S2, a2, a3 ≥ 0 (cond. não negatividade) 
 
 
 
 
Variáveis básicas: S1 = 10; a2 = 20; a3 = 30 
Variáveis não básicas: x = y = z = S2 = 0 
 
Obs.: O objetivo das variáveis artificial é de promover uma primeira solução 
e, por isto, compõe a 1a tabela, antes das variáveis de folga. (D. M. – pág. 64) 
 
1a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 1 1 1 0 0 -M -M (L. obj.) 
Ci 
Var. 
Sol. X y z S1 S2 a2 a3 bj bj/aij 
0 S1 2 1 -1 1 0 0 0 10 -10 
-M a2 1 1 2 0 -1 1 0 20 10 
-M a3 2 1 3 0 0 0 1 60 20 
Z -3M -2M -5M 0 M -M -M -80M 
(C-Z) 1+3M 1+2M 1+5M 0 -M 0 0 
 
 
 
 
Onde: M2 = M3 = M Pivô: 2 
Forma genérica do problema 
Variável que entra na base: z. 
Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: x, y, z, 
S2) → F. obj. 
Sai 
(LP) 
 57
x, y, z: variáveis de decisão 
ai: variável artificial (i = 2, 3) 
Sj: variável de folga (j = 1, 2) 
 
Linha Z: inicialmente ≠ de zero (o modelo apresenta variáveis de folgas e 
artificial). 
Valores da linha Z: (ver Tabela 1) 
 
 
 
 
 
 
Valores da linha (C-Z): 
 
 
 
 
Linha (C-Z) apresenta valores positivos: melhorar a solução (solução ótima 
não encontrada). 
 
Montagem da 2a Tabela: 
- Variável que entra na base: z → maior coeficiente na linha (C-Z): 
(1+5M). 
- Variável que sai da base: 
entecorrespond
j
z
b
 
 
20
3
60
:linha3
)a:sai.(varvalormenor:10
2
20
:linha2
)esquecer(10
1
10
:linha1
a
2
a
a
=
=
−=
−
 
 
Linha Principal (LP): Linha da variável que sai (referente a a2). 
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (=2) 
 
Variável x y z S1 S2 a2 a3 bj 
Antiga LP 
Nova LP 
 1 1 2 0 -1 1 0 20 
 1/2 1/2 1 0 -1/2 1/2 0 10 
  
 
 
 
 
 
 
 



x Ci →→→→ Para cada coluna. Coeficientes e lados direitos (bj) das restrições 
 
Somam-se os produtos. 
 - (Valor Z correspondente)
 Para cada coluna. 
 Coefs. da variável na 
função objetivo (F. O.) 
 58
- Determinar novas linhas restantes (linhas S1 e a3): 
 
1a linha: (no = -1) 
Variável X y z S1 S2 a2 a3 bj 
L. Antiga 
NLP x no 
Nova S1 
 2 1 -1 1 0 0 0 10 
1/2(-1) 1/2(-1) 1(-1) 0(-1) -1/2(-1) 1/2(-1) 0(-1) 10(-1) - 
 5/2 3/2 0 1 -1/2 1/2 0 20 
 
3a linha: (no = 3) 
Variável x y z S1 S2 a2 a3 bj 
L. Antiga 
NLP x no 
Nova a3 
 2 1 3 0 0 0 1 60 
1/2(3) 1/2(3) 1(3) 0(3) -1/2(3) 1/2(3) 0(3) 10(3) - 
 1/2 -1/2 0 0 3/2 -3/2 1 30 
- Cálculo da linha Z: (ver tabela 2) 
 
- Cálculo da linha (C-Z): (ver tabela 2) 
 Linha (C-Z) apresenta coefs. > zero (melhorar). 
 
2a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 1 1 0 0 -M -M (L. obj.) 
Ci 
Var. 
Sol. X y z S1 S2 a2 a3 bj bj/aij 
0 S1 5/2 3/2 0 1 -1/2 1/2 0 20 -40 
 1 z ½ 1/2 1 0 -1/2 1/2 0 10 -20 
-M a3 ½ -1/2 0 0 3/2 -3/2 1 30 20 
Z (1/2-M/2) 
(1/2+
M/2) 1 0 
-(1/2+ 
3M/2) 
(1/2+ 
3M/2) -M 
(10-
30M) 
(C-Z) (1/2+M/2) 
(1/2-
M/2) 0 0 
(1/2+
3M/2) 
-(1/2+ 
5M/2) 0 
 
 
 
 
Onde: M2 = M3 = M Pivô: 3/2 = 1,5 
 
Obs.: Até o presente momento: 
Variáveis básicas: Variáveis não básicas: 
S1 = 20 x = y = S2 = a2 = 0 
z = 10 
a3 = 30 Função Z: (10 - 30M) 
Var. que entra na base: S2. 
Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: x, y, 
S2, a2) → F. obj. 
Sai 
(LP) 
 59
Montagem da 3a Tabela: 
Linha (C-Z), maior coeficiente positivo: (1/2+3M/2) – coeficiente da variável 
S2. 
 
- Variável que entra na base: S2 
 
- Variável que sai da base: 
entecorrespond2
j
S
b
 
 
3
a
a
a
asai)(valormenor:20
3
60
3
2
x30
2/3
30
:linha3
)negativovaloresquecer(20)2/1(
10
:linha2
)negativovaloresquecer(40)2/1(
20
:linha1
−+===
−−=
−
−−=
−
 
 
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (= 3/2) 
 
Variável x y z S1 S2 a2 a3 bj 
Antiga LP 
Nova LP 
 1/2 -1/2 0 0 3/2 -3/2 1 30 
 1/3 -1/3 0 0 1 -1 2/3 20 
 
- Determinar novas linhas restantes(linhas S1 e z): 
 
1a linha: (no = -1/2) 
Variável X y z S1 S2 a2 a3 bj 
L. Antiga 
 
NLP x no 
 
Nova S1 
5/2 3/2 0 1 -1/2 1/2 0 20 - 
 
1/3(-1/2) -1/3(-1/2) 0(-1/2) 0(-1/2) 1(-1/2) -1(-1/2) 2/3(-1/2) 20(-1/2) 
 
8/3 4/3 0 1 0 0 1/3 30 
 
2a linha: (no = -1/2) 
Variável X y z S1 S2 a2 a3 bj 
L. Antiga 
 
NLP x no 
 
Nova z
 
1/2 1/2 1 0 -1/2 1/2 0 10 - 
 
1/3(-1/2) -1/3(-1/2) 0(-1/2) 0(-1/2) 1(-1/2) -1(-1/2) 2/3(-1/2) 20(-1/2) 
 
2/3 1/3 1 0 0 0 1/3 20 
 
 60
- Cálculo da linha Z: (ver tabela 3) 
- Cálculo da linha (C-Z): (ver tabela 3) 
 Linha (C-Z) apresenta coef. > zero (melhorar). 
 
3a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 1 1 0 0 -M -M (L. obj.) 
Ci 
Var. 
Sol. X y z S1 S2 a2 a3 bj bj/aij 
0 S1 8/3 4/3 0 1 0 0 1/3 30 45/2 
 1 z 2/3 1/3 1 0 0 0 1/3 20 60 
 0 S2 1/3 -1/3 0 0 1 -1 2/3 20 -60 
Z 2/3 1/3 1 0 0 0 1/3 20 
 (C-Z) 1/3 2/3 0 0 0 -M -(M+1/3) 
 
 
 
 
 
Onde: M2 = M3 = M Pivô: 4/3 ≅≅≅≅ 1,333 
 
Obs.: Até o presente momento: 
Variáveis básicas: Variáveis não básicas: 
S1 = 30 x = y = a2 = a3 = 0 
 z = 20 
S2 = 20 Função Obj.: Z = 20 
 
Neste estágio, abandonar as variáveis artificiais, pois são nulas (não básicas) e 
não voltam mais para a base devido ao grande valor de M (negativo). 
 
Montagem da 4a Tabela: 
 
Linha (C-Z), maior coeficiente positivo: 2/3 – coeficiente da variável y. 
 
- Variável que entra na base: y 
 
- Variável que sai da base: 
entecorrespond
j
y
b
 
 
Var. que entra na base: y. 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: x, y, a2, a3) → F. obj. 
Sai 
(LP) 
 61
 
).negativovalor(esquecer:60)3/1(
20
:linha3
603x20)3/1(
20
:linha2
)LP(Ssai
2
45
4
90
4
3x30
)3/4(
30
:linha1
a
a
1
a
−=
−
==
−===
 
 
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (= 4/3) 
 
Variável x y z S1 S2 bj 
Antiga LP 
Nova LP 
 8/3 4/3 0 1 0 30 
 2 1 0 3/4=0,75 0 45/2=22,5 
 
- Determinar novas linhas restantes (linhas z e S2): 
 
2a linha: (no = 1/3) 
Variável X y z S1 S2 bj 
L. Antiga 
NLP x no 
Nova z
 
2/3 1/3 1 0 0 20 - 
2(1/3) 1(1/3) 0(1/3) 3/4(1/3) 0(1/3) 45/2(1/3) 
 0 0 1 -(3/12)= -0,25 0 75/6= 12,5 
 
3a linha: (no = -1/3) 
 
Variável X y z S1 S2 bj 
L. Antiga 
NLP x no 
Nova S2 
1/3 -1/3 0 0 1 20 - 
2(-1/3) 1(-1/3) 0(-1/3) 3/4(-1/3) 0(-1/3) 45/2(-1/3) 
 1 0 0 3/12 = -0,25 1 165/6= 27,5 
 
- Cálculo da linha Z: (ver tabela 4) 
 
- Cálculo da linha (C-Z): (ver tabela 4) 
 
Linha (C-Z) apresenta coefs. ≤ zero (Solução ótima). 
 
 
 
 
 62
4a Tabela: 
 
 Variáveis de decisão (título da tabela) 
 1 1 1 0 0 (Linha objetivo) 
Ci 
V. na 
Solução x y z S1 S2 bj bj/aij 
1 y 2 1 0 ¾ 0 45/2 
1 z 0 0 1 -3/12 0 75/6 
0 S2 1 0 0 3/12 1 165/6 
 Z 2 1 1 ½ 0 210/6 
 (C-Z) -1 0 0 -1/2 0 
 
 
 
 
� A solução ótima não é múltipla: coefs. de variáveis não básicas 
(x, S1) são diferentes de zero. 
 
Solução ótima do modelo: 
Variáveis básicas: Variáveis não básicas: F. Objetivo: 
y = 45/2 = 22,5 x = S1 = 0 Z = 210/6 = 35 
z = 75/6 = 12,5 
S2 = 165/6 = 27,5 
 
OBS.: Na primeira parte do modelo (até a tabela 3), que levou à eliminação 
das variáveis artificiais ai, o que se pretendia não era maximizar o objetivo, e 
sim eliminar as variáveis artificiais, retornando assim ao problema original. 
 
b) Método da Função Objetiva Artificial W (P. O. – pág. 67, Puccini – pág. 83) 
Eqs. tipo: (≥) e (=) → Variável de folga e artificial. 
 
Função Objetiva Artificial W: Soma das variáveis artificiais (ou fictícias). 
W = a1 + a2 + ... + an 
Sendo: ai ≥ 0, i = 1, ..., n → função de não negatividade. 
 
� Assim, achar o mínimo de W igual a zero: exclui-se da base a variável 
artificial ai (Sendo W = 0 → ai será nula). 
 
Quando as variáveis artificiais forem não básicas, isto é, 
 a1 = a2 = ... = an = 0 e W = 0 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: x, S1) → F. obj. 
 63
as variáveis artificiais e função artificial podem ser abandonadas. O novo 
objetivo será otimizar a função objetiva original. 
 
Observação: 
Caso a Função Objetiva Artificial W apresente Solução ótima e valor não 
nulo, as variáveis artificiais não serão todas nulas e o modelo original não 
apresentará então uma Solução básica. Neste caso, o problema não tem 
Solução . 
 
Exercício 1 
Método da Função Objetiva Artificial W (P. O. – pág. 67) 
 
Maximizar Z = x + y + z 
 Sujeito a: 2x + y – z ≤ 10 (var. folga: S1) 
 x + y + 2z ≥ 20 (var. folga (-): -S2 / artificial: a2) 
 2x + y + 3z = 60 (var. artificial: a3) 
 x ≥ 0, y ≥ 0, z ≥ 0 (cond. não negatividade) 
 
Solução: 
Minimizar W = a2 + a3 
Sujeito a: 2x + y – z + 1S1 = 10 (1a restrição) 
 x + y + 2z – 1S2 + 1a2 = 20 (2a restrição) 
 2x + y + 3z + 1a3 = 60 (3a restrição) 
 x, y, z ≥ 0; S1, S2 ≥ 0; a2, a3 ≥ 0 (cond. não negatividade) 
 
2a restrição: a2 = 20 – x – y – 2z + S2 
3a restrição: a3 = 60 – 2x – y – 3z 
 
 Substituindo a2 e a3 em W: 
Minimizar W = - 3x – 2y – 5z + S2 + 80 
 
Problema de Problema de 
Minimizar Maximizar 
 
Maximizar (-W) = 3x + 2y + 5z –1S2 – 80 
Maximizar (-W + 80) = 3x + 2y + 5z – 1S2 
 
OBS.: Deve-se achar: W = 0 
 
 Minimizar W = Maximizar (-W) 
x (-1) 
 64
 Como W = 0, W = -W = 0 
 
1a Tabela: (Inicialmente, trabalha-se com a função W) 
 Variáveis de decisão (título da tabela) 
 3 2 5 0 -1 0 0 80 (L. obj.) 
Ci 
Var. 
Sol. x y z S1 S2 a2 a3 bj bj/aij 
0 S1 2 1 -1 1 0 0 0 10 -10 
 0 a2 1 1 2 0 -1 1 0 20 10 
 0 a3 2 1 3 0 0 0 1 60 20 
W 0 0 0 0 0 0 0 0 
(C-W) 3 2 5 0 -1 0 0 80 
 
 
 
 
 
Pivô: 2 
Onde: x, y, z: variáveis de decisão 
ai: variáveis de artificiais (i = 2, 3) 
Sj: variáveis de folga (j = 1, 2) 
 
OBS.: 
x + y + 2z ≥ 20 (2a restrição) 
x + y + 2z = 20 + 1S2 (variável de folga: transforma inequação em equação) 
 
S2: quantidade que falta do lado direito para 
seigualar ao esquerdo. 
 
x + y + 2z - 1S2 = 20 (Prioridade de entrar na base: S2 – variável de folga) 
 Então, S2 = -20 (x = y = z = 0 → variáveis não básicas) 
S2: base negativa → não pode (cond. não negativa deve ser obedecida 
sempre). 
 
Como solucionar: usar, além de variável de folga, variável artificial. Assim, 
x + y + 2z – 1S2 + 1a2 = 20 (vars. de folga e artificial: transformam ineq. em eq.). 
 
Variável artificial é usada, com prioridade de entrar na base. Deve-se, 
neste caso, buscar valor nulo para a2, retirando-a da base através de 
programação linear (variável a2 sai da base, sendo a2 = 0). 
Variável que entra na base: z. 
Linha (C-W): em termos de variáveis não 
básicas (neste caso: x, y, z, S2) → F. obj. 
Sai 
(LP) 
Termo independente (bj): 
não entra na análise da 
variável que entra na base. 
 65
Valores da linha W: (ver Tabela 1) 
 
 
 
 
 
 
Valores da linha (C-W): (ver Tabela 1) 
 
 
 
 
 
Linha (C-W) apresenta valores positivos, portanto melhorar a solução 
(solução ótima não encontrada). 
 
Montagem da 2a Tabela: 
- Variável que entra na base: z → maior coeficiente na linha (C-W): (5). 
 
- Variável que sai da base: 
entecorrespond
j
z
b
 
20
3
60
:linha3
)a:sai.(varvalormenor:10
2
20
:linha2
)esquecer(10
1
10
:linha1
a
2
a
a
=
=
−=
−
 
 
Linha Principal (LP): Linha da variável que sai (referente a a2). 
 
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (= 2) 
 
Variável x y z S1 S2 a2 a3 bj 
Antiga LP 
Nova LP 
 1 1 2 0 -1 1 0 20 
 1/2 1/2 1 0 -1/2 1/2 0 10 
 
 
 
  
 
 
 
 
 
 
 



x Ci →→→→ Para cada coluna. Coeficientes e lados direitos (bj) das restrições e F. obj. 
 
Soma-se os produtos. 
 - (Valor W correspondente) 
 
 Para cada coluna.






 Coefs. da variável na 
função objetivo (F. O.) 
 66
- Determinar novas linhas restantes (linhas S1 e a3): 
 
1a linha: (no = -1) 
Variável x y z S1 S2 a2 a3 bj 
L. Antiga 
NLP x no 
Nova S1
 
 2 1 -1 1 0 0 0 10 - 
1/2(-1) 1/2(-1) 1(-1) 0(-1) -1/2(-1) 1/2(-1) 0(-1) 10(-1) 
5/2=2,5 3/2=1,5 0 1 -1/2 1/2 0 20 
 
3a linha: (no = 3) 
Variável x y z S1 S2 a2 a3 bj 
L. Antiga 
NLP x no 
Nova a3
 
 2 1 3 0 0 0 1 60 - 
1/2(3) 1/2(3) 1(3) 0(3) -1/2(3) 1/2(3) 0(3) 10(3) 
 1/2 -1/2 0 0 3/2=1,5 -3/2 1 30 
 
- Cálculo da linha W: (ver tabela 2) 
(Coefs. restrições e bj) x Ci 
Soma (para cada coluna) 
 
- Cálculo da linha (C-W): (ver tabela 2) 
(Coefs. da F. Obj.) – (Wcorrespondente) (para cada coluna) 
 
Linha (C-W) apresenta coefs. > zero (melhorar). 
 
2a Tabela: 
 Variáveis de decisão (título da tabela) 
 3 2 5 0 -1 0 0 80 (L. obj.) 
Ci 
Var. 
Sol. x y z S1 S2 a2 a3 bj bj/aij 
0 S1 5/2 3/2 0 1 -1/2 1/2 0 20 -40 
 5 z 1/2 1/2 1 0 -1/2 1/2 0 10 -20 
 0 a3 ½ -1/2 0 0 3/2 -3/2 1 30 20 
W 5/2 5/2 5 0 -5/2 5/2 0 50 
(C-W) ½ -1/2 0 0 3/2 -5/2 0 30=W 
 
 
 
 
 
 
Var. que entra na base: S2. 
Linha (C-W) é descrita em termos de variáveis 
não básicas (neste caso: x, y, S2, a2) → F. obj. 
Sai 
(LP) 
Pivô: 3/2 = 1,5 
 
 67
Obs.: Até o presente momento: 
Variáveis básicas: Variáveis não básicas: 
S1 = 20 x = y = S2 = a2 = 0 
z = 10 
a3 = 30 Função obj. Artificial: W = 30 
 
Montagem da 3a Tabela: 
Linha (C-W), maior coeficiente positivo: (3/2) – coeficiente da variável S2 
(desconsiderar coeficiente do termo independente). 
 
- Variável que entra na base: S2 
 
- Variável que sai da base: 
entecorrespond2
j
S
b
 
 
3
a
a
a
asai)(valormenor:20
3
60
3
2x30
2/3
30
:linha3
)negativovaloresquecer(20)2/1(
10
:linha2
)negativovaloresquecer(40)2/1(
20
:linha1
−+===
−−=
−
−−=
−
 
 
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (= 3/2) 
 
Variável x y z S1 S2 a2 a3 bj 
Antiga LP 
Nova LP 
 1/2 -1/2 0 0 3/2 -3/2 1 30 
 1/3 -1/3 0 0 1 -1 2/3 20 
 
- Determinar novas linhas restantes (linhas S1 e z): 
 
1a linha: (no = -1/2) 
Variável x y z S1 S2 a2 a3 bj 
L. Antiga 
 
NLP x no 
 
Nova S1 
5/2 3/2 0 1 -1/2 1/2 0 20 - 
 
1/3(-1/2) -1/3(-1/2) 0(-1/2) 0(-1/2) 1(-1/2) -1(-1/2) 2/3(-1/2) 20(-1/2) 
 
8/3=2,67 4/3=1,33 0 1 0 0 1/3=0,33 30 
 
 68
2a linha: (no = -1/2) 
Variável x y z S1 S2 a2 a3 bj 
L. Antiga 
 
NLP x no 
 
Nova z
 
1/2 1/2 1 0 -1/2 1/2 0 10 - 
 
1/3(-1/2) -1/3(-1/2) 0(-1/2) 0(-1/2) 1(-1/2) -1(-1/2) 2/3(-1/2) 20(-1/2) 
 
2/3=0,67 1/3=0,33 1 0 0 0 1/3=0,33 20 
 
- Cálculo da linha W: (ver tabela 3) 
 
 
 
- Cálculo da linha (C-W): (ver tabela 3) 
 Linha (C-W) apresenta coef. ≤ zero (Solução ótima em W). 
 
3a Tabela: 
 Variáveis de decisão (título da tabela) 
 3 2 5 0 -1 0 0 80 (L. obj.) 
Ci 
Var. 
Sol. x y z S1 S2 a2 a3 bj bj/aij 
0 S1 8/3 4/3 0 1 0 0 1/3 30 
5 z 2/3 1/3 1 0 0 0 1/3 20 
-1 S2 1/3 -1/3 0 0 1 -1 2/3 20 
W 3 2 5 0 -1 1 1 80 
(C-W) 0 0 0 0 0 -1 -1 0=W 
 
 
 
 
 
 
Obs.: Até o presente momento: 
Variáveis básicas: Variáveis não básicas: 
S1 = 30 x = y = a2 = a3 = 0 
 z = 20 
S2 = 20 Função Obj.: W = 0 
 
 
Abandonar variáveis artificiais (a2 e a3) da tabela e continuar os cálculos com 
a função objetivo original Z. 
 
Coefs. da linha (C-W) ≤ 0 → Solução ótima em W. 
 
Tem-se uma solução básica formada pelas variáveis originais. 
Observar que, neste 
estágio, a2 e a 3 são 
nulas e W = 0. 
↓ 
Mínimo valor de W 
é encontrado (zero). 
W = 0 → Mínimo de W é encontrado. 
 69
4a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 1 1 0 0 (L. obj.) 
Ci 
Var. 
Sol. x y z S1 S2 bj bj/aij 
0 S1 8/3 4/3 0 1 0 30 45/2 
 1 z 2/3 1/3 1 0 0 20 60 
 0 S2 1/3 -1/3 0 0 1 20 -60 
Z 2/3 1/3 1 0 0 20 
 (C-Z) 1/3 2/3 0 0 0 
 
 
 
 
 
Linha Z: (Coef., bj x Ci), Soma 
Ci 
0 
1 
0 
 x y z S1 S2 bj 
8/3(0) 4/3(0) 0(0) 1(0) 0(0) 30(0) 
2/3(1) 1/3(1) 1(1) 0(1) 0(1) 20(1) + 
1/3(0) -1/3(0) 0(0) 0(0) 1(0) 20(0)Z 2/3 1/3 1 0 0 20 
 
OBS.: Neste estágio, Ci das variáveis básicas correspondem aos coeficientes 
da função objetiva original (Z). 
 
Linha (C-Z): Coeficientes da F. obj. original Z. 
Variáveis 
Coef. F. O. 
Z 
 x y z S1 S2 
 1 1 1 0 0 - 
2/3 1/3 1 0 0 
(C-Z) 1/3 2/3 0 0 0 
 
y: Variável de maior coeficiente positivo – entra na base. 
 
Obs.: Até o presente momento: (ver Tabela 4) 
Variáveis básicas: Variáveis não básicas: 
S1 = 30 x = y = 0 
z = S2 = 20 Função Obj.: Z = 20 
 
L. P. → referente a variável S1 → Pivô = 4/3 
 
Var. que entra na base: y. 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: x, y) → F. obj. 
Sai 
(LP) 
Pivô: 4/3 ≅≅≅≅ 1,333 
 
 70
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (= 4/3) 
 
Variável x y z S1 S2 bj 
Antiga LP 
Nova LP 
 8/3 4/3 0 1 0 30 
 2 1 0 ¾=0,75 0 45/2=22,5 
 
- Determinar novas linhas restantes (linhas z e S2): 
 
2a linha: (no = 1/3) 
Variável x y z S1 S2 bj 
L. Antiga 
NLP x no 
Nova z
 
2/3 1/3 1 0 0 20 - 
2(1/3) 1(1/3) 0(1/3) 3/4(1/3) 0(1/3) 45/2(1/3) 
 0 0 1 -(3/12)= -0,25 0 75/6= 12,5 
 
3a linha: (no = -1/3) 
Variável x y z S1 S2 bj 
L. Antiga 
NLP x no 
Nova S2
 
1/3 -1/3 0 0 1 20 - 
2(-1/3) 1(-1/3) 0(-1/3) 3/4(-1/3) 0(-1/3) 45/2(-1/3) 
 1 0 0 3/12 = -0,25 1 165/6= 27,5 
 
- Cálculo da linha Z: (ver tabela 5) 
 
Linha Z: (Coef., bj x Ci), Soma 
Ci 
1 
1 
0 
 x y z S1 S2 bj 
 2(1) 1(1) 0(1) 3/4(1) 0(1) 45/2(1) 
 0(1) 0(1) 1(1) -3/12(1) 0(1) 75/6(1) + 
 1(0) 0(0) 0(0) 3/12(0) 1(0) 165/6(0) 
Z 2 1 1 1/2 0 210/6 
 
- Cálculo da linha (C-Z): (ver tabela 5) 
 
Linha (C-Z): Coeficientes da F. obj. original Z. 
Variáveis 
Coef. F. O. 
Z 
 x y z S1 S2 
 1 1 1 0 0 - 
 2 1 1 1/2 0 
(C-Z) -1 0 0 -1/2 0 
 
Linha (C-Z): coeficientes ≤ zero (Solução ótima). 
 
Não é caso de solução múltipla: 
Variáveis não básicas: x, S1 →→→→ coeficientes ≠ zero. 
 71
5a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 1 1 0 0 (Linha objetivo) 
Ci 
V. na 
Solução x y z S1 S2 bj bj/aij 
1 Y 2 1 0 3/4 0 45/2 
1 z 0 0 1 -3/12 0 75/6 
0 S2 1 0 0 3/12 1 165/6 
 Z 2 1 1 1/2 0 210/6 
 (C-Z) -1 0 0 -1/2 0 
 
 
 
 
� A solução ótima não é múltipla: coefs. de variáveis não básicas 
(x, S1) são diferentes de zero. 
 
Solução ótima do modelo: 
Variáveis básicas: Variáveis não básicas: F. Objetivo: 
y = 45/2 = 22,5 x = S1 = 0,0 Z = 210/6 = 35 
z = 75/6 = 12,5 
S2 = 165/6 = 27,5 
 
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. 
 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: x, S1) → F. obj. 
 72
/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.