ENGENHARIA

A solução gráfica pode ser aplicada a resolução de problemas de PL com duas ou, no máximo, três variáveis de decisão. Como alternativa, o método Simplex pode ser aplicado para a solução de qualquer problema de PL.

O método Simplex é uma metodologia que envolve uma sequência de cálculos repetitivos por meio dos quais é possível chegar à solução de um problema de programação linear.

Essa

sequência

cálculos recebe o nome de algoritmo.

de

Inicialização

Iteratividade

Se Não
Regra de parada Se Sim

Pare

Passos do Método Simplex
1. Monta-se um tableau (tabela) inicial que corresponde à origem;
2. Esse primeiro tableau é transformado em um segundo, que apresenta uma solução melhorada, por meio de uma série de cálculos;
3. Esse procedimento se repete até que se chegue a um tableau que reflita a solução ótima.
4. Quando da criação da cada tableau, existe um teste para verificar se a solução ótima foi ou não atingida. Considere-se as seguintes definições
Variável Básica
- são as m variáveis que compõem a solução básica
(x1, x2,... xn).
Variáveis Não Básicas
- são as n variáveis que não compõem a solução básica. Valem, obrigatoriamente, zero, por construção. Variáveis de Folga
- Como as restrições dos problemas possuem uma estrutura lógica do tipo:
UTILIZAÇÃO DOS RECURSOS ≤ DIPONIBILIDADES

ou
UTILIZAÇÃO DOS RECURSOS ≥ DIPONIBILIDADES

Ao introduzirmos o conceito de folga de recurso, essa relação pode ser escrita da seguinte forma: UTILIZAÇÃO + FOLGA = DISPONIBILIDADE

Isso significa que:
UTILIZAÇÃO < DISPONIBILIDADE implica FOLGA > 0

UTILIZAÇÃO = DISPONIBILIDADE implica FOLGA = 0

UTILIZAÇÃO > DISPONIBILIDADE implica FOLGA < 0

Solução Algébrica
Considere os seguinte modelo de PL:

Max z = 50 x1 + 40 x2
s.a.
30 x1 + 20 x2 ≤ 360
5 x + 10 x ≤ 120
 1
2
Restrições 
≤ 20
 x1
 x1 , x2 ≥ 0


1º passo:
“Preparar” as equações para transforma as desigualdades em