Metodo Simplex completo

Prévia do material em texto

06/05/2014 
1 
MÉTODO SIMPLEX 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
Vamos entender a solução analítica com o uso de um 
exemplo. 
Considere o seguinte modelo: 
 
max Z = 3*X1 + 2*X2 
 
sujeito a 
 X1 + X2 ≤ 6 
 5*X1 + 2*X2 ≤ 20 
 X1, X2 ≥ 0 
06/05/2014 
2 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 INÍCIO 
Colocar o problema em formato padrão, ou seja: 
 Equações lineares (igualdades); 
 Termos independentes (RHS) não negativos; 
 Variáveis de decisão não negativas. 
 
Max Z = 3*X1 + 2*X2 (0) 
 
sujeito a 
 X1 + X2 + X3 = 6 (1) 
 5*X1 + 2*X2 + X4 = 20 (2) 
 X1, X2, X3, X4 ≥ 0 (3) 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 PASSO 1 
Encontrar uma solução básica inicial para o 
problema de PL. 
Atribuir 0 às variáveis de decisão X1 e X2 (variáveis 
não básicas). 
 
Assim: 
VNB = {X1, X2} e VB = {X3, X4} 
Solução básica factível: X3 = 6 e X4 = 20 
Solução: {X1, X2, X3, X4} = {0, 0, 6, 20} 
Função Objetivo: Z = 0 
06/05/2014 
3 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 PASSO 2 
Teste de otimalidade: verificar os coeficientes das 
variáveis não básicas na função objetivo. Se estes 
não forem positivos, achou-se o ótimo e para-se as 
iterações. Se algum for positivo, ainda não estamos 
no ótimo e devemos determinar uma Solução Básica 
Factível Adjacente melhor. 
Para tanto temos 3 sub-passos: 
 Definir variável não básica que entrará na base 
 Definir variável básica que sairá da base 
 Transformar o sistema de equações e recalcular a 
solução básica 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Sub-Passo 2.1: Definir VNB a entrar na base 
 
A VNB a entrar na base é aquela que apresentar o 
maior coeficiente positivo na função objetivo. 
No nosso exemplo, a F.O. é: 
 
max Z = 3*X1 + 2*X2 
 
Dessa forma, a variável X1 entrará na base. 
06/05/2014 
4 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Sub-Passo 2.2: Definir VB a sair da base 
A VB a sair da base é a VB atual que mais restringe 
o crescimento da variável não básica escolhida para 
entrar na base. 
Para definir isso, usamos as restrições que temos e 
atribuímos 0 às variáveis que permaneceram não 
básicas (nesse exemplo somente X2). Assim temos: 
X3 = 6 – X1 
X4 = 20 – 5*X1 
Como sabemos que as variáveis básicas devem 
assumir valores não negativos, temos: 
X3 = 6 – X1 ≥ 0  X1 ≤ 6 
X4 = 20 – 5*X1 ≥ 0  X1 ≤ 4 
Portanto, X4 deve sair da base, pois limita mais o 
crescimento de X1. 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Sub-Passo 2.3: Transformar o sistema de 
equações e recalcular a solução básica 
Agora temos: 
VNB = {X2, X4} e VB = {X1, X3} 
 
Importante: as equações precisam conter somente uma 
variável básica, ou seja, uma variável básica com 
coeficiente 1 e as demais com coeficiente 0. A F.O. deve 
conter os coeficientes das VB iguais a 0. 
 
Dessa forma vamos transformar as equações para que: 
 A equação (2) tenha o coeficiente de X1 igual a 1 (pois foi 
nesta equação de X4 tinha coeficiente 1) e de X3 igual a 0; 
 A equação (1) tenha o coeficiente de X1 igual a 0 e de X3 
igual a 1; 
 A F.O. tenha os coeficientes de X1 e X3 iguais a 0. 
06/05/2014 
5 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Continuação Sub-Passo 2.3 
Equação de troca da variável básica (de X4 por X1): 
5*X1 + 2*X2 + X4 = 20 (2) 
dividir por 5 
X1 + 2/5*X2 + 1/5*X4 = 4 (2.1) 
 
A nova equação (1) pode ser obtida subtraindo a 
mesma por N vezes a nova equação (2.1), sendo neste 
caso N = 1: 
X1 + X2 + X3 = 6 (1) 
menos 1 vezes 
X1 + 2/5*X2 + 1/5*X4 = 4 (2.1) 
temos 
3/5*X2 + X3 – 1/5*X4 = 2 (1.1) 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Continuação Sub-Passo 2.3 
Mudar a F.O. para que o coeficiente de X1 seja 0. 
Para tanto, pode-se subtrair da F.O. antiga a eq. (2.1) 
vezes 3: 
Z = 3*X1 + 2*X2 
menos 3 vezes 
X1 + 2/5*X2 + 1/5*X4 = 4 (2.1) 
temos 
Z = 4/5*X2 – 3/5*X4 + 12 (0.1) 
06/05/2014 
6 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 PASSO 2 
Portanto, temos agora o novo sistema: 
Max Z = 4/5*X2 – 3/5*X4 + 12 (0.1) 
sujeito a 
 3/5*X2 + X3 – 1/5*X4 = 2 (1.1) 
X1 + 2/5*X2 + 1/5*X4 = 4 (2.1) 
 
Assim tem-se: 
VNB = {X2, X4} e VB = {X1, X3} 
Solução não básica: X2 = 0 e X4 = 0 
Solução básica factível: X1 = 4 e X3 = 2 
Solução: {X1, X2, X3, X4} = {4, 0, 2, 0} 
Função Objetivo: Z = 12 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 VOLTAMOS AO INÍCIO DO PASSO 2 
 Verificamos a otimalidade: 
A variável X2 ainda tem coeficiente positivo na F.O. 
 
 NOVA ITERAÇÃO 
 Definir VNB a entrar na base: 
X2  única variável com coeficiente positivo na F.O. 
 
 Definir VB a sair da base: 
Fazendo X4 = 0, tem-se 
X3 = 2 – 3/5*X2 ≥ 0  X2 ≤ 10/3 
X1 = 4 – 2/5*X2 ≥ 0  X2 ≤ 10 
Portanto X3 deve sair da base, pois limita mais o 
crescimento de X2. 
 
06/05/2014 
7 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Continuação da nova iteração 
Transformar o sistema de equações e recalcular a solução básica 
Agora temos: 
VNB = {X3, X4} e VB = {X1, X2} 
 
Equação de troca da variável básica (de X3 por X2): 
3/5*X2 + X3 – 1/5*X4 = 2 (1.1) 
dividir por 3/5 (ou multiplicar por 5/3) 
X2 + 5/3*X3 – 1/3*X4 = 10/3 (1.2) 
 
A nova equação (2.1) pode ser obtida subtraindo a mesma por 2/5 
da nova equação (1.2) : 
X1 + 2/5*X2 + 1/5*X4 = 4 (2.1) 
menos 2/5 de 
X2 + 5/3*X3 – 1/3*X4 = 10/3 (1.2) 
temos 
X1 – 2/3*X3 + 1/3*X4 = 8/3 (2.2) 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 Continuação da nova iteração 
Transformar o sistema de equações e recalcular a 
solução básica 
Mudar a F.O.: 
Subtrair da F.O. antiga (0.1) a Eq. 1.2 vezes 4/5 
Z = 4/5*X2 – 3/5*X4 + 12 (0.1) 
menos 4/5 de 
X2 + 5/3*X3 – 1/3*X4 = 10/3 (1.2) 
temos 
Z = – 4/3*X3 – 1/3*X4 + 44/3 (0.2) 
06/05/2014 
8 
SOLUÇÃO ANALÍTICA DO MÉTODO SIMPLEX 
 PASSO 2 
Portanto, temos agora o novo sistema: 
Max Z = – 4/3*X3 – 1/3*X4 + 44/3 (0.2) 
sujeito a 
 X2 + 5/3*X3 – 1/3*X4 = 10/3 (1.2) 
X1 – 2/3*X3 + 1/3*X4 = 8/3 (2.2) 
 
Assim tem-se: 
VNB = {X3, X4} e VB = {X1, X2} 
Solução não básica: X3 = 0 e X4 = 0 
Solução básica factível: X1 = 8/3 e X2 = 10/3 
Solução: {X1, X2, X3, X4} = {8/3, 10/3, 0, 0} 
Função Objetivo: Z = 44/3 
 
Final do Simplex, pois pelo teste de otimalidade, não há 
variáveis com coeficiente positivo na F.O. 
FORMA TABULAR DO MÉTODO SIMPLEX 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 ... Xn 
0 1 -c1 -c2 ... -cn 0 
1 0 a11 a12 ... a1n b1 
2 0 a21 a22 ... a2n b2 
... 0 ... ... ... ... ... 
m 0 am1 am2 ... amn bm 
06/05/2014 
9 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolva o seguinte problema: 
 
max Z = 3*X1 + 2*X2 
sujeito a 
 X1 + X2 ≤ 6 
 5*X1 + 2*X2 ≤ 20 
 X1, X2 ≥ 0 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
 
Colocando na forma padrão: 
 
max Z = 3*X1 + 2*X2 (0) 
sujeito a 
 X1 + X2 + X3 = 6 (1) 
 5*X1 + 2*X2 + X4 = 20 (2) 
 X1, X2, X3, X4 ≥ 0 
 
06/05/2014 
10 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
 
 
 
 
 
 
 
Z = 3*X1 + 2*X2  Z – 3*X1 – 2*X2 = 0 
 
Teste Otimalidade: 
Para maximização  se existem VNB com coeficientes 
negativos, ainda não é a solução ótima. 
Para minimização  se existem VNB com coeficientes 
positivos, ainda não é asolução ótima. 
 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X4 0 5 2 0 1 20 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Definir a VNB a entrar na base: 
Para maximização, escolhe-se a variável com o maior 
incremento positivo em Z, ou seja, o maior coeficiente 
negativo na equação 0. 
Para minimização, escolhe-se a variável com o maior 
incremento negativo em Z, ou seja, o maior coeficiente 
positivo na equação 0. 
No nosso problema (de max.), os coeficientes são -3 e -2, 
portanto escolhe-se o X1 (coeficiente -3). 
 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X4 0 5 2 0 1 20 
Coluna Pivô 
06/05/2014 
11 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Definir a VB a sair da base: 
A variável a sair da base (e tornar-se nula) é aquela que 
limita mais o crescimento da variável que entrará na base. 
Para defini-la faz-se o seguinte: 
 Para cada coeficiente (das restrições) positivo na coluna pivô: 
 Dividir a constante (RHS) da mesma linha pelo coeficiente, gerando 
um quociente para cada linha 
 Escolher a linha com o menor quociente. Esta é a linha pivô. 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X4 0 5 2 0 1 20 
6÷1 = 6 
20÷5 = 4 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Definir a VB a sair da base: 
A variável a sair da base (e tornar-se nula) é aquela que 
limita mais o crescimento da variável que entrará na base. 
Para defini-la faz-se o seguinte: 
 Para cada coeficiente (das restrições) positivo na coluna pivô: 
 Dividir a constante (RHS) da mesma linha pelo coeficiente, gerando 
um quociente para cada linha 
 Escolher a linha com o menor quociente. Esta é a linha pivô. 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X4 0 5 2 0 1 20 
Linha 
Pivô 
Número 
Pivô 
06/05/2014 
12 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Transformar o sistema de equações e recalcular 
a solução básica: 
Temos que transformar os coeficientes da VNB a 
entrar na base em 1 (para a equação da linha pivô) e 
em 0 (para as demais equações). 
Dica para transformação: 
Nova linha pivô = linha pivô atual ÷ número pivô 
Para demais linhas, incluindo Z: 
 Nova linha = linha atual – (coeficiente da 
coluna pivô da linha atual) * (nova linha pivô) 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Transformar o sistema de equações e recalcular a solução 
básica: 
Nova linha pivô = linha pivô atual ÷ 5 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X4 0 5 2 0 1 20 
Linha 
Pivô 
Atual 
Número 
Pivô 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X1 0 1 2/5 0 1/5 4 
Nova
Linha 
Pivô 
06/05/2014 
13 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Transformar o sistema de equações e recalcular a solução 
básica: 
Nova equação 1 = equação 1 atual – (1)*(Nova linha pivô) 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X1 0 1 2/5 0 1/5 4 
Nova
Linha 
Pivô 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
Nova 
Equação 
1 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução 
Transformar o sistema de equações e recalcular a solução 
básica: 
Nova equação 0 (F.O.) = equação 0 atual – (-3)*(Nova linha pivô) 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 -3 -2 0 0 0 
1 X3 0 1 1 1 0 6 
2 X1 0 1 2/5 0 1/5 4 
Nova
Linha 
Pivô 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
Nova 
Equação 
0 
06/05/2014 
14 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
Teste Otimalidade: 
 
Maximização  ainda existem VNB com coeficientes 
negativos, portanto ainda não é a solução ótima. 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
Definir a VNB a entrar na base: 
No nosso problema (de max.), o coeficiente de X2 é negativo, 
portanto X2 deve entrar na base. 
 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
06/05/2014 
15 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
Definir a VB a sair da base: 
 
 
 
 
 
Eq. 1  2 ÷ 3/5 = 10/3 Eq. 2  4 ÷ 2/5 = 10 
Portanto, X3 (eq. 1) deve sair da base: 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
Transformar o sistema de equações e recalcular a solução 
básica: 
Nova linha pivô = linha pivô atual ÷ 3/5 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X3 0 0 3/5 1 -1/5 2 
2 X1 0 1 2/5 0 1/5 4 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X2 0 0 1 5/3 -1/3 10/3 
2 X1 0 1 2/5 0 1/5 4 
06/05/2014 
16 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
Transformar o sistema de equações e recalcular a solução 
básica: 
Nova equação 2 = equação 2 atual – (2/5)*(Nova linha pivô) 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X2 0 0 1 5/3 -1/3 10/3 
2 X1 0 1 2/5 0 1/5 4 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X2 0 0 1 5/3 -1/3 10/3 
2 X1 0 1 0 -2/3 1/3 8/3 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
Transformar o sistema de equações e recalcular a solução 
básica: 
Nova equação 0 (F.O.) = equação 0 atual – (-4/5)*(Nova linha pivô) 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 -4/5 0 3/5 12 
1 X2 0 0 1 5/3 -1/3 10/3 
2 X1 0 1 0 -2/3 1/3 8/3 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 0 4/3 1/3 44/3 
1 X2 0 0 1 5/3 -1/3 10/3 
2 X1 0 1 0 -2/3 1/3 8/3 
06/05/2014 
17 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Resolução - Próxima iteração 
 
 
 
 
 
 
Teste Otimalidade: 
Maximização  não existem mais VNB com coeficientes negativos, 
portanto achamos a SOLUÇÃO ÓTIMA. 
X1 = 8/3 
X2 = 10/3 
Z= 44/3 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 0 4/3 1/3 44/3 
1 X2 0 0 1 5/3 -1/3 10/3 
2 X1 0 1 0 -2/3 1/38/3 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Exercício 
 
Um fabricante de móveis deseja determinar o mix 
ideal de produção, levando em conta lucros de venda 
dos produtos e quantidade disponível de insumos. 
A situação atual vem dada na tabela abaixo: 
 
06/05/2014 
18 
FORMA TABULAR DO MÉTODO SIMPLEX 
 Exercício de Minimização 
 
Min Z = 4*X1 – 2*X2 
sujeito a 
 2*X1 + X2 ≤ 10 
 X1 – X2 ≤ 8 
 X1, X2 ≥ 0 
 
 
 
* Solução: X1 = 0, X2 = 10, X4 = 18, Z = -20 
O BIG M 
 Quando tenho restrições de igualdade ou de “>=“ 
preciso usar de alguns “subterfúgios”. Nesse caso o 
BIG M. 
Considere o seguinte modelo: 
Min Z = 10*X1 + 6*X2 
s.a. 
 4*X1 + 2*X2 >= 24 
 X1 <= 8 
 X1 + 2*X2 = 12 
 X1, X2 >= 0 
06/05/2014 
19 
O BIG M 
Min Z = 10*X1 + 6*X2 
s.a. 
 4*X1 + 2*X2 – X3 = 24 
 X1 + X4 = 8 
 X1 + 2*X2 = 12 
 X1, X2, X3, X4 >= 0 
 
Min Z = 10*X1 + 6*X2 
s.a. 
 4*X1 + 2*X2 – X3 + a1 = 24 
 X1 + X4 = 8 
 X1 + 2*X2 + a2 = 12 
 X1, X2, X3, X4, a1, a2 >= 0 
 
O BIG M 
Min Z = 10*X1 + 6*X2 + M*a1 + M*a2 
s.a. 
 4*X1 + 2*X2 – X3 + a1 = 24 
 X1 + X4 = 8 
 X1 + 2*X2 + a2 = 12 
 X1, X2, X3, X4, a1, a2 >= 0 
 
Eliminando a1 e a2 da F.O. 
 equação 0 Z – 10*X1 – 6*X2 – M*a1 – M*a2 =0 
+ equação 1 * M 4M*X1 + 2M*X2 – M*X3 + M*a1 = 24M 
+ equação 3 * M M*X1 + 2M*X2 + M*a2 = 12M 
SOMA ---------------------------------------------------------------------------------- 
Nova equação 0: Z + (5M-10)X1 + (4M-6)X2 – M*X3 = 36M 
06/05/2014 
20 
O BIG M 
no. da 
equaç
ão 
Variáv
el 
básica 
Coeficientes 
Constan
te 
Z X1 X2 X3 X4 a1 a2 
0 Z 1 5M-10 4M-6 -M 0 0 0 36M 
1 a1 0 4 2 -1 0 1 0 24 
2 X4 0 1 0 0 1 0 0 8 
3 a2 0 1 2 0 0 0 1 12 
Resolver, neste caso, para minimização. 
 
 
 
Resultado: {X1, X2, X3, X4, a1, a2} = {4, 4, 0, 4, 0, 0} 
Z = 64 
CASOS ESPECIAIS 
 Múltiplas soluções ótimas 
Na solução ótima, o coeficiente de uma das VNB for nulo 
na linha da F.O. 
 
Ex. de Maximização: 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 0 2 0 32 
1 X1 0 1 1/2 1/4 0 4 
2 X4 0 0 1/2 -1/4 1 2 
06/05/2014 
21 
CASOS ESPECIAIS 
 Função Objetivo Ilimitada 
Quando, em uma das formas tabulares, uma VNB 
candidata fica impossibilitada de entrar na base porque 
as linhas de todas as variáveis básicas possuem 
coeficientes não positivos na coluna da VNB candidata. 
 
Ex. de Maximização: 
 
no. da 
equação 
Variável 
básica 
Coeficientes 
Constante 
Z X1 X2 X3 X4 
0 Z 1 0 0 -3/5 14/5 172/5 
1 X2 0 0 1 -1/5 -2/5 4/5 
2 X4 0 1 0 0 1 8 
CASOS ESPECIAIS 
 Não existe solução ótima 
Sempre que pelo menos uma das VB assume valores 
negativos. 
 
Ex. de Maximização: 
 
no. da 
equaçã
o 
Variáve
l básica 
Coeficientes 
Constant
e 
Z X1 X2 X3 X4 a1 
0 Z 1 3M+1 0 M 4M+1 0 -16M+6 
1 a1 0 -3 0 -1 -4 1 16 
2 X2 0 2 1 0 1 0 6