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