PUC-Rio Pesquisa Operacional - PO E Met W e Min 2013.2

Prévia do material em texto

Pesquisa Operacional. 
 Método Fç. Objetiva Artificial W (continuação). 
 Exemplo de Fç Objetivo de Minimização. 
73 
PO - PESQUISA OPERACIONAL 
Profa. Léa Benatti 
 
b) Método da Função Objetiva Artificial W (P. O. – pág. 67, Puccini – pág. 83) 
 (Continuação) 
 
Exercício2 – Método da Função Objetiva Artificial W (Puccini – pág. 83) 
 
Maximizar Z = 5x + 2y 
 
 Sujeito a: x ≤ 3 (var. folga: S1) 
 y ≤ 4 (var. folga: S2) 
 x + 2y ≥ 9 (var. folga (-): -S3 / artificial: a3) 
 x ≥ 0, y ≥ 0 (cond. não negatividade) 
 
Solução: 
Minimizar W = a3 
 
 Sujeito a: x + 1S1 = 3 (1a restrição) 
 y + 1S2 = 4 (2a restrição) 
 x + 2y – 1S3 + 1a3 = 9 (3a restrição) 
 
 x, y ≥ 0; S1, S2, S3 ≥ 0; a3 ≥ 0 (cond. não negatividade) 
 
3a restrição: a3 = 9 – x – 2y + 1S3 
 
Substituindo a3 em W: 
Minimizar W = 9 - x – 2y + 1S3 
 
Problema de Minimizar Problema de Maximizar 
 
Maximizar (-W) = - 9 + x + 2y –1S3 
Maximizar (-W + 9) = x + 2y – 1S3 
 
OBS.: Deve-se achar: W = 0 
 
 Minimizar W = Maximizar (-W) 
 Como W = 0,W = -W = 0 
 
 
 
X (-1) 
 
 74
1a Tabela: (Inicialmente, trabalha-se com a função W) 
 Variáveis de decisão(título da tabela) 
 1 2 0 0 -1 0 9 (L. obj.) 
Ci 
Var. 
Sol. X y S1 S2 S3 a3 bj bj/aij 
0 S1 1 0 1 0 0 0 3 3/0=ind 
 0 S2 0 1 0 1 0 0 4 4/1=4 
 0 a3 1 2 0 0 -1 1 9 9/2=4,5 
W 0 0 0 0 0 0 0 
(C-W) 1 2 0 0 -1 0 9 
 
 
 
 
 
 
Pivô: 1 
 
Onde:x, y, : variáveis de decisão 
ai: variável de fictícia (i = 2, 3) 
Sj:variável de folga (j = 1, 2) 
 
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). 
 
 
 
  
 
 
 
 
 
 
 



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.) 
Variável que entra na base: y. 
Linha (C-W): em termos de variáveis não 
básicas (neste caso: x, y, S3)→→→→ F. obj. 
Sai 
(LP) 
Termo independente (bj): 
não entra na análise da 
variável que entra na base. 
 
 75
Montagem da 2a Tabela: 
- Variável que entra na base: y→→→→ maior coeficiente na linha (C-W): (2). 
 
-Variável que sai da base: 
entecorrespond
j
y
b
→→→→ S2 
 
Linha Principal (LP): Linha da variável que sai (referente a S2). 
 
OBS.: Observar que está presente na base uma variável artificial (ou fictícia) 
a3. Verificar se a entrada da variável de segundo (ou terceiro, ou quarto, ...) 
maior coeficiente positivo da linha (C-W) retira a variável artificial da base. 
Caso nenhum destes valores eliminarem a variável artificial, voltar à situação 
inicial entrando na base com a variável de maior coeficiente positivo, o que 
significa que a variável artificial sairá da base em um passo posterior. Esta 
verificação implica em eliminar passos de cálculo, possibilitando trabalhar 
com menor número de tabelas e menor exposição a erros. 
 Neste exercício, após verificação abordada acima, conclui-se que a3 
será eliminada posteriormente. 
 
- Determinar os valores da novalinhaprincipal (NLP): 
(Linha Antiga) ÷ Pivô (=1) 
 
Variável X y S1 S2 S3 a3 bj 
Antiga LP 
Nova LP 
0 1 0 1 0 0 4 
0 1 0 1 0 0 4 
 
-Determinar novas linhas restantes (linhas S1 e a3): 
 
1a linha: (no = 0) 
Variável X y S1 S2 S3 a3 bj 
L. Antiga 
NLP x no 
Nova S1
 
1 0 1 0 0 0 3 - 
0(0) 1(0) 0(0) 1(0) 0(0) 0(0) 4(0) 
 1 0 1 0 0 0 3 
 
3a linha: (no = 2) 
Variável x y S1 S2 S3 a3 bj 
L. Antiga 
NLP x no 
Nova a3
 
1 2 0 0 -1 1 9 - 
0(2) 1(2) 0(2) 1(2) 0(2) 0(2) 4(2) 
 1 0 0 -2 -1 1 1 
 
 76
- Cálculo da linha W:(ver tabela 2) 
 
- Cálculo da linha (C-W): (ver tabela 2) 
 Linha (C-W) apresenta coefs. > zero(melhorar). 
 
2a Tabela: 
 Variáveis de decisão(título da tabela) 
 1 2 0 0 -1 0 9 (L. obj.) 
Ci 
Var. 
Sol. X y S1 S2 S3 a3 bj bj/aij 
0 S1 1 0 1 0 0 0 3 3/1=3 
 2 y 0 1 0 1 0 0 4 4/0=ind 
 0 a3 1 0 0 -2 -1 1 1 1/1=1 
W 0 2 0 2 0 0 8 
(C-W) 1 0 0 -2 -1 0 1=W 
 
 
 
 
 
Obs.: Até o presente momento: 
Variáveis básicas: Variáveis não básicas: 
S1 = 3 x = S2 = S3 = 0 
y= 4 
a3 = 1 Função obj. Artificial: W = 1 
 
a3≠ 0 
W ≠ 0 
 
 
Montagem da 3a Tabela: 
Linha (C-W), maior coeficiente positivo: (1) – coeficiente da variável x 
(desconsiderar coeficiente do termo independente). 
 
-Variável que entra na base: x 
 
-Variável que sai da base: 
entecorrespond
j
x
b
→→→→ a3→→→→ L. P. 
 
Var. que entra na base: x. 
Linha (C-W): descrita em termos de variáveis 
nãobásicas (neste caso: x, S2, S3)→→→→ F. obj. 
Sai 
(LP) 
Pivô:1 
 
Continuar até a função objetivo artificial 
W e a variável a3 ser zero. 
 
 77
 -Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (=1) 
Variável X y S1 S2 S3 a3 bj 
Antiga LP 
Nova LP 
 1 0 0 -2 -1 1 1 
 1 0 0 -2 -1 1 1 
 
-Determinar novas linhas restantes (linhas S1 e z): 
 
1a linha: (no = 1) 
Variável x y S1 S2 S3 a3 bj 
L. Antiga 
NLP x no 
Nova S1
 
1 0 1 0 0 0 3 - 
1(1) 0(1) 0(1) -2(1) -1(1) 1(1) 1(1) 
0 0 1 2 1 -1 2 
 
2a linha: (no = 0) 
Variável X y S1 S2 S3 a3 bj 
L. Antiga 
NLP x no 
Nova z
 
 0 1 0 1 0 0 4 - 
1(0) 0(0) 0(0) -2(0) -1(0) 1(0) 1(0) 
 0 1 0 1 0 0 4 
 
- Cálculo da linha W:(ver tabela 3) 
 (coef., bj x Ci); soma. 
 
- Cálculo da linha (C-W): (ver tabela 3) 
 (Ci Fç. Obj. - Wi), i: coluna 
Linha (C-W) apresenta coef. ≤zero (Solução ótima em W). 
3a Tabela: 
 Variáveis de decisão (título da tabela) 
 1 2 0 0 -1 0 9 (L. obj.) 
Ci 
Var. 
Sol. X y S1 S2 S3 a3 bj bj/aij 
0 S1 0 0 1 2 1 -1 2 
2 y 0 1 0 1 0 0 4 
1 x 1 0 0 -2 -1 1 1 
W 1 2 0 0 -1 1 9 
(C-W) 0 0 0 0 0 -1 0=W 
 
 
 
W = 0 
Coefs. da linha (C-W) ≤ 0 →→→→ Solução ótima em W. 
Tem-se uma solução básica formadapelas variáveis originais. 
(x, y) = (1, 4): 
Pto extremo 
 
 78
Obs.: Até o momento: 
Variáveis básicas: Variáveis não básicas: 
S1 = 2 S2 = S3 = a3 = 0 
 y= 4 
 x= 1 Função Obj.: W = 0 
 
 
 
Abandonar variável artificial a3 e continuar os cálculos com a função objetivo 
original Z. 
 
OBS.: Notar que os coeficientes das variáveis não básicas na linha (C-W) são 
nulos: S2 = S3 = 0. Como se trata de função objetiva artificial W, não é 
necessário procurar outras soluções para encontrar seu mínimo. O que 
se deseja é maximizar Z e somente após encontrar Solução em Z é que 
há a necessidade de verificar se é caso de Solução Múltipla. 
 
4a Tabela: 
 Variáveis de decisão(título da tabela) 
 5 2 0 0 0 (L. obj.) 
Ci 
Var. 
Sol. x y S1 S2 S3 bj bj/aij 
0 S1 0 0 1 2 1 2 2/2=1 
 2 y 0 1 0 1 0 4 4/1=4 
 5 x 1 0 0 -2 -1 1 1/(-2)<0 
Z 5 2 0 -8 -5 13 
 (C-Z) 0 0 0 8 5 
 
 
 
 
 
Linha Z: (Coef., bj x Ci), Soma (Ver tabela 4) 
Ci 
0 
2 
5 
 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(5) 0(5) 0(5) -2(5) -1(5) 1(5) 
Z 5 2 0 -8 -5 13 
 
Observar que a3 é 
variável não básica 
(a3 =0) e W = 0. 
↓ 
Mínimo valor de W 
é encontrado (zero). 
Var. que entra na base: S2. 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: S2, S3)→→→→ F. obj. 
Sai 
(LP) 
Pivô:2 
 
 
 79
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. (Ver tabela 4) 
Variáveis 
Coef. F. O. 
Z 
 x y S1 S2 S3 
 5 2 0 0 0 - 
 5 2 0 -8 -5 
(C-Z) 0 0 0 8 5 
 
S2: 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 = 2 S2 = S3 = 0 
 y= 4 
 x= 1 Função Obj.: Z = 13 
 
Montagem da 5a Tabela: 
L. P. →→→→ referente a variável S1 →→→→ Pivô = 2 
 
-Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (=2) 
 
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 (linhas y e x): 
 
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 
 
 80
 
- Cálculo da linha Z: (ver tabela 5) 
 
Linha Z:(Coef., bj x Ci), Soma 
 
- Cálculo da linha (C-Z): (ver tabela 5) 
 
Linha (C-Z): coeficiente > zero (melhorar). 
 
5a Tabela: 
 Variáveis de decisão(título da tabela) 
 5 2 0 0 0 (Linha objetivo) 
Ci 
V. na 
Solução x y S1 S2 S3 bj bj/aij 
0 S2 0 0 1/2 1 1/2 1 1/(1/2) = 2 
2 y 0 1 -1/2 0 -1/2 3 3/(-1/2) < 0 
5 x
 
1 0 1 0 0 3 3/0 = ind. 
Z 5 2 4 0 -1 21 
(C-Z) 0 0 -4 0 1 
 
 
 
 
 
Obs.:Até o momento: (ver Tabela 5) 
 
Variáveis básicas: Variáveis não básicas: 
S2 = 1 S1 = S3 = 0 
x = y= 3 Função Obj.: Z = 21 
 
Montagem da 6a Tabela: 
 
 Variável que entra na base:S3 
 Variável que sai da base:S2 →→→→ L. P. 
 
- Determinar os valores da nova linha principal (NLP): 
(Linha Antiga) ÷ Pivô (=1/2) 
 
Variável x y S1 S2 S3 bj 
Antiga LP 
Nova LP 
 0 0 1/2 1 1/2 1 
 0 0 1 2 1 2 
 
Var. que entra na base: S3. 
Linha (C-Z) é descrita em termos de variáveis 
não básicas (neste caso: S1, S3)→ F. obj. 
Sai 
(LP) 
Pivô:1/2 
 
 
 81
 
- Determinar novas linhas restantes (linhas y e x): 
2a linha: (no = -1/2) 
Variável x y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova y
 
 0 1 -1/2 0 -1/2 3 - 
0(-1/2) 0(-1/2) 1(-1/2) 2(-1/2) 1(-1/2) 2(-1/2) 
 0 1 0 1 0 4 
 
3a linha: (no = 0) 
Variável x y S1 S2 S3 bj 
L. Antiga 
NLP x no 
Nova x
 
 1 0 1 0 0 3 - 
0(0) 0(0) 1(0) 2(0) 1(0) 2(0) 
 1 0 1 0 0 3 
 
- Cálculo da linha Z: Linha Z: (Coef., bj x Ci), Soma (ver tabela 6) 
 
- Cálculo da linha (C-Z): (ver tabela 6) 
Linha (C-Z): coeficiente ≤ zero (Solução Ótima). 
 
6a Tabela: 
 Variáveis de decisão(título da tabela) 
 5 2 0 0 0 (Linha objetivo) 
Ci 
V. na 
Solução x y S1 S2 S3 bj bj/aij 
0 S3 0 0 1 2 1 2 
2 y 0 1 0 1 0 4 
5 x
 
1 0 1 0 0 3 
 Z 5 2 5 2 0 23 
 (C-Z) 0 0 -5 -2 0 
 
 
 
 
� Coeficientes de S1 e S2 (variáveis não básicas)na linha (C-Z) 
≠ zero →→→→ Solução não é múltipla. 
 
Solução ótima do modelo: 
Variáveis básicas: Variáveis não básicas: F. Objetivo: 
S3= 2 S1 = S2 = 0 Z = 23 
 y= 4 
 x= 3 
Pto (x, y) = (3, 4) 
Linha (C-Z): descrita em termos de variáveis não básicas (neste 
caso: S1, S2) →→→→ F. obj. 
 
 82
Solução ótima corresponde ao ponto (x, y) = (3, 4) →→→→ ponto extremo (vértice) 
da zona permissível em caso de se usar método gráfico. 
 
Problemas Propostos: 
 
Exercício1(Puccini – pág. 86 – exercício resolvido) 
Achar, pelo processo da função objetiva artificial, todas as Soluções 
compatíveis básicas do seguinte sistema de equações: 
 3X1 + 2X2 – 5X3 = 6 (var. artificial) 
 4X1 +7X2 + 4X3 = 9 (var. artificial) 
X1 ≥ 0; X2 ≥ 0; X3 ≥ 0 (condições não negativas) 
 
Solução: 
3X1 + 2X2 – 5X3 + a1 = 6 
4X1 +7X2 + 4X3 + a2 = 9 
 X1 ≥ 0; X2 ≥ 0; X3 ≥ 0 
 
W = a1 + a2 ; a1 = 6 - 3X1 – 2X2 + 5X3 
 a2 = 9 - 4X1 – 7X2 - 4X3 
W = 15 – 7X1 – 9X2 + X3 
 
Minimizar W = 15 – 7X1 – 9X2 + X3 (x (-1) →→→→ maximizar W) 
 
Maximizar (-W) = -15 + 7X1 + 9X2 – X3 
Maximizar (-W) +15 = 7X1 + 9X2 – X3 
 
1a Tabela: 
 Variáveis de decisão(título da tabela) 
 7 9 -1 0 0 15 (L. objetivo) 
Ci 
V. na 
Solução X1 X2 X3 a1 a2 bj bj/aij 
0 a1 3 2 -5 1 0 6 6/2 = 3 
0 a2 4 7 4 0 1 9 9/7 = 1,29 
W 0 0 0 0 0 0 
(C-W) 7 9 -1 0 0 15 
 
 
 
 
 
Checar ai: a1 = a2 = 0 
 W = 0 
Var. que entra na base: a2. 
Linha (C-W): descrita emtermos de variáveis não básicas 
(neste caso: X1, X2, X3) → F. obj. 
Sai 
(LP) 
Pivô: 7 
 
 
 83
Nova Linha Principal: (L. antiga) ÷ pivô (= 7) 
 
Variável X1 X2 X3 a1 a2 bj 
Antiga LP 
Nova LP 
 4 7 4 0 1 9 
 4/7 1 4/7 0 1/7 9/7 
 
Nova Linha a1:(Linha antiga) – (NLP x no) 
1a linha: (no = 2) 
Variável X1 X2 X3 a1 a2 bj 
L. Antiga 
NLP x no 
Nova a1 
 3 2 -5 1 0 6 - 
4/7(2) 1(2) 4/7(2) 0(2) 1/7(2) 9/7(2) 
 13/7 0 -43/7 1 -2/7 24/7 
 
-Cálculo da linha W: (ver tabela 2) 
Linha W:(Coef., bj x Ci), Soma 
 
-Cálculo da linha (C-W): (ver tabela 2) 
Linha (C-W): coeficiente > zero (melhorar). 
 
... 
 
Resposta: 
Solução múltipla: variável não básica X3 apresenta coeficiente nulo na linha 
(C-W) da tabela que gera a Solução ótima em W. 
 
Primeira Solução: 
Variáveis básicas: Variáveis não básicas: F. obj. artificial: 
X1 = 24/13 X3 = 0 W = 0 
X2 = 3/13 a1 = a2 = 0 
Mínimo de W = 0→ indica que se obteve uma solução compatível básica para 
o sistema 
 
Segunda Solução: 
Variáveis básicas: Variáveis não básicas: F. obj. artificial: 
X1 = 897/416 X2 = 0 W = 0 
X3 = 3/32 a1 = a2 = 0 
 
 
 
 
 84
Exercício2: (Puccini – pág. 88 – exercício resolvido) 
Resolver o modelo de programação linear abaixo, usando o Método da Função 
Objetiva Artificial. 
 Minimizar Z = 3X1 + 2X2 , sujeito a 
 X1 + X2 ≥ 5 
2X1 + X2 ≥ 7 
 X1, X2 ≥ 0 (condição não negativa) 
 
Resposta: 
Solução ótima: (não é caso de solução múltipla) 
Variáveis básicas: Variáveis não básicas: F. objetiva: 
X2 = 3 S1, S2 = 0 Z = 12 
X1 = 2 a1 = a2 = 0 
 
Obs.: Caso de minimizar a função objetivo: 
Valores das variáveis básicas são os encontrados no quadro que gera a 
solução ótima e o valor da função objetivo Z tem sinal contrário do 
obtido no mesmo quadro. 
 
Exercício3: (Puccini – pág. 88 – exercício resolvido pelo método W) 
Resolver o exercício anterior usando o método do M grande. 
 
Exercício4: (Puccini – pág. 91 – no 3.1 - exercício resolvido) 
Resolva o seguinte problema de programação linear, utilizando o método 
Simplex: 
 Maximizar Z = 7X1 + 9X2 , sujeito a 
 X1 - X2 ≥ - 2 
3X1 + 5X2 ≤ 15 
5X1 + 4X2 ≥ 20 
 X1, X2 ≥ 0 (condição não negativa) 
 
Resposta: 
Solução ótima: 
Variáveis básicas: Variáveis não básicas: F. objetiva: 
X2 = 15/13 S2, S3 = 0 Z = 415/13 
X1 = 40/13 a3 = 0 
 S1 = 51/13 
 
 
 
 
 
 85
Exercício5: (Puccini – pág. 91 – no 3.2 - exercício resolvido) 
Resolva o seguinte problema de programação linear: 
 Maximizar Z = 3X1 + 2X2 + 5X3, sujeito a 
2X1 + 3X2 + 4X3 ≤ 10 
5X1 + 6X2 + 2X3 ≤ 12 
 X1, X2, X3 ≥ 0 (condição não negativa) 
 
Resposta: 
Solução ótima: 
Variáveis básicas: Variáveis não básicas: F. objetiva: 
X3 = 13/8 X2 = 0 Z = 107/8 
X1 = 7/4 S1 = S2 = 0 
 
Exercício6: (Puccini – pág. 92 – no 3.5 - exercício resolvido) 
Resolva o seguinte problema de programação linear: 
 Maximizar Z = 4X1 + 2X2 + 2X3, sujeito a 
 X1 + X2 + 2X3 ≤ 4 
4X1 - 5X2 + 3X3 ≤ 30 
 X1, X3 ≥ 0 (condição não negativa) 
 
Notar que X2 não tem restrição de sinal. 
 
Resposta: 
 X2 = X2’ – X2” 
Solução ótima: 
Variáveis básicas: Variáveis não básicas: F. objetiva: 
X1= 50/9 X3, X2’ = 0 Z = 172/9 
X2” = 14/9 S1 = S2 = 0 
 
X2 = 0 – (14/9) = - 14/9 
 
Exercício7: (Puccini – pág. 92 – no 3.8 - exercício resolvido) 
Achar, pelo processo da Função Objetiva Artificial, todas as soluções 
compatíveis básicas do sistema: 
 
X1 + X2 + X3 = 1/3 
 X1 + X2 + 3X3 = 1 
Resposta: 
Solução ótima (única solução compatível básica): 
Variáveis básicas: Variáveis não básicas: F. objetiva: 
X2 = 0 X1 = 0 W = 0 
X3 = 1/3 a1, a2 = 0 
 
 86
Exercício8: (P. O. (Medeiros) – pág. 73 – no 1) 
Resolva pelo Simplex, usando o método do M grande para obter a solução 
básica inicial. 
 Maximizar Z = 2X1 + 3X2 , sujeito a 
 X1 + X2 ≥ 10 
2X1 + X2 ≤ 16 
 X1, X2 ≥ 0 (condição não negativa) 
 
Resposta: 
X1 = 0,X2 = 16, Z = 48 
 
Exercício9: (P. O. (Medeiros) – pág. 75 – no 7) 
Minimizar Z = 3X1 + 2X2 + X3, sujeito a 
 3X1 + X2 + 3X3 ≥ 6 
 3X1 + 2X2 = 6 
 X1 - X2 ≤ 1 
 X1, X2, X3 ≥ 0 (condição não negativa) 
 
Resposta: 
X1 = 1,60; X2 = 0,60; X3 = 0,20; Z = 6,20 
 
Exercício10: (P. O. (Medeiros) – pág. 74) 
Minimizar Z = 3X1 + 2X2 , sujeito a 
 2X1 + X2 ≥ 10 
 X1 + 5X2 ≥ 15 
 X1, X2 ≥ 0(condição não negativa) 
 
Resposta: 
X1 = 3,89; X2 = 2,22; Z = 16,11 
 
 
Exercício - Minimização: 
 
Exercício1 (P. O. - Medeiros – pág. 74 – exercício de Minimização) 
Resolver pelo Método Simplex: 
Min Z = 3X1 + 2 X2 , Sujeito a: 
 2X1 + X2 ≥10 (var. folga (-) e artificial) 
 X1 + 5X2 ≥ 15 (var. folga (-) e artificial) 
 X1, X2 ≥ 0; (condições não negativas) 
 
 
Resposta: 
X1 = 3,89 
X2 = 2,22 
Z = 16,11 
 
 87
Solução: Método de M Grande: 
Max. (-Z) = -3X1 - 2X2 
Max.(-Z) = - 3X1- 2X2 -0S1- 0S2- Ma1 - Ma2 
 
 S. a. 2X1 + X2 – S1 + a1 = 10 
 X1 + 5X2 –S2 + a2 = 15 
 X1, X2, S1 , S2 , a1 , a2 ≥ 0 
 
1a Tabela: 
 Variáveis de decisão (título da tabela) 
 -3 -2 0 0 -M -M (L. obj.) 
Ci 
Var. 
Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 
 -M a1 2 1 -1 0 1 0 10 10/1=10 
 -M a2 1 5 0 -1 0 1 15 15/5=3 
Z -3M -6M M M -M -M -25M 
(C-Z) (3M-3) 
(6M-
2) -M -M 0 0 
 
 
 
 
 
- Determinar NLP: 
(Linha Antiga) ÷ Pivô (=5) 
 
Variável X1 X2 S1 S2 a1 a2 bj 
Antiga LP 
Nova LP 
 1 5 0 -1 0 1 15 
1/5 1 0 -1/5 0 1/5 3 
 
-Nova a1: 
 
1a linha: (no = 1) 
Variável X1 X2 S1 S2 a1 a2 bj 
L. Antiga 
NLP x no 
Nova a1
 
 2 1 -1 0 1 0 10 - 
1/5 1 0 -1/5 0 1/5 3 
9/5 0 -1 1/5 1 -1/5 7 
 
 
 
 Variável que entra na base: X2. 
Linha (C-Z): em termos de variáveis não básicas (neste caso: X1, 
X2, S1, S2) →→→→ F. obj. 
Sai 
(LP) 
 
 88
2a Tabela: 
 Variáveis de decisão (título da tabela) 
 -3 -2 0 0 -M -M (L. obj.) 
Ci Var. 
Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 
 -M a1 9/5 0 -1 1/5 1 -1/5 7 35/9=3,88 
 -2 X2 1/5 1 0 -1/5 0 1/5 3 15 
Z -(9M/5 +2/5) -2 M 
(-M/5 
+2/5) -M 
(M/5 -
2/5) -7M-6 
(C-Z) (9M/5 -13/5) 0 -M (M/5- 2/5) 0 (-6M/5 +2/5) 
 
 
 
 
 
-Determinar NLP:(Linha Antiga) ÷ Pivô (=9/5)Variável X1 X2 S1 S2 a1 a2 bj 
Antiga LP 
Nova LP 
9/5 0 -1 1/5 1 -1/5 7 
 1 0 -5/9 1/9 5/9 -1/9 35/9 
 
-Novo X2: 2a linha: (no = 1/5) 
Variável X1 X2 S1 S2 a1 a2 bj 
L. Antiga 
NLP x no 
NovoX2
 
 1/5 1 0 -1/5 0 1/5 3 - 
 1/5 0 -1/9 1/45 1/9 -1/45 35/45 
 0 1 1/9 -2/9 -1/9 2/9 20/9 
 
3a Tabela: 
 Variáveis de decisão (título da tabela) 
 -3 -2 0 0 -M -M (L. obj.) 
Ci 
Var. 
Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 
 -3 X1 1 0 -5/9 1/9 5/9 -1/9 35/9 
 -2 X2 0 1 1/9 -2/9 -1/9 2/9 20/9 
Z -3 -2 13/9 1/9 -13/9 -1/9 -145/9 
(C-Z) 0 0 -13/9 -1/9 (-M+ 13/9) (-M +1/9) 
 
 
 
 
Variável que entra na base: X1. 
Linha (C-Z): em termos de variáveis não básicas (neste caso: X1, 
S1, S2, a2) →→→→ F. obj. 
Sai 
(LP) 
Solução Ótima 
Linha (C-Z): em termos de variáveis não básicas (neste caso: S1, 
S2, a1, a2) →→→→ F. obj. 
 
 89
Solução: 
Variáveis básicas: Variáveis não básicas: F. obj.: 
X1 = 35/9 = 3,89 S1 =S2 = 0 (-Z) = -145/9 = -16,11 
X2 = 20/9 = 2,22 a1 = a2 = 0 (Z) = 16,11 
 
* Coeficientes de S1 e S2 (variáveis não básicas) ≠ Zero → não é 
caso de solução múltipla. 
 
Solução: Método da Função Objetiva Artificial W: 
 
Max. (-Z) = -3X1 - 2X2 
 a1 = 10 – 2X1 – X2 + S1 
 a2 = 15 – X1 – 5X2 + S2 
 
W = a1 + a2 
W = 10 – 2X1 – X2 + S1+ 15 – X1 – 5X2 + S2 
 W = 25 – 3X1 – 6X2 + S1+ S2 
 
 Min. W = 25 – 3X1 – 6X2 + S1+ S2 → x (-1) 
 Min. (-W) = - 25+3X1+6X2 - S1- S2 
 
Min. (-W) + 25 = 3X1 + 6X2 - S1 - S2 
 
1a Tabela: (Inicialmente, trabalha-se com a função W) 
 
 Variáveis de decisão (título da tabela) 
 3 6 -1 -1 0 0 25 (L. obj.) 
Ci 
Var. 
Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 
 0 a1 2 1 -1 0 1 0 10 10/1=10 
 0 a2 1 5 0 -1 0 1 15 15/5=3 
W 0 0 0 0 0 0 0 
(C-W) 
 3 6 -1 -1 0 0 25 
 
 
 
 
- Determinar NLP: (Linha Antiga) ÷ Pivô (=5) 
 
Variável X1 X2 S1 S2 a1 a2 bj 
Antiga LP 
Nova LP 
 1 5 0 -1 0 1 15 
1/5 1 0 -1/5 0 1/5 3 
 
Entra na base 
Sai 
L. P. 
OBS.: Coeficiente da linha (C-W) e coluna bj não 
entra na avaliação da variável que entra na base. 
 
 
 90
- Nova a1: 1a linha: (no = 1) 
Variável X1 X2 S1 S2 a1 a2 bj 
L. Antiga 
NLP x no 
Nova a1
 
 2 1 -1 0 1 0 10 - 
1/5 1 0 -1/5 0 1/5 3 
9/5 0 -1 1/5 1 -1/5 7 
 
2a Tabela: 
 Variáveis de decisão (título da tabela) 
 3 6 -1 -1 0 0 25 (L. obj.) 
Ci 
Var. 
Sol. 
X1 X2 S1 S2 a1 a2 bj bj/aij 
 0 a1 9/5 0 -1 1/5 1 -1/5 7 35/9=3,89 
 6 X2 1/5 1 0 -1/5 0 1/5 3 15 
W 6/5 6 0 -6/5 0 6/5 18 
(C-W) 9/5 0 -1 1/5 0 -6/5 7 
 
 
 
-Determinar NLP:(Linha Antiga) ÷ Pivô (=9/5) 
Variável X1 X2 S1 S2 a1 a2 bj 
Antiga LP 
Nova LP 
9/5 0 -1 1/5 1 -1/5 7 
 1 0 -5/9 1/9 5/9 -1/9 35/9 
 
-Novo X2: 2a linha: (no = 1/5) 
Variável X1 X2 S1 S2 a1 a2 bj 
L. Antiga 
NLP x no 
NovoX2
 
 1/5 1 0 -1/5 0 1/5 3 - 
 1/5 0 -1/9 1/45 1/9 -1/45 35/45 
 0 1 1/9 -10/45 -1/9 10/45 20/9 
 
3a Tabela: 
 Variáveis de decisão (título da tabela) 
 3 6 -1 -1 0 0 25 (L. obj.) 
Ci 
Var. 
Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 
 3 X1 1 0 -5/9 1/9 5/9 -1/9 35/9 
 6 X2 0 1 1/9 -2/9 -1/9 2/9 20/9 
W 3 6 -1 -1 1 1 
 25 
(C-W) 0 0 0 0 -1 -1 0=W 
 
Variável que entra na base: X1. 
Sai 
(LP) 
Solução Ótima em W. 
 
 91
W = 0; a1 = a2 = 0 ok 
 
4a Tabela: (F. Obj. Original Z) 
Variáveis de decisão (título da tabela) 
 -3 -2 0 0 (L. obj.) 
Ci 
Var. 
Sol. X1 X2 S1 S2 bj bj/aij 
 -3 X1 1 0 -5/9 1/9 35/9 
 -2 X2 0 1 1/9 -2/9 20/9 
Z -3 -2 13/9 1/9 -145/9 
(C-Z) 0 0 -13/9 -1/9 
 
 
Solução: 
Variáveis básicas: Variáveis não básicas: F. obj.: 
X1 = 35/9 = 3,89 S1 =S2 = 0 (-Z) = -145/9 = -16,11 
X2 = 20/9 = 2,22 a1 = a2 = 0 (Z) = 16,11 
 
* Coeficientes de S1 e S2 na linha (C-Z) (variáveis não 
básicas) ≠ Zero → não é caso de solução múltipla. 
 
 
PRGRAMAÇÃO INTEIRA: 
 
Em um modelo de Programação Linear, se alguma ou se todas as variáveis de 
decisão devem apresentar valores inteiros, deve-se usar um algoritmo de 
resolução chamado “Método da Ramificação e Limites” (é um algoritmo de 
Programação Linear Inteira). 
 
Obs.: Programação Inteira é considerada restrição do modelo de Programação 
Linear. 
 
 
 
 
 
 
 
 
 
≤≤≤≤ 0: Solução Ótima em Z. 
 
 92
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.