Capitulo 5: Simplex
Voltando ao exemplo da confecção da D. Maria, e modificando um pouco os valores apenas para facilitar nossos
cálculos e o entendimento, teríamos a seguinte situação:
D. Maria possui uma confecção que produz agora outros dois tipos de roupas, calças e vestidos. O lucro sobre a venda
da calça é de R$ 4,00 e na sua fabricação, são gastos 2m em tecido (matéria prima) por dia. Já o lucro do vestido é de
R$1,00 e o gasto com tecido é de 3m. D. Maria recebe apenas 12m de tecido por dia.
D. Maria também já calculou o custo relativo à Mão de Obra. Para a calça, é utilizada 2h de Mão de Obra e para o
vestido, apenas 1h. D. Maria tem disponível 8h de MO/dia.
1)
Variáveis de decisão:
X1: Quantidade de calças
X2: Quantidade de vestidos
2)
Função Objetivo
Max Z= 4X1+1X2
3)
Restrições
2X1+3X2≤12
2X1+1X2≤8
X1≥0 e X2≥0
Resumo:
Max Z= 4X1+1X2
Sujeito a
2X1+3X2
≤12
2X1+1X2
≤8
X1
≥0
X2 ≥0
Capitulo 5: Simplex
Para usarmos o simplex, as seguintes regras tem que ser respeitadas:
As restrições são sempre ≤ uma constante (bi)
Todas essas constantes (bi) são ≥ 0
Estaremos maximizando Z (para minimizar, algumas adaptações serão feitas)
Solução usando o método Simplex
Passo 1)
Transformar as desigualdades lineares em equações lineares. Como? Introduzindo variáveis de folgas,
sempre positivas (tantas quanto forem necessárias)
Maximizar
Z= 4X1+1X2
Sujeito a
Z - 4X1-1X2
2X1+3X2 ≤12
2X1+3X2+1X3
2X1+1X2 ≤8
2X1+1X2+
X1 e X2 ≥0
Passo 2)
=0
=12
1X4
X1, X2, X3 e X4 ≥0
Montar quadro com Z na ultima linha e as variáveis de folga na base (≠ 0).
Nota: As variáveis que não estão na base são iguais a “zero”
Base
X1
X2
X3
X4
b
X3
2
3
1
0
12
X4
2
1
0
1
8
Z
-4
-1
0
0
0
=8
Capitulo 5: Simplex
Esse é um processo iterativo. Assim, já teríamos a primeira solução onde:
X1=0
Importante:
Esse “cruzamento” é chamado de
Pivô.
Nesse caso: Pivô=2
X2=0
X3=12
X4=8
Z=0
Obviamente, essa solução não é a ótima. Continuaremos o processo até encontrar a solução ótima
Passo 3) Colocar uma variável não-básica (nesse caso X1 ou X2) na base e retirar uma variável básica (X3 ou X4) da
base.
Qual variável não-básica escolher? A de maior contribuição para a função Z (o maior valor negativo, podendo até ser
zero) e que tenha pelo menos um coeficiente positivo na sua coluna: No caso X1=-4
Qual variável básica tirar? Para isso, basta dividir a coluna “b” pela coluna que vai entrar na base (X1) e escolher o
menor resultado não negativo
Base
X1
X2
X3
X4
b
X3
2
3
1
0
12
X4
2
1
0
1
8
Z
-4
-1
0
0
0
Maior valor negativo é o da
variável X1.
É quem vai entrar na base.
Menor quociente é o da
variável X4.
É quem vai sair da base
b/X1=> 12/2=6
b/X1=>
8/2=4
Capitulo 5: Simplex
Continuando o desenvolvimento da tabela:
1ª Operação: divida a linha que sai (X4) pelo Pivô (2) e inclua na nova tabela
Base
X1
X2
X3
X4
b
X3
2
3
1
0
12
X4
2
1
0
1
8
Z
-4
-1
0
0
0
2/2=1
½= 0,5
0/2=0
½=0,5
8/2=4
Base
X1
X2
X3
X4
b
X1
1
0,5
0
0,5
4
Capitulo 5: Simplex
2ª Operação: Multiplique a nova linha pelo oposto do pivô da próxima linha da tabela e some com ela própria
Base
X1
X2
X3
X4
b
X3
2
3
1
0
12
X4
2
1
0
1
8
Z
-4
-1
0
0
0
-2+2=0
-1+3=2
Base
X1
X2
X3
0
X1
Pivô=2=> Oposto=-2
1
1*(-2)=-2
0+1=1
-1+0=-1
-8+12=4
X3
X4
b
2
1
-1
4
0,5
0
0,5
4
½*(-2)=-1
0*(-2)=0
½*(-2)=-1
4*(-2)=-8
Nova Linha
Capitulo 5: Simplex
3ª Operação: Novamente, multiplique a nova linha pelo oposto do pivô da linha da tabela que ainda não foi modificada e
e some com ela própria
Base
X1
X2
X3
X4
b
X3
2
3
1
0
12
X4
2
1
0
1
8
Z
-4
-1
0
0
0
-4+4=0
2+(-1)=1
Base
X1
X2
X3
0
0+0=0
2+0=2
X3
X4
b
2
1
-1
4
4
X1
1
0,5
0
0,5
Z
0
1
0
2
1*4=4
½*4=2
Pivô=-4=> Oposto=4
16+0=16
0*4=0
½*4=2
16
4*4=16
Nova Linha
Capitulo 5: Simplex
Repita essas operações até que na linha “Z” não tenha mais nenhum coeficiente negativo.
Como isso acaba de acontecer, concluímos que chegamos na solução ótima, onde
X3=4 (coluna “b”)
X1=4 (coluna “b”)
Z=16 (coluna “b”)
E conseqüentemente (variáveis não-básicas):
X2=0
X4=0
Base
X1
X2
X3
X4
b
X3
0
2
1
-1
4
4
X1
1
0,5
0
0,5
Z
0
1
0
2
16
Capitulo 5: Simplex
Interpretação Econômica dos Resultados:
Voltando ao inicio do problema, temos que:
Max Z = 4X1+1X2
Sujeito a
2X1+3X2+1X3
2X1+1X2+
=12 (recurso tecido)
1X4 =8 (recurso mão de obra)
Onde as variáveis devem ser interpretadas da seguinte maneira:
X1: Quantidade de calças
X2: Quantidade de vestidos
X3: Folga na utilização do recurso tecido
X4: Folga na utilização do recurso mão de obra
Como vimos que o resultado do Simplex foi
Z=16
X1=4
X2=0
X3=4
X4=0
Concluímos que foram produzidos 4 calças(X1) e 0 vestidos (X2), dando um lucro de $16 (Z), sendo que todo o recurso
de mão de obra foi utilizado (X4=0), mas sobraram 4m do recurso tecido (X3)
Capitulo 5: Simplex
Exercício 5.1
Resolva utilizando o Simplex:
Maximizar Z= 3X1+5X2
Sujeito a
X1≤4
X2≤6
3X1+2X2≤18
X1≥0 e X2≥0
Solução:
Passo 1)
Transformar em equações lineares:
-3X1-5X2+0X3+0X4+0X5 =0
1X1
+1X3
1X2
3X1+2X2
=4
+1X4
=6
+1X5 =18
Capitulo 5: Simplex
Passo 2)
Passo 3)
Criar tabela
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
X4
0
1
0
1
0
6
X5
3
2
0
0
1
18
Z
-3
-5
0
0
0
0
Qual variável entra para a base e qual sai da base?
Entra: X2=-5 (maior valor negativo em Z)
Sai: X4=3 Menor relação b/X2 não negativo
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
4/0=Indeterm.
X4
0
1
0
1
0
6
6/1=6
X5
3
2
0
0
1
18
18/2=9
Z
-3
-5
0
0
0
0
Capitulo 5: Simplex
1ª Operação: divida a linha que sai (X4) pelo Pivô (1)e inclua na nova tabela
Base
X1
X2
X3
X4
X5
b
X4
0
1
0
1
0
6
0/1=0
1/1=1
0/1=0
1/1=1
0/1=0
6/1=6
Base
X1
X2
X3
X4
X5
b
X2
0
1
0
1
0
6
Capitulo 5: Simplex
2ª Operação: Multiplique a nova linha pelo oposto do pivô (0) da próxima linha da tabela e some com ela própria
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
0+0=0
4+0=4
1+0=1
Pivô=0
Oposto=0
0+0=0
1+0=1
0+0=0
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
X2
0
1
0
1
0
6
1*0=0
0*0=0
0*0=0
1*0=0
0*0=0
6*0=0
Nova Linha
Capitulo 5: Simplex
3ª Operação: Multiplique a nova linha pelo oposto do pivô (-2) da próxima linha da tabela e some com ela própria
Pivô=2
Base
X1
X2
X3
X4
X5
b
X5
3
2
0
0
1
18
0+0=0
0-2=-2
Oposto=-2
3+0=3
2-2=0
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
X2
0
1
0
1
0
6
X5
3
0
0
-2
1
6
0*(-2)=0
1*(-2)=-2
0*(-2)=0
1*(-2)=-2
1+0=1
0*(-2)=0
18-12=6
6*(-2)=-12
Nova Linha
Capitulo 5: Simplex
4ª Operação: Multiplique a nova linha pelo oposto do pivô (5) da próxima linha da tabela e some com ela própria
Pivô=-5
Base
X1
X2
X3
X4
X5
b
Z
-3
-5
0
0
0
0
Oposto=5
-3+0=-3
-5+5=0
0+0=0
0+5=5
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
X2
0
1
0
1
0
6
X5
3
0
0
-2
1
6
Z
-3
0
0
5
0
30
0*5=0
6*5=30
0*5=0
1*5=5
0*5=0
1*5=5
0+0=0
0+30=30
Nova Linha
Capitulo 5: Simplex
Já mudamos toda a base. Encontramos a solução ótima? Não, pois ainda existe um numero negativo na linha “Z”.
Vamos repetir todas as operações novamente desde o início do passo 3.
Passo 3)
Qual variável entra para a base e qual sai da base?
Entra: X1=-3 (maior valor negativo em Z)
Sai: X5=2 Menor relação b/X2 não negativo
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
4/1=4
X2
0
1
0
1
0
6
6/0= Indeter.
X5
3
0
0
-2
1
6
6/3=2
Z
-3
0
0
5
0
30
Capitulo 5: Simplex
1ª Operação: divida a linha que sai (X5) pelo Pivô (3) e inclua na nova tabela
Base
X1
X2
X3
X4
X5
b
X5
3
0
0
-2
1
6
3/3=1
0/3=0
0/3=0
-2/3=-2/3
1/3=1/3
6/3=2
Base
X1
X2
X3
X4
X5
b
X1
1
0
0
-2/3
1/3
2
Capitulo 5: Simplex
2ª Operação: Multiplique a nova linha pelo oposto do pivô (-1) da próxima linha da tabela e some com ela própria
Base
X1
X2
X3
X4
X5
b
X3
1
0
1
0
0
4
1-1=0
Pivô=1
Oposto=-1
0+0=0
1+0=1
0+2/3=2/3
0-1/3=-1/3
4-2=2
Base
X1
X2
X3
X4
X5
b
X3
0
0
1
2/3
-1/3
2
X1
1
0
0
-2/3
1/3
2
1*(-1)=-1
0*(-1)=0
0*(-1)=0
(-2/3)*(-1)=2/3 1/3*(-1)=-1/3 2*(-1)=-2
Nova Linha
Capitulo 5: Simplex
3ª Operação: Multiplique a nova linha pelo oposto do pivô (0) da próxima linha da tabela e some com ela própria
Base
X1
X2
X3
X4
X5
b
X2
0
1
0
1
0
6
0+0=0
Pivô=0
Oposto=0
1+0=1
0+0=0
1+0=1
0+0=0
6+0=6
Base
X1
X2
X3
X4
X5
b
X3
0
0
1
2/3
-1/3
2
X2
0
1
0
1
0
6
X1
1
0
0
-2/3
1/3
2
1/3*0=0
2*0=0
1*0=0
0*0=0
0*0=0
(-2/3)*0=0
Nova Linha
Capitulo 5: Simplex
4ª Operação: Multiplique a nova linha pelo oposto do pivô (3) da próxima linha da tabela e some com ela própria
Pivô=-3
Oposto=3
Base
X1
X2
X3
X4
X5
b
Z
-3
0
0
5
0
30
-3+3=0
0+0=0
0+0=0
5-2=3
0+1=1
30+6=36
Base
X1
X2
X3
X4
X5
b
X3
0
0
1
2/3
-1/3
2
X2
0
1
0
1
0
6
X1
1
0
0
-2/3
1/3
2
Z
0
0
0
3
1
36
0*3=0
0*3=0
(-2/3)*3=-2
1/3*3=1
1*3=3
2*3=6
Nova Linha
Capitulo 5: Simplex
Como a linha “Z” não possui nenhum coeficiente negativo, atingimos a solução ótima, onde
X1=2
X2=6
X3=2
Z=36
E conseqüentemente (variáveis não-básicas):
X4=0
X5=0
Base
X1
X2
X3
X4
X5
b
X3
0
0
1
2/3
-1/3
2
X2
0
1
0
1
0
6
X1
1
0
0
-2/3
1/3
2
Z
0
0
0
3
1
36
Observação: Quando analisamos os coeficientes das variáveis não-básicas na linha “Z”, a solução será ótima e única
quando todos forem positivos. Se alem de valores positivos, também encontrarmos valores nulos, a solução é ótima
porem não é única
Capitulo 5: Simplex
Interpretação econômica dos resultados:
Max Z= 3X1+5X2
Sujeito a:
1X1
+1X3
1X2
3X1+2X2
=4 (Recurso A)
+1X4
=6 (Recurso B)
+1X5 =18(Recurso C)
Com a seguinte interpretação:
X1: Quantidade do produto 1
X2: Quantidade do produto 2
X3: Folga na utilização do recurso A
X4: Folga na utilização do recurso B
X5: Folga na utilização do recurso C
Assim,
Temos um total de Z=36
Onde:
X1=2
Produzimos 2 unidades do produto 1
X2=6
Produzimos 6 unidades do produto 2
X3=2
Há uma sobra de 2 unidades do recurso A
X4=0
Utilização total do recurso B
X5=0
Utilização total do recurso C
Capitulo 5: Simplex
E quando o objetivo do nosso modelo matemático for de minimização? O que devemos fazer?
Para isso, basta trocar o sinal da Função Objetivo (mantendo as restrições inalteradas), tratar a mesma como
maximização, resolver o problema, e finalmente, inverter o sinal do “Z” resultante.
Exercício 5.2
Resolva utilizando o Simplex:
Minimizar Z= 3X1-X2
Sujeito a
2X1+X2≤4
X1-X2≤2
X1≥0 e X2≥0
Capitulo 5: Simplex
Solução Exercício 5.2
Antes de iniciar a solução, precisamos transformar a minimização em maximização, trocando o sinal da função objetivo:
Minimizar Z= 3X1-X2 =
Maximizar (-Z)=-3X1+X2
Sujeito a
2X1+X2≤4
X1-X2≤2
X1≥0 e X2≥0
Agora seguimos a solução padrão do Simplex:
Passo 1)
Transformar em equações lineares:
3X1-X2+0X3+0X4
=0
2X1+ X2 + X3
=4
X1- X2
+ X4
=2
Capitulo 5: Simplex
Passo 2)
Passo 3)
Criar tabela
Base
X1
X2
X3
X4
b
X3
2
1
1
0
4
X4
1
-1
0
1
2
(-Z)
3
-1
0
0
0
Qual variável entra para a base e qual sai da base?
Entra: X2=-1 (maior valor negativo em Z)
Sai: X3=4 Menor relação b/X2 não negativo
Base
X1
X2
X3
X4
b
X3
2
1
1
0
4
4/1=4
X4
1
-1
0
1
2
2/-1=-2
(-Z)
3
-1
0
0
0
Capitulo 5: Simplex
1ª Operação: divida a linha que sai (X3) pelo Pivô (1) e inclua na nova tabela
Base
X1
X2
X3
X4
b
X3
2
1
1
0
4
2/1=2
1/1=1
1/1=1
0/1=0
4/1=4
Base
X1
X2
X3
X4
b
X2
2
1
1
0
4
Capitulo 5: Simplex
2ª Operação: Multiplique a nova linha pelo oposto do pivô (1) da próxima linha da tabela e some com ela própria
Base
X1
X2
X3
X4
b
X4
1
-1
0
1
2
1+2=3
Pivô=-1
Oposto=1
-1+1=0
0+1=1
1+0=1
2+4=6
Base
X1
X2
X3
X4
b
X2
2
1
1
0
4
X4
3
0
1
1
6
2*1=2
1*1=1
0*1=0
4*1=4
1*1=1
Nova Linha
Capitulo 5: Simplex
2ª Operação: Multiplique a nova linha pelo oposto do pivô (1) da próxima linha da tabela e some com ela própria
Base
X1
X2
X3
X4
b
(-Z)
3
-1
0
0
0
3+2=5
Pivô=-1
Oposto=1
-1+1=0
0+1=1
0+0=0
0+4=4
Base
X1
X2
X3
X4
b
X2
2
1
1
0
4
X4
3
0
1
1
6
(-Z)
5
0
1
0
4
2*1=2
1*1=1
0*1=0
4*1=4
1*1=1
Nova Linha
Capitulo 5: Simplex
Como a linha “Z” não possui nenhum coeficiente negativo, atingimos a solução ótima. Devemos agora alterar o valor de
“Z” que passa de:
De (-Z)= 4
Para
Z=-4
Assim temos o resultado final:
X2=4
X4=6
Z=-4
E conseqüentemente (variáveis não-básicas):
X1=0
X3=0
Base
X1
X2
X3
X4
b
X2
2
1
1
0
4
X4
3
0
1
1
6
(-Z)
5
0
1
0
4
Capitulo 5: Simplex
Interpretação econômica dos resultados:
Min Z= 3X1-X2=0
Sujeito a:
2X1+ X2 + X3
X1- X2
=4 (Recurso A)
+ X4=2 (Recurso B)
Com a seguinte interpretação:
X1: Quantidade do produto 1
X2: Quantidade do produto 2
X3: Folga na utilização do recurso A
X4: Folga na utilização do recurso B
Assim,
Temos um total de Z=-4
Onde:
X1=0
Utilizamos 0 unidades do produto 1
X2=4
Utilizamos 4 unidades do produto 2
X3=0
Utilização total do recurso A
X4=6
Há uma sobra de 6 unidades do recurso B